Lifting
Lambda lifting
fact n return: isZero n base recurse
base: return 1
recurse: sub n 1 step1
step1 m: fact m step2
step2 f: mul n f return
with the following closures:
fact:
base: return
recurse: n return
step1: n return
step2: n return
Lift this into variables:
fact n return: isZero n base[return] recurse[n return]
base return: return 1
recurse n return: sub n 1 step1[n return]
step1 m n return: fact m step2[n return]
step2 f n return: mul n f return
We would need to generate special pass through versions of isZero
, sub
and mul
. This can be done with some effort. If we try to do the same for fact
we will end up in a recursion. This reflects that the function is not in tail-recursive form and requires a call stack.
Lambda dropping
http://www.brics.dk/RS/99/27/BRICS-RS-99-27.pdf
Closure allocation
Empty closures are not allocated at all.
Closures that are compile time constant can be statically allocated in read-only memory. If their call-sites are known, it can also be inlined and removed.
Closures that do not escape can be statically allocated on the heap. Liveliness analysis can allow for overlap.
Other closure maybe be shown to be stack-structured and could benefit from optimized memory reclamation.