constructor applied to an identifier.
Python class Ref_Var1: def __init__(self,idvar): self.idvar = idvarOCaml type ’a refer = Ref_Var1 of ’a
Hence, rx will be represented by Ref_Var1(”x”). As the relation →Def1 defines a function, it can be implemented directly as follows:
Python def trans_def1(st,d): (env,mem) = st if isinstance(d,Let_def1): v = eval_exp1(env,mem,d.exp) if isinstance(v,VCste1): return (ajout_liaison_env(env,d.var,v.cste),mem) raise ValueError if isinstance(d,Var_def1): v = eval_exp1(env,mem,d.exp) if isinstance(v,VCste1): r = Ref_Var1(d.var) return (ajout_liaison_env(env,d.var,CRef1(r)), write_mem(mem,r,v.cste)) raise ValueError raise ValueErrorOCaml let trans_def1 (env, mem) d = match d with | Let_def1 (x, e) -> (match eval_exp1 env mem e with | VCste1 v -> ((ajout_liaison_env env x v), mem) | Erreur1 -> failwith “Erreur”) | Var_def1 (x, e) -> (match eval_exp1 env mem e with | VCste1 v -> ((ajout_liaison_env env x (CRef1 (Ref_Var1 x))), (write_mem mem (Ref_Var1 x) v)) | Erreur1 -> failwith “Erreur”) val trans_def1 : (’a * ’a refer const1) list * (’a refer * ’a refer const1) list -> ’a def1 -> (’a * ’a refer const1) list * (’a refer * ’a refer const1) list
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)])
2.3.2. Assignment
The language Lang1 extends Def 1 by adding assignment. The syntax of an assignment instruction is:
x : = e
where x ∈ X and e ∈ Exp1. 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 →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 etat0 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)
