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

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