El cálculo lambda es un sistema formal en lógica matemática para expresar cálculos basados en abstracciones y aplicar funciones usando unión y sustitución de variables. Este es un modelo universal que se puede aplicar al diseño de cualquier máquina de Turing. El cálculo lambda fue introducido por primera vez por Church, un famoso matemático, en la década de 1930.
El sistema consiste en construir miembros lambda y realizar operaciones de reducción sobre ellos.
Explicaciones y aplicaciones
La letra griega lambda (λ) se usa en expresiones lambda y términos lambda para indicar el enlace de una variable en una función.
El cálculo lambda puede escribirse o escribirse. En la primera variante, las funciones solo se pueden utilizar si son capaces de recibir datos de este tipo. Los cálculos lambda tipificados son más débiles, pueden expresar un valor más pequeño. Pero, por otro lado, te permiten probar más cosas.
Una de las razones por las que hay tantos tipos diferentes es el deseo de los científicos de hacer más sin renunciar a la oportunidad de probar teoremas de cálculo lambda sólidos.
El sistema tiene aplicaciones en muchas áreas diferentes de las matemáticas, la filosofía, la lingüística y la informática. En primer lugar, el cálculo lambda es un cálculo que ha jugado un papel importante en el desarrollo de la teoría de los lenguajes de programación. Son los estilos de creación funcional que implementan los sistemas. También son un tema candente de investigación en la teoría de estas categorías.
Para tontos
El matemático Alonzo Church introdujo el cálculo lambda en la década de 1930 como parte de su investigación sobre los fundamentos de la ciencia. Se demostró que el sistema original era lógicamente inconsistente en 1935 cuando Stephen Kleen y J. B. Rosser desarrollaron la paradoja de Kleene-Rosser.
Más tarde, en 1936, Church seleccionó y publicó solo la parte que es relevante para los cálculos, lo que ahora se llama el cálculo lambda sin tipo. En 1940 también introdujo una teoría más débil pero lógicamente consistente conocida como sistema de tipos primos. En su trabajo, explica toda la teoría en términos simples, por lo que se puede decir que Church publicó el cálculo lambda para tontos.
Hasta la década de 1960, cuando quedó clara su relación con los lenguajes de programación, λ era solo un formalismo. Gracias a las aplicaciones de Richard Montagu y otros lingüistas en la semántica del lenguaje natural, el cálculo ha ocupado un lugar privilegiado tanto en la lingüística como en la informática.
Origen del símbolo
Lambda no significa una palabra o un acrónimo, proviene de una referencia en Principal Mathematics de Russell seguida de dos cambios tipográficos. Ejemplo de notación: para una función f con f (y)=2y + 1 es 2ŷ + 1. Y aquí usamos un signo de intercalación ("sombrero") sobre y para etiquetar la variable de entrada.
La iglesia originalmente tenía la intención de usar símbolos similares, pero los tipógrafos no pudieron colocar el símbolo del "sombrero" sobre las letras. Entonces, en cambio, lo imprimieron originalmente como "/\y.2y+1". En el siguiente episodio de edición, los mecanógrafos reemplazaron "/ \" con un carácter visualmente similar.
Introducción al cálculo lambda
El sistema consiste en un lenguaje de términos, los cuales son elegidos por una determinada sintaxis formal, y un conjunto de reglas de transformación que permiten manipularlos. El último punto puede considerarse como una teoría ecuacional o como una definición operativa.
Todas las funciones en el cálculo lambda son anónimas, lo que significa que no tienen nombres. Solo toman una variable de entrada, y el curry se usa para implementar gráficos con múltiples variables.
Términos lambda
La sintaxis del cálculo define algunas expresiones como válidas y otras como no válidas. Al igual que diferentes cadenas de caracteres son programas C válidos y algunos no lo son. La expresión real del cálculo lambda se denomina "término lambda".
Las tres reglas siguientes proporcionan una definición inductiva que se puedeaplicar a la construcción de todos los conceptos sintácticamente válidos:
La variable x en sí misma es un término lambda válido:
- si T es LT y x no es constante, entonces (lambda xt) se denomina abstracción.
- si tanto T como s son conceptos, entonces (TS) se denomina aplicación.
Nada más es un término lambda. Así, un concepto es válido si y sólo si puede obtenerse mediante la aplicación repetida de estas tres reglas. Sin embargo, algunos paréntesis pueden omitirse según otros criterios.
Definición
Las expresiones lambda consisten en:
- variables v 1, v 2, …, v n, …
- símbolos de abstracción 'λ' y punto '.'
- corchetes ().
El conjunto Λ se puede definir inductivamente:
- Si x es una variable, entonces x ∈ Λ;
- x no es constante y M ∈ Λ, entonces (λx. M) ∈ Λ;
- M, N ∈ Λ, luego (MN) ∈ Λ.
Designación
Para mantener ordenada la notación de las expresiones lambda, se utilizan comúnmente las siguientes convenciones:
- Corchetes exteriores omitidos: MN en lugar de (MN).
- Se supone que las aplicaciones siguen siendo asociativas: se puede escribir MNP en lugar de ((MN) P).
- El cuerpo de abstracción se extiende más hacia la derecha: λx. MN significa λx. (MN), no (λx. M) N.
- La secuencia de abstracciones se reduce: λx.λy.λz. N puede ser λxyz. N.
Variables libres y enlazadas
El operador λ conecta su no constante dondequiera que esté en el cuerpo de abstracción. Las variables que caen dentro del ámbito se denominan vinculadas. En la expresión λ x. M, la parte λ x a menudo se denomina aglutinante. Como insinuando que las variables se convierten en un grupo con la adición de X x a M. Todos los demás inestables se llaman libres.
Por ejemplo, en la expresión λ y. x x y, y - enlazado no permanente, y x - libre. Y también vale la pena señalar que la variable se agrupa por su abstracción "más cercana". En el siguiente ejemplo, la solución de cálculo lambda está representada por una sola ocurrencia de x, que está relacionada con el segundo término:
λx. y (λ x. z x)
El conjunto de variables libres M se denota como FV (M) y se define por recursión sobre la estructura de términos de la siguiente manera:
- FV (x)={x}, donde x es una variable.
- VF (λx. M)=VF (M) {x}.
- FV (MN)=FV (M) ∪ FV (N).
Una fórmula que no contiene variables libres se llama cerrada. Las expresiones lambda cerradas también se conocen como combinadores y son equivalentes a los términos de la lógica combinatoria.
Abreviatura
El significado de las expresiones lambda está determinado por cómo se pueden abreviar.
Hay tres tipos de cortes:
- Transformada α: cambio de variables ligadas (alfa).
- β-reducción: aplicando funciones a sus argumentos (beta).
- η-transformada: cubre la noción de extensionalidad.
Aquí también estáestamos hablando de las equivalencias resultantes: dos expresiones son equivalentes en β si pueden transformarse en β en el mismo componente, y la equivalencia α / η se define de manera similar.
El término redex, abreviatura de facturación reducible, se refiere a subtemas que pueden reducirse mediante una de las reglas. Cálculo lambda para principiantes, ejemplos:
(λ x. M) N es un redex beta en la expresión para reemplazar N con x en M. El componente al que se reduce un redex se llama su reducción. La reducción (λ x. M) N es M [x:=N].
Si x no es libre en M, λ x. M x también em-REDEX con regulador M.
α-transformación
Los cambios de nombre alfa le permiten cambiar los nombres de las variables vinculadas. por ejemplo x x puede dar λ y. y. Los términos que difieren solo en la transformación alfa se dice que son α-equivalentes. A menudo, cuando se utiliza el cálculo lambda, los equivalentes α se consideran recíprocos.
Las reglas exactas para la conversión alfa no son del todo triviales. En primer lugar, con esta abstracción, solo se renombran aquellas variables que están asociadas al mismo sistema. Por ejemplo, la transformada alfa λ x.λ x. x puede conducir a λ y.λ x. x, pero esto puede no conducir a λy.λx.y Este último tiene un significado diferente al original. Esto es análogo al concepto de programación de sombreado variable.
En segundo lugar, una transformación alfa no es posible si resultara en ser capturada por otra abstracción no permanente. Por ejemplo, si reemplaza x con y en λ x.λ y. x, entonces puedes obtenerλy.λy. u, que no es lo mismo en absoluto.
En lenguajes de programación con alcance estático, la conversión alfa se puede utilizar para simplificar la resolución de nombres. Al mismo tiempo, cuidando que el concepto de variable no enmascare la designación en el área contenedora.
En la notación de índice de De Bruyne, dos términos equivalentes alfa son sintácticamente idénticos.
Reemplazo
Los cambios escritos por E [V:=R] son el proceso de sustituir todas las ocurrencias libres de la variable V en la expresión E con el volumen de negocios R. La sustitución en términos de λ se define por la lambda de la recursividad cálculo de la estructura del concepto de la siguiente manera (nota: x e y - solo variables, y M y N - cualquier expresión λ).
x [x:=norte] ≡ norte
y [x:=N] ≡ y si x ≠ y
(M 1 METRO 2) [x:=N] ≡ (M 1 [x:=N]) (M 2 [x:=N])
(λ x. M) [x:=N] ≡ λ x. M
(λ y. M) [x:=N] y λ y. (M [x:=N]) si x ≠ y, siempre que y ∉ FV (N).
Para la sustitución en una abstracción lambda, a veces es necesario transformar una expresión en α. Por ejemplo, no es cierto que (λ x. Y) [y:=x] resulte en (λ x. X) porque la x sustituida debería haber sido libre, pero terminó siendo ligada. El reemplazo correcto en este caso es (λ z. X) hasta la equivalencia α. Tenga en cuenta que la sustitución se define de forma única hasta lambda.
reducción β
La reducción beta refleja la idea de aplicar una función. Beta-reductivo se define en términossustitución: ((X V. E) E ') es E [V:=E'].
Por ejemplo, suponiendo alguna codificación 2, 7, ×, existe la siguiente reducción β: ((λ n. N × 2) 7) → 7 × 2.
La reducción beta puede verse como lo mismo que el concepto de reducibilidad local bajo deducción natural a través del isomorfismo de Curry-Howard.
η-transformada
Esta conversión expresa la idea de extensionalidad, que en este contexto es que dos funciones son iguales cuando dan el mismo resultado para todos los argumentos. Esta conversión se intercambia entre λ x. (F x) y f siempre que x no parezca libre en f.
Esta acción puede considerarse como la misma que el concepto de completitud local en la deducción natural a través del isomorfismo de Curry-Howard.
Formas normales y fusión
Para un cálculo lambda sin tipo, la regla de reducción β generalmente no es una normalización fuerte ni débil.
Sin embargo, se puede demostrar que la reducción β se fusiona cuando se ejecuta antes de la transformación α (es decir, dos formas normales pueden considerarse iguales si es posible una transformación α de una a la otra).
Por lo tanto, tanto los términos fuertemente normalizados como los términos débilmente ajustados tienen una sola forma normal. Para los primeros términos, se garantiza que cualquier estrategia de reducción dará como resultado una configuración típica. Mientras que para condiciones de normalización débil, algunas estrategias de reducción pueden no encontrarlo.
Métodos de programación adicionales
Hay muchos modismos de creación para el cálculo lambda. Muchos de ellos se desarrollaron originalmente en el contexto del uso de sistemas como base para la semántica de un lenguaje de programación, aplicándolos efectivamente como una construcción de bajo nivel. Dado que algunos estilos incluyen un cálculo lambda (o algo muy similar) como un fragmento, estas técnicas también encuentran uso en la creación práctica, pero luego pueden percibirse como oscuras o extrañas.
Constantes con nombre
En cálculo lambda, una biblioteca toma la forma de un conjunto de funciones previamente definidas, donde los términos son solo constantes concretas. El cálculo puro no tiene concepto de inmutables nombrados ya que todos los términos lambda atómicos son variables. Pero también se pueden imitar tomando lo mutable como el nombre de la constante, usando una abstracción lambda para vincular ese volátil en el cuerpo y aplicando esa abstracción a la definición prevista. Entonces, si usas f para representar M en N, podrías decir
(λ frente a N) M.
Los autores a menudo introducen un concepto sintáctico como let para permitir que las cosas se escriban de una manera más intuitiva.
f=M a N
Al encadenar tales definiciones, se puede escribir un "programa" de cálculo lambda como cero o más definiciones de función seguidas de un solo miembro lambda, usando esas definiciones que constituyen la mayor parte del programa.
Una limitación notable de este let es que el nombre f no está definido en M,ya que M está fuera del alcance vinculante de la abstracción lambda f. Esto significa que un atributo de función recursiva no se puede usar como M con let. La sintaxis letrec más avanzada, que le permite escribir definiciones de funciones recursivas en este estilo, además utiliza en su lugar combinadores de punto fijo.
Análogos impresos
Este tipo es un formalismo tipificado que usa un símbolo para representar una abstracción de 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 depende del cálculo en cuestión. Desde cierto punto de vista, la LI tipada puede considerarse como un refinamiento de la LI no tipificada. Pero, por otro lado, también pueden considerarse una teoría más fundamental, y el cálculo lambda sin tipo es un caso especial con un solo tipo.
Typed LI son la base de los lenguajes de programación y la columna vertebral de los lenguajes funcionales como ML y Haskell. Y, más indirectamente, estilos imperativos de creación. Los cálculos lambda tipados juegan un papel importante en el desarrollo de sistemas de tipos para lenguajes de programación. En este caso, la tipificación generalmente captura las propiedades deseadas del programa, por ejemplo, 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 un lenguaje interno de clases de categorías, por ejemplo, quesimplemente es el estilo de los cierres cartesianos.
