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
