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

;; values are either numbers or closures
(define (value? v)
  (match v
    [(? number? n) #t]
    [`(closure ,(? expr? e) ,(? environment?)) #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?)
  (match expr
    [(? number? n) n]
    [(? symbol? x) (hash-ref env x)]
    [`(lambda (,x) ,e) `(closure ,expr ,env)]
    [`(+ ,e0 ,e1)
     (let* ([v0 (interp e0 env)]
            [v1 (interp e1 env)])
       (+ v0 v1))]
    [`(,e0 ,e1)
     (let ([clo-to-apply (interp e0 env)])
       (match clo-to-apply
         [`(closure (lambda (,x) ,e-body) ,env+)
          (interp e-body (hash-set env+ x (interp e1 env)))]
         [_ (error "expected to apply a closure")]))]))

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