Concepts and Semantics of Programming Languages 1

5Types

The syntax of the language Exp₂ , i.e. the rules defining the correct form of the expressions that make up the language, was presented in Chapter 3. The execution semantics of this language, which explains how programs written in the language are executed, was described using a variety of approaches.

However, when introducing expressions of the language (in particular, the applications, see section 3.1.1), then the evaluation function (see section 3.2) and then the interpretation of operators (see section 3.2.3), we noted that the syntax does not prevent us from writing expressions that cannot be evaluated, such as 3 + true or (1 2) or 1 = false. In other words, the execution semantics chosen for this language cannot assign a value to these expressions. The existing syntax also allows us to write the expression f = g where f and g are functions, raising substantive questions concerning the meaning of such an expression. In the following, the semantics of these syntactically correct expressions having no clear meaning is more deeply discussed.

In the expression 3 + true, the semantics for the primitive + is the addition over ℤ. The semantics assigned to true is not an element in ℤ, and thus does not belong to the domain of definition of this addition. Hence, this expression cannot be evaluated. However, it would be possible to assign a semantics to true in ℤ by associating it with an integer, such as 1. This might be unwise, as true would then have two roles, denoting ...