JuvixCore transformation: Lambda-lifting

[lukaszcz]

Depends on PR #1421

Notes

• Lambda-lifting a single node can be performed with dmapM and the InfoTableBuilder effect.
• With the current Node data structure where only explicit lambdas need to be lifted, a "straightforward" bottom-up lambda-lifting transformation should be possible in O(n k) where:
  • n is the size of the Node (in practice, n should be treated as proportional to input program size),
  • k is the maximum number of distinct free variables in any given subnode, equal to the maximum number of binders on any path in the program tree (in practice, k may be treated as a non-negligible constant; k is roughly the maximum number of lexically available variables at any given point in the source program -- this is in practice much smaller than the total number of variables and usually bounded by a constant)
• Each lambda-expression \y1 .. \yn A should be replaced with f x1 .. xm where:
  • $FV(\lambda y_1 ... \lambda y_n A) = \{x_1, ..., x_m\}$,
  • f is a fresh function symbol,
  • f := \x1 ... \xm \y1 .. \yn A' is added to the IdentContext in the InfoTable, with A' the result of recursively lambda-lifting A.
• We need to avoid the situation where in \x \y A first \y A is lifted out separately. So we need to go top-down (dmapM), use unfoldLambdas from Core/Extra/Base.hs when noticing a lambda, and manually recursively call lambda-lifting on the body A which does not begin with a lambda-abstraction anymore.
• Literature:
  • Danvy & Schultz, Lambda-lifting in quadratic time
  • Peyton Jones & Lester, Implementing functional languages: a tutorial, Chapter 6: Lambda-lifting
  • Peyton Jones, The implementation of functional programming languages (1987 book), Chapters 13, 14
  • Haskell Wiki: Lambda-lifting

Starting point

• Core/Transformation/Base.hs defines the transformation framework.
• Core/Data/InfoTableBuilder.hs may be needed to modify the InfoTable.
• Core/Info/FreeVarsInfo.hs computes free variables for each subnode in O(n k) total time (untested).
• Core/Transformation/LambdaLifting.hs contains a stub for the lambda-lifting transformation.

Justification

The problem with closure conversion is that it turns every local function into a heap-allocated closure with a heap-allocated environment. For functions that can easily be compiled to use the stack, one should compile them to use the stack.

Note that because of partial application, we need closures even with lambda-lifting. But we do not want to be dynamically allocating closures on the heap if we don't need to. There are typically much fewer closure-allocating functions in an eager language than in a lazy one.

Once we get to more sophisticated optimisations, lambda-lifting probably should be done selectively. But I think it's a reasonable default. It turns out well for functions that can be compiled to use the stack, but may result in slower code for ones that need to allocate closures anyway. See: Peyton Jones & Graf, Selective Lambda Lifting.