CS 496: Homework Assignment 4 Solution

Under absolutely no circumstances code can be exchanged between students. Excerpts of code presented in class can be used.
Assignments from previous offerings of the course must not be re-used. Violations will be penalized appropriately.
2 Assignment
This assignment has two parts. Part I consist in adding records with mutable fields to EXPLICIT-REFS to obtain EXPLICIT-REFS-MF. Part II consists in writing a series of programs in the language EXPLICIT-REFS-MF that make use of this new language construct.
2.1 Part I
let p = {ssn = 10; age <= 30} in begin
p.age <= 31; (* updates age to 31 *)
p.age end
2
4
Evaluating this expression should produce Ok (NumVal 31). Consider the evaluation of this other expression:
let p = {ssn = 10; age <= 30} in begin
p.age <= 31;
p end
2
4
It should produce Ok (RecordVal [("ssn", (false, NumVal 10)); ("age", (true, RefVal 1))]). Notice two things here:
1. false indicates the field is immutable and true that it is mutable.
Updating an immutable field should not be allowed. For example, the following expression should report an error Error "Field not mutable":
let p = { ssn = 10; age <= 20}
in begin
p.ssn <= 11;
p.age end
2
4
EXPLICIT-REFS-MF also has a predicate to check whether a run-time value is a number or not. Here is how it should behave:
# interp "number?(2)";;
- : exp_val Explicit_refs.Ds.result = Ok (BoolVal true) # interp "number?(2+1)";;
- : exp_val Explicit_refs.Ds.result = Ok (BoolVal true) utop # interp "number?(zero?(0))";;
- : exp_val Explicit_refs.Ds.result = Ok (BoolVal false) utop # interp "number?(proc(x) {x+1})";;
- : exp_val Explicit_refs.Ds.result = Ok (BoolVal false)

utop
1
3
5
7
The updated concrete syntax is:
<Expression> ::= { <Identifier><FieldType><Expression>+(;)}
<Expression> ::= <Expression>. <Identifier>
<Expression> ::= <Expression>. <Identifier><= <Expression>
<Expression> ::= number?(<Expression>)
<FieldType> ::= =|<=
The updated abstract syntax is as follows:
type expr =
...
| Record of (string*(bool*expr)) list
| Proj of expr*string
| SetField of expr*string*expr
| IsNumber of expr
2
4
6
For example,
# parse " let p = {ssn = 10; age <= 30} in begin
p.age <= 31; p
end";;
- : expr =
Let ("p", Record [("ssn", (false, Int 10)); ("age", (true, Int 30))],
BeginEnd [SetField (Var "p", "age", Int 31); Var "p"])

utop
2
4
6
8
You are asked to implement the interpreter extension. The RecordVal constructor has added for you.

As for eval_expr, the case for Record has already been implemented for you. You are asked to implement Proj, SetField and IsNumber:
let rec eval_expr : expr -> exp_val ea_result = fun e ->
match e with
| IsNumber(e) -> failwith "implement"
| Record(fs) -> sequence (List.map process field fs) >>= fun evs -> return (RecordVal (addIds fs evs))
| Proj(e,id) -> failwith "implement"
| SetField(e1,id,e2) -> failwith "implement"
| IsNumber(e) -> failwith "implement" and
process field ( id,(is mutable,e))
=
eval_expr e >>= fun ev -> if is_mutable
then return (RefVal (Store.new_ref g_store ev)) else return ev
2
4
6
8
10
12
14
16
18
where sequence is define here:
let rec sequence : (’a ea_result) list -> (’a list) ea_result =
fun cs -> match cs with
| [] -> return []
| c::t -> c >>= fun v -> sequence t >>= fun vs ->
return (v::vs)

ds.ml
2
4
6
8
2.2 Part II: Implementing Linked Lists in EXPLICIT-REFS-MF
Example 1 below creates a linked-list with two nodes.
(* Example 1 *)
let l1 = { head <= 0; size <= 0} (* 0 in head signals null *) in let add_front = proc (x) { proc (l) {
begin
l.head <={ data <=x; next <= l.head };
l.size <= l.size+1
end
} }
in begin
((add_front 2) l1);
((add_front 3) l1); debug(l1) (* required to inspect the list *) end

ll add front.exr
2
4
6
8
10
12
14
# interpf "ll_add_front";; >>Environment:
l1->{head <= RefVal (0); size <= RefVal (1)},
add_front->ProcVal(x,Proc(l,BeginEnd(Var l.head<={data=Var x;next=Var l.head}; Var l.size<=Add(Var l.size,Int 1))),
[l1->{head <= RefVal (0); size <= RefVal (1)}]) >>Store:
0->{data <= RefVal (4); next <= RefVal (5)},
1->NumVal 2,
2->NumVal 2,
3->NumVal 0,
4->NumVal 3,
5->{data <= RefVal (2); next <= RefVal (3)}
- : exp_val Explicit_refs.Ds.result = Error "Reached breakpoint"

utop
2
4
6
8
10
12
14
Example 2 below creates a linked list with two nodes and then adds one to each data element in each node.
(* Example 2 *)
let l1 = { head <= 0; size <= 0} in let add_front = proc (x) { proc (l) {
begin
l.head <={ data <=x; next <= l.head };
l.size <= l.size+1
2
4
6
end } }
in letrec bump_helper (node) = if number?(node) then 0 else (begin node.data <= node.data + 1;
(bump_helper node.next) end) in let bump = proc (ll) { (bump_helper ll.head) } in begin
((add_front 2) l1);
((add_front 3) l1);
(bump l1); debug(l1) end

ll bump.exr
8
10
12
14
16
18
20
22
2
utop # interpf "ll_bump";; >>Environment:
l1->{head <= RefVal (0); size <= RefVal (1)},
add_front->ProcVal(x,Proc(l,BeginEnd(Var l.head<={data=Var x;next=Var l.head};
Var l.size<=Add(Var l.size,Int 1))),[l1->{head <= RefVal (0); bump_helper->Rec(node,IfThenElse(Number?(Var node),Int 0,BeginEnd(
Var node.data<=Add(Var node.data,Int 1);App(Var bump_helper,Var node.next)))), bump->ProcVal(ll,App(Var bump_helper,Var ll.head),[l1->{head <= RefVal (0); size <= RefVal (1)},add_front->ProcVal(x,Proc(l,BeginEnd(Var l.head<={data=Var x >>Store:
0->{data <= RefVal (4); next <= RefVal (5)},
1->NumVal 2,
2->NumVal 3,
3->NumVal 0,
4->NumVal 4,
5->{data <= RefVal (2); next <= RefVal (3)}
- : exp_val Explicit_refs.Ds.result = Error "Reached breakpoint"

utop
4 size <= RefVal (1)}]),
6
8
;next=Var l.head}
10
12
14
16
1. ll add last.exr. For example,
utop # interpf "ll_add_last" >>Environment:
l1->{head <= RefVal (0); add_last_helper->..., add_last->..., >>Store:
0->{data <= RefVal (2); ;;
size <= RefVal (1)},
next <= RefVal (3)},
1->NumVal 3,
2->NumVal 2,
3->{data <= RefVal (4); next <= RefVal (5)},
4->NumVal 3,
5->{data <= RefVal (6); next <= RefVal (7)},
6->NumVal 4,
7->NumVal 0
- : exp_val Explicit_ref s.Ds.result = Error "Reached breakpoint"
1
3
5
7
9
11
13
15

2. ll remove first.exr For example,
1
3
utop # interpf "ll_remove_first";; >>Environment:
l1->{head <= RefVal (0); size <= RefVal (1)},
add_front->ProcVal(x,Proc(l,BeginEnd(Var l.head<={data=Var x;
Var l.size<=Add(Var l.size,Int 1))),[l1->{head <= RefVal (0); remove_first-> ..., >>Store:
0->{data <= RefVal (4); next <= RefVal (5)},
1->NumVal 2,
2->NumVal 2,
3->NumVal 0,
4->NumVal 3,
5->{data <= RefVal (2); next <= RefVal (3)},
6->NumVal 4,
7->{data <= RefVal (4); next <= RefVal (5)}
- : exp_val Explicit_refs.Ds.result = Error "Reached breakpoint"

utop
next=Var l.head};
5 size <= RefVal (1)}]),
7
9
11
13
15
3. ll remove last.exr For example,
2
utop # interpf "ll_remove_last";; >>Environment:
l1->{head <= RefVal (0); size <= RefVal (1)},
add_front->ProcVal(x,Proc(l,BeginEnd(Var l.head<={data=Var x;
Var l.size<=Add(Var l.size,Int 1))),[l1->{head <= RefVal (0); remove_last_helper->..., remove_last->..., >>Store:
0->{data <= RefVal (6); next <= RefVal (7)},
1->NumVal 2,
2->NumVal 2,
3->NumVal 0,
4->NumVal 3,
5->NumVal 0,
6->NumVal 4,
7->{data <= RefVal (4); next <= RefVal (5)}
- : exp_val Explicit_refs.Ds.result = Error "Reached breakpoint"

utop
4 next=Var l.head}; size <= RefVal (1)}]),
6
8
10
12
14
16
3 Submission instructions
Submit a file named HW4.zip through Canvas. Include the original stub provided. Please write the names of the members of the team in the as a comment at the top of the interp.ml file.