staged-interpreter.rkt

#lang racket

;; An Expression is a Variable, an Abstraction, or an Application.
;; A Variable is a Symbol, denoting use of a bound variable.

;; An Abstraction is an (abs Symbol Expression), denoting a lambda term and evaluating to a Closure.
(struct abs (var exp))

;; An Application is an (app Expression Expression), denoting a function call
(struct app (fun arg))

;; An Environment is a hash-table mapping Symbol to Value.

;; extend-env : Symbol Value Environment -> Environment
;; Extends the given environment with a new binding.
(define (extend-env var val env) (hash-set env var val))

;; lookup-env : Symbol Environment -> Value or exception
(define (lookup-env env var) (hash-ref env var))

;; A Value is a Closure, represented by a Racket closure.

;;---------------------------------------------------------------------------
;;
;; Direct interpreter. Walks the syntax tree, doing the work *immediately*.

;; direct-eval : Expression Environment -> Value
(define (direct-eval exp env)
  (match exp
    [(abs var body) (lambda (val) (direct-eval body (extend-env var val env)))]
    [(app fun arg)
     (define f (direct-eval fun env))
     (define a (direct-eval arg env))
     (f a)]
    [var (lookup-env env var)]))

;;---------------------------------------------------------------------------
;;
;; Staged interpreter. Walks the syntax tree, building another tree of closures that do the
;; work *later*. (Depending on how you look at it, you might think of this is a kind of very
;; high-level compiler.)
;;
;; The environment is split into two: a *static* environment, managed at compile time, and
;; useful for detecting invalid variable references before runtime even starts; and a *dynamic*
;; or runtime environment, that actually holds the run-time values associated with particular
;; variables.

;; A StaticEnvironment is a hash-table mapping Symbol to a constant #t value.
(define (extend-static-env var static-env) (hash-set static-env var #t))
(define (bound-in-static-env? static-env var) (hash-has-key? static-env var))

;; staged-eval : Expression StaticEnvironment -> Environment -> Value
(define (staged-eval exp static-env)
  (match exp
    [(abs var body)
     (define body-c (staged-eval body (extend-static-env var static-env)))
     (lambda (runtime-env) (lambda (val) (body-c (extend-env var val runtime-env))))]
    [(app fun arg)
     (define fun-c (staged-eval fun static-env))
     (define arg-c (staged-eval arg static-env))
     (lambda (runtime-env) ((fun-c runtime-env) (arg-c runtime-env)))]
    [var
     (when (not (bound-in-static-env? static-env var))
       (error 'staged-eval "Detected use of an unbound variable: ~a" var))
     (lambda (runtime-env) (lookup-env runtime-env var))]))