lenguajes de programación no determinista

Sé que en Prolog se puede hacer algo comolenguajes de programación no determinista

someFunction(List) :- 
    someOtherFunction(X, List) 
    doSomethingWith(X) 
    % and so on

esto no va a iterar sobre cada elemento de la lista; en su lugar, se ramificará en diferentes "máquinas" (mediante el uso de varios subprocesos, retrocediendo en un solo subproceso, creando universos paralelos o lo que tenga), con una ejecución separada para cada valor posible de X que causa someOtherFunction(X, List) para devolver verdadero !
(no tengo ni idea de cómo se hace esto, pero eso no es importante para la cuestión)

Mi pregunta es: ¿Qué otros lenguajes de programación no determistic están ahí fuera? Parece que el no-determinismo es la forma más simple y 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?

Fuente

2010-02-02 BlueRaja - Danny Pflughoeft

Y sí, esto es muy similar a mi última pregunta: http://stackoverflow.com/questions/2174535/multithreading-in-functional-languages-prolog Estoy haciendo una nueva pregunta porque aparentemente redacté la última muy mal; todos comenzaron a discutir sobre los detalles de Prolog, pero realmente no sobre Prolog. –

Google, ayuda, principalmente. E.g: http://en.wikipedia.org/wiki/Ndeterministic_programming es lo que encontré. ¿Eso ayuda? – dirkgently

Eso da unos pocos (3) ejemplos, pero realmente no explica por qué el no determinismo no se usa, por ejemplo, en la mayoría de los lenguajes funcionales –

Prolog es realmente determinista — se ordena el orden de evaluación, y el orden es importante.

¿Por qué el no determinismo es más popular?

no determinismo no es popular, ya que hace que sea más difícil para razonar acerca de los resultados de sus programas, y verdaderamente no deterministas ejecuciones (en contraposición a la semántica) son difíciles de implementar.

Las únicas lenguas no deterministas yo sepa son

cálculo de Dijkstra de comandos guardados, que quiso nunca ser implementado
concurrente ML, en el que las comunicaciones se puede sincronizar nondeterministically
Idioma Promela de Gerard Holzmann, que es el idioma del verificador de modelo SPIN

SPIN realmente utiliza el no determinismo y explora todo el espacio de estado cuando puede.

Y, por supuesto, cualquier lenguaje multiproceso se comporta de forma no determinante si los hilos no están sincronizados, pero eso es exactamente el tipo de cosa difícil de razonar — y por qué es tan difícil implementar estructuras de datos correctas, eficientes y sin bloqueos.

Por cierto, si busca lograr el paralelismo, puede lograr lo mismo con una función simple map en un lenguaje funcional puro como Haskell. Hay una razón por la cual Google MapReduce se basa en lenguajes funcionales.

Fuente

2010-02-02 15:55:08

Estoy seguro de que puedes * lograr * lo mismo con 'map', pero no estoy tan seguro de que sea tan trivial como lo haces sonar. Por ejemplo, el código que di no tiene nada que ver con iterar los elementos de 'List' -' someOtherFunction() 'podría ser cualquier cosa (¡por ejemplo, la suma de comprobación de' List' tiene 'X' bits establecidos)! También hay no determinismo en las funciones: en Prolog, puede escribir varias definiciones de una función, y todas serán llamadas (si alguna devuelve verdadera, el resultado es verdadero). * ¿Por qué * sería difícil ejecutar esto usando hilos separados? Dado que todas las variables son inmutables, no necesitamos bloqueos, ¿verdad? –

Bajé la respuesta porque no diría que Prolog es determinista en un sentido particular de determinismo utilizado en CS. Hay un sentido que se refiere a la semántica del programa, y Prolog tiene verdaderamente un semántico de programa no determinista, aunque la primera búsqueda de profundidad es incompleta. Cada predicado define una relación entre una sustitución y múltiples sustituciones de respuestas refinadas. Los lenguajes de programación funcional van bastante en una longitud con mónadas, continuaciones, etc. para archivar eso. –

Creo que Haskell tiene la capacidad de construir máquinas no deterministas. Haskell al principio puede parecer demasiado difícil y abstracto para el uso práctico, pero en realidad es muy poderoso.

Fuente

2010-02-02 15:57:48

Java 2K

Nota: Antes de hacer clic en el enlace y estar decepcionado: Este es un lenguaje esoteric y no tiene nada que ver con el paralelismo.

Fuente

2010-02-02 16:18:43 Meinersbur

Cuando dije "no determinista", quise decir que el programa toma todos los caminos. Este programa no es no determinista en ese sentido, aunque definitivamente no es determinista. –

El Wikipedia article apunta a Amb que es un derivado del Esquema con capacidades para programación no determinista.

Por lo que yo 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 todas las computadoras existentes) es intrínsecamente costoso. Básicamente, una máquina de Turing no determinista puede resolver problemas complejos en tiempo polinomial, para lo cual no se conoce ningún algoritmo polinomial para una máquina determinante de Turing. 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 terriblemente 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 Prolog explorará los posibles caminos, de una manera determinista y muy procesal. Las cosas que son muy procesales no se combinan bien con la programación funcional, ya que este último es principalmente un esfuerzo de 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 exista, 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 idiomas son funcionales. Puede encontrar una serie de enlaces útiles en este Wikipedia page. Aparentemente, diseñar un lenguaje de programación cuántica, funcional o no, y usarlo, no es fácil y ciertamente no es "simple".

Fuente

2010-02-02 16:37:38

Hay un lenguaje de programación para problemas no deterministas que se denomina "programación de red de control". Si desea obtener más información, vaya al http://controlnetworkprogramming.com. Este sitio todavía está en progreso, pero puede leer información sobre él.

Fuente

2010-09-30 13:55:55 cpxx

Un ejemplo de 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 los sistemas multiprocesador, implementando los programas fine grain parallel.

Al usar canales blandos, es decir, canales entre procesos en el mismo procesador, la implementación de ALT hará que el comportamiento se acerque al determinista ^{& dagger;}, pero tan pronto como comienzas a usar canales duros (enlaces de comunicación físicos sin procesador), cualquier ilusión de determinismo desaparece. No se espera que diferentes procesadores remotos se sincronicen de ninguna manera y es posible que ni siquiera tengan la misma velocidad de reloj o núcleo.

^{& dagger;}_{El constructo ALT a menudo se implementa con un PRI ALT, por lo que debe codificar explícitamente la equidad si necesita que sea justo.}

no determinismo es visto como una desventaja cuando se trata de razonar acerca de los programas y que demuestran correcta, pero en muchos aspectos una vez que haya aceptado, quedas libre de muchas de las limitaciones que las fuerzas de determinismo tu razonamiento

Mientras la secuenciación de la comunicación no conduce a deadlock, lo cual puede hacerse mediante la aplicación de técnicas de CSP, entonces el orden preciso en que se hacen las cosas debería importar mucho menos que el hecho de que obtenga los resultados que se querer a tiempo.

Podría decirse que fue esta falta de determinismo que era un factor importante en la prevención de la adopción de Occam y Transputer sistemas en proyectos militares, dominado por Ada en el momento, en que saber exactamente lo que una CPU estaba haciendo en cada ciclo de reloj se consideró esencial para demostrando un sistema correcto. Sin esta restricción, los sistemas Occam y Transputer en los que se ejecutó (las únicas CPU en ese momento con una implementación de coma flotante IEEE probada formalmente) habrían sido una opción perfecta para sistemas militares duros en tiempo real que necesitan altos niveles de funcionalidad de procesamiento en un pequeño espacio.

Fuente

2011-11-09 18:52:24

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 subprocesos múltiples en la ejecución de ciertos tipos de algoritmos. Sin embargo, parece ser un trabajo en progreso.

Fuente

2014-03-02 05:00:49 MilesHampson

En Prolog puede tener no determinismo y concurrencia. No determinismo es lo que describiste en tu pregunta sobre el código de ejemplo. Puede imaginar que una cláusula Prolog está llena de instrucciones amb implícitas. Se sabe menos que la simultaneidad también es compatible con 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 la IC-Prolog. Las versiones posteriores de la programación lógica concurrente incluyen Concurrent Prolog de Shapiro y el lenguaje GHC de Ueda Guarded Horn Clause. https://en.wikipedia.org/wiki/Concurrent_logic_programming

Pero hoy podríamos ir con peldaños dentro de la programación lógica. Here es 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 generar redes de agentes para la inteligencia artificial distribuida.

Fuente

2016-07-01 19:53:38

lenguajes de programación no determinista

Respuesta

Cuestiones relacionadas