;;; 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 ;;; ;;; Note: you will actually need to be in the "Advanced Student Language" ;;; because the REPL function takes no arguments. ;;; Syntax -- the grammar of Husky *programs*, as Racket *data* ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; 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. ;;; Some example Husky programs: ;;; ;;; (* 3 (- 10 7)) ; Produces 9. ;;; ;;; ((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) ; Should produce ;;; (const (input is negative)) ; '(input is negative). ;;; (if (= x 0) ;;; (const (input is zero)) ;;; (const (input is positive))))) ;;; (* 3 (- 7 10))) ;;; ;;; ((fun (x) (append (const (input is)) ; Does the same as above. ;;; (if (< x 0) ;;; (const (negative)) ;;; (if (= x 0) ;;; (const (zero)) ;;; (const (positive)))))) ;;; (* 3 (- 7 10))) ;;; ;;; (cons (const a) ; Should produce '(a = 3). ;;; (const (= 3))) ;;; ;;; For these programs to work, you'd have to run them with a top-level ;;; environment that provided bindings for the five variables ;;; list - < = * append cons ;;; 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 ( ...), <-- [ListOf Var] ;;; - the function's expression, and <-- HExp ;;; - the current environment <-- Env ;;; into a closure. ;;; ;;; Primops represent "built-in" primitive operations that the interpreter does ;;; directly. Every primop comes with a handler (a *Racket* function) that the ;;; interpreter will use to do the primop -- think of the handlers as being ;;; part of the interpreter. (define-struct closure [params body env]) (define-struct primop [handler]) ;;; Env = [Listof (make-binding Var Value)] ;;; An environment represents a set of variable/value bindings. (define-struct binding [var val]) ;;; lookup: Env Var -> Value ;;; 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. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; Symbol SExp -> Boolean ;;; Is the s-expression the given keyword? (define (keyword=? kwd sexp) ; Cheesy little syntax (and (symbol? sexp) ; utility function. (symbol=? kwd sexp))) ;; eval : HExp Env -> Value ;; Evaluate the Husky expression in the given environment. (define (eval exp env) (cond [(number? exp) exp] ; Numeric constants self-evaluate. ;; Look up variable references in the current environment. [(symbol? exp) (lookup env exp)] ;; Expression is a list -- CONST exp, FUN exp, IF exp or function call. [(cons? exp) (local [(define e1 (first exp))] (cond ;; (CONST sexp) -- a constant [(keyword=? 'const e1) (second exp)] ;; (FUN (var ...) body) [(keyword=? 'fun e1) ;; Make a code+env closure: (make-closure (second exp) ; the params (third exp) ; the body env)] ; the env the FUN form "sees". ;; (IF test then else) [(keyword=? 'if e1) ;; Depending on the results of evaluating the test expression, ;; pick either the "then" expression or the "else" expression, ;; and evaluate that. (eval (cond [(eval (second exp) env) (third exp)] [else (fourth exp)]) env)] ;; Function application: (fun-exp arg-exp1 ...) ;; Eval the function, and all the args, then apply function to args. [else (app (eval (first exp) env) (map (lambda (a) (eval a env)) (rest exp)))]))] [else (error 'eval "Not a valid Husky expression: " exp)])) ;;; Value [Listof Value] -> Value ;;; Apply the Husky function to the Husky arguments. (define (app f args) (cond [(closure? f) ; Proc is a closure: (eval (closure-body f) ; Eval the function's body (append (map make-binding ; in the closure env extended (closure-params f) ; with the parameter/argument args) ; bindings. (closure-env f)))] ;; Just hand off to primop's handler. [(primop? f) ((primop-handler f) args)] [else (error 'app "Attempting to apply a non-function: " f)])) ;;; Side note: Did you know MAP can operate on *multiple* lists? It can. ;;; (map < '(3 1 4) ;;; '(1 5 9)) => '(#f #t #t) ;;; Note the *big* difference between "eval" and "apply": ;;; - Eval works on code -- that is, an expression, program text. ;;; - Apply works on values. ;;; You can see this in the signatures of the two functions. ;; HExp -> Value ;; Run the Husky expression in the top-level environment (define (run e) (eval e top-env)) ; (The TOP-ENV is defined below.) (check-expect (run '1) 1) (check-expect (run '(const 1)) 1) (check-expect (run '(plus2 5)) 7) (check-expect (run '((fun (x) (minus1 (plus2 x))) 5)) 6) (check-expect (run '((fun (f) (f (f 0))) plus2)) 4) ;;; "REPL" is programming jargon for the "read-eval-print loop." ;;; Read in expressions, evaluating & printing each one, until the ;;; user inputs the symbol 'quit. This is basically the "evaluation" ;;; pane in Dr. Racket. (define (repl) ; <- No arguments, so you need "Advanced Student Language" (let ((exp (read))) ; Read in an expression from the terminal (cond [(and (symbol? exp) (symbol=? exp 'quit)) ; 'quit => all done "Done!"] ;; BEGIN is a magic keyword that means "do all the sub-expressions, ;; one after the other, then return the value of the last one." [else (begin (display (run exp)) ; Evaluate expression & print it, (newline) ; then print a new line, (repl))]))) ; then loop. ;;; What's missing? ;;; - A way to add definitions to the top-level environment in the repl. ;;; - A way to do functions with "circular" scope, so we can easily ;;; define recursive functions. See LETREC in the helpdesk. ;;; - The REPL should somehow recover control when the Husky code ;;; triggers an error, print out the error message, and continue. ;;; This involves figuring out a way to "catch" error exceptions, ;;; for which you'd have to dig into the Racket documentation a bit ;;; more... ;;; - More careful error checking. For example, a Husky IF expression should ;;; have *exactly* three sub-expressions. Greater or fewer than three should ;;; be an error. Likewise, we don't check to see if there are too many or ;;; too few arguments passed to a function by APP. What other syntactic ;;; and semantic errors could your interpreter check? Good error checking ;;; is important for a production-quality interpreter; less important for ;;; a "toy" student implementation. ;;; ;;; Scheme interpreters: you can write one in fifteen minutes... and ;;; spend the rest of your life improving it. ;;; ;;; Primops & the top-level environment ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; These are "built-in" functions that are implemented *in Racket*. ;;; That is, they are part of the interpreter, not written in Husky. ;;; Convert a Racket/ISL/ASL function into a Husky-interpreter primop. (define (racket->husky-primop f) (make-primop (lambda (args) (apply f args)))) (define top-env (list (make-binding 'plus1 (racket->husky-primop add1)) (make-binding 'minus1 (racket->husky-primop sub1)) (make-binding 'cons (racket->husky-primop cons)) (make-binding 'cons? (racket->husky-primop cons?)) (make-binding 'head (racket->husky-primop first)) (make-binding 'tail (racket->husky-primop rest)) (make-binding 'list (racket->husky-primop list)) (make-binding 'append (racket->husky-primop append)) (make-binding 'not (racket->husky-primop not)) (make-binding 'plus2 (racket->husky-primop (lambda (n) (+ n 2)))) (make-binding '* (racket->husky-primop *)) (make-binding '+ (racket->husky-primop +)) (make-binding '- (racket->husky-primop -)) (make-binding '= (racket->husky-primop =)) (make-binding '< (racket->husky-primop <)))) ;;; More examples ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (check-expect (run '((fun (abs) (list (abs (- 5 7)) (abs (- 7 5)))) (fun (x) (if (< x 0) (- x) x)))) '(2 2)) (check-expect (run '((fun (x) (if (< x 0) (const (input is negative)) (if (= x 0) (const (input is zero)) (const (input is positive))))) (* 3 (- 7 10)))) '(input is negative)) ;;; The hard way to write 120 -- really exercise the interpreter. ;;; Apply the Y combinator to a factorial generator; apply the result to 5. ;;; Yahoo. ;;; ;;; Do not attempt to operate heavy machinery while reading code below. (check-expect (run '(((fun (f) ((fun (g) (f (fun (x) ((g g) x)))) (fun (g) (f (fun (x) ((g g) x)))))) (fun (fact) (fun (n) (if (= n 0) 1 (* n (fact (- n 1))))))) 5)) 120) ;;; Some extensions you could make: ;;; - If we made strings & booleans self-evaluate, like numbers, ;;; we wouldn't have to tediously wrap them in (CONST ...) to ;;; include string & boolean constants. ;;; - Add COND, AND, OR as keywords ;;; - Add top-level DEFINE ;;; This is a little tricky -- a DEFINE form is not really an "expression." ;;; So it's not something we'd give to EVAL... ;;; - Add LETREC with circular scope to allow recursive functions ;;; to easily be defined. (You can look up LETREC in the Racket ;;; help desk. You will also need to figure out how to side-effect ;;; BINDING structs, with SET-BINDING-VALUE!, which is only available ;;; in the Advanced Student Language.)