Re-opening Closures

Abstract:

There are two different commonly-used evaluation methods for functional languages: normal-order graph reduction, and call-by-value execution of closure code. The former is usually more expensive per operation, but has the capability of partially evaluating functions before they are applied. The latter
method usually leads to faster execution - and is thus used in most compilers - but can't "optimize" functions before they are called. The different advantages of the two methods are particularly visible in the evaluation of higher-order functions. After a higher-order function is applied to one argument, the graph-reducer can begin evaluation, while the closure-code evaluator must wait until all arguments are present. On the other hand, because the closure-code evaluator executes the native code of the computer, it usually outperforms the graph-reducer. The two evaluation algorithms can be combined to take advantage of the best behaviors of both. Fragments from programs that are already executing can be extracted, reduced, and re-compiled. This is done with an operator, reduce, that is semantically transparent: - reduce(f) does not change the behaviour of the program fragment f, but can make f much more efficient. This applies not just to functions f in the original program, but to functions
constructed at runtime.