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 before 4:30PM on Monday, Sep. 29.

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 Conceptually boxes behave like single element mutable vectors in SMoL.

(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))