Therese Hardin - Concepts and Semantics of Programming Languages 1

Using Python, we define the following classes to represent the constructors of the set Exp1:

Python class Cstel: def __init__(self,cste): self.cste = cste class Var1: def __init__(self,symb): self.symb = symb class Plusl: def __init__(self,exp1,exp2): self.exp1 = exp1 self.exp2 = exp2 class Bang1: def __init__(self,symb): self.symb = symb

For example, the expression e 1= !x + y defined in example 2.1 is written as:

Python ex_expl = Plusl(Bangl(“x”),Varl(“y”))

Using OCaml, the type of arithmetic expressions is defined directly as:

OCaml type ’a exp1 = Cstel of int | Var1 of ’a | Plusl of ’a expl * ’a expl | Bangl of ’a

Values of this type are thus obtained using either the Cste1 constructor applied to an integer value, in which case they correspond to a constant expression, or using the Var1 constructor applied to a value of type ’a, corresponding to the type used to represent identifiers (the type ’a exp1 is thus polymorphic, as it depends on another type), or by applying the Plus1 constructor to two values of the type ’a expl, or by applying the Bang1 constructor to a value of type ’a. For example, the expression e 1= ! x + y is written as:

OCaml let ex_exp1 = Plus1 (Bang1 (“x”), Var1 (“y”)) val ex_exp1 : string exp1

Given a state (Env , Mem), we determine the evaluation semantics of an expression e ∈ Exp 1by computing the value of e in this state, i.e. by evaluating e in this state. Values may be relative integers or references, hence V= ℤ U R. An additional, specific value Err is added to the set V; this result is returned as the value of “meaningless” expressions. The result of the evaluation of an expression in Exp 1will therefore be a value belonging to the set

Values in Vare either relative integers or references. By defining a sum type, these two collections of values can be grouped into a single type.

Python class CInt1: def __init__(self,cst_int): self.cst_int = cst_int class CRef1: def __init__(self,cst_adr): self.cst_adr = cst_adr

Each class possesses a (object) constructor with the same name as the class: the constant k obtained from integer n (or, respectively, from reference r) is thus written as CInt1( n ) (respectively, CRef1( r )), and this integer (respectively, reference) can be accessed from (the object) k by writing k . cst_int(respectively k . cst_adr). With OCaml, the type of elements in Vis defined directly, as follows:

OCaml type ’a constl = CIntI of int | CRefl of ‘a

A value of this type is obtained either using the constructor CInt1applied to an integer value or using the constructor CRef1applied to a value of type ’a corresponding to the type used to represent references.

A type grouping the elements of is defined by applying the same method:

Python class VCste1: def __init__(self,cste): self.cste = cste class Erreur1: pass

An element v in is either a value in Vobtained from a constant k and written as VCste1(k), or an object in the class Erreur1 (passis used here to express the fact that the (object) constructor has no argument). With OCaml, the type of the elements in 𝕧 is defined directly as follows:

OCaml type ’a valeursl = VCstel of ’a constl | Erreur1

There are several formalisms that may be used to describe the evaluation of an expression. These will be introduced later. Let us construct an evaluation function:

The evaluation of the expression e in the environment Env and memory state Mem is denoted as with v ∈ V. Table 2.2contains the recursive definition of the function

Table 2.2. Evaluation of the expressions of Exp 1

	( k ∈ ℤ)
	if x ∈ Xand x ∈dom( Env)
	if x ∈ X and x ∉ dom( Env)

The value of an integer constant is the integer that it represents. The value of an identifier is that which is bound to it in the environment, or Err. The value of an expression constructed with an addition symbol and two expressions e 1and e 2is obtained by adding the relative integers resulting from the evaluations of e 1and e 2; the result will be Err if e 1or e 2is not an integer. The value of ! x is the value stored at the reference Env( x ) when x is a mutable variable, and Err otherwise.

Thus, if e is evaluated as a reference, then e can only be an identifier. Furthermore, certain expressions in Exp 1are syntactically correct, but meaningless: for example, the expression ! x when x is not a mutable variable, i.e. when x does not bind a reference in the environment, or x 1+ x 2when x 1(or x 2) is a mutable variable. On the other hand, ! x + y is a meaningful expression that denotes a value when y binds an integer and x binds a reference to an integer.