Programación declarativa

Este artículo tiene varios problemas. Ayúdenos a mejorarlo o a discutir estos problemas en la página de discusión . ( Aprenda cómo y cuándo eliminar estos mensajes ) Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Please help to improve this article by introducing more precise citations. (April 2010) (Learn how and when to remove this message) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Declarative programming" – news · newspapers · books · scholar · JSTOR (February 2015) (Learn how and when to remove this message) (Learn how and when to remove this message)

En informática , la programación declarativa es un paradigma de programación (un estilo de construir la estructura y los elementos de los programas informáticos) que expresa la lógica de un cálculo sin describir su flujo de control . ^[1]

Muchos lenguajes que aplican este estilo intentan minimizar o eliminar los efectos secundarios al describir lo que el programa debe lograr en términos del dominio del problema , en lugar de describir cómo lograrlo como una secuencia de primitivas del lenguaje de programación ^[2] (el cómo se deja en manos de la implementación del lenguaje ). Esto contrasta con la programación imperativa , que implementa algoritmos en pasos explícitos. ^{[3] [4]}

La programación declarativa suele considerar los programas como teorías de una lógica formal y los cálculos como deducciones en ese espacio lógico. La programación declarativa puede simplificar enormemente la escritura de programas paralelos . ^[5]

Los lenguajes declarativos comunes incluyen los lenguajes de consulta de bases de datos (por ejemplo, SQL , XQuery ), expresiones regulares , programación lógica (por ejemplo, Prolog , Datalog , programación de conjuntos de respuestas ), programación funcional , gestión de configuración y sistemas de modelado algebraico .

La programación declarativa suele definirse como cualquier estilo de programación que no sea imperativo. Otras definiciones comunes intentan definirla simplemente contrastándola con la programación imperativa. Por ejemplo:

• Un programa de alto nivel que describe lo que debe realizar un cálculo.
• Cualquier lenguaje de programación que carezca de efectos secundarios (o más específicamente, que sea referencialmente transparente ).
• Un lenguaje con una clara correspondencia con la lógica matemática . ^[6]

Estas definiciones se superponen sustancialmente.

La programación declarativa es un estilo de programación no imperativo en el que los programas describen los resultados deseados sin enumerar explícitamente los comandos o pasos que deben realizarse. Los lenguajes de programación funcional y lógica se caracterizan por un estilo de programación declarativa. En la programación lógica, los programas consisten en oraciones expresadas en forma lógica, y los cálculos utilizan esas oraciones para resolver problemas, que también se expresan en forma lógica.

En un lenguaje funcional puro , como Haskell , todas las funciones no tienen efectos secundarios y los cambios de estado solo se representan como funciones que transforman el estado, que se representa explícitamente como un objeto de primera clase en el programa. Aunque los lenguajes funcionales puros no son imperativos, a menudo proporcionan una función para describir el efecto de una función como una serie de pasos. Otros lenguajes funcionales, como Lisp , OCaml y Erlang , admiten una mezcla de programación funcional y procedimental.

Algunos lenguajes de programación lógica, como Prolog , y lenguajes de consulta de bases de datos, como SQL, aunque declarativos en principio, también admiten un estilo de programación procedimental.

La programación declarativa es un término general que incluye varios paradigmas de programación más conocidos .

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

Entre los ejemplos más conocidos de lenguajes declarativos específicos de dominio (DSL) se incluyen el lenguaje de entrada del generador de analizador sintáctico yacc , QML , el lenguaje de especificación de compilación Make , el lenguaje de gestión de configuración de Puppet , expresiones regulares , Datalog , programación de conjuntos de respuestas y un subconjunto de SQL (consultas SELECT, por ejemplo). Los DSL tienen la ventaja de ser útiles sin tener que ser necesariamente Turing-completos , lo que hace que sea más fácil que un lenguaje sea puramente declarativo.

Muchos lenguajes de marcado como HTML , MXML , XAML , XSLT u otros lenguajes de marcado de interfaz de usuario suelen ser declarativos. HTML, por ejemplo, solo describe lo que debería aparecer en una página web; no especifica ni el flujo de control para representar una página ni las posibles interacciones de la página con un usuario .

A partir de 2013 ^[update], algunos sistemas de software ^{[ ¿cuáles? ]} combinan lenguajes de marcado de interfaz de usuario tradicionales (como HTML) con un marcado declarativo que define qué (pero no cómo) deben hacer los sistemas de servidor back-end para admitir la interfaz declarada. Dichos sistemas, que normalmente utilizan un espacio de nombres XML específico del dominio , pueden incluir abstracciones de sintaxis de base de datos SQL o llamadas parametrizadas a servicios web mediante transferencia de estado representacional (REST) ​​y SOAP . ^{[ cita requerida ]}

Los lenguajes de programación funcional como Haskell , Scheme y ML evalúan expresiones a través de la aplicación de funciones. A diferencia del paradigma relacionado pero más imperativo de la programación procedimental , la programación funcional pone poco énfasis en la secuenciación explícita. En cambio, los cálculos se caracterizan por varios tipos de aplicación y composición de funciones recursivas de orden superior y, como tales, pueden considerarse simplemente como un conjunto de asignaciones entre dominios y codominios . Muchos lenguajes funcionales, incluidos la mayoría de los de las familias ML y Lisp, no son puramente funcionales y, por lo tanto, permiten la introducción de efectos con estado en los programas.

Los Makefiles, por ejemplo, especifican dependencias de forma declarativa, ^[7] 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 normalmente es imperativo (como C ).

Los lenguajes de programación lógica, como Prolog , Datalog y la programación de conjuntos de respuestas , realizan los cálculos 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 realiza los cálculos reduciendo los objetivos a subobjetivos, de arriba hacia abajo mediante razonamiento inverso , mientras que la mayoría de los sistemas Datalog realizan los cálculos de abajo hacia arriba mediante razonamiento directo . 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. El 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, una computadora puede realizar manipulaciones algebraicas para formular mejor el algoritmo de solución. La causalidad matemática se impone típicamente en los límites del sistema físico, mientras que la descripción del comportamiento del sistema en sí es declarativa o acausal. Los lenguajes y entornos de modelado declarativos incluyen Analytica , Modelica y Simile. ^[8]

Lisp es una familia de lenguajes de programación inspirados vagamente en la notación matemática y el cálculo lambda de Alonzo Church . Algunos dialectos, como Common Lisp , son principalmente imperativos pero admiten programación funcional. Otros, como Scheme , están diseñados para programación funcional.

En Scheme, la función factorial se puede definir de la siguiente manera:

( define ( factorial n ) ( si ( = n 0 ) 1 ;;; 0! = 1 ( * n ( factorial ( - n 1 ))))) ;;; n! = n*(n-1)!                

Esto define la función factorial mediante su definición recursiva. Por el contrario, es más habitual definir un procedimiento para un lenguaje imperativo.

En el cálculo lambda y en el lenguaje LISP, las funciones son, por lo general, ciudadanos de primera clase . En términos generales, esto significa que las funciones pueden ser entradas y salidas para otras funciones. Esto puede simplificar la definición de algunas funciones.

Por ejemplo, escribir una función para generar los primeros n números cuadrados en Racket se puede hacer de la siguiente manera:

( define ( first-n-squares n ) ( map ( lambda ( x ) ( * x x )) ;;; Una función que mapea x -> x^2 ( range n ))) ;;; Lista de los primeros n enteros no negativos            

La función de mapa acepta una función y una lista; la salida es una lista de resultados de la función de entrada en cada elemento de la lista de entrada.

ML (1973) ^[9] significa "Meta Lenguaje". ML está tipificado estáticamente y los argumentos de función y los tipos de retorno pueden ser anotados. ^[10]

diversión  veces_10 ( n  :  int )  :  int  =  10  *  n ;

ML no se centra tanto en los corchetes como Lisp y, en cambio, utiliza una variedad más amplia de sintaxis para codificar la relación entre los elementos del código, en lugar de recurrir al ordenamiento y la anidación de listas para expresar todo. La siguiente es una aplicación de times_10:

veces_10 2

Devuelve "20 : int", es decir, 20un valor de tipo int.

Al igual que Lisp , ML está diseñado para procesar listas, aunque todos los elementos de una lista deben ser del mismo tipo. ^[11]

Prolog (1972) significa "PROgramming in LOGic" (Programación en Lógica). Fue desarrollado para responder preguntas en lenguaje natural , ^[12] utilizando la resolución en lenguaje natural ^[13] tanto para deducir respuestas a consultas como para analizar y generar oraciones en lenguaje natural.

Los elementos básicos de un programa Prolog son hechos y reglas . A continuación se muestra 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 la consulta a los subobjetivos de encontrar primero una X tal que se cumpla y luego demostrar que se cumple. Utiliza reglas repetidamente para reducir aún más los subobjetivos a otros subobjetivos, hasta que finalmente logra unificar todos los subobjetivos con hechos en el 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 . ^[14]eat(X,jerry)big(X)small(jerry)

La amplia gama de aplicaciones de Prolog se destaca en el Libro del Año de Prolog, ^[15] 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 separada alrededor de 1977. Sintácticamente y semánticamente , es un subconjunto de Prolog. Pero debido a que no tiene términos compuestos , no es Turing-completo .

La mayoría de los sistemas Datalog ejecutan programas de abajo a 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. En el ejemplo anterior, un sistema Datalog típico primero derivaría los nuevos hechos:

animal ( tom ). animal ( jerry ). grande ( tom ). pequeño ( jerry ).

Utilizando estos hechos, se derivaría el hecho adicional:

come ( tom ,  jerry ).

Entonces terminaría, tanto porque no se pueden derivar hechos nuevos adicionales, como porque el hecho recién derivado se unifica con la consulta.

come ( X ,  jerry ).

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 . ^{[16] [17]}

La programación de conjuntos de respuestas (ASP) evolucionó a fines de la década de 1990, basándose en la semántica del modelo estable (conjunto de respuestas) de la programación lógica. Al igual que Datalog, es un subconjunto de Prolog y, debido a que no tiene términos compuestos, no es Turing-completo.

La mayoría de las implementaciones de ASP ejecutan un programa primero "fundamentando" el programa, reemplazando todas las variables en las reglas por constantes de todas las formas 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 difíciles de búsqueda y representación de conocimiento . ^{[18] [19]}

• Programación inductiva
• Lista de lenguajes de programación declarativos

• Frans Coenen. Características de los lenguajes de programación declarativos. 1999.
• Roberto Harper .
  • ¿Qué es, si es que hay algo, un lenguaje declarativo?. 2013.
  • "Existe un lenguaje declarativo y es el mejor DSL del mundo". 2013.
• Olof Torgersson. Una nota sobre los paradigmas de programación declarativa y el futuro de la programación definicional. 1996.