Very Lazy Evaluation - A new execution model for functional programming languages

Abstract

In the recent years a multitude of functional language implementations has been developed, whereby those being intended for practical use share a very fundamental property: The execution models employed by implementations designed for efficient program execution are all based on some form of graph-reduction. This thesis introduces a new execution model for strongly-typed, higher-order, non-strict, purely-functional programming languages, that does not rely on graph-reduction but a new concept called very lazy evaluation. It uses an unconventional approach to evaluate expressions of the λ-calculus, that differs considerably from traditional term rewrite systems. Its method to perform function applications allows arguments to be handled in a way, that is more lazy than in existing graph-reduction based models. This leads to a new type of abstract machine, which promises very efficient program execution and might also be quite suitable to be implemented in hardware. A proof-of-concept implementation of the execution model is given, which consists of a compiler generating abstract machine code from a source program, and the abstract machine that interpretes the result. By using it to execute real programs it is shown, that the correct results are evaluated and that the approach therefore is a valid alternative to existing execution models.