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.