There are many evaluation and compilation strategies for functional languages based on the lambda calculus. For simplicity, I'll assume you're talking about how one would treat your example as if it were really a strict functional language (where we have applicative-order call-by-value application and a suitable encoding of integer literals).
If we consider the program you've given:
(λx.λy.x) 5 2
The first step is usually to perform some kind of unique-renaming where we ensure lexical scope is apparent (as you may know, λx.λx.x is alpha-equivalent to λy.λx.x - although the latter is more clear) and that potential code motion optimisations don't accidentally lead to scoping conflicts. The program above already has unique names so I'll avoid it as a step here.
The second step is to perform some kind of conversion into a normal form representation (where intermediary values produced by computations become bound to variables given unique names). For strict functional languages, generally one decides between ANF (A Normal Form) and CPS (Continuation Passing Style). I'll go with a variant of ANF for simplicity (you can find thorough treatment of the ideas of CPS compilation in Andrew Appel's "Compiling with Continuations" if you're interested).
Here's a potential result of this kind of transformation:
let f x =
let g y = x in g
in
let x0 = f 5 in
let x1 = x0 2 in
x1
As you can see, the previously-anonymous functions (lambda abstractions) are now represented by named functions and the intermediary results of the two applications are now bound to variables. There are quite a few transformations one can do within this form but this answer focuses more on introducing this representation for structural clarity rather than any optimisations we could apply.
The next step is to perform closure conversion. This step addresses a problem that occurs when compiling code with higher-order functions whose bodies capture values outwith their own lexical scope. Since we have not performed an uncurrying transformation, a partial application is present in our code (f 5). This must return a function that, when applied, returns the x we provided to f (regardless of the scope). To solve this without runtime code generation, compiler developers opt to represent these higher-order functions using a "closure" data structure
(so-called because it closes over the function by providing values to free variables).
The transformation itself adapts functions to take a supplementary argument (to their environment) and the returning of higher-order functions to return a closure data structure (in our case we'll use a "flat" closure: a pair consisting of a code pointer and a pointer to an environment that will be represented in memory by a record). On top of this, all call sites must be adapted to destructure the returned closure in order to apply it.
That sounds like a lot but here's some pseudo-code to demonstrate this transformation performed naively:
let f(x, e) =
let g(y, e') = e'.x in (g, {x})
in
let x0 = f(5, {}) in
let g_ptr = x0.0 in
let g_env = x0.1 in
let x1 = g_ptr(2, g_env) in
x1
Here, I've used brace syntax to represent the construction of environments (so {} is an empty environment - an artefact left over from this naive transformation - and {x} represents a heap-allocated record storing the value of x). The pair syntax (g, {x}) heap-allocates a pair (as a structure) where the first component is the code pointer for g and the second component is the pointer to the heap-allocated record for {x}. The .0 and .1 projections represent accessing these components. You may also notice that I've adopted multi-argument application syntax f(x,y,...) - this should not be confused with the syntax I've used for pairs.
After closure conversion, the program is closed and, therefore, we can safely perform the so-called "hoisting" transformation where we lift nested functions into the global scope (so they appear more like C-like functions which are simpler to compile - a lot of the compilation process is a kind of linearisation).
The result of hoisting could look like:
let g(y, e') = e'.x
let f(x, e) = (g, {x})
let entry() =
let x0 = f(5, {}) in
let g_ptr = x0.0 in
let g_env = x0.1 in
let x1 = g_ptr(2, g_env) in
x1
From here, generally compilers may go to some kind of three-address code IR that has some notion of aggregate and pointers types (to conveniently deal with the auxilliary structures introduced by closure conversion). It is entirely possible to lower the above representation into LLVM (with a few cheap i64* casting tricks - notice that each function is conveniently 2-argument so we don't need to book-keep any typing information to produce a call). As an exercise, you may wish to convert the above into C code (which is also straightforward). But, since your answer wanted some assembly, here's a very naive (leaking) implementation:
.data
fmt: .asciz "result = %lld\n"
.text
.globl main
g:
mov 0(%rsi), %rax # get and return x from environment
ret
f:
sub $24, %rsp
mov %rdi, (%rsp) # preserve x
mov $8, %edi # allocate space for {x}
call malloc@plt
mov (%rsp), %rcx # load and store x into environment
mov %rcx, 0(%rax)
mov %rax, 8(%rsp) # preserve environment
mov $16, %edi # allocate closure pair (2 pointers)
call malloc@plt
lea g(%rip), %rcx
mov %rcx, 0(%rax) # store g's code pointer as first component
mov 8(%rsp), %rcx
mov %rcx, 8(%rax) # store g's environment, {x}, as second component
add $24, %rsp
ret
main:
push %rbx
mov $5, %edi
xor %esi, %esi # {} = null, for simplicity
call f # f(5, {})
mov 0(%rax), %rbx # extract code pointer
mov 8(%rax), %rsi # extract environment
mov $2, %edi
call *%rbx # g(2, {x})
# print the result
mov %rax, %rsi
lea fmt(%rip), %rdi
xor %eax, %eax
call printf@plt
xor %eax, %eax
pop %rbx
ret
Now I'll go into some important, practical, details that I neglected to mention throughout this answer:
- The "extent" (or lifetime) of a closure cannot always be deduced so, by default, we choose to allocate them on the heap. If we can deduce that a closure does not escape upwards (a process known as "escape analysis" is used to discover these cases), we can be more economical about where we allocate these closures (such as on the stack). The cases we want to optimise for are where closures only escape downwards (in other words, a higher-order function is only passed down the call-stack but never escapes upwards - in the call-chain's result - or by being assigned to some other location that outlives the closure's creation site).
- The representation of a closure's environment as a record is very important as we'll be relying on garbage collection to collect them. This has a huge bearing on the representations we choose for how we represent unboxed literal values (such as the
5 and 2 in the above example) alongside pointers to heap-allocated things (such as closure environments that, themselves, store both integer literals and pointers to closure pairs). The way that languages such as OCaml choose to do this is to perform least-significant-bit tagging (by exploiting the alignment of pointers, we can differentiate between unboxed 63 bit integers and 64 bit pointers by checking the lowest bit - this does, however, mean that all arithmetic must be adapted to work on values that are shifted left by 1 place and incremented by 1; so 34 looks like 69 in compiled OCaml programs). On top of this differentiation, garbage collectors must traverse the data structures to find pointers and so we require a fairly homogeneous structure to efficiently do this without compiling in layout information (hence records have strict alignment requirements and store 64 bit values - you can see a diagram of the homogeneous "block" layout used by OCaml here).
I hope this answer gives a kind of understanding of how strict, functional, languages that find their roots in the lambda calculus are generally tackled.
To summarise, the steps are basically:
- Unique renaming (scope-checking can be done at the same time)
- Selective or whole-program transformation into ANF or CPS (involves creating fresh names)
- ANF or CPS-specific optimisations (general things like uncurrying, inline expansion, dead code removal, constant folding, tuple argument flattening, etc.)
- Closure conversion (followed, potentially, by elimination strategies such as lambda lifting of known closures, fix-minimisation using SCCs, etc.)
- Hoisting
- Further lowering into a more machine-like three (or two) address code IR that gives more explicit detail to treatment of auxiliary structures introduced by transformations
- Lowering of that IR into target-specific assembly language
This is definitely not the whole story when it comes to compilation of strict, functional, languages. For example, if we extended our language to have named, mutually-recursive, functions, it would be desirable to work closure sharing into our closure conversion transformation (and also eliminate the cases where closures aren't necessary).
