An implementation of the lambda calculus with closures and environment passing

lambda-closure.rkt

#lang plait

(define-type Exp
  [varE (s : Symbol)]
  [numE (n : Number)]
  [lamE (var : Symbol) (body : Exp)]
  [appE (fun : Exp) (arg : Exp)])

(define-type Value
  [numV (n : Number)]
  [funV (arg : Symbol) (body : Exp) (closure : Env)])

(define-type-alias Env (Hashof Symbol Value))
(define mt-env (hash empty)) ;; "empty environment"

(define (lookup (s : Symbol) (n : Env))
  (type-case (Optionof Value) (hash-ref n s)
    [(none) (error 'runtime "not bound")]
    [(some v) v]))

(extend : (Env Symbol Value -> Env))
(define (extend old-env new-name value)
  (hash-set old-env new-name value))


(interp : (Exp Env -> Value))
(define (interp e env)
  (type-case Exp e
    [(varE s) (lookup s env)]
    [(numE n) (numV n)]
    [(lamE v b) (funV v b env)]
    [(appE fun arg)
     (let [(evalfun (interp fun env))
           (evalarg (interp arg env))]
       (type-case Value evalfun
         [(funV arg body closure)
          ; run body with environment closure[arg |-> evalarg]
          (interp body (extend closure arg evalarg))]
         [(numV n) (error 'runtime "trying to run a number")]))]))

(test (interp (appE (lamE 'x (varE 'x)) (numE 10)) mt-env) (numV 10))
(test (interp (appE (lamE 'x (varE 'x)) (lamE 'y (varE 'y))) mt-env) (funV 'y (varE 'y) mt-env))
(test (interp (appE (lamE 'x (lamE 'x (varE 'x))) (numE 10)) mt-env) (funV 'x (varE 'x) (hash (list (pair 'x (numV 10))))))