multithreading - tipos - Lenguajes de programación no deterministas.
tipos de lenguaje de programacion y sus caracteristicas (8)
Creo que Haskell tiene la capacidad de construir una máquina no determinista. Al principio, Haskell puede parecer demasiado difícil y abstracto para el uso práctico, pero en realidad es muy poderoso.
Sé que en Prolog puedes hacer algo como
someFunction(List) :-
someOtherFunction(X, List)
doSomethingWith(X)
% and so on
Esto no se repetirá en todos los elementos de la Lista; en cambio, se ramificará en diferentes "máquinas" (mediante el uso de varios subprocesos, retroceso en un solo subproceso, creando universos paralelos o lo que sea) , con una ejecución separada para cada valor posible de X que hace que someOtherFunction(X, List) devuelve el verdadero
(No tengo idea de cómo hace esto, pero eso no es importante para la pregunta)
Mi pregunta es: ¿Qué otros lenguajes de programación no determinísticos existen? Parece que el no-determinismo es la forma más simple y lógica de implementar subprocesos múltiples en un lenguaje con variables inmutables, pero nunca antes había visto esto hecho. ¿Por qué esta técnica no es más popular?
El en.wikipedia.org/wiki/Nondeterministic_programming apunta a Amb que es un esquema derivado con capacidades para la programación no determinista.
Por lo que entiendo, la razón principal por la que los lenguajes de programación no lo hacen es porque ejecutar un programa no determinista en una máquina determinista (como lo son todas las computadoras existentes) es inherentemente costoso. Básicamente, una máquina de Turing no determinista puede resolver problemas complejos en el tiempo polinomial, por lo que no se conoce ningún algoritmo polinomial para una máquina de Turing determinista. En otras palabras, la programación no determinista no logra captar la esencia de los algoritmos en el contexto de las computadoras existentes.
El mismo problema afecta a Prolog. Cualquier aplicación de Prolog eficiente, o al menos no muy ineficiente, debe usar el operador "cortar" para evitar explorar un número exponencial de rutas. Ese operador funciona solo mientras el programador tenga una buena visión mental de cómo el intérprete de Prolog explorará los posibles caminos, de manera determinista y muy procesal. Las cosas que son muy procedimentales no se combinan bien con la programación funcional, ya que esta última es principalmente un esfuerzo por no pensar en absoluto en el procedimiento.
Como nota al margen, entre las máquinas de Turing deterministas y no deterministas, existe el modelo de "computación cuántica". Una computadora cuántica, suponiendo que existe una, no hace todo lo que puede hacer una máquina de Turing no determinista, pero puede hacer más que una máquina de Turing determinista. Hay personas que actualmente están diseñando lenguajes de programación para la computadora cuántica (asumiendo que finalmente se construirá una computadora cuántica). Algunos de esos nuevos lenguajes son funcionales. Puede encontrar una gran cantidad de enlaces útiles en esta página de Wikipedia . Aparentemente, diseñar un lenguaje de programación cuántico, funcional o no, y usarlo, no es fácil y ciertamente no es "simple".
El lenguaje de programación Sly en desarrollo en IBM Research es un intento de incluir el no determinismo inherente en la ejecución de múltiples subprocesos en la ejecución de ciertos tipos de algoritmos. Sin embargo, parece ser un trabajo en progreso.
El prólogo es en realidad determinista: se prescribe el orden de evaluación y el orden importa.
¿Por qué no es más popular el no determinismo?
El no determinismo es impopular porque hace que sea más difícil razonar sobre los resultados de sus programas, y las ejecuciones realmente no deterministas (en oposición a la semántica) son difíciles de implementar.
Los únicos lenguajes no deterministas que conozco son
El cálculo de Dijkstra de las órdenes vigiladas, que él quería que nunca se implementara
ML concurrente, en el cual las comunicaciones pueden ser sincronizadas no deterministicamente
El lenguaje Promela de Gerard Holzmann, que es el lenguaje del verificador de modelos SPIN
SPIN realmente usa el no determinismo y explora todo el espacio de estados cuando puede.
Y, por supuesto, cualquier lenguaje multiproceso se comporta de manera no determinista si los subprocesos no están sincronizados, pero ese es exactamente el tipo de cosas por las que es difícil razonar, y por qué es tan difícil implementar estructuras de datos eficientes y correctas sin bloqueo.
Por cierto, si está buscando lograr un paralelismo, puede lograr lo mismo con una simple función de map en un lenguaje funcional puro como Haskell. Hay una razón por la que Google MapReduce se basa en lenguajes funcionales.
En Prolog puedes tener tanto no determinismo como concurrencia. El no determinismo es lo que describió en su pregunta sobre el código de ejemplo. Puede imaginar que una cláusula de Prolog está llena de declaraciones implícitas de amb . Es menos conocido que la concurrencia también es compatible con la programación lógica.
La historia dice:
El primer lenguaje de programación de lógica concurrente fue el lenguaje relacional de Clark y Gregory, que era una rama de IC-Prolog. Las versiones posteriores de la programación de la lógica concurrente incluyen el Prólogo concurrente de Shapiro y el lenguaje GHC de Ueda''s Guarded Horn Clause. https://en.wikipedia.org/wiki/Concurrent_logic_programming
Pero hoy podríamos ir con huellas dentro de la programación lógica. Here hay un ejemplo para implementar un findall a través de hilos. Esto también puede modificarse para realizar todo tipo de tareas en la colección, o incluso producir redes de agentes hacia la inteligencia artificial distribuida.
Existe un lenguaje de programación para problemas no deterministas que se denomina "programación de red de control". Si desea más información, vaya a http://controlnetworkprogramming.com . Este sitio todavía está en progreso, pero puedes leer algo de información al respecto.
Un ejemplo de un lenguaje no determinista es Occam , basado en la teoría CSP . La combinación de las construcciones PAR y ALT puede dar lugar a un comportamiento no determinista en sistemas multiprocesador, implementando programas paralelos de grano fino .
Cuando se usan canales blandos, es decir, canales entre procesos en el mismo procesador, la implementación de ALT hará que el comportamiento sea casi determinista † , pero tan pronto como comience a usar canales duros (enlaces de comunicación físicos fuera del procesador), desaparecerá toda ilusión de determinismo. No se espera que los diferentes procesadores remotos estén sincronizados de ninguna manera y es posible que ni siquiera tengan el mismo núcleo o velocidad de reloj.
† La construcción ALT menudo se implementa con un PRI ALT , por lo que debe codificar explícitamente la imparcialidad si necesita que sea justo.
El no determinismo se considera una desventaja cuando se trata de razonar y probar que los programas son correctos, pero en muchos sentidos, una vez que lo haya aceptado, se liberará de muchas de las restricciones que el determinismo impone a su razonamiento.
Siempre que la secuencia de la comunicación no genere un deadlock , lo que se puede hacer aplicando técnicas de CSP, el orden preciso en el que se hacen las cosas debería ser mucho menos importante que obtener los resultados que desea a tiempo.
Podría decirse que esta falta de determinismo fue un factor importante en la prevención de la adopción de los sistemas Occam y Transputer en proyectos militares, dominados por Ada en ese momento, donde saber exactamente lo que hacía una CPU en cada ciclo de reloj se consideraba esencial para probar una sistema correcto Sin esta restricción, los sistemas Occam y Transputer en los que se ejecutaba (las únicas CPU en ese momento con una implementación de punto flotante IEEE probada formalmente) habrían sido un ajuste perfecto para los sistemas militares en tiempo real que necesiten altos niveles de funcionalidad de procesamiento en un pequeño espacio.