Programación declarativa

La programación con restricciones establece relaciones entre variables mediante restricciones que especifican las propiedades de la solución objetivo. El conjunto de restricciones se resuelve asignando un valor a cada variable de manera que la solución sea consistente con el número máximo de restricciones. La programación con restricciones suele complementar otros paradigmas: programación funcional, lógica e incluso imperativa.

Los Makefiles, por ejemplo, especifican dependencias de forma declarativa, ^{[ 6 ]} pero también incluyen una lista imperativa de acciones a realizar. De manera similar, yacc especifica una gramática libre de contexto de forma declarativa, pero incluye fragmentos de código de un lenguaje anfitrión, que suele ser imperativo (como C ).

Los lenguajes de programación lógica, como Prolog , Datalog y la programación de conjuntos de respuestas , calculan demostrando que un objetivo es una consecuencia lógica del programa o mostrando que el objetivo es verdadero en un modelo definido por el programa. Prolog calcula reduciendo los objetivos a subobjetivos, de arriba hacia abajo mediante razonamiento hacia atrás , mientras que la mayoría de los sistemas Datalog calculan de abajo hacia arriba mediante razonamiento hacia adelante . Los programas de conjuntos de respuestas suelen utilizar solucionadores SAT para generar un modelo del programa.

Los modelos, o representaciones matemáticas, de sistemas físicos pueden implementarse en código informático declarativo. Este código contiene una serie de ecuaciones, no asignaciones imperativas, que describen ("declaran") las relaciones de comportamiento. Cuando un modelo se expresa en este formalismo, un ordenador puede realizar manipulaciones algebraicas para formular de la mejor manera el algoritmo de solución. La causalidad matemática se impone normalmente en los límites del sistema físico, mientras que la descripción del comportamiento del sistema en sí es declarativa o acausal. Entre los lenguajes y entornos de modelado declarativo se incluyen Analytica , Modelica y Simile . ^{[ 7 ]}

Prolog (1972) significa "PROgramación en lógica". Fue desarrollado para responder preguntas en lenguaje natural , ^{[ 8 ]} utilizando la resolución SL ^{[ 9 ]} tanto para deducir respuestas a consultas como para analizar y generar oraciones en lenguaje natural.

Los componentes básicos de un programa Prolog son los hechos y las reglas . He aquí un ejemplo sencillo:

gato ( tom ). % Tom es un gato ratón ( jerry ). % Jerry es un ratónanimal ( X ) :- gato ( X ). % cada gato es un animal animal ( X ) :- ratón ( X ). % cada ratón es un animalgrande ( X ) :- gato ( X ). % cada gato es grande pequeño ( X ) :- ratón ( X ). % cada ratón es pequeñocomer ( X , Y ) :- ratón ( X ), queso ( Y ). % cada ratón come cada queso comer ( X , Y ) :- grande ( X ), pequeño ( Y ). % cada ser grande come cada ser pequeño

Dado este programa, la consulta tiene éxito, mientras que falla. Además, la consulta tiene éxito con la sustitución de respuesta .eat(tom,jerry)eat(jerry,tom)eat(X,jerry)X=tom

Prolog ejecuta programas de arriba hacia abajo, utilizando la resolución SLD para razonar hacia atrás , reduciendo los objetivos a subobjetivos. En este ejemplo, utiliza la última regla del programa para reducir el objetivo de responder a la consulta a los subobjetivos de encontrar primero una X tal que se cumpla y luego demostrar que se cumple. Repite el uso de reglas para reducir aún más los subobjetivos a otros subobjetivos, hasta que finalmente logra unificar todos los subobjetivos con los hechos del programa. Esta estrategia de razonamiento hacia atrás y reducción de objetivos trata las reglas en los programas lógicos como procedimientos, y convierte a Prolog en un lenguaje de programación tanto declarativo como procedimental . ^{[ 10 ]}eat(X,jerry)big(X)small(jerry)

La amplia gama de aplicaciones de Prolog se destaca en el libro Año de Prolog, ^{[ 11 ]} que celebra el 50 aniversario de Prolog.

Los orígenes de Datalog se remontan a los inicios de la programación lógica, pero se identificó como un área independiente alrededor de 1977. Sintáctica y semánticamente , es un subconjunto de Prolog. Sin embargo, debido a que carece de términos compuestos , no es Turing-completo .

La mayoría de los sistemas Datalog ejecutan programas de abajo hacia arriba, utilizando reglas para razonar hacia adelante , derivando nuevos hechos a partir de hechos existentes y finalizando cuando no hay nuevos hechos que se puedan derivar, o cuando los hechos derivados se unifican con la consulta.

Datalog se ha aplicado a problemas como la integración de datos , la extracción de información , las redes , la seguridad , la computación en la nube y el aprendizaje automático . ^{[ 12 ] [ 13 ]}

La programación de conjuntos de respuestas (ASP) surgió a finales de la década de 1990, basándose en la semántica de modelos estables (conjuntos de respuestas) de la programación lógica. Al igual que Datalog, es un subconjunto de Prolog; y, debido a que carece de términos compuestos, no es Turing-completa.

La mayoría de las implementaciones de ASP ejecutan un programa estableciendo primero su base , reemplazando todas las variables en las reglas por constantes de todas las maneras posibles, y luego utilizando un solucionador SAT proposicional, como el algoritmo DPLL , para generar uno o más modelos del programa.

Sus aplicaciones están orientadas a resolver problemas de búsqueda difíciles y a la representación del conocimiento . ^{[ 14 ] [ 15 ]}