;;; An evaluator (interpreter) for Husky, a higher-order functional language, ;;; written in the Intermediate Student Language with Lambda. ;;; ;;; (But really it's a meta-circular Scheme interpreter.) ;;; This file is mostly comments; the core of the interpreter is only ;;; 26 lines of actual code. ;;; -Olin ;;; Syntax -- the grammar of Husky, as Racket sexpressions. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; A HExp (Husky Expression) is one of: ;;; The Data ; How it looks as an s-exp ;;; -------- ; ------------------------ ;;; - Number ; ;;; - Var ; ;;; - (list 'const SExp) ; (const ) ;;; - (list 'fun (list Var ...) HExp) ; (fun ( ...) ) ;;; - (list 'if HExp HExp HExp) ; (if ) ;;; - (list HExp HExp ...) ; ( ...) ;;; ;;; A Var is a Symbol. ;;; Two example Husky programs: ;;; ((fun (abs) (list (abs (- 5 7)) ; Should produce ;;; (abs (- 7 5)))) ; '(2 2). ;;; (fun (x) (if (< x 0) (- x) x))) ;;; ;;; ((fun (x) (if (< x 0) (const (x is negative)) ; Should produce ;;; (if (= x 0) (const (x is zero)) ; '(x is negative). ;;; (const (x is positive))))) ;;; (* 3 (- 7 10))) ;;; ;;; For these two programs to work, you'd have to run them with a top-level ;;; environment that provided bindings for the five variables ;;; list - < = * ;;; Semantics -- semantic values, environments and the interpreter ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; A Value is one of: ;;; - SExp (a number, boolean, cons, etc.) ;;; - Procedure ;;; ;;; A Procedure is one of: ;;; - (make-closure [List-of Var] HExp Env) (a user procedure) ;;; - (make-primop [[List-of Value] -> Value]) (a built-in procedure) ;;; ;;; Closures are what we get when we evaluate (fun ( ...) ) terms ;;; in some given environment -- we package up the parameters ( ...), ;;; the function's expression, and the current environment into a ;;; closure. ;;; ;;; Primops represent "built-in" primitive operations that the interpreter does ;;; directly. Every primop comes with a handler that we use to do the primop. (define-struct closure (params body env)) (define-struct primop (handler)) ;;; Env = [Listof (make-binding Var Value)] (define-struct binding (var val)) ;;; An environment represents a set of variable/value bindings. ;;; lookup: Env Var -> Val ;;; Look up the variable's value in the environment. ;;; Environments are scanned left to right, so consing a binding for variable ;;; V onto the front of a list shadows any other bindings of V further down ;;; in the environment. (define (lookup env var) (cond [(empty? env) (error 'lookup "Variable is not bound: " var)] [else (local [(define b (first env))] (cond [(symbol=? (binding-var b) var) (binding-val b)] [else (lookup (rest env) var)]))])) (define test-env (list (make-binding 'x 5) (make-binding 'y 2) (make-binding 'x 7))) (check-expect (lookup test-env 'x) 5) (check-expect (lookup test-env 'y) 2) (check-error (lookup test-env 'z) "lookup: Variable is not bound: 'z") ;;; Eval & Apply -- the yin/yang pair that make the interpreter. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; eval : HExp Env -> Value ;;; app : Procedure [List-of Value] -> Value ;;;