Description
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