Concepts and Semantics of Programming Languages 1. Therese Hardin

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 →_Lang1 and 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.

2.4. Exercises

       Exercise 2.1

      Consider the state etat₀ defined 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₃ = (Env₃, Mem₃) and etat₄ = (Env₄, Mem₄). 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.

       1) Define an evaluation function:for expressions in the language Exp1, extended so that expresses the fact that evaluation of the expression e in the state (Env, Mem) transforms this state into a state (Env’, Mem’) and produces the value v.

       2) Let Env = [(x, rx)] and Mem = [(rx, 6)]. Compute:

       3) Show that, for any state (Env, Mem):Now, we extend the language Lang1 by considering the expressions of the extended Def 1 language and adding the construction x+ := e. In informal terms, the execution of this instruction in a state (Env, Mem) consists of first finding the value vx stored at the reference v in Mem, then evaluating the expression e in this state to obtain its value ve and a new state (Env’, Mem’), and finally, assigning to v the result of the addition of ve and vx. If at least one of the two values ve and vx is not an integer, the execution fails.

       4) Redefine the relation →Lang1 for the extended Lang1 language.

       5) Let Env0 = [(x, rx)] and Mem0 = [(rx, 2)]. Determine the state etat1 such that

       6) Do the assignments x := x + +, x := + + x and x+ := 1 produce the same states when executed in the same state?