Due: Friday, September 22nd, 2023 11:59pm
Difficulty: ★★★★
Start with store_reslet.rhm. In the starting program, the representation of the store grows every time that a box’s content is modified with set_box. Change the implementation of set_box so that the old value of the box is dropped (i.e., replaced with the new value) instead of merely hidden by the outside-in search order of fetch.
Example:
check: interp(parse('let b = box(1):
begin:
set_box(b, 2)
unbox(b)'),
mt_env,
mt_store)
~is res(intV(2),
override_store(cell(1, intV(2)),
mt_store))Generalize begin to allow one or more sub-expressions, instead of exactly two sub-expressions.
<Exp> = ....
| begin:
<Exp>
<Exp>
...Example:
check: interp(parse('let b = box(1):
begin:
set_box(b, 2 + unbox(b))
set_box(b, 3 + unbox(b))
set_box(b, 4 + unbox(b))
unbox(b)'),
mt_env,
mt_store)
~is res(intV(10),
override_store(cell(1, intV(10)),
mt_store))A note on pattern matching: To match a begin form with one or more expressions, each on its own line, you can use this Shplait pattern:
'begin:
$exp0
$exp
...'After matching that pattern, exp0 stands for one line/group, and exp is a sequence of additional lines/group. Although the exp repetition is created from separate lines, the repetition doesn’t have to be used in a template as different lines. You can use syntax_to_list('[$exp0, $exp, ...]') to put the matches together in a list syntax object and convert it to a list of syntax objects.
A tip on dealing with nonempty lists: As you know, a list has two cases: [] and cons(item, list). A nonempty_list has two different cases: it is always a cons pair and its rest may or may not be empty. A match cannot easily follow the shape of nonempty lists (it needs a case for [] and a nested match), so we recommend cond instead, which can check for the first nonempty-list case with the test is_empty(rest(nonempty_list)).
Extend the interpreter to support the construction of records with named fields, to support field selection from a record (as in record.rhm):
<Exp> = ....
| {<Sym> : <Exp>, ...}
| <Exp> . <Sym>Adding records means that the language now has four kinds of values: numbers, functions, boxes, and records. At run-time, an error may occur because a record is misused as a number or function, a number or function is supplied to ., or a record supplied to . does not have the named field, and so on. Your error message for the last case should include the words “no such field”, but beyond that constraint, you can make up your own error messages.
Expressions within a {} form should be evaluated when the {} form itself is evaluated, and in the order that the expressions appear in the {} form. For example,
let b = box(0):
let r = { a: unbox(b) }:
begin:
set_box(b, 1)
r.ashould produce 0, not 1, because unbox(b) is evaluated when the {} expression is evaluated, not when the . expression is evaluated.
Note that you will not be able to use map to interp field values, since a store must be carried from one field’s evaluation to the next. Instead, interping the field value will be more like interping a sequence of expressions for begin.
You can assume (without checking) that all field names in a {} form are distinct.
For homework purposes, we don’t want to nail down the representation of a record value, because there are many choices. The examples below therefore use interp_expr, which you must define as a wrapper on interp that takes just an Exp and produces just an syntax object: a syntax number if interp produces any number, the syntax object 'function' if interp produces a closure, the syntax object 'box' if interp produces a box, or the syntax object 'record' if interp produces a record value.
Examples:
check: interp_expr(parse('1 + 4'))
~is '5'
check: interp_expr(parse('{ a: 10, b: 1 + 2 }'))
~is 'record'
check: interp_expr(parse('{ a: 10, b: 1 + 0 }.b'))
~is '1'
check: interp_expr(parse('{ a: 10 }.b'))
~raises "no such field"
check: interp_expr(parse('{ r : { z: 0 } }.r'))
~is 'record'
check: interp_expr(parse('{ r : { z: 0 } }.r.z'))
~is '0'
check: interp_expr(parse('let b = box(0):
let r = { a: unbox(b) }:
begin:
set_box(b, 1)
r.a'))
~is '0'This exercise is required for CS 6520 students, but it counts as extra credit for CS 3520 students.
Add an assignment form that modifies the value of a record field imperatively (as opposed to functional update):
<Exp> = ....
| <Exp> . <Sym> := <Exp>Evaluation of a {} expression allocates a location for each of its fields. A . expression without := accesses from the record produced by the sub-expression the value in the location of the field named by the identifier. A . with := form changes the value in the location for a field; the value of the sub-expression after := determines the field’s new value, and that value is also the result of the assignment expression.
Note that making record fields mutable has the same effect as forcing every field of a record to be a Moe box, where the box contains the proper value of the field. Internal to the interpreter implementation, you could use Moe boxes in your implementation of mutable records, or you could use addresses more directly. You should not use Shplait boxes at all.
Examples:
check: interp_expr(parse('let r = { x: 1 }:
r.x'))
~is '1'
check: interp_expr(parse('let r = { x: 1 }:
begin:
r.x := 5
r.x'))
~is '5'
check: interp_expr(parse('let r = { x: 1 }:
let get_r = (fun (d): r):
begin:
(get_r(0)).x := 6
(get_r(0)).x'))
~is '6'
check: interp_expr(parse('let g = (fun (r): r.a):
let s = (fun (r): fun (v): r.b := v):
let r1 = { a: 0, b: 2 }:
let r2 = { a: 3, b: 4 }:
r1.b + (begin:
s(r1)(g(r2))
(begin:
s(r2)(g(r1))
r1.b) + r2.b)'))
~is '5'| Last update: Thursday, November 9th, 2023mflatt@cs.utah.edu |