cálculo lambda

Sistema matemático-lógico basado en funciones.

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]

1. ${\textstyle x}$: Una variable es un carácter o cadena que representa un parámetro.
2. ${\textstyle (\lambda x.M)}$: Una abstracción lambda es una definición de función, que toma como entrada la variable vinculada (entre λ y el punctum/dot . ) y devuelve el cuerpo . ${\displaystyle x}$ ${\textstyle M}$
3. ${\textstyle (M\ N)}$: Una aplicación, que aplica una función a un argumento . Ambos y son términos lambda. ${\textstyle M}$ ${\textstyle N}$ ${\textstyle M}$ ${\textstyle N}$

Las operaciones de reducción incluyen:

• ${\textstyle (\lambda x.M[x])\rightarrow (\lambda y.M[y])}$: conversión α, que cambia el nombre de las variables vinculadas en la expresión. Se utiliza para evitar colisiones de nombres .
• ${\textstyle ((\lambda x.M)\ N)\rightarrow (M[x:=N])}$: β-reducción, ^[b] reemplazando las variables vinculadas con la expresión del argumento en el cuerpo de la abstracción.

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.

Explicación y aplicaciones.

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]

Historia

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]

Origen del símbolo λ

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, tal vez 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. ${\displaystyle {\hat {x}}}$ ${\displaystyle {\hat {x}}}$ ${\displaystyle \land x}$ ${\displaystyle \land }$

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 ".

descripción informal

Motivación

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

${\displaystyle \operatorname {square\_sum} (x,y)=x^{2}+y^{2}}$

se puede reescribir de forma anónima como

${\displaystyle (x,y)\mapsto x^{2}+y^{2}}$

(que se lee como "se asigna una tupla de xey a " ) . ^[d] De manera similar, la función ${\textstyle x^{2}+y^{2}}$

${\displaystyle \operatorname {id} (x)=x}$

se puede reescribir de forma anónima como

${\displaystyle x\mapsto x}$

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, ${\textstyle \operatorname {square\_sum} }$

${\displaystyle (x,y)\mapsto x^{2}+y^{2}}$

se puede reelaborar en

${\displaystyle x\mapsto (y\mapsto x^{2}+y^{2})}$

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 ${\textstyle \operatorname {square\_sum} }$

${\textstyle ((x,y)\mapsto x^{2}+y^{2})(5,2)}$

${\textstyle =5^{2}+2^{2}}$

${\textstyle =29}$,

Considerando que la evaluación de la versión con curry requiere un paso más

${\textstyle {\Bigl (}{\bigl (}x\mapsto (y\mapsto x^{2}+y^{2}){\bigr )}(5){\Bigr )}(2)}$

${\textstyle =(y\mapsto 5^{2}+y^{2})(2)}$// la definición de se ha utilizado en la expresión interna. Esto es como la reducción β. ${\displaystyle x}$ ${\displaystyle 5}$

${\textstyle =5^{2}+2^{2}}$// la definición de se ha utilizado con . De nuevo, similar a la reducción β. ${\displaystyle y}$ ${\displaystyle 2}$

${\textstyle =29}$

para llegar al mismo resultado.

El cálculo lambda

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 nombre, 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.

términos lambda

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]

• La variable x es en sí misma un término lambda válido.
• si t es un término lambda y x es una variable, entonces ^[f] es un término lambda (llamado abstracción ); ${\displaystyle (\lambda x.t)}$
• si t y s son términos lambda, entonces es un término lambda (llamado aplicación ). ${\displaystyle (t}$  ${\displaystyle s)}$

Nada más es un término lambda. Por tanto, un término lambda es válido si y sólo si puede obtenerse mediante la aplicación repetida de estas tres reglas. Sin embargo, se pueden omitir algunos paréntesis según ciertas reglas. Por ejemplo, los paréntesis más externos no suelen estar escritos. Consulte § Notación, a continuación, para saber cuándo incluir paréntesis.

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 de la función que utiliza el término para t . El nombre es superfluo cuando se utiliza la abstracción. une 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. Consulte la § Notación a continuación para conocer el uso de paréntesis. ${\displaystyle \lambda x.t}$ ${\displaystyle \lambda x.(x^{2}+2)}$ ${\displaystyle f(x)=x^{2}+2}$ ${\displaystyle x^{2}+2}$ ${\displaystyle f(x)}$ ${\displaystyle (\lambda x.t)}$

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 . ${\displaystyle t}$  ${\displaystyle s}$ ${\displaystyle t(s)}$

No existe ningún concepto en el cálculo lambda de declaración de variables. En una definición como (es decir ), en el cálculo lambda y es una variable que aún no está definida. La abstracción es sintácticamente válida y representa una función que agrega su entrada al aún desconocido y . ${\displaystyle \lambda x.(x+y)}$ ${\displaystyle f(x)=(x+y)}$ ${\displaystyle \lambda x.(x+y)}$

Se pueden utilizar paréntesis, que podrían ser necesarios para eliminar la ambigüedad de los términos. Por ejemplo,

1. ${\displaystyle \lambda x.((\lambda x.x)x)}$que es de forma  , una abstracción, y ${\displaystyle \lambda x.B}$
2. ${\displaystyle (\lambda x.(\lambda x.x))}$ ${\displaystyle x}$que es de forma  : una aplicación. ${\displaystyle M}$  ${\displaystyle N}$

Los ejemplos 1 y 2 denotan términos diferentes; excepto por el alcance de los paréntesis, serían los mismos. Pero 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 . ${\displaystyle \lambda x.B}$ ${\displaystyle B}$ ${\displaystyle (\lambda x.x)x}$ ${\displaystyle (\lambda x.x)}$ ${\displaystyle x}$ ${\displaystyle M}$  ${\displaystyle N}$ ${\displaystyle M}$ ${\displaystyle (\lambda x.(\lambda x.x))}$ ${\displaystyle N}$ ${\displaystyle x}$ ${\displaystyle \lambda x.x}$

Funciones que operan sobre funciones.

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 . ${\displaystyle \lambda x.x}$ ${\displaystyle x\mapsto x}$ ${\displaystyle \lambda x.y}$ ${\displaystyle x\mapsto y}$ ${\displaystyle y}$ ${\displaystyle \lambda f.\lambda g.\lambda x.(f(gx))}$

Existen varias nociones de "equivalencia" y "reducción" que permiten que los términos lambda se "reduzcan" a términos lambda "equivalentes".

equivalencia alfa

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. ${\displaystyle \lambda x.x}$ ${\displaystyle \lambda y.y}$ ${\displaystyle x}$ ${\displaystyle y}$

Las siguientes definiciones son necesarias para poder definir la reducción β:

variables libres

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:

• Las variables libres de son solo ${\displaystyle x}$ ${\displaystyle x}$
• El conjunto de variables libres de es el conjunto de variables libres de , pero sin eliminar ${\displaystyle \lambda x.t}$ ${\displaystyle t}$ ${\displaystyle x}$
• El conjunto de variables libres de es la unión del conjunto de variables libres de y el conjunto de variables libres de . ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$

Por ejemplo, el término lambda que representa la identidad no tiene variables libres, pero la función tiene una única variable libre . ${\displaystyle \lambda x.x}$ ${\displaystyle \lambda x.y}$ ${\displaystyle x}$ ${\displaystyle y}$

Sustituciones que evitan la captura

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: ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle t[x:=r]}$ ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle t}$

• ${\displaystyle x[x:=r]=r}$ ; con sustituido por , se convierte ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle r}$
• ${\displaystyle y[x:=r]=y}$si  ; con sustituido por , (que no es ) permanece ${\displaystyle x\neq y}$ ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$
• ${\displaystyle (t}$ ${\displaystyle s)[x:=r]=(t[x:=r])(s[x:=r])}$ ; la sustitución se distribuye a ambos lados de una aplicación
• ${\displaystyle (\lambda x.t)[x:=r]=\lambda x.t}$ ; una variable ligada por una abstracción no está sujeta a sustitución; sustituir dicha variable deja la abstracción sin cambios
• ${\displaystyle (\lambda y.t)[x:=r]=\lambda y.(t[x:=r])}$si y no aparece entre las variables libres de ( se dice que es " fresco " para ); la sustitución de una variable que no está vinculada por una abstracción se produce en el cuerpo de la abstracción, siempre que la variable abstraída sea "nueva" para el término de sustitución . ${\displaystyle x\neq y}$ ${\displaystyle y}$ ${\displaystyle r}$ ${\displaystyle y}$ ${\displaystyle r}$ ${\displaystyle y}$ ${\displaystyle r}$

Por ejemplo, y . ${\displaystyle (\lambda x.x)[y:=y]=\lambda x.(x[y:=y])=\lambda x.x}$ ${\displaystyle ((\lambda x.y)x)[x:=y]=((\lambda x.y)[x:=y])(x[x:=y])=(\lambda x.y)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. ${\displaystyle y}$ ${\displaystyle r}$

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 . ${\displaystyle (\lambda x.y)[y:=x]=\lambda x.(y[y:=x])=\lambda x.x}$ ${\displaystyle \lambda x.y}$ ${\displaystyle \lambda x.x}$

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. ${\displaystyle (\lambda x.y)[y:=x]}$ ${\displaystyle z}$ ${\displaystyle (\lambda z.y)[y:=x]=\lambda z.(y[y:=x])=\lambda z.x}$

reducció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. ${\displaystyle (\lambda x.t)s}$ ${\displaystyle t[x:=s]}$ ${\displaystyle (\lambda x.t)s\to t[x:=s]}$ ${\displaystyle (\lambda x.t)s}$ ${\displaystyle t[x:=s]}$ ${\displaystyle s}$ ${\displaystyle (\lambda x.x)s\to x[x:=s]=s}$ ${\displaystyle \lambda x.x}$ ${\displaystyle (\lambda x.y)s\to y[x:=s]=y}$ ${\displaystyle \lambda x.y}$

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á. ${\displaystyle \Omega =(\lambda x.xx)(\lambda x.xx)}$ ${\displaystyle (\lambda x.xx)(\lambda x.xx)\to (xx)[x:=\lambda x.xx]=(x[x:=\lambda x.xx])(x[x:=\lambda x.xx])=(\lambda x.xx)(\lambda x.xx)}$

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.

Definicion formal

Definición

Las expresiones lambda se componen de:

• variables v ₁ , v ₂ , ...;
• los símbolos de abstracción λ (lambda) y . (punto);
• paréntesis ().

El conjunto de expresiones lambda, Λ , se puede definir inductivamente :

1. Si x es una variable, entonces x ∈ Λ.
2. Si x es una variable y M ∈ Λ, entonces (λ x . M ) ∈ Λ.
3. Si M , N ∈ Λ, entonces ( MN ) ∈ Λ.

Las instancias de la regla 2 se conocen como abstracciones y las instancias de la regla 3 se conocen como aplicaciones . ^{[18] [19]}

Notación

Para mantener ordenada la notación de expresiones lambda, generalmente se aplican las siguientes convenciones:

• Los paréntesis más externos se eliminan: M N en lugar de ( M N ).
• Se supone que las aplicaciones son asociativas por la izquierda: M N P puede escribirse en lugar de (( M N ) P ). ^[20]
• Cuando todas las variables sean de una sola letra, se podrá omitir el espacio en las aplicaciones: MNP en lugar de M N P . ^[21]
• El cuerpo de una abstracción se extiende lo más a la derecha posible : λ x . MN significa λ x .( MN ) y no (λ x . M ) N .
• Se contrae una secuencia de abstracciones: λ x .λ y .λ z . N se abrevia como λ xyz . norte . ^{[22] [20]}

Variables libres y ligadas

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:

1. FV( x ) = { x }, donde x es una variable.
2. FV(λ x . M ) = FV( M ) \ { x }. ^[i]
3. FV( MN ) = FV( M ) ∪ FV( N ). ^[j]

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 .

Reducción

El significado de las expresiones lambda se define por cómo se pueden reducir las expresiones. ^[23]

Hay tres tipos de reducción:

• Conversión α : cambio de variables ligadas;
• β-reducción : aplicar funciones a sus argumentos;
• η-reducción : que captura una noción de extensionalidad.

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 .

conversión α

La conversión α ( conversión alfa ), a veces conocida como cambio de nombre α, ^[24] 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.

Sustitución

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):

x [ x  := norte ] = norte

y [ x  := N ] = y , si x ≠ y

( M ₁ M ₂ )[ x  := N ] = M ₁ [ x  := N ] M ₂ [ x  := N ]

(λ x . M )[ x  := N ] = λ x . METRO

(λ y . M )[ x  := N ] = λ y .( M [ x  := N ]), si x ≠ y y y ∉ FV( N ) Véase arriba para el FV

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

reducción β

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 .

η-reducción

La reducción η ( reducción eta ) expresa la idea de extensionalidad , ^[25] 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 .

Formas normales y confluencia.

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.

Codificación de tipos de datos

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 .

Aritmética en cálculo lambda

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:

0 := λ f .λ x . X

1 := λ f .λ x . f x

2 := λ f .λ x . f ( f x )

3 := λ f .λ x . f ( f ( f x ))

etcétera. O usando la sintaxis alternativa presentada anteriormente en Notación :

0 := λfx . X

1 := λfx . f x

2 := λfx . f ( f x )

3 := λfx . f ( f ( f x ))

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 ⁽⁰⁾ 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

λ norte .λ x . n (PAR x ) NULO

Al variar lo que se repite y al argumento al que 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':

SUCC := λ n .λ f .λ x . f ( n f 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:

MÁS := λ m .λ n .λ f .λ x . m f ( n f x )

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

MÁS 2 3

y

5

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:

MÁS := λ m .λ n . m SUCC norte  ^[26]

De manera similar, la multiplicación se puede definir como

MULT := λ m .λ n .λ f . m ( nf ) ^[22 ]

Alternativamente

MULT := λ m .λ n . metro (MÁS norte ) 0

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

Prisionero de guerra := λ b .λ e . e b ^[1]

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

PRED := λ n .λ f .λ x . norte (λ g .λ h . h ( g f )) (λ u . x ) (λ u . u )

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 := λ metro .λ norte . norte PRED m ,

SUB m n produce m − n cuando m > n y 0 en caso contrario.

Lógica y predicados

Por convención, se utilizan las dos definiciones siguientes (conocidas como booleanos de Church) para los valores booleanos VERDADERO y FALSO :

VERDADERO := λ x .λ y . X

FALSO := λ x .λ y . y

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):

Y := λ p .λ q . pq p ​

O := λ p .λ q . p p q

NO := λ p . FALSO VERDADERO

ENTONCES:= λ p .λ a .λ b . pag ​ ​

Ahora podemos calcular algunas funciones lógicas, por ejemplo:

Y VERDADERO FALSO

≡ (λ p .λ q . p q p ) VERDADERO FALSO → _β VERDADERO FALSO VERDADERO

≡ (λ x .λ y . x ) FALSO VERDADERO → _β FALSO

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:

ES CERO := λ norte . n (λ x .FALSO) VERDADERO

El siguiente predicado prueba si el primer argumento es menor o igual que el segundo:

LEQ := λ m .λ n .ISZERO (SUB m n ) ,

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:

PRED := λ norte . n (λ g .λ k .ISZERO ( g 1) k (MÁS ( g k ) 1)) (λ v .0) 0

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.

Pares

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.

PAR := λ x .λ y .λ f . f x y

PRIMERO := λ p . VERDADERO​

SEGUNDO := λ p . FALSO​

NULO := λ x .VERDADERO

NULO := λ p . p (λ x .λ y .FALSO)

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

Φ := λ x .PAR (SEGUNDO x ) (SUCC (SEGUNDO x ))

lo que nos permite dar quizás la versión más transparente de la función predecesora:

PRED := λ n .PRIMERO ( n Φ (PAR 0 0)).

Técnicas de programación adicionales

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.

Constantes nombradas

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 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

(λ f . M ) norte

Los autores suelen introducir azúcar sintáctico , como let , ^[k] para permitir escribir lo anterior en el orden más intuitivo.

sea ​​f = N en M

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.

Recursión y puntos fijos.

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

F( n ) = 1, si n = 0; de lo contrario norte × F( norte − 1) .

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 pretendido como autorreferencial (llamado r aquí) siempre debe pasarse a sí mismo dentro del cuerpo de la función, en un punto de llamada:

GRAMO := λ r . λ n .(1, si n = 0; en caso contrario n × ( r r ( n −1)))

con  r r x = F x = G r x  para mantener, entonces  r = G  y

F := GG = (λ x . x x ) G

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:

GRAMO := λ r . λ n .(1, si n = 0; en caso contrario n × ( r ( n −1)))

con  r x = F x = G r x  para mantener, entonces  r = G r =: FIX G  y

F := FIX G  donde  FIX g  := ( r donde r = g r ) = g (FIX g )

de modo que  FIX G = G (FIX G) = (λ n .(1, si n = 0; en caso contrario n × ((FIX G) ( n −1))))

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:

Y  := λ g .(λ x . g ( x x )) (λ x . g ( x x ))

En el cálculo lambda, Y g   es un punto fijo de g , ya que se expande a:

Yg ​

(λ h .(λ x . h ( x x )) (λ x . h ( x x ))) g

(λ x . g ( x x )) (λ x . g ( x x ))

g ((λ x . g ( x x )) (λ x . g ( x x )))

gramo ( Y gramo )

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:

( YG ) 4

G ( YG ) 4

(λ r .λ n .(1, si n = 0; en caso contrario n × ( r ( n −1)))) ( Y G) 4

(λ n .(1, si n = 0; en caso contrario n × (( Y G) ( n −1)))) 4

1, si 4 = 0; más 4 × (( Y G) (4−1))

4 × (GRAMO ( Y GRAMO) (4−1))

4 × ((λ n .(1, si n = 0; de lo contrario n × (( Y G) ( n −1)))) (4−1))

4 × (1, si 3 = 0; en caso contrario 3 × (( Y G) (3−1)))

4 × (3 × (G ( Y G) (3−1)))

4 × (3 × ((λ n .(1, si n = 0; de lo contrario n × (( Y G) ( n −1)))) (3−1)))

4 × (3 × (1, si 2 = 0; en caso contrario 2 × (( Y G) (2−1))))

4 × (3 × (2 × (G ( Y G) (2−1))))

4 × (3 × (2 × ((λ n .(1, si n = 0; de lo contrario n × (( Y G) ( n −1)))) (2−1))))

4 × (3 × (2 × (1, si 1 = 0; en caso contrario 1 × (( Y G) (1−1)))))

4 × (3 × (2 × (1 × (G ( Y G) (1−1)))))

4 × (3 × (2 × (1 × ((λ n .(1, si n = 0; de lo contrario n × (( Y G) ( n −1)))) (1−1)))))

4 × (3 × (2 × (1 × (1, si 0 = 0; de lo contrario 0 × (( Y G) (0−1))))))

4 × (3 × (2 × (1 × (1))))

24

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.

Cláusulas estándar

Ciertos términos tienen nombres comúnmente aceptados: ^{[28] [29] [30]}

Yo  := λ x . X

S  := λ x .λ y .λ z . x z ( y z )

K  := λ x .λ y . X

B  := λ x .λ y .λ z . x ( y z )

C  := λ x .λ y .λ z . x z y

W  := λ x .λ y . x y y

ω o Δ o U  := λ x . x x

Ω  := ω ω

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únmente como T y F.

Eliminación de abstracciones

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:

T ( x , x ) := yo

T ( x , N ) := K N si x no está libre en N .

T ( x , M N ) := S T ( x , M ) T ( x , N )

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 .

Cálculo lambda mecanografiado

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. ^[31] ${\displaystyle \lambda }$

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).

Estrategias de reducción

Si un término se está normalizando 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: ^{[32] [33] [34]}

orden normal

La redex más externa y a la izquierda siempre se reduce primero. Es decir, siempre que sea posible, los argumentos se sustituyen en el cuerpo de una abstracción antes de reducirlos.

Orden aplicativo

La redex más interna e izquierda siempre se reduce primero. Intuitivamente, esto significa que los argumentos de una función siempre se reducen antes que la función misma. El orden aplicativo siempre intenta aplicar funciones a formas normales, incluso cuando esto no es posible.

Reducciones β completas

Cualquier redex se puede reducir en cualquier momento. Esto significa esencialmente la falta de una estrategia de reducción particular; con respecto a la reducibilidad, "todas las apuestas están canceladas".

Las estrategias de reducción débil no se reducen bajo abstracciones lambda:

Llamar por valor

Una redex se reduce sólo cuando su lado derecho se ha reducido a un valor (variable o abstracción). Sólo se reducen las redex más externas.

Llamar por nombre

Como orden normal, pero no se realizan reducciones dentro de las abstracciones. Por ejemplo, λ x .(λ y . y ) x está en forma normal según esta estrategia, aunque contiene el redex (λ y . y ) x .

Las estrategias para compartir reducen los cálculos que son "iguales" en paralelo:

Reducción óptima

Como orden normal, pero los cálculos que tienen la misma etiqueta se reducen simultáneamente.

llamar por necesidad

Como llamada por nombre (por lo tanto, débil), pero las aplicaciones de funciones que duplicarían términos en lugar de nombrar el argumento, que luego se reduce solo "cuando es necesario".

Computabilidad

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.

Complejidad

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. ^[35] 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. ^[36] 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. ^[37] 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. ^[38]

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 expresiones redex durante la reducción β. ^[39] 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. ^[38] Además, la implementación del prototipo BOHM de reducción óptima superó a Caml Light y Haskell en términos lambda puros. ^[39]

Cálculo lambda y lenguajes de programación.

Como lo señala el artículo de Peter Landin de 1965 "Una correspondencia entre ALGOL 60 y la notación Lambda de Church", ^{[40] 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.

Funciones anónimas

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 lambdacrea 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 de función 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.

Paralelismo y concurrencia

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.

Semántica

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 sí 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. ^[41]

Este trabajo también formó la base para la semántica denotacional de los lenguajes de programación.

Variaciones y extensiones

Estas extensiones están en el cubo lambda :

• Cálculo lambda escrito : cálculo lambda con variables (y funciones) escritas
• Sistema F : un cálculo lambda tipificado con variables de tipo
• Cálculo de construcciones : un cálculo lambda tipificado con tipos como valores de primera clase

Estos sistemas formales son extensiones del cálculo lambda que no están en el cubo lambda:

• Cálculo lambda binario : una versión del cálculo lambda con E/S binaria, una codificación binaria de términos y una máquina universal designada.
• Cálculo lambda-mu : una extensión del cálculo lambda para el tratamiento de la lógica clásica

Estos sistemas formales son variaciones del cálculo lambda:

• Cálculo kappa : un análogo de primer orden del cálculo lambda

Estos sistemas formales están relacionados con el cálculo lambda:

• Lógica combinatoria : una notación para la lógica matemática sin variables
• Cálculo combinador SKI : un sistema computacional basado en los combinadores S , K e I , equivalente al cálculo lambda, pero reducible sin sustituciones de variables.

Ver también

• Portal de matemáticas

• Sistemas de computación aplicativa – Tratamiento de objetos al estilo del cálculo lambda
• Categoría cerrada cartesiana : un escenario para el cálculo lambda en la teoría de categorías
• Máquina abstracta categórica : un modelo de cálculo aplicable al cálculo lambda
• Clojure , lenguaje de programación
• Isomorfismo de Curry-Howard : la correspondencia formal entre programas y pruebas
• Índice de De Bruijn : notación que elimina la ambigüedad de las conversiones alfa
• Notación de De Bruijn : notación que utiliza funciones de modificación de sufijos
• Teoría de dominio : estudio de ciertos posets que brindan semántica denotacional para el cálculo lambda
• Estrategia de evaluación – Reglas para la evaluación de expresiones en lenguajes de programación
• Sustitución explícita : la teoría de la sustitución, tal como se utiliza en la reducción β
• Programación funcional
• Fórmula de Harrop : un tipo de fórmula lógica constructiva tal que las pruebas son términos lambda
• Redes de interacción
• Paradoja de Kleene-Rosser : una demostración de que alguna forma de cálculo lambda es inconsistente
• Knights of the Lambda Calculus : una organización semificticia de hackers de LISP y Scheme
• Máquina Krivine : una máquina abstracta para interpretar llamadas por nombre en cálculo lambda
• Definición del cálculo lambda : definición formal del cálculo lambda.
• Let expresión : una expresión estrechamente relacionada con una abstracción.
• Minimalismo (informática)
• Reescritura – Transformación de fórmulas en sistemas formales
• Máquina SECD : una máquina virtual diseñada para el cálculo lambda
• Teorema de Scott-Curry : un teorema sobre conjuntos de términos lambda
• Burlarse de un ruiseñor : una introducción a la lógica combinatoria
• Máquina universal de Turing : una máquina informática formal equivalente al cálculo lambda
• Unlambda : un lenguaje de programación funcional esotérico basado en lógica combinatoria

Otras lecturas

• Abelson, Harold y Gerald Jay Sussman. Estructura e Interpretación de Programas Informáticos . La prensa del MIT . ISBN  0-262-51087-1 .
• Barendregt, Hendrik Pieter Introducción al cálculo Lambda.
• Barendregt, Hendrik Pieter, El impacto del cálculo Lambda en lógica e informática. The Bulletin of Symbolic Logic, Volumen 3, Número 2, junio de 1997.
• Barendregt, Hendrik Pieter, The Type Free Lambda Calculus pp1091-1132 del Manual de lógica matemática , Holanda Septentrional (1977) ISBN 0-7204-2285-X 
• Cardone, Felice y Hindley, J. Roger, 2006. Historia del cálculo Lambda y la lógica combinatoria Archivado el 6 de mayo de 2021 en Wayback Machine . En Gabbay y Woods (eds.), Manual de historia de la lógica , vol. 5. Elsevier.
• Church, Alonzo, Un problema irresoluble de la teoría de números elemental , American Journal of Mathematics , 58 (1936), págs. Este artículo contiene la prueba de que la equivalencia de expresiones lambda en general no es decidible.
• Iglesia, Alonso (1941). Los cálculos de la conversión Lambda. Princeton: Prensa de la Universidad de Princeton . Consultado el 14 de abril de 2020 .( ISBN 978-0-691-08394-0 ) 
• Frink hijo, Orrin (1944). "Reseña: Los cálculos de la conversión Lambda de Alonzo Church" (PDF) . Toro. América. Matemáticas. Soc . 50 (3): 169-172. doi : 10.1090/s0002-9904-1944-08090-7 .
• Kleene, Stephen, Una teoría de los enteros positivos en lógica formal , American Journal of Mathematics , 57 (1935), págs. 153–173 y 219–244. Contiene las definiciones del cálculo lambda de varias funciones familiares.
• Landin, Peter , Una correspondencia entre ALGOL 60 y la notación Lambda de Church , Comunicaciones de la ACM , vol. 8, núm. 2 (1965), páginas 89-101. Disponible en el sitio de ACM. Un artículo clásico que destaca la importancia del cálculo lambda como base para los lenguajes de programación.
• Larson, Jim, Introducción al cálculo y esquema Lambda. Una suave introducción para programadores.
• Michaelson, Greg (10 de abril de 2013). Introducción a la programación funcional mediante cálculo Lambda . Corporación de mensajería. ISBN 978-0-486-28029-5.^[42]
• Schalk, A. y Simmons, H. (2005) Una introducción a los cálculos λ y la aritmética con una buena selección de ejercicios . Notas para un curso de Maestría en Lógica Matemática en la Universidad de Manchester.
• de Queiroz, Ruy JGB (2008). "Sobre reglas de reducción, significado como uso y semántica de teoría de prueba". Estudios Lógica . 90 (2): 211–247. doi :10.1007/s11225-008-9150-5. S2CID  11321602.Un artículo que brinda un fundamento formal a la idea de "el significado es uso" que, incluso si se basa en pruebas, es diferente de la semántica de la teoría de la prueba como en la tradición de Dummett-Prawitz, ya que toma la reducción como las reglas que dan significado.
• Hankin, Chris, Introducción a los cálculos Lambda para informáticos, ISBN 0954300653 

Monografías/libros de texto para estudiantes de posgrado.

• Sørensen, Morten Heine y Urzyczyn, Paweł (2006), Lectures on the Curry-Howard isomorphism , Elsevier, ISBN 0-444-52077-5 es una monografía reciente que cubre los temas principales del cálculo lambda desde la variedad sin tipografía hasta la mayoría de los cálculos lambda tipificados , incluidos desarrollos más recientes como los sistemas de tipo puro y el cubo lambda . No cubre extensiones de subtipos . 
• Pierce, Benjamin (2002), Tipos y lenguajes de programación , MIT Press, ISBN 0-262-16209-1cubre los cálculos lambda desde una perspectiva práctica del sistema de tipos; Algunos temas, como los tipos dependientes, solo se mencionan, pero los subtipos son un tema importante.

Documentos

• Una breve introducción al cálculo Lambda - ( PDF ) por Achim Jung
• Una cronología del cálculo lambda - ( PDF ) por Dana Scott
• Tutorial de Introducción al Cálculo Lambda -( PDF ) por Raúl Rojas
• Notas de la conferencia sobre el cálculo Lambda - ( PDF ) por Peter Selinger
• Cálculo lambda gráfico de Marius Buliga
• Lambda Calculus como modelo de flujo de trabajo por Peter Kelly, Paul Coddington y Andrew Wendelborn; menciona la reducción de gráficos como un medio común para evaluar expresiones lambda y analiza la aplicabilidad del cálculo lambda para la computación distribuida (debido a la propiedad de Church-Rosser , que permite la reducción de gráficos paralelos para expresiones lambda).

Notas

1. Estas reglas producen expresiones como: . Se pueden eliminar los paréntesis si la expresión no es ambigua. Para algunas aplicaciones, se pueden incluir términos para constantes y operaciones lógicas y matemáticas. ${\displaystyle (\lambda x.\lambda y.(\lambda z.(\lambda x.z\ x)\ (\lambda y.z\ y))(x\ y))}$
2. Barendregt,Barendsen (2000) llame a esta forma
   • axioma β : (λx.M[x]) N = M[N] , reescrito como (λx.M) N = M[x := N], "donde M[x := N] denota la sustitución de N por cada aparición de x en M". ^{[1] : 7} También denominado M[N/x], "la sustitución de N por x en M". ^[2]
3. Para obtener una historia completa, consulte "Historia del cálculo Lambda y lógica combinatoria" de Cardone y Hindley (2006).
4. se pronuncia " mapas a ". ${\displaystyle \mapsto }$
5. La expresión e puede ser: variables x, abstracciones lambda o aplicaciones —en BNF, .— del cálculo lambda simplemente escrito de Wikipedia # Sintaxis para cálculo lambda sin tipo ${\displaystyle e::=x\mid \lambda x.e\mid e\,e}$
6. a veces se escribe en ASCII como ${\displaystyle (\lambda x.t)}$ ${\displaystyle Lx.t}$
7. En forma anónima, se reescribe en . ${\displaystyle (\lambda x.t)}$ ${\displaystyle x\mapsto t}$
8. las variables libres en notación lambda y su cálculo son comparables al álgebra lineal y los conceptos matemáticos del mismo nombre
9. El conjunto de variables libres de M, pero con { x } eliminada
10. La unión del conjunto de variables libres de y el conjunto de variables libres de ^[1] ${\displaystyle M}$ ${\displaystyle N}$
11. (λ f . M ) N se puede pronunciar "sea f N en M".
12. Ariola y Blom ^[27] emplean 1) axiomas para un cálculo representacional utilizando gráficos lambda cíclicos bien formados ampliados con letrec , para detectar árboles que se desenrollan posiblemente infinitos; 2) el cálculo representacional con reducción β de gráficos lambda con alcance constituye la extensión cíclica del cálculo lambda de Ariola/Blom; 3) Ariola/Blom razonan sobre lenguajes estrictos usando § llamada por valor y lo comparan con el cálculo de Moggi y con el cálculo de Hasegawa. Conclusiones en la pág. 111. ^[27]

Referencias

Algunas partes de este artículo se basan en material de FOLDOC , utilizado con autorización .

1. Barendregt, Henk ; Barendsen, Erik (marzo de 2000), Introducción al cálculo Lambda (PDF)^{[ enlace muerto permanente ]}
2. sustitución explícita en el n Lab
3. Turing, Alan M. (diciembre de 1937). "Computabilidad y λ-Definibilidad". La revista de lógica simbólica . 2 (4): 153–163. doi :10.2307/2268280. JSTOR  2268280. S2CID  2317046.
4. Coquand, Thierry (8 de febrero de 2006). Zalta, Edward N. (ed.). "Teoría de tipos". La Enciclopedia de Filosofía de Stanford (edición de verano de 2013) . Consultado el 17 de noviembre de 2020 .
5. Moortgat, Michael (1988). Investigaciones categoriales: aspectos lógicos y lingüísticos del cálculo de Lambek. Publicaciones Foris. ISBN 9789067653879.
6. Toque, Harry; Muskens, Reinhard, eds. (2008). Significado informático. Saltador. ISBN 978-1-4020-5957-5.
7. Mitchell, John C. (2003). Conceptos en lenguajes de programación. Prensa de la Universidad de Cambridge. pag. 57.ISBN​ 978-0-521-78098-8..
8. Chacón Sartori, Camilo (5 de diciembre de 2023). Introducción al cálculo Lambda utilizando Racket (Informe técnico). Archivado desde el original el 7 de diciembre de 2023.
9. Pierce, Benjamin C. Teoría de categorías básicas para informáticos . pag. 53.
10. Iglesia, Alonso (1932). "Un conjunto de postulados para el fundamento de la lógica". Anales de Matemáticas . Serie 2. 33 (2): 346–366. doi :10.2307/1968337. JSTOR  1968337.
11. Kleene, Stephen C .; Rosser, JB (julio de 1935). "La inconsistencia de ciertas lógicas formales". Los Anales de las Matemáticas . 36 (3): 630. doi : 10.2307/1968646. JSTOR  1968646.
12. Iglesia, Alonzo (diciembre de 1942). "Revisión de Haskell B. Curry, La inconsistencia de ciertas lógicas formales ". La revista de lógica simbólica . 7 (4): 170–171. doi :10.2307/2268117. JSTOR  2268117.
13. Iglesia, Alonzo (1936). "Un problema irresoluble de la teoría elemental de números". Revista Estadounidense de Matemáticas . 58 (2): 345–363. doi :10.2307/2371045. JSTOR  2371045.
14. Iglesia, Alonso (1940). "Una formulación de la sencilla teoría de tipos". Revista de Lógica Simbólica . 5 (2): 56–68. doi :10.2307/2266170. JSTOR  2266170. S2CID  15889861.
15. Parte, BBH; ter Meulen, A .; Muro, RE (1990). Métodos matemáticos en lingüística. Saltador. ISBN 9789027722454. Consultado el 29 de diciembre de 2016 .
16. Alma, Jesse. Zalta, Edward N. (ed.). "El cálculo Lambda". La Enciclopedia de Filosofía de Stanford (edición de verano de 2013) . Consultado el 17 de noviembre de 2020 .
17. Dana Scott, "Looking Backward; Looking Forward", charla invitada en el taller en honor al 85.º cumpleaños de Dana Scott y sus 50 años de teoría de dominios, del 7 al 8 de julio, FLoC 2018 (charla del 7 de julio de 2018). El pasaje relevante comienza a las 32:50. (Véase también este extracto de una charla de mayo de 2016 en la Universidad de Birmingham, Reino Unido).
18. Barendregt, Hendrik Pieter (1984). El cálculo Lambda: su sintaxis y semántica. Estudios de Lógica y Fundamentos de las Matemáticas. vol. 103 (edición revisada). Holanda del Norte. ISBN 0-444-87508-5.
19. ^{[ enlace muerto ]} Correcciones ^{[ enlace muerto permanente ]} .
20. "Ejemplo de reglas de asociatividad". Lambda-bound.com . Consultado el 18 de junio de 2012 .
21. "La gramática básica de las expresiones Lambda". Opción suave . 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.
22. Selinger, Peter (2008), Apuntes de la conferencia sobre el cálculo Lambda (PDF) , vol. 0804, Departamento de Matemáticas y Estadística, Universidad de Ottawa, p. 9, arXiv : 0804.3434 , código Bib : 2008arXiv0804.3434S
23. de Queiroz, Ruy JGB (1988). "Una explicación teórica de la programación y el papel de las reglas de reducción". Dialéctica . 42 (4): 265–282. doi :10.1111/j.1746-8361.1988.tb00919.x.
24. Turbak, Franklyn; Gifford, David (2008), Conceptos de diseño en lenguajes de programación , MIT Press, p. 251, ISBN 978-0-262-20175-9
25. Luke Palmer (29 de diciembre de 2010) Haskell-cafe: ¿Cuál es la motivación para η reglas?
26. Felleisen, Matías; Flatt, Matthew (2006), Lenguajes de programación y cálculos Lambda (PDF) , p. 26, archivado desde el original (PDF) el 2009-02-05; Una nota (consultada en 2017) en la ubicación original sugiere que los autores consideran que la obra a la que se hace referencia originalmente ha sido reemplazada por un libro.
27. Zena M. Ariola y Stefan Blom, Proc. TACS '94 Sendai, Japón 1997 (1997) Cálculos lambda cíclicos 114 páginas.
28. Ker, Andrew D. "Tipos y cálculo Lambda" (PDF) . pag. 6 . Consultado el 14 de enero de 2022 .
29. Dezani-Ciancaglini, Mariangiola; Ghilezan, Silvia (2014). "Precisión de la subtipificación de tipos de intersecciones y uniones" (PDF) . Reescritura y cálculos Lambda mecanografiados . Apuntes de conferencias sobre informática. vol. 8560. pág. 196.doi : 10.1007 /978-3-319-08918-8_14. hdl :2318/149874. ISBN 978-3-319-08917-1. Consultado el 14 de enero de 2022 .
30. Forster, Yannick; Smolka, Gert (agosto de 2019). "Cálculo Lambda de llamada por valor como modelo de computación en Coq" (PDF) . Revista de razonamiento automatizado . 63 (2): 393–413. doi :10.1007/s10817-018-9484-2. S2CID  53087112 . Consultado el 14 de enero de 2022 .
31. Tipos y lenguajes de programación, pag. 273, Benjamín C. Pierce
32. Pierce, Benjamín C. (2002). Tipos y lenguajes de programación. Prensa del MIT . pag. 56.ISBN​ 0-262-16209-1.
33. Sestoft, Peter (2002). "Demostración de la reducción del cálculo Lambda" (PDF) . La esencia de la computación . Apuntes de conferencias sobre informática. vol. 2566, págs. 420–435. doi :10.1007/3-540-36377-7_19. ISBN 978-3-540-00326-7. Consultado el 22 de agosto de 2022 .
34. Biernacka, Małgorzata; Charatonik, Witold; Monótono, Tomasz (2022). Andrónico, junio; de Moura, Leonardo (eds.). "El zoológico de las estrategias de reducción del cálculo Lambda y Coq" (PDF) . 13.ª Conferencia Internacional sobre Demostración Interactiva de Teoremas (ITP 2022) . Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 237 : 7:1–7:19. doi : 10.4230/LIPIcs.ITP.2022.7 . Consultado el 22 de agosto de 2022 .
35. Frandsen, Gudmund Skovbjerg; Sturtivant, Carl (26 de agosto de 1991). "¿Qué es una implementación eficiente del cálculo λ?". Lenguajes de programación funcionales y arquitectura de ordenadores . Apuntes de conferencias sobre informática. vol. 523. Springer-Verlag. págs. 289–312. CiteSeerX 10.1.1.139.6913 . doi :10.1007/3540543961_14. ISBN  9783540543961. {{cite book}}: |journal=ignorado ( ayuda )
36. Sinot, F.-R. (2005). "Director Strings revisitado: un enfoque genérico para la representación eficiente de variables libres en la reescritura de orden superior" (PDF) . Revista de Lógica y Computación . 15 (2): 201–218. doi : 10.1093/logcom/exi010.
37. Accattoli, Beniamino; Dal Lago, Ugo (14 de julio de 2014). "La reducción beta es invariante, de hecho". Actas de la reunión conjunta de la vigésima tercera conferencia anual de EACSL sobre lógica informática (CSL) y el vigésimo noveno simposio anual ACM/IEEE sobre lógica en informática (LICS) . págs. 1–10. arXiv : 1601.01233 . doi :10.1145/2603088.2603105. ISBN 9781450328869. S2CID  11485010.
38. Accattoli, Beniamino (octubre de 2018). "Modelos de (in)eficiencia y costes razonables". Apuntes Electrónicos en Informática Teórica . 338 : 23–43. doi : 10.1016/j.entcs.2018.10.003 .
39. Asperti, Andrea (16 de enero de 2017). "Acerca de la reducción eficiente de términos lambda". arXiv : 1701.04240v1 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
40. Landín, PJ (1965). "Una correspondencia entre ALGOL 60 y la notación Lambda de Church". Comunicaciones de la ACM . 8 (2): 89-101. doi : 10.1145/363744.363749 . S2CID  6505810.
41. Scott, Dana (1993). "Una alternativa teórica de tipos a ISWIM, CUCH, OWHY" (PDF) . Informática Teórica . 121 (1–2): 411–440. doi : 10.1016/0304-3975(93)90095-B . Consultado el 1 de diciembre de 2022 .Escrito en 1969, circuló ampliamente como manuscrito inédito.
42. "Página de inicio de Greg Michaelson". Ciencias Matemáticas e Informática . Riccarton, Edimburgo: Universidad Heriot-Watt . Consultado el 6 de noviembre de 2022 .

enlaces externos

• Graham Hutton, Lambda Calculus, un vídeo breve (12 minutos) para informáticos sobre Lambda Calculus
• Helmut Brandl, Introducción paso a paso al cálculo Lambda
• "Cálculo lambda", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• David C. Keenan, Para diseccionar un ruiseñor: una notación gráfica para el cálculo Lambda con reducción animada
• L. Allison, Algunos ejemplos ejecutables de cálculo λ
• Georg P. Loczewski, El cálculo Lambda y A++
• Bret Victor, Alligator Eggs: un juego de rompecabezas basado en Lambda Calculus
• Lambda Calculus Archivado el 14 de octubre de 2012 en Wayback Machine en el sitio web de Safalra Archivado el 2 de mayo de 2021 en Wayback Machine.
• LCI Lambda Interpreter, un intérprete de cálculo puro simple pero potente
• Enlaces de Lambda Calculus en Lambda-the-Ultimate
• Mike Thyer, Lambda Animator, un subprograma gráfico de Java que demuestra estrategias de reducción alternativas.
• Implementación del cálculo Lambda usando plantillas C++
• Shane Steinert-Threlkeld, "Lambda Calculi", Enciclopedia de Filosofía de Internet
• Anton Salikhmetov, Cálculo Macro Lambda