A methodology for investigating evaluation models for functional programs.

Abstract

The central aspect of implementing a functional programming language is the design of an evaluation model: an abstract view of how the underlying machine executes functional programs. To make informed decisions in designing an evaluation model, the implementation designer needs to have a good understanding of mechanisms constituting the available evaluation models and their relationship to functional programming and computer architecture. This thesis provides one way of arriving at that understanding through analyzing the execution behavior of a set of functional programs on implementations based on two contrasting evaluation models: an environment one and a reduction one. The essential difference between the environment and reduction evaluation models, is that the former centralizes the dynamic context$\sp1$ while the latter distributes it. The consequences of choosing either to centralize or distribute the dynamic context are studied using data on execution behavior of functional programs. In the experimental part of the thesis, environment and reduction evaluators are built and instrumented to generate execution profiles, which contain measures of computational resource usage. It is demonstrated how the execution profiles can be used to compute costs incurred by the two evaluators. ftn $\sp1$In general, the dynamic context of a computation is that part of the overall context which changes during a computation and, therefore, reflects the progress of the computation.