Exercise 1 Consider the following programming language, called miniML, that features (recursive) procedures and explicit references.
Syntax The syntax is defined as follows:
P
→
E
E
→
n
|
x
|
E + E | E − E | E ∗ E | E/E
|
E − E
|
iszero E
|
if E then E else E
|
let x = E in E
|
letrec f(x) = E in E
|
proc x E
|
E E
|
ref E
|
! E
|
E := E
|
E;E
|
begin E end
Semantics The semantics is defined with the following domain:
Val
=
Z + Bool + Procedure + RecProcedure + Loc
Procedure
=
Var × E × Env
RecProcedure
=
Var × Var × E × Env
ρ ∈ Env
=
Var → Val
σ ∈ Mem
=
Loc → Val
1
and evaluation rules:
ρ,σ0 0,σ1 ρ,σ0
ρ,σ0 ` iszero E ⇒ true,σ1 ρ,σ0 ` iszero
ρ,σ0 ` E1 ⇒ true,σ1 ρ,σ1 ` E2 ⇒ v,σ2
ρ,σ0 ` if E1 then E2 else E3 ⇒ v,σ2
ρ,σ0 ` E1 ⇒ false,σ1 ρ,σ1 ` E3 ⇒ v,σ2
ρ,σ0 ` if E1 then E2 else E3 ⇒ v,σ2
ρ,σ0 ` E1 ⇒ v1,σ1 [x 7→ v1]ρ,σ1 ` E2 ⇒ v,σ2
ρ,σ0 ` let x = E1 in E2 ⇒ v,σ2
[f 7→ (f,x,E1,ρ)]ρ,σ0 ` E2 ⇒ v,σ1
ρ,σ ` letrec f(x) = E in E ⇒ v,σ ρ,σ ` proc x E ⇒ (x,E,ρ),σ
Dom(σ1)
ρ,σ0 ` E ⇒ v,σ1
ρ,σ0 ` begin E end ⇒ v,σ1
Implement an interpreter of miniML. Raise an exception UndefinedSemantics whenever the semantics is undefined. Skeleton code will be provided (before you start, see README.md).
2
