CSSE 304 Day 19
First, we finish the material from Day 18. Interpreter details
Today or tomorrow: add let, if, lambda to the interpreted language
Aside: more about map
> (define a 0)
> (map (lambda (x)
(set! a (add1 a))
a)
‘(a b c d e f g h i j k l
m n o p))
What is the result?
1
INTERPRETER PROJECT INTRODUCTION
Why and What?
• Why do I have you write an interpreter?
• What is an interpreter? – A mapping from
__source code___ to _____meaning___ .
– Usually the “meaning” will be a returned Scheme value
2
Major parts of an interpreter
• Front-end Analysis
– Lexical analysis (scanning)
What are the pieces (tokens) of the program?
– Syntax analysis (parsing, lexical address)
How do the pieces fit together (AST)?
– Type checking/coercion. (not in Scheme)
Are the types of things consistent with their uses?
• Optimization of the code
– We will not discuss this much (Take CSSE 404)
• Evaluation
– This is the part that we will focus on
Language
• Why is Scheme
… the implementation language?
– In CSSE 404, …
• … the source language?
• They do it differently in the EoPL book.
3
Interpreter background code
• We have
– The notion of free and bound variables
– parser that produces abstract expression trees
– syntax error checking
– environments
– lexical-address
– A knowledge of how closures and environments work
– soon we will encounter CPS • The rest is mostly details
Load everything up!
; evaluator for simple expressions.
; Possible starting point for first
; interpreter assignment. In file main.ss ;
; Claude Anderson. Last modified October, 2014
(load “chez-init.ss”)
(define load-all ; make it easy to reload the files (lambda () ; when you are testing
(load “datatypes.ss”) (load “parse.ss”)
(load “env.ss”)
(load “interpreter.ss”)))
(load-all)
Code is linked from today’s session on the Schedule page.
There is also a single-file version.
4
CSSE 304 Interpreter
• Read-eval-print (REP) loop:
– Print a prompt
– Read the next form (e.g., expression) to be evaluated.
– Parse the form to give an abstract syntax tree (AST). A11
– Syntax-expand the AST to produce an AST that only has
core forms. A14
– Evaluate the expanded AST to produce an expressed
value. A13, A16, A17-A19
– Print the value (if not void) and repeat all of these steps.
– Write things in continuation-passing style A15, A18
• Alternate interface for grading program
– (eval-one-exp
read-eval-print loop
Here is the main driver for the interactive interpreter. The major part that is left for you to write is top-level- eval (and the procedures that it calls).
(define rep ; “read-eval-print” loop
(lambda ()
(display “–> “) ; new prompt on purpose
(let ([answer
(top-level-eval
(parse-exp(read)))])
(eopl:pretty-print answer)
;; TODO: are there answers that
;; should display differently?
(rep))))
; tail-recursive, so stack doesn’t grow
5
top-level-eval
(define top-level-eval
(lambda (parsed-form)
(eval-exp parsed-form)))
Later we’ll add some syntactic forms that are not expressions; for example,
(define var exp).
eval-exp may not be sufficient for those forms, so we may need to add other cases to top-level-eval.
representing procedures
(define-datatype proc-val proc-val?
[prim-proc ; primitive procedure
(name symbol?)])
; Datatype for procedures.
; At first we have only one kind of procedure,
; but more kinds will be added later.
; The first kind that we will add:
; closures created by execution of lambda
6
eval-exp – how it works
• What it returns depends on the type of expression.
– If it’s a literal expression … – If it’s a variable reference … – If it’s an application …
eval-exp code
; eval-exp “is” the interpreter
(define eval-exp
(lambda (exp)
(cases expression exp
[lit-exp (datum) datum]
[var-exp (id) ; look up its value.
(apply-env init-env id
(lambda (x) x) ; procedure to call if id
; is found in the environment
(lambda () ; proc to call if id is not found
(eopl:error ‘apply-env
“variable not bound: ~s”
id)))]
[app-exp (rator rands)
(let ([proc-value (eval-exp rator)]
[args (eval-rands rands)])
(apply-proc proc-value args))]
[else (eopl:error ‘eval-exp
“Bad abstract syntax: ~a” exp)])))
7
eval-rands and apply-proc
(define eval-rands ; evaluate all of the args
(lambda (rands) ; return a list of values
(map eval-exp rands)))
; Apply a procedure to its arguments.
; At this point, only primitive procedures.
; User-defined procedures will be added later.
(define apply-proc
(lambda (proc-value args)
(cases proc-val proc-value
[prim-proc (op) (apply-prim-proc op
args)]
[else (eopl:error ‘apply-proc
“Attempt to apply bad procedure:”
proc-value)])))
apply-prim-proc
; Usually an interpreter must define each
; built-in (primitive) procedure
; individually.
(define apply-prim-proc
(lambda (prim-proc args)
(case prim-proc
[(+) (+ (1st args) (2nd args))]
; better?: (apply + args)
[(-) (- (1st args) (2nd args))]
[(*) (* (1st args) (2nd args))]
[(add1) (+ (1st args) 1)]
[(sub1) (- (1st args) 1)]
[(cons) (cons (1st args) (2nd args))]
[(=) (= (1st args) (2nd args))]
[else (eopl:error ‘apply-prim-proc
“Bad primitive procedure name:”
prim-op)])))
8
build the initial environment
(define *prim-proc-names* ‘(+ – * add1 sub1 cons =))
(define init-env ; initial environment
(extend-env ; only contains
; primitive procedures.
*prim-proc-names* ; Recall that an
; environment
; associates values
(map prim-proc ; (not expressions)
; with variables.
*prim-proc-names*)
(empty-env)))
Next: Enhance the Interpreter
• add to eval-exp: – let-exp,
– if-exp,
– lambda-exp
• How to apply user-defined procedures?
(define-datatype expression expression?
[let-exp
(vars (list-of symbol?))
(exps (list-of expression?))
(bodies (list-of expression?))] . . .)
9
top-level-eval
(modified to support let)
(define global-env init-env)
(define top-level-eval
(lambda (form)
(eval-exp form (empty-env))))
eval-exp code
(modified to support let) ; eval-exp “is” the interpreter
(define eval-exp
(let ([identity-proc (lambda (x) x)])
(lambda (exp env)
(cases expression exp
[lit-exp (datum) datum]
[var-exp (id) ; look up its value.
(apply-env env
id
identity-proc ; procedure to call if var is in env (lambda () ; procedure to call if var is not in env
(apply-env global-env ; was init-env
id
identity-proc
(lambda ()
(error ‘apply-env
“variable ~s is not bound”
id)))))]
;; more cases on next slide
10
eval-exp code (modified to support let)
; eval-exp “is” the interpreter
(define eval-exp
(lambda (exp env)
(cases expression exp
; cases from the previous slide
[app-exp (rator rands)
(let ([proc-value (eval-exp rator env)]
[args (eval-rands rands env)])
(apply-proc proc-value args))]
[else (error ‘eval-exp
“Bad abstract syntax: ~a” exp)])))
Now add if and lambda
• if
• lambda
• application of a closure
• These are likely to happen in the the next day’s class
11