Curry (lenguaje de programación)

Curry es un lenguaje de programación declarativo , una implementación del paradigma de programación lógica funcional , ^{[2] [3]} y basado en el lenguaje Haskell . Fusiona elementos de programación lógica y funcional, ^[4] incluyendo la integración de programación con restricciones .

Es casi un superconjunto de Haskell, pero no admite todas las extensiones de lenguaje de Haskell. A diferencia de Haskell, Curry tiene compatibilidad integrada con cálculos no deterministas que implican búsquedas.

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 función) hasta que no sean posibles más reemplazos (o reducciones) y se obtenga un valor o una 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 . Esta última puede reemplazarse por 2 si interpretamos que el operador “ + ” está definido por un conjunto infinito de ecuaciones, por ejemplo, 1+1 = 2 , 1+2 = 3 , etc. De manera similar, se pueden evaluar expresiones anidadas (donde las subexpresiones que se reemplazarán están entrecomilladas):

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

También existe 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 desprende de una propiedad fundamental de los lenguajes funcionales puros, denominada transparencia referencial : el valor de un resultado calculado no depende del orden o del tiempo de evaluación, debido a la ausencia de efectos secundarios . Esto simplifica el razonamiento sobre los programas funcionales puros y su mantenimiento.

Al igual que muchos lenguajes funcionales como Haskell , Curry admite la definición de tipos de datos algebraicos enumerando 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 = Verdadero | Falso     

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

 no es cierto = falso no es falso = verdadero   
    

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

no '(no es falso)' → 'no es 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 = [] | a : Lista a         

El tipo “ Lista a ” se escribe normalmente como [a] y las listas finitas x1 : x2 : ... : xn :[] se escriben como [ x1 , x2 , ... , xn ] . Podemos definir operaciones sobre tipos recursivos mediante definiciones inductivas donde la coincidencia de patrones admite la separación conveniente de los diferentes casos. Por ejemplo, la operación de concatenación “ ++ ” sobre 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       
      
       

Además de su aplicación para diversas tareas de programación, la operación “ ++ ” también es útil para especificar el comportamiento de otras funciones en 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 si ∃ys : ys ++[ e ] = xs.

En base a 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 de lógica funcional proporcionan la búsqueda de soluciones para variables cuantificadas existencialmente. 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 | ys ++ [ e ] =:= xs = e donde ys , e libre          

Aquí, el símbolo “ =:= ” se utiliza para las restricciones ecuacionales con el fin de proporcionar una distinción sintáctica con respecto a las ecuaciones definitorias. De manera similar, las variables adicionales (es decir, las variables que no se encuentran en el lado izquierdo de la ecuación definitoria) se declaran explícitamente mediante “ where...free ” con el fin de proporcionar 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 su condición c ha sido resuelta. A diferencia de los lenguajes puramente funcionales donde las condiciones solo se evalúan como un valor booleano, los lenguajes de lógica funcional admiten la resolución de condiciones adivinando valores para las incógnitas en la condición. La restricción, como se analiza en la siguiente sección, se utiliza para resolver este tipo de condiciones.

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

La restricció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 puede considerarse como una reducción en un gráfico de términos de programa, y ​​a menudo hay muchas formas diferentes ( estrategias ) de reducir un gráfico de términos dado. Antoy et al. ^[5] demostraron en la década de 1990 que una estrategia de estrechamiento particular, el estrechamiento necesario , es óptima en el sentido de realizar una serie de reducciones para llegar a una "forma normal" correspondiente a una solución que es mínima entre las estrategias sólidas y completas. El estrechamiento necesario corresponde a una estrategia perezosa, en contraste con la estrategia de resolución SLD de Prolog .

La regla que define lo último que se muestra arriba expresa el hecho de que el argumento real debe coincidir con el resultado de restringir la expresión ys++[e] . Curry también puede expresar esta propiedad 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 ( ++ ). Este patrón también se llama patrón funcional . ^[6] Los patrones funcionales son posibles gracias a las características lógicas y funcionales combinadas de Curry y admiten definiciones concisas de tareas que requieren una coincidencia profunda de patrones en estructuras de datos jerárquicas.

Dado que Curry es capaz de resolver ecuaciones que contienen llamadas a funciones con valores desconocidos, su mecanismo de ejecución se basa en cálculos no deterministas, de manera similar a la programación lógica. Este mecanismo también admite la definición de operaciones no deterministas , es decir, operaciones que ofrecen más de un resultado para una entrada dada. El arquetipo de las operaciones no deterministas es la operación infija predefinida ? , llamada operador de elección , que devuelve uno de sus argumentos. Este operador se define mediante las siguientes reglas:

x ? y = x
 x ? y = y

Por lo tanto, la evaluación de la expresión 0 ? 1 devuelve tanto 0 como 1. El cálculo con operaciones no deterministas y el cálculo con variables libres por restricción tienen el mismo poder expresivo. ^[7]

Las reglas que definen ? muestran una característica importante de Curry: todas las reglas se prueban para evaluar alguna operación. Por lo tanto, se puede definir por

 insertar x ys = x : ys insertar x ( y : ys ) = y : insertar x ys          
         

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

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

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

Debido a la ausencia de efectos secundarios, un programa de lógica funcional puede ejecutarse con diferentes estrategias. Para evaluar expresiones, Curry utiliza una variante de la estrategia de restricción necesaria que combina la evaluación diferida 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, donde el usuario puede seleccionar fácilmente una estrategia de búsqueda, como la búsqueda en profundidad (backtracking), la búsqueda en amplitud , la profundización iterativa o la búsqueda paralela.

• Sitio web oficial
• Smap: un entorno de ejecución basado en web para Curry y Haskell con varios programas de ejemplo
• Paquetes de Curry: una colección de paquetes de software para Curry
• MCC - El compilador de curry de Münster, objetivos C
• PAKCS Una importante implementación de Curry, dirigida a Prolog
• KiCS2 Una implementación de Curry, dirigida a Haskell
• Curry2Go Una implementación de Curry, orientada a Go y compatible con la búsqueda paralela justa
• Lista de correo de Curry
• Página de inicio de Michael Hanus
• Programación puramente funcional perezosa no determinista (Fischer, Kiselyov, Shan, 2009), Transformación de programas lógicos funcionales en programas funcionales monádicos (Braßel, Fischer, Hanus, Reck, 2010) sobre el modelado de programación (lógica) perezosa no determinista (como en Curry) en un lenguaje puramente funcional ( Haskell ); dicho enfoque podría dar al programador más flexibilidad en el control sobre las estrategias que, en el caso de Curry, están integradas.