Elevación de lambda

Metaproceso de globalización

El levantamiento de lambda es un metaproceso que reestructura un programa informático de modo que las funciones se definan de forma independiente entre sí en un ámbito global . Un "levantamiento" individual transforma una función local en una función global. Es un proceso de dos pasos, que consiste en:

• Eliminar variables libres en la función añadiendo parámetros.
• Trasladar funciones de un ámbito restringido a un ámbito más amplio o global.

El término "elevación de lambda" fue introducido por primera vez por Thomas Johnsson alrededor de 1982 y se consideró históricamente como un mecanismo para implementar lenguajes de programación funcional . Se utiliza junto con otras técnicas en algunos compiladores modernos .

La elevación de lambda no es lo mismo que la conversión de cierre. Requiere que se ajusten todos los sitios de llamada (agregando argumentos adicionales a las llamadas) y no introduce un cierre para la expresión lambda elevada. Por el contrario, la conversión de cierre no requiere que se ajusten los sitios de llamada, pero sí introduce un cierre para la expresión lambda que asigna variables libres a valores.

La técnica puede utilizarse en funciones individuales, en la refactorización de código , para hacer que una función sea utilizable fuera del ámbito en el que fue escrita. Los levantamientos lambda también pueden repetirse, para transformar el programa. Los levantamientos repetidos pueden usarse para convertir un programa escrito en cálculo lambda en un conjunto de funciones recursivas , sin lambdas. Esto demuestra la equivalencia de los programas escritos en cálculo lambda y los programas escritos como funciones. ^[1] Sin embargo, no demuestra la solidez del cálculo lambda para la deducción, ya que la reducción eta utilizada en el levantamiento lambda es el paso que introduce problemas de cardinalidad en el cálculo lambda, porque elimina el valor de la variable, sin verificar primero que solo hay un valor que satisface las condiciones en la variable (ver la paradoja de Curry ).

La elevación de lambda es costosa en términos de tiempo de procesamiento para el compilador. Una implementación eficiente de la elevación de lambda es costosa en términos de tiempo de procesamiento para el compilador. ^[2] ${\displaystyle O(n^{2})}$

En el cálculo lambda sin tipo , donde los tipos básicos son funciones, la elevación puede cambiar el resultado de la reducción beta de una expresión lambda. Las funciones resultantes tendrán el mismo significado, en un sentido matemático, pero no se consideran la misma función en el cálculo lambda sin tipo. Véase también igualdad intensional versus igualdad extensional .

La operación inversa a la elevación de lambda es la caída de lambda. ^[3]

La eliminación de lambda puede hacer que la compilación de programas sea más rápida para el compilador y también puede aumentar la eficiencia del programa resultante, al reducir la cantidad de parámetros y el tamaño de los marcos de pila. Sin embargo, hace que sea más difícil reutilizar una función. Una función eliminada está vinculada a su contexto y solo se puede usar en un contexto diferente si se elimina primero.

Algoritmo

El siguiente algoritmo es una forma de aplicar un efecto lambda a un programa arbitrario en un lenguaje que no admite cierres como objetos de primera clase :

1. Cambie el nombre de las funciones para que cada una tenga un nombre único.
2. Reemplace cada variable libre con un argumento adicional a la función que la contiene y pase ese argumento a cada uso de la función.
3. Reemplace cada definición de función local que no tenga variables libres con una función global idéntica.
4. Repita los pasos 2 y 3 hasta eliminar todas las variables libres y funciones locales.

Si el lenguaje tiene cierres como objetos de primera clase que pueden pasarse como argumentos o devolverse desde otras funciones, el cierre deberá estar representado por una estructura de datos que capture los enlaces de las variables libres.

Ejemplo

El siguiente programa OCaml calcula la suma de los números enteros del 1 al 100:

sea  ​​rec  suma  n  =  si  n  =  1  entonces  1  de lo contrario  sea  f  x  =  n  +  x  en  f  ( suma  ( n  -  1 ))  en suma  100

(La función f let recse declara sumcomo una función que puede llamarse a sí misma). La función f, que suma el argumento de suma a la suma de los números menores que el argumento, es una función local. Dentro de la definición de f, n es una variable libre. Comience convirtiendo la variable libre en un parámetro:

sea  ​​rec  suma  n  =  si  n  =  1  entonces  1  de lo contrario  sea  f  w  x  =  w  +  x  en  f  n  ( suma  ( n  -  1 ))  en suma  100

A continuación, eleve f a una función global:

sea  ​​rec  f  w  x  =  w  +  x y  suma  n  =  si  n  =  1  entonces  1  de lo contrario  f  n  ( suma  ( n  -  1 ))  en suma  100

El siguiente es el mismo ejemplo, esta vez escrito en JavaScript :

// Versión inicialfunción suma ( n ) { función f ( x ) { devolver n + x ; }           si ( n == 1 ) devuelve 1 ; de lo contrario devuelve f ( suma ( n - 1 )); }          // Después de convertir la variable libre n en un parámetro formal wfunción suma ( n ) { función f ( w , x ) { devolver w + x ; }            si ( n == 1 ) devuelve 1 ; de lo contrario devuelve f ( n , suma ( n - 1 )); }           // Después de elevar la función f al ámbito globalfunción f ( w , x ) { devuelve w + x ; }       función suma ( n ) { si ( n == 1 ) devuelve 1 ; de lo contrario devuelve f ( n , suma ( n - 1 )); }              

Elevación de lambda versus cierres

La elevación y el cierre de Lambda son métodos para implementar programas estructurados en bloques . Implementa la estructura en bloques eliminándola. Todas las funciones se elevan al nivel global. La conversión de cierre proporciona un "cierre" que vincula el marco actual con otros marcos. La conversión de cierre requiere menos tiempo de compilación.

Las funciones recursivas y los programas estructurados en bloques, con o sin elevación, pueden implementarse utilizando una implementación basada en pila , que es simple y eficiente. Sin embargo, una implementación basada en un marco de pila debe ser estricta (ansiosa) . La implementación basada en un marco de pila requiere que la vida de las funciones sea del tipo último en entrar, primero en salir (LIFO). Es decir, la función más reciente en comenzar su cálculo debe ser la primera en finalizar.

Algunos lenguajes funcionales (como Haskell ) se implementan utilizando la evaluación diferida , que retrasa el cálculo hasta que se necesita el valor. La estrategia de implementación diferida le da flexibilidad al programador. La evaluación diferida requiere retrasar la llamada a una función hasta que se realiza una solicitud al valor calculado por la función. Una implementación es registrar una referencia a un "marco" de datos que describe el cálculo, en lugar del valor. Más tarde, cuando se requiere el valor, el marco se utiliza para calcular el valor, justo a tiempo para cuando se necesita. El valor calculado luego reemplaza la referencia.

El "marco" es similar a un marco de pila , con la diferencia de que no se almacena en la pila. La evaluación diferida requiere que todos los datos necesarios para el cálculo se guarden en el marco. Si la función se "elimina", entonces el marco solo necesita registrar el puntero de función y los parámetros de la función. Algunos lenguajes modernos utilizan la recolección de basura en lugar de la asignación basada en pila para administrar la vida de las variables. En un entorno administrado y recolectado de basura, un cierre registra referencias a los marcos de los cuales se pueden obtener valores. En contraste, una función eliminada tiene parámetros para cada valor necesario en el cálculo.

Expresiones let y cálculo lambda

La expresión Let es útil para describir el levantamiento y la caída, y para describir la relación entre ecuaciones recursivas y expresiones lambda. La mayoría de los lenguajes funcionales tienen expresiones let. Además, los lenguajes de programación estructurados en bloques como ALGOL y Pascal son similares en el sentido de que también permiten la definición local de una función para su uso en un ámbito restringido .

La expresión let utilizada aquí es una versión totalmente recursiva de let rec , tal como se implementa en muchos lenguajes funcionales.

Las expresiones let están relacionadas con el cálculo lambda . El cálculo lambda tiene una sintaxis y una semántica simples, y es bueno para describir la elevación de lambda. Es conveniente describir la elevación de lambda como traducciones de lambda a una expresión let , y la eliminación de lambda como lo inverso. Esto se debe a que las expresiones let permiten la recursión mutua, que es, en cierto sentido, más elevada que la que admite el cálculo lambda. El cálculo lambda no admite la recursión mutua y solo se puede definir una función en el ámbito global más externo.

Las reglas de conversión que describen la traducción sin elevación se proporcionan en el artículo Expresión Let .

Las siguientes reglas describen la equivalencia de las expresiones lambda y let,

Se darán metafunciones que describen la elevación y la caída de lambda. Una metafunción es una función que toma un programa como parámetro. El programa son datos para el metaprograma. El programa y el metaprograma se encuentran en diferentes metaniveles.

Se utilizarán las siguientes convenciones para distinguir el programa del metaprograma,

• Se utilizarán corchetes [] para representar la aplicación de la función en el metaprograma.
• Se utilizarán letras mayúsculas para las variables del metaprograma. Las letras minúsculas representan las variables del programa.
• ${\displaystyle \equiv }$se utilizará para iguales en el metaprograma.
• ${\displaystyle \_}$representa una variable ficticia o un valor desconocido.

Para simplificar, se aplicará la primera regla que establece que se aplicarán las coincidencias. Las reglas también suponen que las expresiones lambda se han procesado previamente de modo que cada abstracción lambda tenga un nombre único.

El operador de sustitución se utiliza ampliamente. La expresión significa sustituir cada ocurrencia de G en L por S y devolver la expresión. La definición utilizada se extiende para cubrir la sustitución de expresiones, a partir de la definición proporcionada en la página de cálculo Lambda . La comparación de expresiones debe comparar expresiones para determinar la equivalencia alfa (cambio de nombre de las variables). ${\displaystyle L[G:=S]}$

Elevación de lambda en el cálculo lambda

Cada elevación de lambda toma una abstracción de lambda que es una subexpresión de una expresión de lambda y la reemplaza por una llamada de función (aplicación) a una función que crea. Las variables libres en la subexpresión son los parámetros de la llamada de función.

Los aumentos de lambda se pueden utilizar en funciones individuales, en la refactorización de código , para hacer que una función sea utilizable fuera del ámbito en el que fue escrita. Dichos aumentos también se pueden repetir, hasta que la expresión no tenga abstracciones de lambda, para transformar el programa.

Elevación lambda

Se le asigna una subexpresión dentro de una expresión a un elevador para elevarlo hasta la parte superior de esa expresión. La expresión puede ser parte de un programa más grande. Esto permite controlar a dónde se eleva la subexpresión. La operación de elevación lambda que se utiliza para realizar un elevador dentro de un programa es:

${\displaystyle \operatorname {lambda-lift-op} [S,L,P]=P[L:=\operatorname {lambda-lift} [S,L]]}$

La subexpresión puede ser una abstracción lambda o una abstracción lambda aplicada a un parámetro.

Son posibles dos tipos de elevación.

• Ascensor anónimo
• Ascensor con nombre

Una función anónima tiene una expresión de elevación que es solo una abstracción lambda. Se considera que define una función anónima. Se debe crear un nombre para la función.

Una expresión de elevación con nombre tiene una abstracción lambda aplicada a una expresión. Esta elevación se considera una definición con nombre de una función.

Ascensor anónimo

Un ascensor anónimo toma una abstracción lambda (llamada S ). Para S ;

• Crea un nombre para la función que reemplazará a S (llamada V ). Asegúrate de que no se haya utilizado el nombre identificado por V.
• Agregue parámetros a V , para todas las variables libres en S , para crear una expresión G (ver make-call ).

La elevación lambda es la sustitución de la abstracción lambda S por una aplicación de función, junto con la adición de una definición para la función.

${\displaystyle \operatorname {lambda-lift} [S,L]\equiv \operatorname {let} V:\operatorname {de-lambda} [G=S]\operatorname {in} L[S:=G]}$

La nueva expresión lambda tiene S sustituida por G. Nótese que L [ S := G ] significa sustitución de S por G en L . En las definiciones de funciones se agregó la definición de función G = S.

En la regla anterior, G es la función de aplicación que sustituye a la expresión S. Se define por:

${\displaystyle G=\operatorname {make-call} [V,\operatorname {FV} [S]]}$

donde V es el nombre de la función. Debe ser una variable nueva, es decir, un nombre que no se haya utilizado ya en la expresión lambda.

${\displaystyle V\not \in \operatorname {vars} [\operatorname {let} F\operatorname {in} L]}$

donde es una metafunción que devuelve el conjunto de variables utilizadas en E. ${\displaystyle \operatorname {vars} [E]}$

Construyendo la llamada

La llamada de función G se construye agregando parámetros para cada variable en el conjunto de variables libres (representado por V ), a la función H ,

• ${\displaystyle X\in V\to \operatorname {make-call} [H,V]\equiv \operatorname {make-call} [H,V\cap \neg \{X\}]\ X}$
• ${\displaystyle \operatorname {make-call} [H,\{\}]\equiv H}$

Ascensor con nombre

El ascensor nombrado es similar al ascensor anónimo excepto que se proporciona el nombre de función V.

${\displaystyle \operatorname {lambda-lift} [(\lambda V.E)\ S,L]\equiv \operatorname {let} V:\operatorname {de-lambda} [G=S]\operatorname {in} L[(\lambda V.E)\ S:=E[V:=G]]}$

En cuanto al ascensor anónimo, la expresión G se construye a partir de V aplicando las variables libres de S. Se define por,

${\displaystyle G=\operatorname {make-call} [V,\operatorname {FV} [S]]}$

Transformación lambda-lift

Una transformación de elevación lambda toma una expresión lambda y eleva todas las abstracciones lambda a la parte superior de la expresión. Las abstracciones se traducen luego en funciones recursivas , lo que elimina las abstracciones lambda. El resultado es un programa funcional en la forma

• ${\displaystyle \operatorname {let} M\operatorname {in} N}$

donde M es una serie de definiciones de funciones y N es la expresión que representa el valor devuelto.

Por ejemplo,

${\displaystyle \operatorname {lambda-lift-tran} [\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))]\equiv \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p}$

Luego, la función meta de-let se puede utilizar para convertir el resultado nuevamente en cálculo lambda.

${\displaystyle \operatorname {de-let} [\operatorname {lambda-lift-tran} [\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))]]\equiv (\lambda p.(\lambda q.q\ p)\ \lambda p.\lambda f.(p\ f)\ (p\ f))\ \lambda f.\lambda x.f\ (x\ x)}$

El procesamiento de transformación de la expresión lambda es una serie de elevaciones. Cada elevación tiene,

• Una subexpresión elegida por la función lift-choice . La subexpresión debe elegirse de modo que pueda convertirse en una ecuación sin lambdas.
• La elevación se realiza mediante una llamada a la metafunción lambda-lift , descrita en la siguiente sección.

${\displaystyle {\begin{cases}\operatorname {lambda-lift-tran} [L]=\operatorname {drop-params-tran} [\operatorname {merge-let} [\operatorname {lambda-apply} [L]]]\\\operatorname {lambda-apply} [L]=\operatorname {lambda-process} [\operatorname {lift-choice} [L],L]\\\operatorname {lambda-process} [\operatorname {none} ,L]=L\\\operatorname {lambda-process} [S,L]=\operatorname {lambda-apply} [\operatorname {lambda-lift} [S,L]]\end{cases}}}$

Después de aplicar los elevadores, los lets se combinan para formar un solo let.

${\displaystyle {\begin{cases}\operatorname {merge-let} [\operatorname {let} V:E\operatorname {in} \operatorname {let} W:F\operatorname {in} G]=\operatorname {merge-let} [\operatorname {let} V,W:E\land F\operatorname {in} G]\\\operatorname {merge-let} [E]=E\end{cases}}}$

Luego, se aplica la eliminación de parámetros para eliminar los parámetros que no son necesarios en la expresión "let". La expresión let permite que las definiciones de funciones hagan referencia entre sí directamente, mientras que las abstracciones lambda son estrictamente jerárquicas y una función no puede hacer referencia directamente a sí misma.

Elegir la expresión para levantar

Hay dos formas diferentes de seleccionar una expresión para su levantamiento. La primera trata todas las abstracciones lambda como si definieran funciones anónimas. La segunda, trata las abstracciones lambda que se aplican a un parámetro como si definieran una función. Las abstracciones lambda aplicadas a un parámetro tienen una doble interpretación, ya sea como una expresión let que define una función o como una función anónima. Ambas interpretaciones son válidas.

Estos dos predicados son necesarios para ambas definiciones.

lambda-free : una expresión que no contiene abstracciones lambda.

${\displaystyle {\begin{cases}\operatorname {lambda-free} [\lambda F.X]=\operatorname {false} \\\operatorname {lambda-free} [V]=\operatorname {true} \\\operatorname {lambda-free} [M\ N]=\operatorname {lambda-free} [M]\land \operatorname {lambda-free} [N]\end{cases}}}$

lambda-anon : una función anónima. Una expresión como donde X es lambda libre. ${\displaystyle \lambda x_{1}.\ ...\ \lambda x_{n}.X}$

${\displaystyle {\begin{cases}\operatorname {lambda-anon} [\lambda F.X]=\operatorname {lambda-free} [X]\lor \operatorname {lambda-anon} [X]\\\operatorname {lambda-anon} [V]=\operatorname {false} \\\operatorname {lambda-anon} [M\ N]=\operatorname {false} \end{cases}}}$

Elegir funciones anónimas solo para elevación

Busque la abstracción anónima más profunda, de modo que cuando se aplique la elevación, la función elevada se convierta en una ecuación simple. Esta definición no reconoce una abstracción lambda con un parámetro como definitoria de una función. Se considera que todas las abstracciones lambda definen funciones anónimas.

lift-choice - El primer anónimo que se encuentra al recorrer la expresión o none si no hay ninguna función.

1. ${\displaystyle \operatorname {lambda-anon} [X]\to \operatorname {lift-choice} [X]=X}$
2. ${\displaystyle \operatorname {lift-choice} [\lambda F.X]=\operatorname {lift-choice} [X]}$
3. ${\displaystyle \operatorname {lift-choice} [M]\neq \operatorname {none} \to \operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [M]}$
4. ${\displaystyle \operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [N]}$
5. ${\displaystyle \operatorname {lift-choice} [V]=\operatorname {none} }$

Por ejemplo,

Elección de funciones nombradas y anónimas para el levantamiento

Busque la definición de función anónima o nombrada más profunda, de modo que cuando se aplique la elevación, la función elevada se convierta en una ecuación simple. Esta definición reconoce una abstracción lambda con un parámetro real como la definición de una función. Solo las abstracciones lambda sin una aplicación se tratan como funciones anónimas.

con nombre lambda

Una función nombrada. Una expresión como donde M es lambda libre y N es lambda libre o una función anónima. ${\displaystyle (\lambda F.M)\ N}$

${\displaystyle {\begin{array}{l}\operatorname {lambda-named} [(\lambda F.M)\ N]=\operatorname {lambda-free} [M]\land \operatorname {lambda-anon} [N]\\\operatorname {lambda-named} [\lambda F.X]=\operatorname {false} \\\operatorname {lambda-named} [V]=\operatorname {false} \end{array}}}$

elección de ascensor

La primera función anónima o con nombre que se encuentra al recorrer la expresión o ninguna si no hay ninguna función.

1. ${\displaystyle \operatorname {lambda-named} [X]\lor \operatorname {lambda-anon} [X]\to \operatorname {lift-choice} [X]=X}$
2. ${\displaystyle \operatorname {lift-choice} [\lambda F.X]=\operatorname {lift-choice} [X]}$
3. ${\displaystyle \operatorname {lift-choice} [M]\neq \operatorname {none} \to \operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [M]}$
4. ${\displaystyle \operatorname {lift-choice} [M\ N]=\operatorname {lift-choice} [N]}$
5. ${\displaystyle \operatorname {lift-choice} [V]=\operatorname {none} }$

Por ejemplo,

Ejemplos

Por ejemplo, el combinador Y ,

${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$

se levanta como,

${\displaystyle \operatorname {let} x\ f\ y=f\ (y\ y)\land q\ x\ f=f\ ((x\ f)\ (x\ f))\operatorname {in} q\ x}$

y después de eliminar los parámetros,

${\displaystyle \operatorname {let} x\ f\ y=f\ (y\ y)\land q\ f=f\ ((x\ f)\ (x\ f))\operatorname {in} q}$

Como expresión lambda (ver Conversión de expresiones let a lambda ),

${\displaystyle (\lambda x.(\lambda q.q)\ \lambda f.f\ (x\ f)\ (x\ f))\ \lambda f.\lambda y.f\ (y\ y)}$

Si solo se levantan funciones anónimas, el combinador Y es,

${\displaystyle \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p}$

y después de eliminar los parámetros,

${\displaystyle \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ f=(p\ f)\ (p\ f)\operatorname {in} q}$

Como expresión lambda,

${\displaystyle (\lambda p.(\lambda q.q)\ \lambda f.(p\ f)\ (p\ f))\ \lambda f.\lambda x.f\ (x\ x)}$

La primera subexpresión que se debe elegir para la elevación es . Esto transforma la expresión lambda en y crea la ecuación . ${\displaystyle \lambda x.f\ (x\ x)}$ ${\displaystyle \lambda f.(p\ f)\ (p\ f)}$ ${\displaystyle p\ f\ x=f(x\ x)}$

La segunda subexpresión que se debe elegir para la elevación es . Esto transforma la expresión lambda en y crea la ecuación . ${\displaystyle \lambda f.(p\ f)\ (p\ f)}$ ${\displaystyle q\ p}$ ${\displaystyle q\ p\ f=(p\ f)\ (p\ f)}$

Y el resultado es,

${\displaystyle \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p\ }$

Sorprendentemente, este resultado es más simple que el que se obtiene al levantar funciones nombradas.

Ejecución

Aplicar función a K ,

${\displaystyle {\begin{cases}\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))\ K&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\ \operatorname {in} \ q\ p\ K\\(\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x))&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\ \operatorname {in} \ p\ K\ (p\ K)\\K\ ((\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x)))&\ \operatorname {let} \ p\ f\ x=f\ (x\ x)\land q\ p\ f=p\ f\ (p\ f)\ \operatorname {in} \ K\ (p\ K\ (p\ K))\\\end{cases}}}$

Entonces,

${\displaystyle (\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x))=K\ ((\lambda x.K\ (x\ x))\ (\lambda x.K\ (x\ x))))\ }$

o

${\displaystyle p\ K\ (p\ K)=K\ (p\ K\ (p\ K))}$

El Y-Combinator llama a su parámetro (función) repetidamente sobre sí mismo. El valor se define si la función tiene un punto fijo . Pero la función nunca terminará.

Caída de lambda en el cálculo lambda

La eliminación de lambda ^[4] consiste en reducir el alcance de las funciones y utilizar el contexto del alcance reducido para reducir la cantidad de parámetros de las funciones. Al reducir la cantidad de parámetros, las funciones resultan más fáciles de comprender.

En la sección de elevación de Lambda, se describió una metafunción para primero elevar y luego convertir la expresión lambda resultante en una ecuación recursiva. La metafunción Lambda Drop realiza lo inverso convirtiendo primero las ecuaciones recursivas en abstracciones lambda y luego eliminando la expresión lambda resultante en el alcance más pequeño que cubre todas las referencias a la abstracción lambda.

La caída de lambda se realiza en dos pasos,

• Hundimiento
• Eliminación de parámetros

Caída de lambda

Se aplica una eliminación de Lambda a una expresión que forma parte de un programa. La eliminación se controla mediante un conjunto de expresiones de las que se excluirá la eliminación.

${\displaystyle \operatorname {lambda-drop-op} [L,P,X]=P[L:=\operatorname {drop-params-tran} [\operatorname {sink-test} [L,X]]]}$

dónde,

L es la abstracción lambda que se debe descartar.

P es el programa

X es un conjunto de expresiones que deben excluirse de la eliminación.

Transformación de caída de lambda

La transformación lambda drop elimina todas las abstracciones de una expresión. El hundimiento se excluye de las expresiones de un conjunto de expresiones.

${\displaystyle \operatorname {lambda-drop-tran} [L,X]=\operatorname {drop-params-tran} [\operatorname {sink-tran} [\operatorname {de-let} [L,X]]]}$

dónde,

L es la expresión a transformar.

X es un conjunto de subexpresiones que se excluirán de la eliminación.

hundir-tran hunde cada abstracción, empezando por lo más interno,

${\displaystyle {\begin{cases}\operatorname {sink-tran} [(\lambda N.B)\ Y,X]=\operatorname {sink-test} [(\lambda N.\operatorname {sink-tran} [B])\ \operatorname {sink-tran} [Y],X]\\\operatorname {sink-tran} [\lambda N.B,X]=\lambda N.\operatorname {sink-tran} [B,X]\\\operatorname {sink-tran} [M\ N,X]=\operatorname {sink-tran} [M,X]\ \operatorname {sink-tran} [M,X]\\\operatorname {sink-tran} [V,X]=V\end{cases}}}$

Abstracción hundiéndose

Hundir consiste en mover una abstracción lambda hacia adentro lo más lejos posible de modo que todavía esté fuera de todas las referencias a la variable.

Aplicación - 4 casos.

${\displaystyle {\begin{cases}E\not \in \operatorname {FV} [G]\land E\not \in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]=G\ H\\E\not \in \operatorname {FV} [G]\land E\in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]=\operatorname {sink-test} [G\ \operatorname {sink-test} [(\lambda E.H)\ Y,X]]\\E\in \operatorname {FV} [G]\land E\not \in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]=(\operatorname {sink-test} [(\lambda E.G)\ Y,X])\ H\\E\in \operatorname {FV} [G]\land E\in \operatorname {FV} [H]\to \operatorname {sink} [(\lambda E.G\ H)\ Y,X]=(\lambda E.G\ H)\ Y\end{cases}}}$

Abstracción . Utilice el cambio de nombre para garantizar que todos los nombres de las variables sean distintos.

${\displaystyle V\neq W\to \operatorname {sink} [(\lambda V.\lambda W.E)\ Y,X]=\lambda W.\operatorname {sink-test} [(\lambda V.E)\ Y,X]}$

Variable - 2 casos.

${\displaystyle E\neq V\to \operatorname {sink} [(\lambda E.V)\ Y,X]=V}$

${\displaystyle E=V\to \operatorname {sink} [(\lambda E.V)\ Y,X]=Y}$

La prueba de hundimiento excluye expresiones de la eliminación.

${\displaystyle L\in X\to \operatorname {sink-test} [L,X]=L}$

${\displaystyle L\not \in X\to \operatorname {sink-test} [L,X]=\operatorname {sink} [L,X]}$

Ejemplo

Eliminación de parámetros

La eliminación de parámetros consiste en optimizar una función para su posición en la función. La eliminación de Lambda agregó parámetros que eran necesarios para que una función pueda sacarse de su contexto. En la eliminación, este proceso se invierte y se pueden eliminar los parámetros adicionales que contienen variables que están libres.

Omitir un parámetro es quitar un parámetro innecesario de una función, donde el parámetro real que se pasa siempre es la misma expresión. Las variables libres de la expresión también deben ser libres donde se define la función. En este caso, el parámetro que se omite se reemplaza por la expresión en el cuerpo de la definición de la función. Esto hace que el parámetro sea innecesario.

Por ejemplo, considere,

${\displaystyle \lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y}$

En este ejemplo, el parámetro real del parámetro formal o es siempre p . Como p es una variable libre en toda la expresión, el parámetro puede omitirse. El parámetro real del parámetro formal y es siempre n . Sin embargo, n está ligado en una abstracción lambda. Por lo tanto, este parámetro no puede omitirse.

El resultado de eliminar el parámetro es:

${\displaystyle \operatorname {drop-params-tran} [\lambda m,p,q.(\lambda g.\lambda n.n\ (g\ m\ p\ n)\ (g\ q\ p\ n))\ \lambda x.\lambda o.\lambda y.o\ x\ y}$

${\displaystyle \equiv \lambda m,p,q.(\lambda g.\lambda n.n\ (g\ m\ n)\ (g\ q\ n))\ \lambda x.\lambda y.p\ x\ y}$

Para el ejemplo principal,

${\displaystyle \operatorname {drop-params-tran} [\lambda f.(\lambda p.(p\ f)\ (p\ f))\ (\lambda f.\lambda x.f\ (x\ x))]}$

${\displaystyle \equiv \lambda f.(\lambda p.p\ p)\ (\lambda x.f\ (x\ x))}$

La definición de drop-params-tran es,

${\displaystyle \operatorname {drop-params-tran} [L]\equiv (\operatorname {drop-params} [L,D,FV[L],[]])}$

dónde,

${\displaystyle \operatorname {build-param-list} [L,D,V,\_]}$

Crear listas de parámetros

Para cada abstracción que define una función, genere la información necesaria para tomar decisiones sobre la eliminación de nombres. Esta información describe cada parámetro: el nombre del parámetro, la expresión para el valor real y una indicación de que todas las expresiones tienen el mismo valor.

Por ejemplo, en,

${\displaystyle \lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y}$

Los parámetros de la función g son,

Cada abstracción se renombra con un nombre único y la lista de parámetros se asocia con el nombre de la abstracción. Por ejemplo, g tiene una lista de parámetros.

${\displaystyle D[g]=[[x,\operatorname {false} ,\_],[o,\_,p],[y,\_,n]]}$

build-param-lists construye todas las listas de una expresión recorriendo la expresión. Tiene cuatro parámetros:

• La expresión lambda que se está analizando.
• Los parámetros de la tabla enumeran los nombres.
• La tabla de valores para los parámetros.
• La lista de parámetros devueltos, que se utiliza internamente por el

Abstracción : se analiza una expresión lambda de la forma para extraer los nombres de los parámetros de la función. ${\displaystyle (\lambda N.S)\ L}$

${\displaystyle {\begin{cases}\operatorname {build-param-lists} [(\lambda N.S)\ L,D,V,R]\equiv \operatorname {build-param-lists} [S,D,V,R]\land \operatorname {build-list} [L,D,V,D[N]]\\\operatorname {build-param-lists} [\lambda N.S,D,V,R]\equiv \operatorname {build-param-lists} [S,D,V,R]\end{cases}}}$

Localice el nombre y comience a crear la lista de parámetros para el nombre, completando los nombres de parámetros formales. Reciba también cualquier lista de parámetros real del cuerpo de la expresión y devuélvala como la lista de parámetros real de esta expresión

${\displaystyle {\begin{cases}\operatorname {build-list} [\lambda P.B,D,V,[X,\_,\_]::L]\equiv \operatorname {build-list} [B,D,V,L]\\\operatorname {build-list} [B,D,V,[]]\equiv \operatorname {build-param-lists} [B,D,V,\_]\end{cases}}}$

Variable : Una llamada a una función.

${\displaystyle \operatorname {build-param-lists} [N,D,V,D[N]]}$

Para un nombre de función o parámetro, comience a completar la lista de parámetros real generando la lista de parámetros para este nombre.

Aplicación : se procesa una aplicación (llamada de función) para extraer detalles de los parámetros reales.

${\displaystyle \operatorname {build-param-lists} [E\ P,D,V,R]\equiv \operatorname {build-param-lists} [E,D,V,T]\land \operatorname {build-param-lists} [P,D,V,K]}$

${\displaystyle \land T=[F,S,A]::R\land (S\implies (\operatorname {equate} [A,P]\land V[F]=A))\land D[F]=K}$

Recupere las listas de parámetros para la expresión y el parámetro. Recupere un registro de parámetro de la lista de parámetros de la expresión y verifique que el valor del parámetro actual coincida con este parámetro. Registre el valor del nombre del parámetro para usarlo más adelante en la verificación.

${\displaystyle {\begin{cases}\operatorname {equate} [A,N]\equiv A=N\lor (\operatorname {def} [V[N]]\land A=V[N])&{\text{if }}N{\text{ is a variable.}}\\\operatorname {equate} [A,E]\equiv A=E&{\text{otherwise.}}\end{cases}}}$

La lógica anterior es bastante sutil en su funcionamiento. El mismo indicador de valor nunca se establece en verdadero. Solo se establece en falso si no se pueden hacer coincidir todos los valores. El valor se recupera utilizando S para crear un conjunto de valores booleanos permitidos para S. Si true es un miembro, entonces todos los valores para este parámetro son iguales y el parámetro puede descartarse.

${\displaystyle \operatorname {ask} [S]\equiv S\in \{X:X=S\}}$

De manera similar, def utiliza la teoría de conjuntos para consultar si a una variable se le ha dado un valor;

${\displaystyle \operatorname {def} [F]\equiv |\{X:X=F\}|}$

Let - Expresión Let.

${\displaystyle \operatorname {build-param-list} [\operatorname {let} V:E\operatorname {in} L,D,V,\_]\equiv \operatorname {build-param-list} [E,D,V,\_]\land \operatorname {build-param-list} [L,D,V,\_]}$

Y - Para usar en "dejar".

${\displaystyle \operatorname {build-param-lists} [E\land F,D,V,\_]\equiv \operatorname {build-param-lists} [E,D,V,\_]\land \operatorname {build-param-lists} [F,D,V,\_]}$

Ejemplos

Por ejemplo, crear las listas de parámetros para,

${\displaystyle \lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ p\ n)\ (g\ q\ p\ n)))\ \lambda x.\lambda o.\lambda y.o\ x\ y}$

da,

${\displaystyle D[g]=[[x,\operatorname {false} ,\_],[o,\operatorname {true} ,p],[y,\operatorname {true} ,n]]}$

y se elimina el parámetro o para dar,

${\displaystyle \lambda m,p,q.(\lambda g.\lambda n.(n\ (g\ m\ n)\ (g\ q\ n)))\ \lambda x.\lambda y.p\ x\ y}$

Otro ejemplo es,

${\displaystyle \lambda f.((\lambda p.f\ (p\ p\ f))\ (\lambda q.\lambda x.x\ (q\ q\ x))}$

Aquí x es igual a f. La asignación de la lista de parámetros es,

${\displaystyle D[p]=[[q,\_,p],[x,\_,f]]}$

y se elimina el parámetro x para dar,

${\displaystyle \lambda f.((\lambda q.f\ (q\ q))\ (\lambda q.f\ (q\ q))}$

Parámetros de caída

Utilice la información obtenida mediante las listas de parámetros de creación para eliminar los parámetros reales que ya no son necesarios. drop-params tiene los parámetros,

• La expresión lambda en la que se deben eliminar los parámetros.
• La asignación de nombres de variables a listas de parámetros (integrada en Crear listas de parámetros).
• El conjunto de variables libres en la expresión lambda.
• Lista de parámetros devueltos. Un parámetro utilizado internamente en el algoritmo.

Abstracción

${\displaystyle \operatorname {drop-params} [(\lambda N.S)\ L,D,V,R]\equiv (\lambda N.\operatorname {drop-params} [S,D,F,R])\ \operatorname {drop-formal} [D[N],L,F]}$

dónde,

${\displaystyle F=FV[(\lambda N.S)\ L]}$

${\displaystyle \operatorname {drop-params} [\lambda N.S,D,V,R]\equiv (\lambda N.\operatorname {drop-params} [S,D,F,R])}$

dónde,

${\displaystyle F=FV[\lambda N.S]}$

Variable

${\displaystyle \operatorname {drop-params} [N,D,V,D[N]]\equiv N}$

Para un nombre de función o parámetro, comience a completar la lista de parámetros real generando la lista de parámetros para este nombre.

Aplicación : se procesa una aplicación (llamada de función) para extraer

${\displaystyle (\operatorname {def} [F]\land \operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-params} [E\ P,D,V,R]\equiv \operatorname {drop-params} [E,D,V,[F,S,A]::R]}$

${\displaystyle \neg (\operatorname {def} [F]\land \operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-params} [E\ P,D,V,R]\equiv \operatorname {drop-params} [E,D,V,[F,S,A]::R]\ \operatorname {drop-params} [P,D,V,\_]}$

Let - Expresión Let.

${\displaystyle \operatorname {drop-params} [\operatorname {let} V:E\operatorname {in} L]\equiv \operatorname {let} V:\operatorname {drop-params} [E,D,FV[E],[]]\operatorname {in} \operatorname {drop-params} [L,D,FV[L],[]]}$

Y - Para usar en "dejar".

${\displaystyle \operatorname {drop-params} [E\land F,D,V,\_]\equiv \operatorname {drop-params} [E,D,V,\_]\land \operatorname {drop-params} [F,D,V,\_]}$

Eliminar parámetros formales

drop-formal elimina los parámetros formales en función del contenido de las listas desplegables. Sus parámetros son:

• La lista desplegable,
• La definición de función (abstracción lambda).
• Las variables libres de la definición de la función.

El formalismo se define como,

1. ${\displaystyle (\operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-formal} [[F,S,A]::Z,\lambda F.Y,V]\equiv \operatorname {drop-formal} [[F,S,A]::Z,Y[F:=A],L]}$
2. ${\displaystyle \neg (\operatorname {ask} [S]\land FV[A]\subset V)\to \operatorname {drop-formal} [[F,S,A]::Z,\lambda F.Y,V]\equiv \lambda F.\operatorname {drop-formal} [[F,S,A]::Z,Y,V]}$
3. ${\displaystyle \operatorname {drop-formal} [Z,Y,V]\equiv Y}$

Lo cual se puede explicar como,

1. Si todos los parámetros reales tienen el mismo valor y todas las variables libres de ese valor están disponibles para la definición de la función, elimine el parámetro y reemplace el parámetro antiguo con su valor.
2. De lo contrario, no elimine el parámetro.
3. de lo contrario, devuelve el cuerpo de la función.

Ejemplo

Comenzando con la definición de la función del combinador Y,

${\displaystyle \operatorname {let} p\ f\ x=f\ (x\ x)\land q\ p\ f=(p\ f)\ (p\ f)\operatorname {in} q\ p\ }$

Lo que devuelve el combinador Y ,

${\displaystyle \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$

Véase también

• Sea expresión
• Combinador de punto fijo
• Cálculo lambda
• Cálculo lambda deductivo
• Supercombinador
• La paradoja de Curry

Referencias

1. Johnsson, Thomas (1985). "Lambda Lifting: Transforming Programs to Recursive Equations". En Jouannaud, JP (ed.). Lenguajes de programación funcional y arquitectura informática. FPCA 1985. Lecture Notes in Computer Science. Vol. 201. Springer. CiteSeerX  10.1.1.48.4346 . doi :10.1007/3-540-15975-4_37. ISBN . 3-540-15975-4.
2. Morazán, Marco T.; Schultz, Ulrik P. (2008), "Optimal Lambda Lifting in Quadratic Time", Implementation and Application of Functional Languages ​​— Revised Selected Papers , págs. 37–56, doi :10.1007/978-3-540-85373-2_3, ISBN 978-3-540-85372-5
3. Danvy, O.; Schultz, UP (1997). "Lambda-dropping". Avisos SIGPLAN de la ACM . 32 (12): 90. doi : 10.1145/258994.259007 .
4. Danvy, Olivier; Schultz, Ulrik P. (octubre de 2000). "Lambda-Dropping: Transforming Recursive Equations into Programs with Block Structure" (PDF) . Ciencias de la computación teórica . 248 (1–2): 243–287. CiteSeerX 10.1.1.16.3943 . doi :10.1016/S0304-3975(00)00054-2. BRICS-RS-99-27. 

Enlaces externos

• Explicación sobre Stack Overflow, con un ejemplo de JavaScript
• Slonneger, Ken; Kurtz, Barry. "5. Algunas discusiones sobre expresiones let" (PDF) . Fundamentos de lenguajes de programación . Universidad de Iowa.