Interpreting Recursion

Strict vs Lazy

Strict versus lazy evaluatoin: streams.rkt
Structure and Interpretation of Computer Programs

Mutation

We follow the section on Mutation section from the Tolk repo.
Now that we can interpret boxes, how would we interpret mutable variables? Add a set! to your language.

Recursion

Once we have set!, we can now use it do define recursive functions.

This did not work because of the self-reference was undefined.

(let ((fact (lambda (n)
              (if (zero? n)
                  1
                  (* n (fact (- n 1)))))))
  (fact 10))

However this does!

(let ((fact 'dummy))
  (begin (set! fact (lambda (n)
                      (if (zero? n)
                          1
                          (* n (fact (- n 1))))))
         (fact 10)))

We can now use the desugaring technique to interpret recursive functions.

(defun interpret (ast env store)
  ...

  ((rec name value body) (let ([name 'dummy])
                           (begin (set! name value)
                                  body)))
  ...)

An example of its use is

(rec fact
  (lambda (n)
    (if (= n 0)
        1
        (* n (fact (- n 1)))))
  (fact 10))

Try to implement a single-binding version of Racket's letrec