En matemáticas y ciencias de la computación , la currificación es la técnica de traducir una función que toma múltiples argumentos en una secuencia de familias de funciones, cada una de las cuales toma un solo argumento.
En el ejemplo prototípico, uno comienza con una función que toma dos argumentos, uno de y otro de y produce objetos en La forma currificada de esta función trata el primer argumento como un parámetro, para crear una familia de funciones. La familia está organizada de modo que para cada objeto en hay exactamente una función.
En este ejemplo, se convierte en una función que toma como argumento y devuelve una función que asigna cada uno a La notación adecuada para expresar esto es verbosa. La función pertenece al conjunto de funciones Mientras tanto, pertenece al conjunto de funciones Por lo tanto, algo que se asigna a será del tipo Con esta notación, es una función que toma objetos del primer conjunto y devuelve objetos del segundo conjunto, y así se escribe Este es un ejemplo algo informal; a continuación se dan definiciones más precisas de lo que se entiende por "objeto" y "función". Estas definiciones varían de un contexto a otro y toman diferentes formas, dependiendo de la teoría en la que uno esté trabajando.
El currying está relacionado con, pero no es lo mismo que, la aplicación parcial . [1] [2] El ejemplo anterior se puede utilizar para ilustrar la aplicación parcial; es bastante similar. La aplicación parcial es la función que toma el par y juntos como argumentos, y devuelve Usando la misma notación que arriba, la aplicación parcial tiene la firma Escrita de esta manera, se puede ver que la aplicación es adjunta al currying.
La currificación de una función con más de dos argumentos se puede definir por inducción.
La currificación es útil tanto en entornos prácticos como teóricos. En los lenguajes de programación funcional y muchos otros, proporciona una forma de gestionar automáticamente cómo se pasan los argumentos a las funciones y excepciones. En la informática teórica , proporciona una forma de estudiar funciones con múltiples argumentos en modelos teóricos más simples que proporcionan solo un argumento. El entorno más general para la noción estricta de currificación y anulación de currificación se encuentra en las categorías monoidales cerradas , que sustentan una amplia generalización de la correspondencia de Curry-Howard de pruebas y programas a una correspondencia con muchas otras estructuras, incluidas la mecánica cuántica, los cobordismos y la teoría de cuerdas. [3]
El concepto de currying fue introducido por Gottlob Frege , [4] [5] desarrollado por Moses Schönfinkel , [6] [5] [7] [8] [9] [10] [11] y desarrollado posteriormente por Haskell Curry . [8] [10] [12] [13]
La descurificación es la transformación dual de la curificación y puede considerarse como una forma de desfuncionalización . Toma una función cuyo valor de retorno es otra función y produce una nueva función que toma como parámetros los argumentos de y y devuelve, como resultado, la aplicación de y posteriormente, a esos argumentos. El proceso puede iterarse.
El currying proporciona una forma de trabajar con funciones que toman múltiples argumentos y usarlas en marcos donde las funciones pueden tomar solo un argumento. Por ejemplo, algunas técnicas analíticas solo se pueden aplicar a funciones con un solo argumento. Las funciones prácticas con frecuencia toman más argumentos que esto. Frege demostró que era suficiente proporcionar soluciones para el caso de un solo argumento, ya que era posible transformar una función con múltiples argumentos en una cadena de funciones de un solo argumento. Esta transformación es el proceso ahora conocido como currying. [14] Todas las funciones "ordinarias" que pueden encontrarse típicamente en el análisis matemático o en la programación de computadoras pueden ser currificadas. Sin embargo, hay categorías en las que el currying no es posible; las categorías más generales que permiten el currying son las categorías monoidales cerradas .
Algunos lenguajes de programación casi siempre utilizan funciones currificadas para lograr múltiples argumentos; ejemplos notables son ML y Haskell , donde en ambos casos todas las funciones tienen exactamente un argumento. Esta propiedad se hereda del cálculo lambda , donde las funciones multiargumento suelen representarse en forma currificada.
El currying está relacionado con, pero no es lo mismo que la aplicación parcial . [1] [2] En la práctica, la técnica de programación de cierres se puede utilizar para realizar una aplicación parcial y un tipo de currying, ocultando argumentos en un entorno que viaja con la función currying.
El "Curry" en "Currying" es una referencia al lógico Haskell Curry , quien utilizó el concepto ampliamente, pero Moses Schönfinkel tuvo la idea seis años antes que Curry. [10] Se ha propuesto el nombre alternativo "Schönfinkelisation". [15] En el contexto matemático, el principio se remonta al trabajo de Frege en 1893. [4] [5]
No está claro quién originó la palabra "currying". David Turner dice que la palabra fue acuñada por Christopher Strachey en sus notas de la conferencia de 1967 Conceptos fundamentales en lenguajes de programación , [16] pero esa fuente introduce el concepto como "un dispositivo originado por Schönfinkel", y el término "currying" no se utiliza, mientras que Curry se menciona más adelante en el contexto de funciones de orden superior. [7] John C. Reynolds definió "currying" en un artículo de 1972, pero no afirmó haber acuñado el término. [8]
La currificación se entiende más fácilmente si se empieza con una definición informal, que luego se puede moldear para que se ajuste a muchos dominios diferentes. Primero, hay que establecer una notación. La notación denota todas las funciones desde hasta . Si es una función de este tipo, escribimos . Sea que denotemos los pares ordenados de los elementos de y respectivamente, es decir, el producto cartesiano de y . Aquí, y pueden ser conjuntos, o pueden ser tipos, o pueden ser otros tipos de objetos, como se explora a continuación.
Dada una función
currying construye una nueva función
Es decir, toma un argumento de tipo y devuelve una función de tipo . Se define por
para de tipo y de tipo . Entonces también escribimos
La descurificación es la transformación inversa, y se entiende más fácilmente en términos de su adjunta derecha, la función
En la teoría de conjuntos , la notación se utiliza para denotar el conjunto de funciones del conjunto al conjunto . La currificación es la biyección natural entre el conjunto de funciones de a , y el conjunto de funciones de al conjunto de funciones de a . En símbolos:
De hecho, es esta biyección natural la que justifica la notación exponencial para el conjunto de funciones. Como sucede en todos los casos de currificación, la fórmula anterior describe un par adjunto de funtores : para cada conjunto fijo , el funtor es adjunto por la izquierda al funtor .
En la categoría de conjuntos , el objeto se llama objeto exponencial .
En la teoría de espacios funcionales , como en el análisis funcional o la teoría de homotopía , normalmente nos interesan las funciones continuas entre espacios topológicos . Se escribe (el functor Hom ) para el conjunto de todas las funciones desde hasta y se utiliza la notación para denotar el subconjunto de funciones continuas. Aquí, es la biyección
mientras que la descurrificación es la función inversa. Si al conjunto de funciones continuas de a se le da la topología compacta-abierta , y si el espacio es localmente compacto Hausdorff , entonces
es un homeomorfismo . Esto también es así cuando , y se generan de forma compacta , [17] : capítulo 5 [18] aunque hay más casos. [19] [20]
Un corolario útil es que una función es continua si y solo si su forma currificada es continua. Otro resultado importante es que el mapa de aplicación , generalmente llamado "evaluación" en este contexto, es continuo (nótese que eval es un concepto estrictamente diferente en informática). Es decir,
es continua cuando es compacta-abierta y localmente compacta de Hausdorff. [21] Estos dos resultados son fundamentales para establecer la continuidad de la homotopía , es decir cuando es el intervalo unitario , de modo que puede considerarse como una homotopía de dos funciones de a , o, equivalentemente, un camino único (continuo) en .
En topología algebraica , la currificación sirve como ejemplo de dualidad de Eckmann-Hilton y, como tal, desempeña un papel importante en una variedad de entornos diferentes. Por ejemplo, el espacio de bucles es adjunto a suspensiones reducidas ; esto se escribe comúnmente como
donde es el conjunto de clases de homotopía de los mapas , y es la suspensión de A , y es el espacio de bucles de A . En esencia, la suspensión puede verse como el producto cartesiano de con el intervalo unitario, módulo una relación de equivalencia para convertir el intervalo en un bucle. La forma currificada entonces mapea el espacio al espacio de funciones de bucles en , es decir, de en . [21] Entonces es el funtor adjunto que mapea suspensiones a espacios de bucles, y la descurrificación es el dual. [21]
La dualidad entre el cono de mapeo y la fibra de mapeo ( cofibración y fibración ) [17] : capítulos 6,7 puede entenderse como una forma de currificación, que a su vez conduce a la dualidad de las secuencias largas exactas y coexactas de Puppe .
En álgebra homológica , la relación entre currificación y descurrificación se conoce como adjunción tensorial-hom . Aquí surge un giro interesante: el funtor Hom y el funtor producto tensorial podrían no elevarse a una secuencia exacta ; esto conduce a la definición del funtor Ext y del funtor Tor .
En teoría de orden , es decir, la teoría de redes de conjuntos parcialmente ordenados , es una función continua cuando la red recibe la topología de Scott . [22] Las funciones Scott-continuas se investigaron por primera vez en el intento de proporcionar una semántica para el cálculo lambda (ya que la teoría de conjuntos ordinaria es inadecuada para hacer esto). De manera más general, las funciones Scott-continuas ahora se estudian en la teoría de dominios , que abarca el estudio de la semántica denotacional de los algoritmos informáticos. Nótese que la topología de Scott es bastante diferente de muchas topologías comunes que uno podría encontrar en la categoría de espacios topológicos ; la topología de Scott es típicamente más fina y no es sobria .
La noción de continuidad hace su aparición en la teoría de tipos de homotopía , donde, en términos generales, dos programas de computadora pueden considerarse homotópicos, es decir, calculan los mismos resultados, si pueden refactorizarse "continuamente" de uno a otro.
En informática teórica , la currificación proporciona una forma de estudiar funciones con múltiples argumentos en modelos teóricos muy simples, como el cálculo lambda , en el que las funciones solo toman un único argumento. Considere una función que toma dos argumentos y tiene el tipo , lo que debe entenderse como que x debe tener el tipo , y debe tener el tipo , y la función en sí misma devuelve el tipo . La forma currificada de f se define como
donde es el abstractor del cálculo lambda. Dado que curry toma como entrada funciones con el tipo , se concluye que el tipo de curry en sí es
El operador → se considera a menudo asociativo por la derecha , por lo que el tipo de función currificada se suele escribir como . Por el contrario, la aplicación de la función se considera asociativa por la izquierda , por lo que es equivalente a
Es decir, los paréntesis no son necesarios para desambiguar el orden de la aplicación.
Las funciones currificadas se pueden usar en cualquier lenguaje de programación que admita cierres ; sin embargo, las funciones no currificadas generalmente se prefieren por razones de eficiencia, ya que la sobrecarga de la aplicación parcial y la creación de cierres se pueden evitar para la mayoría de las llamadas de función.
En la teoría de tipos , la idea general de un sistema de tipos en informática se formaliza en un álgebra de tipos específica. Por ejemplo, al escribir , la intención es que y sean tipos , mientras que la flecha es un constructor de tipos , específicamente, el tipo de función o tipo de flecha . De manera similar, el producto cartesiano de tipos se construye mediante el constructor de tipos de producto .
El enfoque teórico de tipos se expresa en lenguajes de programación como ML y los lenguajes derivados e inspirados en él: Caml , Haskell y F# .
El enfoque de la teoría de tipos proporciona un complemento natural al lenguaje de la teoría de categorías , como se analiza a continuación. Esto se debe a que las categorías, y específicamente las categorías monoidales , tienen un lenguaje interno , siendo el cálculo lambda de tipos simples el ejemplo más destacado de dicho lenguaje. Es importante en este contexto, porque se puede construir a partir de un único constructor de tipos, el tipo flecha. El currying dota entonces al lenguaje de un tipo de producto natural. La correspondencia entre objetos en categorías y tipos permite entonces que los lenguajes de programación se reinterpreten como lógicas (a través de la correspondencia Curry-Howard ) y como otros tipos de sistemas matemáticos, como se explora más adelante.
Según la correspondencia Curry-Howard , la existencia de currificación y descurrificación es equivalente al teorema lógico (también conocido como exportación ), ya que las tuplas ( tipo producto ) corresponden a la conjunción en lógica, y el tipo función corresponde a la implicación.
El objeto exponencial en la categoría de álgebras de Heyting normalmente se escribe como implicación material . Las álgebras de Heyting distributivas son álgebras booleanas , y el objeto exponencial tiene la forma explícita , lo que deja claro que el objeto exponencial realmente es implicación material . [23]
Las nociones anteriores de currificación y descurrificación encuentran su enunciado más general y abstracto en la teoría de categorías . La currificación es una propiedad universal de un objeto exponencial y da lugar a una adjunción en categorías cartesianas cerradas . Es decir, existe un isomorfismo natural entre los morfismos de un producto binario y los morfismos de un objeto exponencial .
Esto se generaliza a un resultado más amplio en categorías monoidales cerradas : Currying es la afirmación de que el producto tensorial y el Hom interno son funtores adjuntos ; es decir, para cada objeto hay un isomorfismo natural :
Aquí, Hom denota el funtor hom (externo) de todos los morfismos en la categoría, mientras que denota el funtor hom interno en la categoría monoidal cerrada. Para la categoría de conjuntos , los dos son lo mismo. Cuando el producto es el producto cartesiano, entonces el hom interno se convierte en el objeto exponencial .
La currificación puede fallar de dos maneras. Una es si una categoría no es cerrada y, por lo tanto, carece de un funtor hom interno (posiblemente porque hay más de una opción para dicho funtor). Otra forma es si no es monoidal y, por lo tanto, carece de un producto (es decir, carece de una forma de escribir pares de objetos). Las categorías que tienen productos y hom internos son exactamente las categorías monoidales cerradas.
El establecimiento de categorías cartesianas cerradas es suficiente para la discusión de la lógica clásica ; el establecimiento más general de categorías monoidales cerradas es adecuado para la computación cuántica . [24]
La diferencia entre estos dos es que el producto de las categorías cartesianas (como la categoría de conjuntos , órdenes parciales completos o álgebras de Heyting ) es simplemente el producto cartesiano ; se interpreta como un par ordenado de elementos (o una lista). El cálculo lambda de tipos simples es el lenguaje interno de las categorías cartesianas cerradas; y es por esta razón que los pares y las listas son los tipos primarios en la teoría de tipos de LISP , Scheme y muchos lenguajes de programación funcional .
Por el contrario, el producto de categorías monoidales (como el espacio de Hilbert y los espacios vectoriales del análisis funcional ) es el producto tensorial . El lenguaje interno de tales categorías es la lógica lineal , una forma de lógica cuántica ; el sistema de tipos correspondiente es el sistema de tipos lineal . Tales categorías son adecuadas para describir estados cuánticos entrelazados y, de manera más general, permiten una vasta generalización de la correspondencia de Curry-Howard con la mecánica cuántica , con los cobordismos en topología algebraica y con la teoría de cuerdas . [3] El sistema de tipos lineal y la lógica lineal son útiles para describir primitivas de sincronización , como las cerraduras de exclusión mutua y el funcionamiento de las máquinas expendedoras.
La currificación y la aplicación de funciones parciales a menudo se confunden. [1] [2] Una de las diferencias significativas entre ambas es que una llamada a una función parcialmente aplicada devuelve el resultado de inmediato, no otra función más abajo en la cadena de currificación; esta distinción se puede ilustrar claramente para funciones cuya aridad es mayor que dos. [25]
Dada una función de tipo , la currificación produce . Es decir, mientras que una evaluación de la primera función podría representarse como , la evaluación de la función currificada se representaría como , aplicando cada argumento a su vez a una función de un solo argumento devuelta por la invocación anterior. Tenga en cuenta que después de llamar a , nos quedamos con una función que toma un solo argumento y devuelve otra función, no una función que toma dos argumentos.
Por el contrario, la aplicación de una función parcial se refiere al proceso de fijar una cantidad de argumentos a una función, produciendo otra función de menor aridad. Dada la definición de anterior, podríamos fijar (o "vincular") el primer argumento, produciendo una función de tipo . La evaluación de esta función podría representarse como . Nótese que el resultado de la aplicación de una función parcial en este caso es una función que toma dos argumentos.
Intuitivamente, la aplicación de funciones parciales dice "si fijas el primer argumento de la función, obtienes una función de los argumentos restantes". Por ejemplo, si la función div representa la operación de división x / y , entonces div con el parámetro x fijado en 1 (es decir, div 1) es otra función: la misma que la función inv que devuelve el inverso multiplicativo de su argumento, definido por inv ( y ) = 1/ y .
La motivación práctica para la aplicación parcial es que muy a menudo las funciones obtenidas al proporcionar algunos, pero no todos, los argumentos de una función son útiles; por ejemplo, muchos lenguajes tienen una función u operador similar a plus_one
. La aplicación parcial facilita la definición de estas funciones, por ejemplo, creando una función que represente el operador de suma con un límite de 1 como su primer argumento.
La aplicación parcial puede verse como la evaluación de una función curriada en un punto fijo, por ejemplo, dado y entonces o simplemente donde cursa el primer parámetro de f.
Por lo tanto, la aplicación parcial se reduce a una función currificada en un punto fijo. Además, una función currificada en un punto fijo es (trivialmente), una aplicación parcial. Para mayor evidencia, note que, dada cualquier función , una función puede definirse tal que . Por lo tanto, cualquier aplicación parcial puede reducirse a una sola operación de curry. Como tal, curry se define más adecuadamente como una operación que, en muchos casos teóricos, a menudo se aplica recursivamente, pero que es teóricamente indistinguible (cuando se considera como una operación) de una aplicación parcial.
Por lo tanto, una aplicación parcial puede definirse como el resultado objetivo de una única aplicación del operador curry en algún orden de las entradas de alguna función.
Existe un dispositivo originado por Schönfinkel, para reducir operadores con varios operandos a la aplicación sucesiva de operadores de un solo operando.
En la última línea hemos utilizado un truco llamado Currying (en honor al lógico H. Curry) para resolver el problema de introducir una operación binaria en un lenguaje en el que todas las funciones deben aceptar un único argumento. (El árbitro comenta que, aunque "Currying" es más sabroso, "Schönfinkeling" podría ser más preciso).Republicado como Reynolds, John C. (1998). "Intérpretes definicionales para lenguajes de programación de orden superior". Computación simbólica y de orden superior . 11 (4). Boston: Kluwer Academic Publishers: 363–397. doi :10.1023/A:1010027404223. 13 – vía Syracuse University: Facultad de Ingeniería y Ciencias de la Computación - Antiguos Departamentos, Centros, Institutos y Proyectos.
Algunos lógicos contemporáneos llaman a esta manera de ver una función "currying", porque yo hice un uso extensivo de ella; pero Schönfinkel tuvo la idea unos 6 años antes que yo.
{{cite book}}
: CS1 maint: date and year (link)