La elevación de lambda es un metaproceso que reestructura un programa informático para que las funciones se definan de forma independiente entre sí en un ámbito global . Un "ascensor" individual transforma una función local en una función global. Es un proceso de dos pasos, que consiste en;
- Eliminando variables libres en la función agregando parámetros.
- Mover funciones de un ámbito restringido a un ámbito más amplio o global.
El término "elevación lambda" fue introducido por primera vez por Thomas Johnsson alrededor de 1982 e históricamente se consideró como un mecanismo para implementar lenguajes de programación funcionales . 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 llamadas (agregando argumentos adicionales a las llamadas) y no introduce un cierre para la expresión lambda levantada. Por el contrario, la conversión de cierre no requiere que se ajusten los sitios de llamada, pero introduce un cierre para la expresión lambda que correlaciona las variables libres con los valores.
La técnica se puede 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 se escribió. Las elevaciones lambda también pueden repetirse para transformar el programa. Se pueden usar elevaciones repetidas para convertir un programa escrito en cálculo lambda en un conjunto de funciones recursivas , sin lambdas. Esto demuestra la equivalencia de programas escritos en cálculo lambda y 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, ya que elimina el valor de la variable, sin comprobar primero que existe es solo un valor que satisface las condiciones de la variable (ver la paradoja de Curry ).
La elevación de lambda es costosa en el tiempo de procesamiento para el compilador. Una implementación eficiente de la elevación lambda esen el tiempo de procesamiento para el compilador. [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. Ver también igualdad intensional versus extensional .
La operación inversa a la elevación lambda es la caída 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 el número de parámetros y reducir el tamaño de los marcos de pila. Sin embargo, dificulta la reutilización de 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 levantar un programa arbitrario en un lenguaje que no admite cierres como objetos de primera clase :
- Cambie el nombre de las funciones para que cada función tenga un nombre único.
- Reemplace cada variable libre con un argumento adicional a la función adjunta y pase ese argumento a cada uso de la función.
- Reemplace cada definición de función local que no tenga variables libres con una función global idéntica.
- Repita los pasos 2 y 3 hasta que se eliminen 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 let rec
declara sum
como una función que puede llamarse a sí misma.) La función f, que agrega 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. Empiece por convertir 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, levante f en una función global:
sea rec f w x = w + x y sume n = si n = 1 entonces 1 de lo contrario f n ( sum ( 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 ) { retorno 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 ) { retorno w + x ; } si ( n == 1 ) devuelve 1 ; de lo contrario, devuelve f ( n , sum ( n - 1 )); }// Después de elevar la función f al ámbito globalfunción f ( w , x ) { return w + x ; }function sum ( n ) { if ( n == 1 ) return 1 ; de lo contrario, devuelve f ( n , sum ( n - 1 )); }
Levantamiento lambda versus cierres
La elevación y el cierre de lambda son métodos para implementar programas estructurados por bloques . Implementa la estructura de bloques eliminándola. Todas las funciones se elevan a nivel global. La conversión de cierre proporciona un "cierre" que vincula el fotograma actual con otros fotogramas. 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 usando una implementación basada en pila , que es simple y eficiente. Sin embargo, una implementación basada en marcos de pila debe ser estricta (ansiosa) . La implementación basada en marcos de pila requiere que la vida útil de las funciones sea el último en entrar , el primero en salir (LIFO). Es decir, la función más reciente para iniciar su cálculo debe ser la primera en finalizar.
Algunos lenguajes funcionales (como Haskell ) se implementan mediante la evaluación diferida , que retrasa el cálculo hasta que se necesita el valor. La estrategia de implementación perezosa da flexibilidad al programador. La evaluación diferida requiere retrasar la llamada a una función hasta que se realice una solicitud al valor calculado por la función. Una implementación es registrar una referencia a un "marco" de datos que describen 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 sea necesario. El valor calculado reemplaza a 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 está "levantada", 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 la pila para administrar la vida de las variables. En un entorno administrado de recolección de basura, un cierre registra referencias a los marcos de los cuales se pueden obtener los valores. Por el contrario, una función elevada tiene parámetros para cada valor necesario en el cálculo.
Deje que las expresiones y el cálculo lambda
La expresión Let es útil para describir la elevación y 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 que también permiten la definición local de una función para su uso en un ámbito restringido .
La expresión let usada aquí es una versión recursiva de let rec , implementada en muchos lenguajes funcionales.
Deje que las expresiones estén relacionadas con el cálculo Lambda . El cálculo de Lambda tiene una sintaxis y una semántica simples, y es bueno para describir el levantamiento de Lambda. Es conveniente describir la elevación de lambda como una traducción de lambda a una expresión let , y la caída de lambda como lo contrario. Esto se debe a que las expresiones let permiten la recursividad mutua, lo que, en cierto sentido, es más elevado de lo que se admite en el cálculo lambda. El cálculo lambda no admite la recursividad 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 dan en el artículo Let expression .
Las siguientes reglas describen la equivalencia de lambda y let expresiones,
Nombre | Ley |
---|---|
Equivalencia de reducción de eta | |
Equivalencia Let-Lambda | |
Deje la combinación |
Se proporcionarán metafunciones que describen la elevación y 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.
Las siguientes convenciones se utilizarán para distinguir el programa del metaprograma,
- Los corchetes [] se utilizarán para representar la aplicación de la función en el metaprograma.
- Se utilizarán letras mayúsculas para las variables en el metaprograma. Las letras minúsculas representan variables en el programa.
- se utilizará para iguales en el metaprograma.
- representa una variable ficticia o un valor desconocido.
Para simplificar la primera regla dada que se aplicarán las coincidencias. Las reglas también asumen que las expresiones lambda se han procesado previamente para que cada abstracción lambda tenga un nombre único.
El operador de sustitución se utiliza ampliamente. La expresionsignifica sustituir cada aparición de G en L por S y devolver la expresión. La definición utilizada se amplía para cubrir la sustitución de expresiones, a partir de la definición dada en la página de cálculo Lambda . La coincidencia de expresiones debe comparar expresiones para la equivalencia alfa (cambio de nombre de las variables).
Elevación lambda en cálculo lambda
Cada elevación lambda toma una abstracción lambda que es una subexpresión de una expresión 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 a la función.
Las elevaciones de Lambda se pueden usar en funciones individuales, en la refactorización de código , para hacer que una función sea utilizable fuera del alcance en el que se escribió. Estos ascensores también pueden repetirse, hasta que la expresión no tenga abstracciones lambda, para transformar el programa.
Elevación lambda
A una elevación se le da una subexpresión dentro de una expresión para elevarla a la parte superior de esa expresión. La expresión puede ser parte de un programa más amplio. Esto permite controlar el lugar al que se eleva la subexpresión. La operación de elevación lambda utilizada para realizar una elevación dentro de un programa es,
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.
Un ascensor anónimo tiene una expresión de ascensor 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.
Elevación anónima
Un ascensor anónimo toma una abstracción lambda (llamada S ). Para S ;
- Cree un nombre para la función que reemplazará a S (llamada V ). Asegúrese 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.
La nueva expresión lambda ha S sustituido por G. Obsérvese que L [ S : = G ] significa la sustitución de S por G en L . Las definiciones de función tienen agregada la definición de función G = S.
En la regla anterior G es la aplicación de la función que se sustituye por la expresión S . Está definido por,
donde V es el nombre de la función. Debe ser una nueva variable, es decir, un nombre que no se haya utilizado ya en la expresión lambda,
dónde es una función de meta que devuelve el conjunto de variables utilizadas en E .
Ejemplo de ascensor anónimo. |
---|
Por ejemplo, Consulte de-lambda en Conversión de lambda para dejar expresiones . El resultado es, |
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 ,
Ejemplo de construcción de llamada. |
---|
Elevación con nombre
El ascensor nombrado es similar al ascensor anónimo, excepto que se proporciona el nombre de función V.
En cuanto a la elevación anónima, la expresión G se construye a partir de V mediante la aplicación de las variables libres de S . Está definido por,
Ejemplo de elevación con nombre. |
---|
Por ejemplo, Consulte de-lambda en Conversión de lambda para dejar expresiones . El resultado es, da, |
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 luego se traducen en funciones recursivas , lo que elimina las abstracciones lambda. El resultado es un programa funcional en la forma,
donde M es una serie de definiciones de funciones y N es la expresión que representa el valor devuelto.
Por ejemplo,
La metafunción de-let se puede usar para convertir el resultado de nuevo en cálculo lambda.
El procesamiento de la transformación de la expresión lambda es una serie de elevaciones. Cada ascensor tiene,
- Una subexpresión elegida para él por la función lift-choice . La subexpresión debe elegirse de modo que pueda convertirse en una ecuación sin lambdas.
- El levantamiento se realiza mediante una llamada a la metafunción lambda-lift , que se describe en la siguiente sección,
Después de que se aplican los ascensores, los permite se combinan en uno solo.
Luego de parámetros de goteo se aplica para eliminar parámetros que no son necesarios en la expresión "dejar". La expresión let permite que las definiciones de funciones se refieran entre sí directamente, mientras que las abstracciones lambda son estrictamente jerárquicas y una función puede no referirse directamente a sí misma.
Elegir la expresión para levantar
Hay dos formas diferentes de seleccionar una expresión para levantar. El primero trata todas las abstracciones lambda como si fueran funciones anónimas. El segundo, 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 interpretación dual 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.
lambda-anon : una función anónima. Una expresión como donde X es libre de lambda.
Elegir funciones anónimas solo para levantar
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 definición 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 atravesar la expresión o ninguno si no hay función.
Por ejemplo,
Regla | tipo de función | elección |
---|---|---|
2 | ||
3 | ||
1 | luego | |
Regla | tipo de función | elección |
---|---|---|
2 | luego | |
2 |
Elección de funciones con nombre y anónimas para levantar
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 definición de una función. Solo las abstracciones lambda sin una aplicación se tratan como funciones anónimas.
- lambda-named
- Una función con nombre. Una expresión como donde M es libre de lambda y N es libre de lambda o una función anónima.
- Elevación de elección
- La primera función anónima o nombrada que se encuentra al atravesar la expresión o ninguna si no hay función.
Por ejemplo,
Regla | tipo de función | elección |
---|---|---|
2 | ||
1 | llamado | |
Regla | tipo de función | elección |
---|---|---|
1 | luego | |
Ejemplos de
Por ejemplo, el combinador Y ,
se levanta como,
y después de la caída de parámetros ,
Como expresión lambda (consulte Conversión de expresiones let a lambda ),
Expresión Lambda | Función | De | A | Variables | |
---|---|---|---|---|---|
1 | cierto | ||||
2 |
| ||||
3 | |||||
4 | |||||
5 |
Si solo levanta funciones anónimas, el combinador Y es,
y después de la caída de parámetros ,
Como expresión lambda,
Expresión Lambda | Función | De | A | Variables | |
---|---|---|---|---|---|
1 | cierto | ||||
2 | |||||
3 | |||||
4 | |||||
5 |
La primera subexpresión que se debe elegir para el levantamiento es . Esto transforma la expresión lambda en y crea la ecuación .
La segunda subexpresión a elegir para el levantamiento es . Esto transforma la expresión lambda en y crea la ecuación .
Y el resultado es
Sorprendentemente, este resultado es más simple que el obtenido al levantar funciones nombradas.
Ejecución
Aplicar la función a K ,
Entonces,
o
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á.
Lambda cayendo en el cálculo lambda
La eliminación de Lambda [4] es reducir el alcance de las funciones y utilizar el contexto del alcance reducido para reducir el número de parámetros a funciones. Reducir el número de parámetros facilita la comprensión de las funciones.
En la sección de elevación de Lambda , se describió una metafunción para primero levantar y luego convertir la expresión lambda resultante en una ecuación recursiva. La metafunción Lambda Drop realiza lo contrario al convertir primero ecuaciones recursivas en abstracciones lambda y luego soltar la expresión lambda resultante en el ámbito 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
- Caída de parámetros
Gota lambda
Se aplica una caída 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.
dónde,
- L es la abstracción lambda que se eliminará.
- P es el programa
- X es un conjunto de expresiones que deben excluirse del descarte.
Transformación de gota lambda
La transformación de caída lambda hunde todas las abstracciones en una expresión. El hundimiento se excluye de las expresiones en un conjunto de expresiones,
dónde,
- L es la expresión a transformar.
- X es un conjunto de subexpresiones que se excluirán del descarte.
sumidero-tran hunde cada abstracción, comenzando desde lo más interno,
La abstracción se hunde
El hundimiento es mover una abstracción lambda hacia adentro tanto como sea posible, de modo que todavía esté fuera de todas las referencias a la variable.
Aplicación - 4 casos.
Abstracción . Utilice el cambio de nombre para asegurarse de que los nombres de las variables sean todos distintos.
Variable - 2 casos.
La prueba de sumidero excluye expresiones de caída,
Ejemplo
Ejemplo de hundimiento | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Por ejemplo,
|
Caída de parámetros
La eliminación de parámetros está optimizando una función para su posición en la función. La elevación de Lambda agregó parámetros que eran necesarios para que una función se pueda mover fuera de su contexto. Al soltar, este proceso se invierte y se pueden eliminar los parámetros adicionales que contienen variables que están libres.
Eliminar un parámetro es eliminar un parámetro innecesario de una función, donde el parámetro real que se pasa es siempre 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 elimina 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
En este ejemplo, el parámetro real para el parámetro formal o es siempre p . Como p es una variable libre en toda la expresión, el parámetro puede descartarse. El parámetro real para el parámetro formal y es siempre n . Sin embargo, n está vinculado en una abstracción lambda. Por lo tanto, este parámetro no se puede eliminar.
El resultado de eliminar el parámetro es,
Para el ejemplo principal,
La definición de drop-params-tran es,
dónde,
Crear listas de parámetros
Para cada abstracción que define una función, cree 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 del valor real y una indicación de que todas las expresiones tienen el mismo valor.
Por ejemplo, en,
los parámetros de la función g son,
Parámetro formal | Todo el mismo valor | Expresión de parámetro real |
---|---|---|
X | falso | _ |
o | cierto | pag |
y | cierto | norte |
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 hay una lista de parámetros.
build-param-lists crea todas las listas para una expresión, atravesando la expresión. Tiene cuatro parámetros;
- La expresión lambda que se analiza.
- El parámetro de la tabla enumera los nombres.
- La tabla de valores de los parámetros.
- La lista de parámetros devuelta, que es utilizada internamente por el
Abstracción : una expresión lambda de la forma. se analiza para extraer los nombres de los parámetros de la función.
Busque el nombre y comience a construir la lista de parámetros para el nombre, completando los nombres formales de los parámetros. También reciba 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
Variable : una llamada a una funció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 los detalles reales del parámetro.
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 actual del parámetro coincida con este parámetro. Registre el valor del nombre del parámetro para usarlo más adelante en la verificación.
La lógica anterior es bastante sutil en la forma en que funciona. 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 mediante el uso de S para construir un conjunto de los valores booleanos permitidos para S . Si true es un miembro, entonces todos los valores de este parámetro son iguales y el parámetro puede descartarse.
De manera similar, def usa la teoría de conjuntos para consultar si a una variable se le ha dado un valor;
Let - Let expresión.
Y - Para usar en "dejar".
Ejemplos de
Por ejemplo, la creación de listas de parámetros para,
da,
y el parámetro o se elimina para dar,
Crear lista de parámetros para | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Ejemplo de lista de parámetros de construcción | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Da,
Como no existen definiciones para, , luego igualar se puede simplificar a, Al eliminar las expresiones que no son necesarias,
Comparando las dos expresiones para , obtener, Si es verdad; Si es falso no hay implicación. Entonces lo que significa que puede ser verdadero o falso. Si es verdad; Si es verdad; Entonces Es falso. El resultado es,
Por argumentos similares a los utilizados anteriormente, obtenga, y de anteriormente, |
Otro ejemplo es
Aquí x es igual af. El mapeo de la lista de parámetros es,
y el parámetro x se elimina para dar,
Crear lista de parámetros para | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
La lógica en equivalencia se utiliza en este ejemplo más difícil.
Después de recopilar los resultados juntos, De las dos definiciones de ; entonces Utilizando y comparando con lo anterior, entonces, en, reduce a, además, reduce a, Entonces, la lista de parámetros para p es efectivamente; |
Parámetros de caída
Utilice la información obtenida por las listas de parámetros de Build 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 eliminarán los parámetros.
- El mapeo de nombres de variables a listas de parámetros (construido en listas de parámetros de Build).
- El conjunto de variables libres en la expresión lambda.
- La lista de parámetros devuelta. Un parámetro utilizado internamente en el algoritmo.
Abstracción
dónde,
dónde,
Variable
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
Let - Let expresión.
Y - Para usar en "dejar".
Eliminar parámetros de las aplicaciones | |||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
A partir de los resultados de la creación de listas de parámetros; entonces, entonces,
|
Eliminar parámetros formales
drop-formal elimina los parámetros formales, basados en el contenido de las listas de drop. 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.
drop-formal se define como,
Que se puede explicar como,
- 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 anterior con su valor.
- de lo contrario, no elimine el parámetro.
- de lo contrario, devuelve el cuerpo de la función.
Condición | Expresión |
---|---|
) | |
Ejemplo
Comenzando con la definición de función del combinador Y,
Transformación | Expresión |
---|---|
resumen * 4 | |
lambda-resumen-tran | |
fregadero-tran | |
fregadero-tran | |
drop-param | |
beta-redex |
Lo que devuelve el combinador Y ,
Ver también
- Dejemos expresión
- Combinador de punto fijo
- Cálculo lambda
- Cálculo lambda deductivo
- Supercombinador
- La paradoja de curry
Referencias
- ^ Johnsson, Thomas (1985), "Lambda Lifting: Transformar programas en ecuaciones recursivas", Conf. en Func. Prog. Lenguajes y Arquitectura de Computadores. , Prensa ACM, CiteSeerX 10.1.1.48.4346
- ^ Elevación óptima de Lambda en tiempo cuadrático , págs. 37–56, doi : 10.1007 / 978-3-540-85373-2_3 , ISBN 978-3-540-85372-5 Parámetro desconocido
|book-title=
ignorado ( ayuda ) - ^ Danvy, O .; Schultz, UP (1997). "Lanzamiento de lambda". Avisos ACM SIGPLAN . 32 (12): 90. doi : 10.1145 / 258994.259007 .
- ^ Danvy, Olivier; Schultz, Ulrik P. (2001). Eliminación de Lambda: Transformación de ecuaciones recursivas en programas con estructura de bloques (PDF) .
enlaces externos
- Explicación sobre Stack Overflow, con un ejemplo de JavaScript
- Alguna discusión sobre las expresiones let