interp-ce.rkt

;; Closure-Creating Interpreters in Racket
#lang racket

;; expressions comprise the λ-calculus extended
;; to include numeric constants and the + builtin
(define (expr? e)
  (match e
    [(? number? n) #t]
    [`(+ ,(? expr? e0) ,(? expr? e1)) #t]
    [(? symbol? x) #t]
    [`(lambda (,(? symbol? x)) ,(? expr? e)) #t]
    [`(,(? expr? e0) ,(? expr? e1)) #t]))

(define empty-map (λ (var) (error "unknown variable")))
(define (ext-map map x val)
  (λ (y) (if (equal? x y)
             val
             (map y))))

;; values are either numbers or closures
(define (value? v)
  (match v
    [(? number? n) #t]
    [`(closure ,(? expr? e) ,env) #t]))

;; environments are mapping from variables to values
(define environment? (hash/c symbol? value?))

;; the interpreter takes an expression and environment
;; (used for variable lookup) and produces a value
(define/contract (interp expr env)
  (-> expr? environment? value?)
  (displayln "At expression, env")
  (pretty-print expr)
  (pretty-print env)
  (match expr
    ;; to evaluate a constant, just return it
    [(? number? n) n]
    ;; addition produces a number
    [`(+ ,(? expr? e0) ,(? expr? e1))
     (define v0 (interp e0 env))
     (define v1 (interp e1 env))
     (+ v0 v1)]
    ;; variables are looked up using the environment
    [(? symbol? x) (hash-ref env x)]
    ;; lambdas produce a value...
    ;; what value do they produce...?
    [`(lambda (,(? symbol? x)) ,(? expr? e))
     `(closure (lambda (,x) ,e) ,env)]
    ;; now do function application
    [`(,(? expr? e0) ,(? expr? e1))
     (define v0 (interp e0 env))
     (define v1 (interp e1 env))
     (match v0
       [`(closure (lambda (,x) ,e-body) ,env+)
        (let ([new-env (hash-set env+ x v1)])
          (interp e-body new-env))]
       [_ (error (format "tried to apply ~a, but it is not a closure" v0))])]))

;; running a program is simply running an expression
;; with the empty environment--this will work when
;; the program is closed (no free vars)
(define (run e)
  (interp e (hash)))

;; As an example...
(run '(((lambda (y) (lambda (x) (y x))) (lambda (z) (+ z 5))) 4))