11 - Evaluation

Summary

In Chapter 3, we presented a model for evaluation of expressions; it was based on the idea of rewrites. This model defined a semantics to which every implementation had to refer. However, an implementation that actually used textual rewrites would be highly inefficient. To achieve reasonable efficiency, we must replace textual rewrites by some other mechanism that simulates it. One possibility is to introduce the idea of an environment.

In this chapter, we present evaluation based on environments. We will write an evaluation function that takes an environment and a Caml expression as its arguments and returns the value of this expression as its result. The ideas for implementing this evaluation function will be refined in Chapter 12 to produce a compiler.

Section 11.1 describes evaluation of expressions with the help of environments. As in Chapter 3, it uses inference rules corresponding to each construction in the language to do so. These inference rules define evaluation by value, the evaluation strategy adopted by Caml. Section 11.2 then shows how to translate these rules into an evaluator written in Caml. Finally, Section 11.3 shows how to modify that evaluator to take into account delayed evaluation rather than evaluation by value.

Evaluation with the Help of Environments

An environment may be regarded as a look-up table in which certain variables are bound to values.