## CS 3520 Homework 8

Due: Wednesday, October 30th, 2019 11:59pm

Difficulty:  ★★★☆

### Part 1 — Boxes

```  <Exp> = ...
| {box <Exp>}
| {unbox <Exp>}
| {box? <Exp>}```

The box? form returns 0 if the result of its argument expression is a box, 1 if it’s not a box. Even so, your interpreter can assume that the argument to unbox is always a box (which is consistent with other forms in the initial interpreter, such as the way that + assumes that its arguments are numbers).

Examples:

```  (reset!)
(ntest (interpx (compile
(parse `{unbox {unbox {box {box 3}}}})
mt-env)
empty-env
(init-k))
3)

(reset!)
(ntest (interpx (compile
(parse `{box? 3})
mt-env)
empty-env
(init-k))
1)

(reset!)
(ntest (interpx (compile
(parse `{box? {box 3}})
mt-env)
empty-env
(init-k))
0)

(reset!)
(ntest (interpx (compile
(parse `{box? {lambda {x} {box x}}})
mt-env)
empty-env
(init-k))
1)

(reset!)
(ntest (interpx (compile
(parse
`{{lambda {mkrec}
{{{lambda {chain}
{lambda {unchain}
;; Make a chain of boxes, then traverse
;; them:
{{unchain 13} {chain 13}}}}
;; Create recursive chain function:
{mkrec
{lambda {chain}
{lambda {n}
{if0 n
1
{box {chain {+ n -1}}}}}}}}
;; Create recursive unchain function:
{mkrec
{lambda {unchain}
{lambda {n}
{lambda {b}
{if0 n
b
{unbox {{unchain {+ n -1}} b}}}}}}}}}
;; mkrec:
{lambda {body-proc}
{{lambda {fX}
{fX fX}}
{lambda {fX}
{body-proc {lambda {x} {{fX fX} x}}}}}}})
mt-env)
empty-env
(init-k))
1)```

### Part 2 — Extra Credit: Box Assignment

CS 3520 and CS 6520 students can complete this exercise for extra credit, but it is not required.

```  <Exp> = ...
| {set-box! <Exp> <Exp>}```

You can make set-box! return whatever you like, and your interpreter can assume that the first argument to set-box! is always a box.

```  (reset!)
(ntest (interpx (compile
(parse `{{lambda {b}
{{lambda {z}
{unbox b}}
{set-box! b {+ {unbox b} 1}}}}
{box 3}})
mt-env)
empty-env
(init-k))
4)```

 Last update: Monday, August 3rd, 2020mflatt@cs.utah.edu