Issues in the implementation of lazy functional languages

Fixed set combinators provide an elegant, but inefficient, method of implementing lazy normal-order evaluation of functional languages. A generalized director-string combinator code is developed to provide an efficiently compiled and fully lazy pure code. This code form facilitates module hierarchies, dynamic debugging and parallel evaluation, being well suited to encoding heuristics and annotations for the implementation of fine grain parallelism, crucial in overcoming the inherent inefficiency of combinators. The debugging of lazy functional programs can be a nontrivial matter. A method is developed to facilitate the debugging of functional programs by allowing dynamic reconstruction of source-like expressions from run-time combinator code with small time and space cost.

The meaning can be briefly explained as follows.

• Every computation takes both time and space.
• Resources are finite such that not everything that could be done can be done.
• Eager evaluation does computations immediately even if the result may never be used.
• Lazy evaluation delays evaluation of what needs to be done until the last possible moment.
• The focus of this research was in implementing lazy evaluation in functional languages while using resources not currently being used to identify and evaluate computations that would need to be done eventually.

My interest was primarily focused in developing meaningful high level notations that could be compiled to efficient low-level code implementations such that, with minimal machine overhead, a meaningful representation of the computation could be reverse engineered and manipulated for debugging and diagnostic purposes.