El cálculo lambda (también escrito como λ -cálculo ) es un sistema formal en lógica matemática para expresar cálculos basados en la abstracción y aplicación de funciones mediante vinculación y sustitución de variables . Es un modelo universal de computación que puede usarse para simular cualquier máquina de Turing . Fue introducido por el matemático Alonzo Church en la década de 1930 como parte de su investigación sobre los fundamentos de las matemáticas .
El cálculo lambda consiste en construir términos lambda y realizar operaciones de reducción sobre ellos. En la forma más simple de cálculo lambda, los términos se construyen utilizando únicamente las siguientes reglas: [a]
Las operaciones de reducción incluyen:
Si se utiliza la indexación de De Bruijn , ya no se requiere la conversión α ya que no habrá colisiones de nombres. Si finalmente termina la aplicación repetida de los pasos de reducción, entonces, según el teorema de Church-Rosser, se producirá una forma β-normal .
Los nombres de las variables no son necesarios si se utiliza una función lambda universal, como Iota y Jot , que pueden crear cualquier comportamiento de función llamándola a sí misma en varias combinaciones.
El cálculo lambda es Turing completo , es decir, es un modelo universal de computación que puede usarse para simular cualquier máquina de Turing . [3] Su homónimo, la letra griega lambda (λ), se utiliza en expresiones lambda y términos lambda para indicar la vinculación de una variable en una función .
El cálculo lambda puede estar tipificado o sin tipificar . En el cálculo lambda escrito, las funciones sólo se pueden aplicar si son capaces de aceptar el "tipo" de datos de la entrada dada. Los cálculos lambda tipificados son más débiles que los cálculos lambda no tipificados, que es el tema principal de este artículo, en el sentido de que los cálculos lambda tipificados pueden expresar menos que los cálculos no tipificados. Por otro lado, los cálculos lambda tipificados permiten demostrar más cosas. Por ejemplo, en el cálculo lambda de tipo simple, es un teorema que cada estrategia de evaluación termina para cada término lambda de tipo simple, mientras que la evaluación de términos lambda sin tipo no necesita terminar (ver más abajo). Una de las razones por las que existen muchos cálculos lambda tipificados diferentes ha sido el deseo de hacer más (de lo que el cálculo no tipificado puede hacer) sin renunciar a poder demostrar teoremas sólidos sobre el cálculo.
El cálculo lambda tiene aplicaciones en muchas áreas diferentes de matemáticas , filosofía , [4] lingüística , [5] [6] e informática . [7] [8] El cálculo Lambda ha jugado un papel importante en el desarrollo de la teoría de los lenguajes de programación . Los lenguajes de programación funcionales implementan el cálculo lambda. El cálculo lambda también es un tema de investigación actual en la teoría de categorías . [9]
El cálculo lambda fue introducido por el matemático Alonzo Church en la década de 1930 como parte de una investigación sobre los fundamentos de las matemáticas . [10] [c] Se demostró que el sistema original era lógicamente inconsistente en 1935 cuando Stephen Kleene y JB Rosser desarrollaron la paradoja de Kleene-Rosser . [11] [12]
Posteriormente, en 1936, Church aisló y publicó sólo la parte relevante para el cálculo, lo que ahora se llama cálculo lambda sin tipo. [13] En 1940, también introdujo un sistema computacionalmente más débil, pero lógicamente consistente, conocido como cálculo lambda simplemente tipado . [14]
Hasta la década de 1960, cuando se aclaró su relación con los lenguajes de programación, el cálculo lambda era sólo un formalismo. Gracias a las aplicaciones de Richard Montague y otros lingüistas en la semántica del lenguaje natural, el cálculo lambda ha comenzado a disfrutar de un lugar respetable tanto en la lingüística [15] como en la informática. [dieciséis]
Existe cierta incertidumbre sobre el motivo por el que Church utiliza la letra griega lambda (λ) como notación para la abstracción de funciones en el cálculo lambda, quizás en parte debido a explicaciones contradictorias del propio Church. Según Cardone y Hindley (2006):
Por cierto, ¿por qué Church eligió la notación “λ”? En [una carta inédita de 1964 a Harald Dickson] afirmó claramente que procedía de la notación " " utilizada para la abstracción de clases por Whitehead y Russell , modificando primero " " por " " para distinguir la abstracción de funciones de la abstracción de clases, y luego cambie “ ” a “λ” para facilitar la impresión.
Este origen también fue reportado en [Rosser, 1984, p.338]. Por otro lado, en sus últimos años Church dijo a dos investigadores que la elección fue más accidental: se necesitaba un símbolo y casualmente se eligió λ.
Dana Scott también ha abordado esta cuestión en varias conferencias públicas. [17] Scott relata que una vez le planteó una pregunta sobre el origen del símbolo lambda al ex alumno y yerno de Church, John W. Addison Jr., quien luego le escribió una postal a su suegro:
Estimado profesor Church,
Russell tenía el operador iota , Hilbert tenía el operador épsilon . ¿Por qué elegiste lambda como tu operador?
Según Scott, toda la respuesta de Church consistió en devolver la postal con la siguiente anotación: " eeny, meeny, miny, moe ".
Las funciones computables son un concepto fundamental dentro de la informática y las matemáticas. El cálculo lambda proporciona una semántica simple para el cálculo que es útil para estudiar formalmente las propiedades del cálculo. El cálculo lambda incorpora dos simplificaciones que simplifican su semántica.La primera simplificación es que el cálculo lambda trata funciones "anónimamente"; no les da nombres explícitos. Por ejemplo, la función
se puede reescribir de forma anónima como
(que se lee como " se asigna una tupla de xey a " ). [d] De manera similar, la función
se puede reescribir de forma anónima como
donde la entrada simplemente se asigna a sí misma. [d]
La segunda simplificación es que el cálculo lambda sólo utiliza funciones de una única entrada. Una función ordinaria que requiere dos entradas, por ejemplo la función, se puede transformar en una función equivalente que acepte una única entrada y, como salida, devuelva otra función, que a su vez acepte una única entrada. Por ejemplo,
se puede reelaborar en
Este método, conocido como curry , transforma una función que toma múltiples argumentos en una cadena de funciones, cada una con un solo argumento.
Función aplicación de la función a los argumentos (5, 2), produce de una vez
Considerando que la evaluación de la versión con curry requiere un paso más
para llegar al mismo resultado.
El cálculo lambda consta de un lenguaje de términos lambda , que están definidos por una determinada sintaxis formal, y un conjunto de reglas de transformación para manipular los términos lambda. Estas reglas de transformación pueden verse como una teoría ecuacional o como una definición operativa .
Como se describió anteriormente, al no tener nombres, todas las funciones del cálculo lambda son funciones anónimas. Solo aceptan una variable de entrada, por lo que el curry se utiliza para implementar funciones de varias variables.
La sintaxis del cálculo lambda define algunas expresiones como expresiones de cálculo lambda válidas y otras como inválidas, del mismo modo que algunas cadenas de caracteres son programas C válidos y otras no. Una expresión de cálculo lambda válida se denomina " término lambda ".
Las siguientes tres reglas dan una definición inductiva que se puede aplicar para construir todos los términos lambda sintácticamente válidos: [e]
Nada más es un término lambda. Es decir, un término lambda es válido si y sólo si puede obtenerse mediante la aplicación repetida de estas tres reglas. Por conveniencia, se pueden omitir algunos paréntesis al escribir un término lambda. Por ejemplo, los paréntesis más externos no suelen estar escritos. Consulte § Notación, a continuación, para obtener una descripción explícita de qué paréntesis son opcionales. También es común ampliar la sintaxis presentada aquí con operaciones adicionales, lo que permite dar sentido a términos como El enfoque de este artículo es el cálculo lambda puro sin extensiones, pero los términos lambda extendidos con operaciones aritméticas se utilizan con fines explicativos.
Una abstracción denota una § función anónima [g] que toma una única entrada x y devuelve t . Por ejemplo, es una abstracción que representa la función definida usando el término para t . El nombre es superfluo cuando se utiliza la abstracción. La sintaxis vincula la variable x en el término t . La definición de una función con una abstracción simplemente "establece" la función pero no la invoca.
Una aplicación representa la aplicación de una función t a una entrada s , es decir, representa el acto de llamar a la función t en la entrada s para producir .
Un término lambda puede referirse a una variable que no ha sido vinculada, como el término (que representa la definición de la función ). En este término, la variable y no ha sido definida y se considera una incógnita. La abstracción es un término sintácticamente válido y representa una función que agrega su entrada a la aún desconocida y .
Se pueden utilizar paréntesis, que podrían ser necesarios para eliminar la ambigüedad de los términos. Por ejemplo,
Los ejemplos 1 y 2 denotan términos diferentes, y sólo difieren en la ubicación de los paréntesis. Tienen diferentes significados: el ejemplo 1 es una definición de función, mientras que el ejemplo 2 es una aplicación de función. La variable lambda x es un marcador de posición en ambos ejemplos.
Aquí, el ejemplo 1 define una función , donde es una función anónima , con entrada ; mientras que en el ejemplo 2 , se aplica M a N, donde se aplica el término lambda a la entrada que es . Ambos ejemplos 1 y 2 se evaluarían como la función de identidad .
En el cálculo lambda, las funciones se consideran " valores de primera clase ", por lo que las funciones pueden usarse como entradas o devolverse como salidas de otras funciones.
Por ejemplo, el término lambda representa la función de identidad ,. Además, representa la función constante , la función que siempre devuelve , sin importar la entrada. Como ejemplo de una función que opera sobre funciones, la composición de la función se puede definir como .
Existen varias nociones de "equivalencia" y "reducción" que permiten que los términos lambda se "reduzcan" a términos lambda "equivalentes".
Una forma básica de equivalencia, definible en términos lambda, es la equivalencia alfa . Capta la intuición de que la elección particular de una variable ligada, en una abstracción, (normalmente) no importa. Por ejemplo, y son términos lambda equivalentes alfa y ambos representan la misma función (la función de identidad). Los términos y no son equivalentes alfa porque no están vinculados a una abstracción. En muchas presentaciones es habitual identificar términos lambda equivalentes alfa.
Las siguientes definiciones son necesarias para poder definir la reducción β:
Las variables libres [h] de un término son aquellas variables que no están ligadas a una abstracción. El conjunto de variables libres de una expresión se define inductivamente:
Por ejemplo, el término lambda que representa la identidad no tiene variables libres, pero la función tiene una única variable libre .
Supongamos que y son términos lambda y y son variables. La notación indica la sustitución de for in para evitar la captura . Esto se define de manera que:
Por ejemplo, y .
La condición de frescura (que requiere que no esté en las variables libres de ) es crucial para garantizar que la sustitución no cambie el significado de las funciones.
Por ejemplo, una sustitución que ignora la condición de frescura podría generar errores: . Esta sustitución errónea convertiría la función constante en la identidad .
En general, el incumplimiento de la condición de frescura se puede solucionar cambiando primero el nombre alfa, con una variable fresca adecuada. Por ejemplo, volviendo a nuestra noción correcta de sustitución, en la abstracción se puede cambiar el nombre con una nueva variable para obtener , y el significado de la función se conserva mediante la sustitución.
La regla de reducción β [b] establece que una aplicación de la forma se reduce al término . La notación se utiliza para indicar que β-se reduce a . Por ejemplo, para cada , . Esto demuestra que realmente es la identidad. De manera similar , lo que demuestra que es una función constante.
El cálculo lambda puede verse como una versión idealizada de un lenguaje de programación funcional, como Haskell o Standard ML . Bajo esta visión,La reducción β corresponde a un paso computacional. Este paso se puede repetir mediante reducciones β adicionales hasta que no queden más aplicaciones para reducir. En el cálculo lambda sin tipo, como se presenta aquí, es posible que este proceso de reducción no termine. Por ejemplo, considere el término . Aquí . Es decir, el término se reduce a sí mismo en una única reducción β y, por tanto, el proceso de reducción nunca terminará.
Otro aspecto del cálculo lambda sin tipo es que no distingue entre diferentes tipos de datos. Por ejemplo, puede ser conveniente escribir una función que sólo opere con números. Sin embargo, en el cálculo lambda sin tipo, no hay forma de evitar que una función se aplique a valores de verdad , cadenas u otros objetos no numéricos.
Las expresiones lambda se componen de:
El conjunto de expresiones lambda, Λ , se puede definir inductivamente :
Las instancias de la regla 2 se conocen como abstracciones y las instancias de la regla 3 se conocen como aplicaciones . [18]
Para mantener ordenada la notación de expresiones lambda, generalmente se aplican las siguientes convenciones:
Se dice que el operador de abstracción, λ, vincula su variable donde quiera que aparezca en el cuerpo de la abstracción. Se dice que las variables que caen dentro del alcance de una abstracción están ligadas . En una expresión λ x . M , la parte λ x a menudo se llama aglutinante , como un indicio de que la variable x se está vinculando al anteponer λ x a M . Todas las demás variables se llaman libres . Por ejemplo, en la expresión λ y . xxy , y es una variable ligada y x es una variable libre. Además, una variable está limitada por su abstracción más cercana. En el siguiente ejemplo, la aparición única de x en la expresión está limitada por la segunda lambda: λ x . y (λx . zx ) .
El conjunto de variables libres de una expresión lambda, M , se denota como FV( M ) y se define mediante recursividad en la estructura de los términos, de la siguiente manera:
Una expresión que no contiene variables libres se dice cerrada . Las expresiones lambda cerradas también se conocen como combinadores y son equivalentes a términos de lógica combinatoria .
El significado de las expresiones lambda se define por cómo se pueden reducir las expresiones. [22]
Hay tres tipos de reducción:
También hablamos de las equivalencias resultantes: dos expresiones son α-equivalentes , si pueden convertirse α-en la misma expresión. La equivalencia β y la equivalencia η se definen de manera similar.
El término redex , abreviatura de expresión reducible , se refiere a subtérminos que pueden reducirse mediante una de las reglas de reducción. Por ejemplo, (λ x . M ) N es un β-redex al expresar la sustitución de N por x en M . La expresión a la que se reduce una redex se llama reducta ; el reducto de (λ x . M ) N es M [ x := N ]. [b]
Si x no está libre en M , λ x . M x también es un η-redex, con un reducto de M .
La conversión α ( conversión alfa ), a veces conocida como cambio de nombre α, [23] permite cambiar los nombres de las variables vinculadas. Por ejemplo, α-conversión de λ x . x podría producir λ y . y . Los términos que difieren sólo por la conversión α se denominan equivalentes α . Con frecuencia, en los usos del cálculo lambda, los términos equivalentes α se consideran equivalentes.
Las reglas precisas para la conversión α no son del todo triviales. En primer lugar, cuando se convierte una abstracción en α, las únicas apariciones de variables a las que se les cambia el nombre son aquellas que están vinculadas a la misma abstracción. Por ejemplo, una conversión α de λ x .λ x . x podría resultar en λ y .λ x . x , pero no podría resultar en λ y .λ x . y . Este último tiene un significado diferente al original. Esto es análogo a la noción de programación de sombreado variable .
En segundo lugar, la conversión α no es posible si daría como resultado que una variable sea capturada por una abstracción diferente. Por ejemplo, si reemplazamos x con y en λ x .λ y . x , obtenemos λ y .λ y . y , que no es en absoluto lo mismo.
En lenguajes de programación con alcance estático, la conversión α se puede utilizar para simplificar la resolución de nombres al garantizar que ningún nombre de variable enmascare un nombre en un alcance contenedor (consulte Cambio de nombre α para simplificar la resolución de nombres ).
En la notación del índice de De Bruijn , dos términos equivalentes a α son sintácticamente idénticos.
La sustitución, escrita M [ x := N ], es el proceso de reemplazar todas las apariciones libres de la variable x en la expresión M con la expresión N. La sustitución en términos del cálculo lambda se define mediante recursividad en la estructura de los términos, de la siguiente manera (nota: x e y son solo variables, mientras que M y N son cualquier expresión lambda):
Para sustituir en una abstracción, a veces es necesario convertir la expresión en α. Por ejemplo, no es correcto que (λ x . y )[ y := x ] dé como resultado λ x . x , porque se suponía que la x sustituida era libre pero terminó estando vinculada. La sustitución correcta en este caso es λ z . x , hasta α-equivalencia. La sustitución se define de forma única hasta la α-equivalencia. Ver sustituciones para evitar capturas arriba
La reducción β ( reducción beta ) captura la idea de aplicación de funciones. La reducción β se define en términos de sustitución: la reducción β de (λ x . M ) N es M [ x := N ]. [b]
Por ejemplo, suponiendo alguna codificación de 2, 7, ×, tenemos la siguiente reducción β: (λ n . n × 2) 7 → 7 × 2.
Se puede considerar que la reducción β es la misma que el concepto de reducibilidad local en la deducción natural , a través del isomorfismo de Curry-Howard .
La reducción η ( reducción eta ) expresa la idea de extensionalidad , [24] que en este contexto es que dos funciones son iguales si y sólo si dan el mismo resultado para todos los argumentos. La reducción η convierte entre λ x . f x y f siempre que x no aparezca libre en f .
Se puede considerar que la reducción η es lo mismo que el concepto de completitud local en la deducción natural , a través del isomorfismo de Curry-Howard .
Para el cálculo lambda sin tipo, la reducción β como regla de reescritura no es ni fuertemente normalizadora ni débilmente normalizante .
Sin embargo, se puede demostrar que la reducción β es confluente cuando se avanza hacia la conversión α (es decir, consideramos que dos formas normales son iguales si es posible convertir una en la otra).
Por lo tanto, tanto los términos fuertemente normalizados como los términos débilmente normalizados tienen una forma normal única. Para términos fuertemente normalizados, se garantiza que cualquier estrategia de reducción producirá la forma normal, mientras que para términos débilmente normalizados, algunas estrategias de reducción pueden no lograr encontrarla.
El cálculo lambda básico se puede utilizar para modelar aritmética , booleanos, estructuras de datos y recursividad, como se ilustra en las siguientes subsecciones i , ii , iii y § iv .
Hay varias formas posibles de definir los números naturales en el cálculo lambda, pero con diferencia las más comunes son los números de Church , que se pueden definir de la siguiente manera:
etcétera. O usando la sintaxis alternativa presentada anteriormente en Notación :
Un número de Church es una función de orden superior : toma una función f de un solo argumento y devuelve otra función de un solo argumento. El número de Church n es una función que toma una función f como argumento y devuelve la enésima composición de f , es decir, la función f compuesta consigo misma n veces. Esto se denota por f ( n ) y de hecho es la n -ésima potencia de f (considerada como un operador); f (0) se define como la función identidad. Este tipo de composiciones repetidas (de una sola función f ) obedecen a las leyes de los exponentes , por lo que estos números pueden usarse para la aritmética. (En el cálculo lambda original de Church, se requería que el parámetro formal de una expresión lambda ocurriera al menos una vez en el cuerpo de la función, lo que hacía imposible la definición anterior de 0 ).
Una forma de pensar en el número de Church n , que suele ser útil al analizar programas, es como una instrucción "repetir n veces". Por ejemplo, utilizando las funciones PAIR y NIL definidas a continuación, se puede definir una función que construya una lista (vinculada) de n elementos, todos iguales a x , repitiendo "anteponer otro elemento x " n veces, comenzando desde una lista vacía. El término lambda es
Variando lo que se repite y variando a qué argumento se aplica esa función que se repite, se pueden lograr muchos efectos diferentes.
Podemos definir una función sucesora, que toma un número de Church n y devuelve n + 1 agregando otra aplicación de f , donde '(mf)x' significa que la función 'f' se aplica 'm' veces en 'x':
Debido a que la m -ésima composición de f compuesta con la n -ésima composición de f da la m + n -ésima composición de f , la suma se puede definir de la siguiente manera:
Se puede considerar PLUS como una función que toma dos números naturales como argumentos y devuelve un número natural; se puede comprobar que
y
son expresiones lambda equivalentes a β. Dado que se puede sumar m a un número n sumando 1 m veces, una definición alternativa es:
De manera similar, la multiplicación se puede definir como
Alternativamente
ya que multiplicar myn es lo mismo que repetir la función sumar n m veces y luego aplicarla a cero. La exponenciación tiene una interpretación bastante simple en los números de la Iglesia, a saber
La función predecesora definida por PRED n = n − 1 para un entero positivo n y PRED 0 = 0 es considerablemente más difícil. La formula
se puede validar mostrando inductivamente que si T denota (λ g .λ h . h ( g f )) , entonces T ( n ) (λ u . x ) = (λ h . h ( f ( n −1 ) ( x ))) para norte > 0 . A continuación se dan otras dos definiciones de PRED , una que usa condicionales y la otra que usa pares. Con la función predecesora, la resta es sencilla. Definiendo
SUB m n produce m − n cuando m > n y 0 en caso contrario.
Por convención, se utilizan las dos definiciones siguientes (conocidas como booleanos de Church) para los valores booleanos VERDADERO y FALSO :
Luego, con estos dos términos lambda, podemos definir algunos operadores lógicos (estas son sólo posibles formulaciones; otras expresiones podrían ser igualmente correctas):
Ahora podemos calcular algunas funciones lógicas, por ejemplo:
y vemos que AND TRUE FALSE equivale a FALSE .
Un predicado es una función que devuelve un valor booleano. El predicado más fundamental es ISZERO , que devuelve VERDADERO si su argumento es el número de la Iglesia 0 , pero FALSO si su argumento fuera cualquier otro número de la Iglesia:
El siguiente predicado prueba si el primer argumento es menor o igual que el segundo:
y dado que m = n , si LEQ m n y LEQ n m , es sencillo construir un predicado para la igualdad numérica.
La disponibilidad de predicados y la definición anterior de VERDADERO y FALSO hacen que sea conveniente escribir expresiones "si-entonces-si no" en cálculo lambda. Por ejemplo, la función predecesora se puede definir como:
lo cual se puede verificar mostrando inductivamente que n (λ g .λ k .ISZERO ( g 1) k (PLUS ( g k ) 1)) (λ v .0) es la función sumar n − 1 para n > 0.
Un par (2-tupla) se puede definir en términos de VERDADERO y FALSO , utilizando la codificación de Church para pares . Por ejemplo, PAIR encapsula el par ( x , y ), FIRST devuelve el primer elemento del par y SECOND devuelve el segundo.
Una lista vinculada se puede definir como NIL para la lista vacía o como el PAR de un elemento y una lista más pequeña. El predicado NULL prueba el valor NIL . (Alternativamente, con NIL := FALSE , la construcción l (λ h .λ t .λ z .deal_with_head_ h _and_tail_ t ) (deal_with_nil) obvia la necesidad de una prueba NULL explícita).
Como ejemplo del uso de pares, la función de desplazamiento e incremento que asigna ( m , n ) a ( n , n + 1) se puede definir como
lo que nos permite dar quizás la versión más transparente de la función predecesora:
Existe una cantidad considerable de modismos de programación para el cálculo lambda. Muchos de estos se desarrollaron originalmente en el contexto del uso del cálculo lambda como base para la semántica del lenguaje de programación , utilizando efectivamente el cálculo lambda como un lenguaje de programación de bajo nivel . Debido a que varios lenguajes de programación incluyen el cálculo lambda (o algo muy similar) como un fragmento, estas técnicas también se utilizan en la programación práctica, pero luego pueden percibirse como oscuras o extrañas.
En el cálculo lambda, una biblioteca tomaría la forma de una colección de funciones previamente definidas, que como términos lambda son simplemente constantes particulares. El cálculo lambda puro no tiene un concepto de constantes con nombre ya que todos los términos lambda atómicos son variables, pero se puede emular el tener constantes con nombre reservando una variable como nombre de la constante, usando la abstracción para vincular esa variable en el cuerpo principal. y aplicar esa abstracción a la definición prevista. Por lo tanto, para usar f para significar N (algún término lambda explícito) en M (otro término lambda, el "programa principal"), se puede decir
Los autores suelen introducir azúcar sintáctico , como let , [k] para permitir escribir lo anterior en el orden más intuitivo.
Al encadenar tales definiciones, se puede escribir un "programa" de cálculo lambda como cero o más definiciones de funciones, seguidas de un término lambda que utilice aquellas funciones que constituyen el cuerpo principal del programa.
Una restricción notable de este let es que el nombre f no esté definido en N , para que N esté fuera del alcance del enlace de abstracción f ; esto significa que una definición de función recursiva no se puede utilizar como N con let . La construcción letrec [l] permitiría escribir definiciones de funciones recursivas.
La recursividad es la definición de una función utilizando la función misma. Una definición que se contiene a sí misma dentro de sí misma, por valor, conduce a que todo el valor sea de tamaño infinito. Otras notaciones que soportan la recursividad superan esto de forma nativa haciendo referencia a la definición de la función por su nombre . El cálculo lambda no puede expresar esto: todas las funciones son anónimas en el cálculo lambda, por lo que no podemos referirnos por nombre a un valor que aún no se ha definido, dentro del término lambda que define ese mismo valor. Sin embargo, una expresión lambda puede recibirse a sí misma como su propio argumento, por ejemplo en (λ x . x x ) E . Aquí E debería ser una abstracción, aplicando su parámetro a un valor para expresar la recursividad.
Considere la función factorial F( n ) definida recursivamente por
En la expresión lambda que representa esta función, se asumirá que un parámetro (normalmente el primero) recibe la expresión lambda como valor, de modo que llamarlo (aplicarlo a un argumento) equivaldrá a recursividad. Por lo tanto, para lograr la recursividad, el argumento que pretende ser autorreferencial (llamado r aquí) siempre debe pasarse a sí mismo dentro del cuerpo de la función, en un punto de llamada:
La autoaplicación logra la replicación aquí, pasando la expresión lambda de la función a la siguiente invocación como un valor de argumento, haciéndola disponible para ser referenciada y llamada allí.
Esto lo resuelve pero requiere reescribir cada llamada recursiva como una autoaplicación. Nos gustaría tener una solución genérica, sin necesidad de reescribirla:
Dado un término lambda con un primer argumento que representa una llamada recursiva (por ejemplo, G aquí), el combinador de punto fijo FIX devolverá una expresión lambda autorreplicante que representa la función recursiva (aquí, F ). No es necesario pasar la función explícitamente a sí misma en ningún momento, ya que la autorreplicación se organiza de antemano, cuando se crea, para que se realice cada vez que se llama. De este modo, la expresión lambda original (FIX G) se recrea dentro de sí misma, en el punto de llamada, logrando la autorreferencia .
De hecho, existen muchas definiciones posibles para este operador FIX , siendo la más sencilla:
En el cálculo lambda, Y g es un punto fijo de g , ya que se expande a:
Ahora, para realizar nuestra llamada recursiva a la función factorial, simplemente llamaríamos a ( Y G) n , donde n es el número cuyo factorial estamos calculando. Dado n = 4, por ejemplo, esto da:
Cada función definida recursivamente puede verse como un punto fijo de alguna función adecuadamente definida que cierra la llamada recursiva con un argumento adicional y, por lo tanto, usando Y , cada función definida recursivamente puede expresarse como una expresión lambda. En particular, ahora podemos definir claramente los predicados de resta, multiplicación y comparación de números naturales de forma recursiva.
Ciertos términos tienen nombres comúnmente aceptados: [27] [28] [29]
I es la función de identidad. SK y BCKW forman sistemas de cálculo combinador completos que pueden expresar cualquier término lambda; consulte la siguiente sección. Ω es UU , el término más pequeño que no tiene forma normal. YI es otro de esos términos. Y es estándar y se define arriba, y también se puede definir como Y = BU(CBU) , de modo que Y g=g( Y g) . VERDADERO y FALSO definidos anteriormente se abrevian comúnmentecomo T y F.
Si N es un término lambda sin abstracción, pero que posiblemente contiene constantes con nombre ( combinadores ), entonces existe un término lambda T ( x , N ) que es equivalente a λ x . N pero carece de abstracción (excepto como parte de las constantes nombradas, si éstas se consideran no atómicas). Esto también puede verse como variables anonimizadoras, ya que T ( x , N ) elimina todas las apariciones de x de N , al tiempo que permite sustituir los valores de los argumentos en las posiciones donde N contiene una x . La función de conversión T se puede definir mediante:
En cualquier caso, un término de la forma T ( x , N ) P se puede reducir haciendo que el combinador inicial I , K o S tome el argumento P , tal como lo haría la reducción β de (λ x . N ) P. Devuelvo ese argumento. K descarta el argumento, tal como lo haría (λ x . N ) si x no tiene una ocurrencia libre en N . S pasa el argumento a ambos subtérminos de la aplicación y luego aplica el resultado del primero al resultado del segundo.
Los combinadores B y C son similares a S , pero pasan el argumento a un solo subtérmino de una aplicación ( B al subtérmino "argumento" y C al subtérmino "función"), guardando así un K posterior si no ocurre de x en un subtérmino. En comparación con B y C , el combinador S en realidad combina dos funcionalidades: reorganizar argumentos y duplicar un argumento para que pueda usarse en dos lugares. El combinador W hace solo lo último, produciendo el sistema B, C, K, W como una alternativa al cálculo del combinador SKI .
Un cálculo lambda escrito es un formalismo escrito que utiliza el símbolo lambda ( ) para denotar la abstracción de una función anónima. En este contexto, los tipos suelen ser objetos de naturaleza sintáctica que se asignan a términos lambda; la naturaleza exacta de un tipo depende del cálculo considerado (consulte Tipos de cálculos lambda tipificados ). Desde cierto punto de vista, los cálculos lambda tipificados pueden verse como refinamientos del cálculo lambda no tipificado, pero desde otro punto de vista, también pueden considerarse la teoría más fundamental y el cálculo lambda no tipificado como un caso especial con un solo tipo. [30]
Los cálculos lambda tipificados son lenguajes de programación fundamentales y son la base de los lenguajes de programación funcionales tipificados como ML y Haskell y, más indirectamente, de los lenguajes de programación imperativos tipificados . Los cálculos lambda tipificados juegan un papel importante en el diseño de sistemas de tipos para lenguajes de programación; aquí la tipificación generalmente captura propiedades deseables del programa, por ejemplo, el programa no causará una violación de acceso a la memoria.
Los cálculos lambda tipificados están estrechamente relacionados con la lógica matemática y la teoría de la prueba a través del isomorfismo de Curry-Howard y pueden considerarse como el lenguaje interno de clases de categorías ; por ejemplo, el cálculo lambda simplemente tipificado es el lenguaje de las categorías cartesianas cerradas (CCC).
Si un término se normaliza o no, y cuánto trabajo se debe hacer para normalizarlo, si lo es, depende en gran medida de la estrategia de reducción utilizada. Las estrategias comunes de reducción del cálculo lambda incluyen: [31] [32] [33]
Las estrategias de reducción débil no se reducen bajo abstracciones lambda:
Las estrategias para compartir reducen los cálculos que son "iguales" en paralelo:
No existe ningún algoritmo que tome como entrada dos expresiones lambda y genere VERDADERO o FALSO dependiendo de si una expresión se reduce a la otra. [13] Más precisamente, ninguna función computable puede decidir la cuestión. Este fue históricamente el primer problema para el cual se pudo demostrar la indecidibilidad. Como es habitual en una prueba de este tipo, computable significa computable mediante cualquier modelo de cálculo que sea completo de Turing . De hecho, la computabilidad puede definirse mediante el cálculo lambda: una función F : N → N de números naturales es una función computable si y sólo si existe una expresión lambda f tal que para cada par de x , y en N , F ( x )= y si y sólo si f x = β y , donde x e y son los números de Church correspondientes a x e y , respectivamente y = β significa equivalencia con reducción β. Consulte la tesis de Church-Turing para conocer otros enfoques para definir la computabilidad y su equivalencia.
La prueba de incomputabilidad de Church primero reduce el problema a determinar si una expresión lambda dada tiene una forma normal . Luego supone que este predicado es computable y, por tanto, puede expresarse en cálculo lambda. Basándose en trabajos anteriores de Kleene y construyendo una numeración de Gödel para expresiones lambda, construye una expresión lambda e que sigue de cerca la prueba del primer teorema de incompletitud de Gödel . Si e se aplica a su propio número de Gödel, se produce una contradicción.
La noción de complejidad computacional para el cálculo lambda es un poco complicada, porque el costo de una reducción β puede variar dependiendo de cómo se implemente. [34] Para ser precisos, uno debe encontrar de alguna manera la ubicación de todas las apariciones de la variable ligada V en la expresión E , lo que implica un costo de tiempo, o uno debe realizar un seguimiento de las ubicaciones de las variables libres de alguna manera, lo que implica un costo del espacio. Una búsqueda ingenua de las ubicaciones de V en E es O ( n ) en la longitud n de E . Las cadenas de directores fueron un enfoque inicial que cambió este costo de tiempo por un uso de espacio cuadrático. [35] De manera más general, esto ha llevado al estudio de sistemas que utilizan sustitución explícita .
En 2014, se demostró que el número de pasos de reducción β tomados por la reducción de orden normal para reducir un término es un modelo de costo de tiempo razonable , es decir, la reducción se puede simular en una máquina de Turing en un tiempo polinomialmente proporcional al número de pasos. [36] Este era un problema abierto desde hacía mucho tiempo, debido a la explosión de tamaño , la existencia de términos lambda que crecen exponencialmente en tamaño para cada reducción β. El resultado soluciona esto trabajando con una representación compartida compacta. El resultado deja claro que la cantidad de espacio necesaria para evaluar un término lambda no es proporcional al tamaño del término durante la reducción. Actualmente no se sabe cuál sería una buena medida de la complejidad del espacio. [37]
Un modelo irrazonable no significa necesariamente ineficiente. La reducción óptima reduce todos los cálculos con la misma etiqueta en un solo paso, evitando el trabajo duplicado, pero el número de pasos paralelos de reducción β para reducir un término dado a su forma normal es aproximadamente lineal en el tamaño del término. Esto es demasiado pequeño para ser una medida de costo razonable, ya que cualquier máquina de Turing puede codificarse en el cálculo lambda en un tamaño linealmente proporcional al tamaño de la máquina de Turing. El verdadero costo de reducir los términos lambda no se debe a la reducción β per se, sino al manejo de la duplicación de las redex durante la reducción β. [38] No se sabe si las implementaciones de reducción óptima son razonables cuando se miden con respecto a un modelo de costo razonable, como el número de pasos más externos a la izquierda hasta la forma normal, pero se ha demostrado para fragmentos del cálculo lambda que la reducción óptima El algoritmo es eficiente y tiene como máximo una sobrecarga cuadrática en comparación con el extremo izquierdo. [37] Además, la implementación del prototipo BOHM de reducción óptima superó a Caml Light y Haskell en términos lambda puros. [38]
Como lo señala el artículo de Peter Landin de 1965 "Una correspondencia entre ALGOL 60 y la notación Lambda de Church", [39] los lenguajes de programación procedimental secuencial pueden entenderse en términos del cálculo lambda, que proporciona los mecanismos básicos para la abstracción procedimental y el procedimiento. (subprograma) aplicación.
Por ejemplo, en Python la función "cuadrado" se puede expresar como una expresión lambda de la siguiente manera:
( lambda x : x ** 2 )
El ejemplo anterior es una expresión que se evalúa como una función de primera clase. El símbolo lambda
crea una función anónima, dada una lista de nombres de parámetros x
(un solo argumento en este caso) y una expresión que se evalúa como el cuerpo de la función x**2
. Las funciones anónimas a veces se denominan expresiones lambda.
Por ejemplo, Pascal y muchos otros lenguajes imperativos han apoyado durante mucho tiempo el paso de subprogramas como argumentos a otros subprogramas a través del mecanismo de punteros de función . Sin embargo, los punteros a funciones no son una condición suficiente para que las funciones sean tipos de datos de primera clase , porque una función es un tipo de datos de primera clase si y sólo si se pueden crear nuevas instancias de la función en tiempo de ejecución. Y esta creación de funciones en tiempo de ejecución está soportada en Smalltalk , JavaScript y Wolfram Language , y más recientemente en Scala , Eiffel ("agentes"), C# ("delegados") y C++11 , entre otros.
La propiedad de Church-Rosser del cálculo lambda significa que la evaluación (reducción β) se puede realizar en cualquier orden , incluso en paralelo. Esto significa que varias estrategias de evaluación no deterministas son relevantes. Sin embargo, el cálculo lambda no ofrece ninguna construcción explícita para el paralelismo . Se pueden agregar construcciones como Futuros al cálculo lambda. Se han desarrollado otros cálculos de procesos para describir la comunicación y la concurrencia.
El hecho de que los términos del cálculo lambda actúen como funciones sobre otros términos del cálculo lambda, e incluso sobre ellos mismos, generó dudas sobre la semántica del cálculo lambda. ¿Se podría asignar un significado sensato a los términos del cálculo lambda? La semántica natural era encontrar un conjunto D isomorfo al espacio funcional D → D , de funciones sobre sí mismo. Sin embargo, no puede existir tal D no trivial , por restricciones de cardinalidad porque el conjunto de todas las funciones de D a D tiene mayor cardinalidad que D , a menos que D sea un conjunto singleton .
En la década de 1970, Dana Scott demostró que si sólo se consideraban funciones continuas , se podía encontrar un conjunto o dominio D con la propiedad requerida, proporcionando así un modelo para el cálculo lambda. [40]
Este trabajo también formó la base para la semántica denotacional de los lenguajes de programación.
Estas extensiones están en el cubo lambda :
Estos sistemas formales son extensiones del cálculo lambda que no están en el cubo lambda:
Estos sistemas formales son variaciones del cálculo lambda:
Estos sistemas formales están relacionados con el cálculo lambda:
Algunas partes de este artículo se basan en material de FOLDOC , utilizado con autorización .
Algunos otros sistemas usan yuxtaposición para referirse a aplicación, por lo que 'ab' significa 'a@b'. Esto está bien excepto que requiere que las variables tengan longitud uno para que sepamos que 'ab' son dos variables yuxtapuestas, no una variable de longitud 2. Pero queremos que etiquetas como 'primeraVariable' signifiquen una sola variable, por lo que no podemos usar esta convención de yuxtaposición.