Curry (lenguaje de programación)

Curry es un lenguaje de programación de lógica funcional experimental, basado en el lenguaje Haskell. Combina elementos de programación funcional y lógica, incluida la integración de programación de restricciones.

Es casi un superconjunto de Haskell, que carece de soporte principalmente para la sobrecarga usando clases de tipos, que algunas implementaciones brindan de todos modos como una extensión del lenguaje, como Münster Curry Compiler.

Fundamentos de programación lógica funcional

Conceptos básicos

Un programa funcional es un conjunto de funciones definidas por ecuaciones o reglas. Un cálculo funcional consiste en reemplazar subexpresiones por subexpresiones iguales (con respecto a las definiciones de funciones) hasta que no sean posibles más reemplazos (o reducciones) y se obtenga un valor o forma normal. Por ejemplo, considere la función double definida por

doble x = x+x

La expresión “doble 1” se reemplaza por 1+1. Este último puede ser reemplazado por 2 si interpretamos que el operador "+” está definido por un conjunto infinito de ecuaciones, p., 1+1 = 2, 1+2 = 3, etc. De manera similar, se pueden evaluar expresiones anidadas (donde se citan las subexpresiones a reemplazar):

'doble (1+2)' → '(1+2)'+(1+2) → 3+'(1+2) → '3+3' → 6

También hay otro orden de evaluación si reemplazamos los argumentos de los operadores de derecha a izquierda:

'doble (1+2)' → (1+2)+'(1+2)' → '(1+2)'+3 → '3+3' → 6

En este caso, ambas derivaciones conducen al mismo resultado, una propiedad conocida como confluencia. Esto se deriva de una propiedad fundamental de los lenguajes funcionales puros, denominada transparencia referencial: el valor de un resultado calculado no depende del orden o el tiempo de evaluación, debido a la ausencia de efectos secundarios. Esto simplifica el razonamiento y el mantenimiento de programas funcionales puros.

Al igual que muchos lenguajes funcionales como Haskell, Curry admite la definición de tipos de datos algebraicos al enumerar sus constructores. Por ejemplo, el tipo de valores booleanos consta de los constructores True y False que se declaran de la siguiente manera:

 datos Bool = Cierto. Silencio Falso

Las funciones en booleanos se pueden definir mediante la coincidencia de patrones, es decir, al proporcionar varias ecuaciones para diferentes valores de argumento:

 no Cierto. = Falso no Falso = Cierto.

El principio de reemplazar iguales por iguales sigue siendo válido siempre que los argumentos reales tengan la forma requerida, por ejemplo:

no '(no Falso)' → 'no Verdadero' → Falso

Se pueden obtener estructuras de datos más complejas mediante tipos de datos recursivos. Por ejemplo, una lista de elementos, donde el tipo de elementos es arbitrario (indicado por la variable de tipo a), es la lista vacía "[]” o la lista no vacía “x:xs” que consta de un primer elemento x y una lista xs:

 datos Lista a = [] Silencio a : Lista a

El tipo “Lista a” generalmente se escribe como [a] y listas finitas x1:x2:...:xn:[] se escriben como [x1,x2,... ,xn]. Podemos definir operaciones en tipos recursivos por definiciones inductivas donde la coincidencia de patrones apoya la separación conveniente de los diferentes casos. Por ejemplo, la operación de concatenación “++” en listas polimórficas se puede definir de la siguiente manera (la declaración de tipo opcional en la primera línea especifica que “ ++” toma dos listas como entrada y produce una lista de salida, donde todos los elementos de la lista son del mismo tipo no especificado):

 ()++) :: [a] - [a] - [a]  [] ++ Ys = Ys  ()x:xs) ++ Ys = x : xs++Ys

Más allá de su aplicación para varias tareas de programación, la operación “++” también es útil para especificar el comportamiento de otras funciones en las listas. Por ejemplo, el comportamiento de una función last que produce el último elemento de una lista se puede especificar de la siguiente manera: para todas las listas xs y elementos e, last xs = e if ∃ys :ys++[e] = xs.

Con base en esta especificación, se puede definir una función que satisfaga esta especificación empleando características de programación lógica. De manera similar a los lenguajes lógicos, los lenguajes lógicos funcionales brindan búsqueda de soluciones para variables existencialmente cuantificadas. A diferencia de los lenguajes de lógica pura, admiten la resolución de ecuaciones sobre expresiones funcionales anidadas, de modo que una ecuación como ys++[e] = [1,2,3] se resuelve instanciando ys en la lista [1,2] y e en el valor 3. En Curry se puede definir la última operación de la siguiente manera:

 último xs Silencio Ys++[e] == xs = e Donde Ys,e gratis

Aquí, el símbolo “=:=” se usa para restricciones ecuacionales con el fin de proporcionar una distinción sintáctica de las ecuaciones definitorias. De manera similar, las variables adicionales (es decir, las variables que no aparecen en el lado izquierdo de la ecuación definitoria) se declaran explícitamente mediante “where...free” para brindar algunas oportunidades. para detectar errores causados por errores tipográficos. Una ecuación condicional de la forma l | c = r es aplicable para la reducción si se ha resuelto su condición c. A diferencia de los lenguajes puramente funcionales donde las condiciones solo se evalúan en un valor booleano, los lenguajes lógicos funcionales admiten la resolución de condiciones adivinando valores para las incógnitas en la condición. El estrechamiento, como se analiza en la siguiente sección, se usa para resolver este tipo de condiciones.

Reducción

La reducción es un mecanismo mediante el cual una variable se vincula a un valor seleccionado entre alternativas impuestas por restricciones. Cada valor posible se prueba en algún orden, con el resto del programa invocado en cada caso para determinar la validez del enlace. El estrechamiento es una extensión de la programación lógica, ya que realiza una búsqueda similar, pero en realidad puede generar valores como parte de la búsqueda en lugar de limitarse a probarlos.

La reducción es útil porque permite tratar una función como una relación: su valor se puede calcular "en ambas direcciones". Los ejemplos de Curry de la sección anterior ilustran esto.

Como se señaló en la sección anterior, el estrechamiento se puede considerar como una reducción en un gráfico de términos de programa y, a menudo, hay muchas formas diferentes (estrategias) para reducir un gráfico de términos determinado. Antonio et al. demostró en la década de 1990 que una estrategia de estrechamiento particular, estrechamiento necesario, es óptima en el sentido de hacer una serie de reducciones para llegar a una "forma normal" correspondiente a una solución mínima entre estrategias sólidas y completas. El estrechamiento necesario corresponde a una estrategia perezosa, en contraste con la estrategia de resolución SLD de Prolog.

Patrones funcionales

La regla que define último que se muestra arriba expresa el hecho de que el argumento real debe coincidir con el resultado de reducir la expresión ys++[e]. Curry puede expresar esta propiedad también de la siguiente manera más concisa:

 último ()Ys++[e]) = e

Haskell no permite tal declaración ya que el patrón en el lado izquierdo contiene una función definida (++). Tal patrón también se llama patrón funcional. Los patrones funcionales están habilitados por las características funcionales y lógicas combinadas de Curry y admiten definiciones concisas de tareas que requieren una coincidencia profunda de patrones en estructuras de datos jerárquicas.

No determinismo

Dado que Curry puede resolver ecuaciones que contienen llamadas a funciones con valores desconocidos, su mecanismo de ejecución se basa en cálculos no deterministas, similar a la programación lógica. Este mecanismo también admite la definición de operaciones no deterministas, es decir, operaciones que entregan más de un resultado para una entrada determinada. El arquetipo de las operaciones no deterministas es la operación infija predefinida ?, denominada operador choice, que devuelve uno de sus argumentos. Este operador está definido por las siguientes reglas:

 x
x ? y = y

Por lo tanto, la evaluación de la expresión 0 ? 1 devuelve 0 así como 1. La computación con operaciones no deterministas y la computación con variables libres por estrechamiento tienen el mismo poder expresivo.

The rules defining ? show an important feature of Curry: all rules are tried in order to evaluate some operation. Hence, one can define by

 insertar x Ys = x : Ys insertar x ()Sí.:Ys) = Sí. : insertar x Ys

una operación para insertar un elemento en una lista en una posición indeterminada para que la operación perm definida por

 perm [] = [] perm ()x:xs) = insertar x ()perm xs)

devuelve cualquier permutación de una lista de entrada dada.

Estrategias

Debido a la ausencia de efectos secundarios, un programa de lógica funcional se puede ejecutar con diferentes estrategias. Para evaluar expresiones, Curry utiliza una variante de la estrategia de estrechamiento necesario que combina la evaluación perezosa con estrategias de búsqueda no deterministas. A diferencia de Prolog, que utiliza el retroceso para buscar soluciones, Curry no fija una estrategia de búsqueda en particular. Por lo tanto, existen implementaciones de Curry, como KiCS2, en las que el usuario puede seleccionar fácilmente una estrategia de búsqueda, como búsqueda en profundidad (retroceso), búsqueda en amplitud, profundización iterativa o búsqueda paralela.