Lambda lifting (original) (raw)
Lambda lifting is a meta-process that restructures a computer program so that functions are defined independently of each other in a global scope. An individual "lift" transforms a local function into a global function. It is a two step process, consisting of; * Eliminating free variables in the function by adding parameters. * Moving functions from a restricted scope to broader or global scope. Lambda lifting is expensive on processing time for the compiler. An efficient implementation of lambda lifting is on processing time for the compiler. The reverse operation to lambda lifting is .
| Property | Value |
|---|---|
| dbo:abstract | Lambda lifting is a meta-process that restructures a computer program so that functions are defined independently of each other in a global scope. An individual "lift" transforms a local function into a global function. It is a two step process, consisting of; * Eliminating free variables in the function by adding parameters. * Moving functions from a restricted scope to broader or global scope. The term "lambda lifting" was first introduced by Thomas Johnsson around 1982 and was historically considered as a mechanism for implementing functional programming languages. It is used in conjunction with other techniques in some modern compilers. Lambda lifting is not the same as closure conversion. It requires all call sites to be adjusted (adding extra arguments to calls) and does not introduce a closure for the lifted lambda expression. In contrast, closure conversion does not require call sites to be adjusted but does introduce a closure for the lambda expression mapping free variables to values. The technique may be used on individual functions, in code refactoring, to make a function usable outside the scope in which it was written. Lambda lifts may also be repeated, in order to transform the program. Repeated lifts may be used to convert a program written in lambda calculus into a set of recursive functions, without lambdas. This demonstrates the equivalence of programs written in lambda calculus and programs written as functions. However it does not demonstrate the soundness of lambda calculus for deduction, as the eta reduction used in lambda lifting is the step that introduces cardinality problems into the lambda calculus, because it removes the value from the variable, without first checking that there is only one value that satisfies the conditions on the variable (see Curry's paradox). Lambda lifting is expensive on processing time for the compiler. An efficient implementation of lambda lifting is on processing time for the compiler. In the untyped lambda calculus, where the basic types are functions, lifting may change the result of beta reduction of a lambda expression. The resulting functions will have the same meaning, in a mathematical sense, but are not regarded as the same function in the untyped lambda calculus. See also intensional versus extensional equality. The reverse operation to lambda lifting is . Lambda dropping may make the compilation of programs quicker for the compiler, and may also increase the efficiency of the resulting program, by reducing the number of parameters, and reducing the size of stack frames.However it makes a function harder to re-use. A dropped function is tied to its context, and can only be used in a different context if it is first lifted. (en) |
| dbo:wikiPageExternalLink | http://homepage.cs.uiowa.edu/~slonnegr/plf/Lecture05.pdf https://stackoverflow.com/questions/592584/what-is-lambda-lifting/592634%23592634 |
| dbo:wikiPageID | 2230361 (xsd:integer) |
| dbo:wikiPageLength | 74846 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124921442 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Lambda_calculus dbr:Curry's_paradox dbr:Deductive_lambda_calculus dbr:Let_expression dbr:LIFO_(computing) dbr:Compiler dbr:Closure_(computer_science) dbr:Call_site dbr:Call_stack dbr:Stack_frame dbr:Subroutine dbr:Closure_(computer_programming) dbr:Computer_program dbr:Function_pointer dbc:Implementation_of_functional_programming_languages dbr:Garbage_collection_(computer_science) dbr:Eager_evaluation dbr:Lazy_evaluation dbr:ALGOL dbr:Fixed_point_(mathematics) dbr:Pascal_(programming_language) dbr:Functional_programming_language dbr:Haskell_(programming_language) dbr:JavaScript dbc:Compiler_construction dbr:Lambda_calculus dbr:Block_(programming) dbr:Code_refactoring dbr:Metaprogramming dbr:OCaml dbr:Recursion_(computer_science) dbr:Scope_(computer_science) dbr:Fixed-point_combinator dbr:Supercombinator dbr:Free_variables dbr:First-class_object dbr:Beta-reduction |
| dbp:wikiPageUsesTemplate | dbt:No2 dbt:Cite_web dbt:Mvar dbt:Reflist dbt:Short_description dbt:Yes2 |
| dcterms:subject | dbc:Lambda_calculus dbc:Implementation_of_functional_programming_languages dbc:Compiler_construction |
| rdfs:comment | Lambda lifting is a meta-process that restructures a computer program so that functions are defined independently of each other in a global scope. An individual "lift" transforms a local function into a global function. It is a two step process, consisting of; * Eliminating free variables in the function by adding parameters. * Moving functions from a restricted scope to broader or global scope. Lambda lifting is expensive on processing time for the compiler. An efficient implementation of lambda lifting is on processing time for the compiler. The reverse operation to lambda lifting is . (en) |
| rdfs:label | Lambda lifting (en) |
| owl:sameAs | freebase:Lambda lifting wikidata:Lambda lifting https://global.dbpedia.org/id/4pzzM |
| prov:wasDerivedFrom | wikipedia-en:Lambda_lifting?oldid=1124921442&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Lambda_lifting |
| is dbo:wikiPageDisambiguates of | dbr:Lifting |
| is dbo:wikiPageRedirects of | dbr:Closure_conversion dbr:Lambda_Lifting dbr:Lambda_lift dbr:Λ-lifting |
| is dbo:wikiPageWikiLink of | dbr:Let_expression dbr:Free_variables_and_bound_variables dbr:Closure_(computer_programming) dbr:Function_object dbr:Closure_conversion dbr:Church_encoding dbr:Nested_function dbr:Lifting dbr:Fixed-point_combinator dbr:Racket_features dbr:Supercombinator dbr:Lambda_Lifting dbr:Lambda_lift dbr:Λ-lifting |
| is foaf:primaryTopic of | wikipedia-en:Lambda_lifting |