Therese Hardin - Concepts and Semantics of Programming Languages 1

By iterating this function, we obtain an implementation of

Python def trans_def1_exec(st,ld): (env,mem) = st if len(ld) == 0: return (env,mem) else: return trans_def1_exec(trans_def1((env,mem),ld[0]),ld[1:])OCaml let trans_def1_exec (env, mem) ld = (List.fold_left trans_def1 (env, mem) ld) val trans_def1_exec : (’a * ’a refer const1) list * (’a refer * ’a refer const1) list -> ’a def1 list -> (’a * ’a refer const1) list * (’a refer * ’a refer const1) list

Now, considering example 2.3, we obtain:

Python ex_ld0 = [Var_def1(“y”,Cste1(2)), Let_def1(“x”,Plus1(Bang1(“y”),Cste1(3)))] (ex_e0,ex_m0) = trans_def1_exec(([],[]),ex_ld0) >>> eval_exp1(ex_e0,ex_m0,Var1(“x”)).cste.cst_int 5 >>> eval_exp1(ex_e0,ex_m0,Bang1(“y”)).cste.cst_int 2OCaml let ex_ld0 = [ Var_def1 (“y”, Cste1 2); Let_def1 (“x”, Plus1 (Bang1 “y”, Cste1 3)) ] val ex_ld0 : string def1 list # (trans_def1_exec ([], []) ex_ld0) ;; - : (string * string refer const1) list * (string refer * string refer const1) list = ([(“x”, CInt1 5); (“y”, CRef1 (Ref_Var1 “y”))], [(Ref_Var1 “y”, CInt1 2)])

The language Lang 1extends Def 1by adding assignment . The syntax of an assignment instruction is:

x : = e

where x ∈ Xand e ∈ Exp 1. When the mutable variable x is already bound in the current environment, this instruction enables us to modify the value of ! x . Formally, execution of the instruction x := e modifies the memory of the current state, and it is described by the following transition:

NOTE.– Once again, if the identifier x is not bound in the environment or if the evaluation of e results in an error, no state is generated and evaluation stops.

EXAMPLE 2.4.– Based on the state obtained in example 2.3, the following two assignments can be executed:

Representing the abstract syntax of the assignment x := e by the pair ( x , e ), the relation → Lang1and the iteration of this relation from a sequence of assignments are implemented as follows:

Python def trans_lang1(st,a): (env,mem) = st (x,e) = a v = valeur_de(env,x) if isinstance(v,CRef1): ve = eval_exp1(env,mem,e) if isinstance(ve,VCste1): return (env,write_mem(mem,v.cst_adr,ve.cste)) raise ValueError def trans_lang1_exec(st,la): (env,mem) = st if len(la) == 0:return (env,mem) else: return trans_lang1_exec(trans_lang1((env,mem),la[0]),la[1:])OCaml let trans_lang1 (env,mem) (x, e) = match valeur_de env x with | Some (CRef1 (Ref_Var1 y)) -> (match eval_exp1 env mem e with | VCste1 v -> (env, (write_mem mem (Ref_Var1 y) v)) | Erreur1 -> failwith “Eval error”) | _ -> failwith “Undefined var” val trans_lang1 : (’a * ’b refer const1) list * (’b refer * ’b refer const1) list -> ’a * ’a exp1 -> (’a * ’b refer const1) list * (’b refer * ’b refer const1) list let trans_lang1_exec (env, mem) la = (List.fold_left trans_lang1 (env, mem) la) val trans_lang1_exec : (’a * ’b refer const1) list * (’b refer * ’b refer const1) list -> (’a * ’a exp1) list -> (’a * ’b refer const1) list * (’b refer * ’b refer const1) list

Considering example 2.4, we obtain:

Python ex_la0 = [(“y”,Plus1(Bang1(“y”),Var1(“x”))), (“y”,Cste1(8))] (ex_e1,ex_m1) = trans_lang1_exec((ex_e0,ex_m0),ex_la0) >>> eval_exp1(ex_e1,ex_m1,Bang1(“y”)).cste.cst_int 8OCaml let ex_la0 = [ (“y”, Plus1 (Bang1 “y”,Var1 “x”)); (“y”, Cste1 8) ] val ex_la0 : (string * string exp1) list # (trans_lang1_exec (trans_def1_exec ([],[]) ex_ld0) ex_la0);; - : (string * string refer const1) list * (string refer * string refer const1) list = ([(“x”, CInt1 5); (“y”, CRef1 (Ref_Var1 “y”))], [(Ref_Var1 “y”, CInt1 8)])

NOTE.– In the presentation above, assignment concerns only mutable variables. Similarly, the dereferencing operator ! can only be applied to a reference to obtain the stored value at this location. Thus, the assignment of a value to a mutable variable from a given reference requires here the use of the dedicated syntactic structures: x := ! x + 1. However, in many languages, assignment does not explicitly mention the dereferencing operator, and the syntactic use of variables is identical on both sides of the assignment: x = x + 1. Hence, an identifier x denotes two different notions: the value Env( x ) on the left of the assignment symbol, and the value Mem(Env( x )) on the right of the assignment symbol.

These languages mask the different roles of a variable according to its position in the assignment. When a variable x is positioned to the left of the assignment, it is known as an l-value and it denotes a location where the value to be assigned should be stored. In this way, it acts as a pointer. The variable x on the right of the assignment is known as the r-value , and implicitly acts as a dereferenced pointer: the value to fetch is found at the location denoted by the variable. Thus, in the expression x = x + 1, even if x is used in the same way from a syntactic perspective, the instance on the right implicitly denotes ! x. In some languages, variable declaration implicitly involves the creation of a reference, unless otherwise stated; the name of the variable represents the location where the compiler will store the values assigned to it.

Exercise 2.1

Consider the state etat 0defined by:

1) compute and .

2) Give a sequence of definitions to obtain the state etat0 from the empty state ([ ], [ ]). Are there other sequences that can be used to obtain this state?

3) compute

4) Give three examples of expressions that generate three different error types when evaluated in the state etat0.

5) Consider the sequenceDetermine the states etat1 = (Env1, Mem2) and etat2 = (Env2, Mem2) and the sets , , .

6) Consider the sequence

Determine the states etat 3= (Env 3 , Mem 3) and etat 4= (Env 4 , Mem 4). Does

Exercise 2.2

The two constructs x + + and + + x:

are added to the language Exp1. In these two new constructs, the identifier x must be a mutable variable. Intuitively, we see that the evaluation of the expression x + + produces the value stored in the location denoted by x and increments the value in the memory by 1. The expression + + x is evaluated differently: the value stored at the location denoted by x is incremented by 1, and this new value is the result of the evaluation.