# Introduction

In this assignment you will implement an untyped version of the `rec`

primitive
discussed under
Typing Recursion
in the text.

You are given an
initial interpreter
that supports `lam`

, `let1`

, and `if0`

from
from the first 4 lectures. Some skeleton code has been added for `rec`

as well.

Hand in your work to the handin server via DrRacket (just like the lab tutorials) before 9:00AM on Tuesday, Feb 20.

A grading rubric is available.

# Recursive environments

The most important change to support `rec`

in the initial interpreter
is change to the `Env`

type to support
Boxes

```
(define-type-alias Env (Hashof Symbol (Boxof Value)))
(define mt-env (hash empty)) ;; "empty environment"
(define (extend old-env new-name value)
(hash-set old-env new-name (box value)))
(define (lookup (s : Symbol) (n : Env))
(type-case (Optionof (Boxof Value)) (hash-ref n s)
[(none) (error s "not bound")]
[(some b) (unbox b)]))
```

Using only box operations for mutatation, implement `extend-rec`

that
ensures functions can look themselves up in their environment value.
In particular your function should pass the following test.
This is essentially the same technique as
Self Reference using Mutation with `set!`

replaced by `set-box!`

.

```
(let* ([exp (parse `{lam x {f 0}})]
[env (extend-rec mt-env 'f exp)]
[fun (lookup 'f env)])
(test (funV-nv fun) env))
```

# Recursive Binding

Use your `extend-rec`

function to complete the `rec`

case of `interp`

.
Your completed interpreter should pass (at least) the following tests

```
(test (run `{rec {f {lam x {+ x 1}}} {f 8}}) (numV 9))
(test (run `{rec {f {let1 {y 7} {lam x {+ x y}}}} {f 8}}) (numV 15))
(test
(run `{rec {fact {lam n {if0 n 1 {* n {fact {- n 1}}}}}}
{fact 10}})
(numV 3628800))
(test
(run
`{rec
{fib
{lam n
{if0 n 1
{if0 {- n 1} 1
{+ {fib {- n 1}}
{fib {- n 2}}}}}}}
{fib 6}})
(numV 13))
(test
(run `{rec {sum {lam n {if0 n 0 {+ n {sum {- n 1}}}}}}
{sum 10}})
(numV 55))
```

# Tests

Referring to the grading grading rubric for guidance, add any needed tests for your solution.