3 - Semantics

Summary

This chapter is devoted to the semantics of the functional language that we described in the previous chapters. The point of its semantics is to define the meaning of expressions in this language; that is, to define precisely the value of each expression. The association between an expression and its value is created by rewrite rules; that is, rules that transform expressions textually. Those rules are presented and discussed in Section 3.1.

These rewrite rules are non-deterministic. That is, in general, for any expression under consideration, there is more than one rule that may be applied to it. The consistency of these rules rests on the fact that they form a convergent system. In other words, whatever the non-deterministic choices made, at every step it is always possible to make any two different computations converge toward the same expression. This property does not exclude the existence of infinite computations, but it does exclude the possibility of an expression having two distinct values. The value of an expression (when it exists), is therefore unique. We assert this convergence property here, but we will not try to prove it. References about the proof of convergence are found at the end of this chapter.

In practice, in order to implement an evaluator for a language, we have to define a strategy that lets us choose a rewrite at every step—we choose one such rewrite among the set of all possible rewrites.