Curry [1] es un lenguaje de programación lógica funcional experimental , [2] basado en el lenguaje Haskell . Combina elementos de programación funcional y lógica, incluida la integración de programación de restricciones .
Paradigma | funcional , lógica , no estricta, modular |
---|---|
Diseñada por | Michael Hanus, Sergio Antoy y col. |
Disciplina de mecanografía | estático , fuerte , inferido |
SO | portátil |
Sitio web | Curry |
Implementaciones importantes | |
PAKCS (con Prolog como objetivo), mcc (con C como objetivo), KiCS2 (con Haskell como objetivo) | |
Influenciado por | |
Haskell y Prolog |
Es casi un superconjunto de Haskell, que carece principalmente de soporte para sobrecargar el uso de clases de tipos , que algunas implementaciones proporcionan de todos modos como una extensión de lenguaje, como Münster Curry Compiler. [3]
Fundamentos de la 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 función) 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 sustituye por 1 + 1 . Este último puede ser reemplazado por 2 si interpretamos el operador " + ”Para ser 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 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 ni del tiempo de evaluación, debido a la ausencia de efectos secundarios. Esto simplifica el razonamiento y el mantenimiento de programas funcionales puros.
Como hacen 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 Verdadero y Falsos que se declaran de la siguiente manera:
datos Bool = Verdadero | Falso
Las funciones en los 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 iguales por iguales sigue siendo válido siempre que los argumentos reales tengan la forma requerida, por ejemplo:
not '(not False)' → 'not True' → False
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 xy una lista xs :
Lista de datos a = [] | a : Lista un
El tipo " La lista a ”generalmente se escribe como [a] y listas finitas x1 : x2 : ... : xn : [] están escritos como [ x1 , x2 , ... , xn ] . Podemos definir operaciones sobre tipos recursivos mediante 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 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 en último lugar que produce el último elemento de una lista se puede especificar de la siguiente manera: para todas las listas xs y elementos e, última xs = e si ∃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 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 para que una ecuación como ys ++ [ e ] = [1,2,3] se resuelve instanciando ys en la lista [1,2] ye al valor 3 . En Curry se puede definir la operación en último lugar de la siguiente manera:
ultimas xs | ys ++ [ e ] =: = xs = e donde ys , e libre
Aquí, el símbolo " =: = ”Se utiliza para restricciones de ecuaciones con el fin de proporcionar una distinción sintáctica de la definición de ecuaciones. 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 brindar algunas oportunidades para detectar errores causados por errores tipográficos. Una ecuación condicional de la forma l | C = r es aplicable para reducción si se ha resuelto su condición c. A diferencia de los lenguajes puramente funcionales donde las condiciones solo se evalúan con un valor booleano, los lenguajes lógicos funcionales apoyan la resolución de condiciones adivinando valores para las incógnitas en la condición. Para resolver este tipo de condiciones, se utiliza el estrechamiento, como se explica en la siguiente sección.
Estrechamiento
El estrechamiento es un mecanismo mediante el cual una variable está vinculada a un valor seleccionado entre las 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 de la vinculación. 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.
El estrechamiento 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érmino de programa y, a menudo, hay muchas formas ( estrategias ) diferentes para reducir un gráfico de término dado. Antoy y col. [4] demostró en la década de 1990 que una estrategia de reducción particular, necesaria reducción , es óptima en el sentido de hacer una serie de reducciones para llegar a una "forma normal" correspondiente a una solución que es 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 El ú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 ( ++ ). Este patrón también se llama patrón funcional . [5] 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 profunda coincidencia 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, 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 entregan más de un resultado para una entrada determinada. El arquetipo de las operaciones no deterministas es la operación infijo predefinida ? , llamado operador de elección , que devuelve uno de sus argumentos. Este operador está definido por las siguientes reglas:
X ? y = x X ? y = y
Así, la evaluación de la expresión 0? 1 devoluciones 0 así como 1 . Computar con operaciones no deterministas y computar con variables libres mediante el estrechamiento tiene el mismo poder expresivo. [6]
Las reglas que definen ? muestran una característica importante de Curry: todas las reglas se prueban para evaluar alguna operación. Por tanto, uno 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 permanente definida por
permanente [] = [] permanente ( x : xs ) = insertar x ( permanente 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 usa una variante de la estrategia de restricción necesaria 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 , donde 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.
Referencias
- ^ Michael Hanus (ed.). "Curry: un lenguaje lógico funcional verdaderamente integrado" .CS1 maint: texto adicional: lista de autores ( enlace )
- ^ Sergio Antoy y Michael Hanus (2010). "Programación lógica funcional". Comunicaciones de la ACM . ACM. 53 (4): 74–85. doi : 10.1145 / 1721654.1721675 . S2CID 14578759 .
- ^ El compilador Münster Curry
- ^ Sergio Antoy, Rachid Echahed y Michael Hanus (2007). "Una estrategia de estrechamiento necesaria". Revista de la ACM . ACM. 47 (4): 776–822. doi : 10.1145 / 347476.347484 . ISSN 0004-5411 . S2CID 47275506 .
- ^ Antoy Sergio, Hanus Michael (2006). "Programación declarativa con patrones de funciones". Apuntes de conferencias en informática . 3901 : 6-22. doi : 10.1007 / 11680093_2 . ISBN 978-3-540-32654-0.
- ^ Antoy Sergio, Hanus Michael (2006). "Superposición de reglas y variables lógicas en programas de lógica funcional". Apuntes de conferencias en informática . 4079 : 87-101. doi : 10.1007 / 11799573_9 . ISBN 978-3-540-36635-5.
enlaces externos
- Curry : la página de inicio de Curry
- Smap : un entorno de ejecución basado en web para Curry y Haskell con varios programas de ejemplo
- MCC : el compilador Münster Curry, que utiliza C como destino
- PAKCS Una implementación importante de Curry con una interfaz WWW, que usa Prolog como objetivo
- KiCS2 Una implementación de Curry, que usa Haskell como objetivo
- Lista de correo de curry
- Página de inicio de Michael Hanus
- Programación no determinista perezosa puramente funcional (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 ); tal enfoque podría dar al programador más flexibilidad en el control de las estrategias que, en el caso de Curry, están integradas.