Lenguajes de programación no deterministas
Sé que en Prolog puedes hacer algo como
someFunction(List) :-
someOtherFunction(X, List)
doSomethingWith(X)
% and so on
Esto no iterará sobre cada elemento en la Lista; en su lugar, se ramificará en diferentes "máquinas" (mediante el uso de múltiples hilos, retrocediendo en un solo hilo, creando universos paralelos o lo que tenga), con una ejecución separada para cada valor posible de X que hace que someOtherFunction(X, List) devuelva true!
(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 deterministas existen? Parece que el no determinismo es la forma simplista y más lógica de implementar multi-threading en un lenguaje con variables inmutables, pero nunca he visto esto antes- ¿Por qué esta técnica no es más popular?
8 answers
El Prolog es en realidad determinista-el orden de evaluación está prescrito, 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 verdaderamente no deterministas (en oposición a la semántica) son difíciles de implementar.
Los únicos lenguajes no deterministas que conozco son
-
Cálculo de Dijkstra de vigilado órdenes, que él quería que nunca se implementaran
-
ML concurrente, en el que las comunicaciones pueden sincronizarse de forma no determinista
-
El lenguaje Promela de Gerard Holzmann, que es el lenguaje del modelo checker SPIN
SPIN realmente usa el no determinismo y explora todo el espacio de estado cuando puede.
Y por supuesto cualquier lenguaje multiproceso se comporta de forma no determinista si los hilos no están sincronizados, pero ese es exactamente el tipo de cosas que es difícil razonar, y por qué es tan difícil implementar estructuras de datos eficientes y correctas sin bloqueos.
Por cierto, si usted está buscando para lograr el paralelismo, se puede lograr lo mismo por una simple función map en un lenguaje funcional puro como Haskell. Hay una razón por la que Google MapReduce se basa en lenguajes funcionales.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-02-02 15:55:08
El artículo de Wikipedia apunta a Amb que es un derivado de Esquema 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 hacen eso es porque ejecutar un programa no determinista en una máquina determinista (como lo son todos los ordenadores existentes) es inherentemente costoso. Básicamente, una máquina de Turing no determinista puede resolver problemas complejos en tiempo polinómico, para el cual no hay algoritmo polinómico para un la máquina de Turing determinista es conocida. En otras palabras, la programación no determinista no logra capturar la esencia de la algorítmica en el contexto de las computadoras existentes.
El mismo problema afecta a Prolog. Cualquier aplicación Prolog eficiente, o al menos no demasiado ineficiente, debe usar el operador " cut " para evitar explorar un número exponencial de rutas. Ese operador solo funciona siempre y cuando el programador tenga una buena visión mental de cómo el intérprete Prolog explorará los posibles caminos, de una manera determinista y muy procedimental. Las cosas que son muy procedimentales no se mezclan bien con la programación funcional, ya que esta última es sobre todo un esfuerzo de no pensar procedimentalmente.
Como nota al margen, entre las máquinas de Turing deterministas y no deterministas, está el modelo de "computación cuántica". Una computadora cuántica, asumiendo que existe, no hace todo lo que una máquina de Turing no determinista puede hacer, pero puede hacer más que una Turing determinista equipo. Hay personas que actualmente están diseñando lenguajes de programación para la computadora cuántica (suponiendo que una computadora cuántica finalmente se construirá). 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ántica, funcional o no, y usarlo, no es fácil y ciertamente no es "simple".
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-02-02 16:37:38
En Prolog puedes tener tanto no-determinismo como concurrencia. El no determinismo es lo que describiste en tu pregunta sobre el código de ejemplo. Puedes imaginar que una cláusula Prolog está llena de sentencias implícitas amb. Es menos conocido que la concurrencia también es soportada por la programación lógica.
La historia dice:
El primer lenguaje de programación lógica concurrente fue el Relacional Lenguaje de Clark y Gregory, que era una rama de IC-Prolog. Tarde las versiones de programación lógica concurrente incluyen la de Shapiro Prolog simultáneo y el lenguaje de la Cláusula de Cuerno Guardado de Ueda GHC. https://en.wikipedia.org/wiki/Concurrent_logic_programming
Pero hoy podríamos ir con bandas de rodadura dentro de la programación lógica. Aquí es un ejemplo para implementar un findall a través de hilos. Esto también se puede modificar para realizar todo tipo de tareas en la colección, o tal vez incluso producir redes de agentes hacia la distribución artificial inteligencia.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-01-30 17:33:23
Un ejemplo de un lenguaje no determinista es Occam, basado en la teoría de CSP. La combinación de los constructos PAR y ALT puede dar lugar a un comportamiento no determinista en sistemas multiprocesadores, implementando programas paralelos de grano fino.
Cuando se utilizan canales suaves, es decir, canales entre procesos en el mismo procesador, la implementación de ALT hará que el comportamiento sea cercano a deterministic†, pero tan pronto como comience a usar duro canales (enlaces de comunicación físicos fuera del procesador) cualquier ilusión de determinismo desaparece. No se espera que los diferentes procesadores remotos se sincronicen de ninguna manera y es posible que ni siquiera tengan el mismo núcleo o la misma velocidad de reloj.
†La construcción ALT a menudo se implementa con un PRI ALT, por lo que debe codificar explícitamente de manera justa si necesita que sea justa.
El no determinismo es visto como una desventaja cuando se trata de razonar y probar los programas son correctos, pero de muchas maneras una vez que lo has aceptado, te liberas de muchas de las restricciones que el determinismo fuerza en tu razonamiento.
Mientras la secuenciación de la comunicación no conduzca a un punto muerto, lo que se puede hacer aplicando técnicas CSP, entonces el orden preciso en el que se hacen las cosas debería importar mucho menos que si obtiene los resultados que desea a tiempo.
Podría decirse que fue esta falta de determinismo la que factor en la prevención de la adopción de Occam y Transputer sistemas en proyectos militares, dominado por Ada en el momento, donde saber con precisión lo que una CPU estaba haciendo en cada ciclo de reloj se consideraba esencial para demostrar un sistema correcto. Sin esta restricción, Occam y los sistemas de Transputer en los que se ejecutaba (las únicas CPU en ese momento con una implementación de punto flotante IEEE formalmente probada) habrían sido un ajuste perfecto para sistemas militares duros en tiempo real necesidad de altos niveles de funcionalidad de procesamiento en un espacio pequeño.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-01-30 18:17:35
Creo que Haskell tiene la capacidad de construir una máquina no determinista. Haskell al principio puede parecer demasiado difícil y abstracto para su uso práctico, pero en realidad es muy poderoso.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-02-02 15:57:48
Existe un lenguaje de programación para problemas no deterministas que se llama "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 puede leer algo de información al respecto.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-01-10 16:51:21
Nota: Antes de hacer clic en el enlace y estar decepcionado: Este es un lenguaje esotérico y no tiene nada que ver con el paralelismo.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-02-07 21:02:47
El lenguaje de programación Sly en desarrollo en IBM Research es un intento de incluir el no determinismo inherente a la ejecución multihilo en la ejecución de ciertos tipos de algoritmos. Sin embargo, parece ser un trabajo en progreso.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-03-02 05:00:49