116.001 SICPInterpretation• Parts of an interpreter• Arithmetic calculator• Names• Conditionals and if• Storing procedures in the environment• Environment as explicit parameter• Defining new procedures2Why do we need an interpreter?• Abstractions let us bury details and focus on use of modules to solve large systems• We need a process to unwind abstractions at execution time to deduce meaning• We have already seen such a process – the Environment Model• Now want to describe that process as a procedure3Stages of an interpreter"(average 40 (+ 5 5))"( average 40 (+ 5 5 ) )40symbolaverage5symbol +525Lexical analyzerParserEvaluatorEnvironmentPrinter"25"input to each stage4Role of each part of the interpreter• Lexical analyzer• break up input string into "words" called tokens• Parser• convert linear sequence of tokens to a tree• like diagramming sentences in elementary school• also convert self-evaluating tokens to their internal values– e.g., #f is converted to the internal false value • Evaluator• follow language rules to convert parse tree to a value• read and modify the environment as needed• Printer• convert value to human-readable output string5Goal of today’s lecture• Implement an interpreter• Only write evaluator and environment• Use Scheme's reader for lexical analysis and parsing• Use Scheme's printer for output• To do this, our language must resemble Scheme• Call the language scheme*• All names end with a star to distinguish from Scheme names• Start with interpreter for simple arithmetic expressions• Progressively add more features61. Arithmetic calculatorWant to evaluate arithmetic expressions of two arguments, like:(plus* 24 (plus* 5 6))27(define (tag-check e sym) (and (pair? e) (eq? (car e) sym)))(define (sum? e) (tag-check e 'plus*))(define (eval exp)(cond((number? exp) exp)((sum? exp) (eval-sum exp))(else(error "unknown expression " exp))))(define (eval-sum exp) (+ (eval (cadr exp)) (eval (caddr exp))))(eval '(plus* 24 (plus* 5 6)))1. Arithmetic calculator8We are just walking through a tree …24plus*65plus*(eval ) 24plus*65plus*sum? checks the tag9We are just walking through a tree …(eval-sum ) 24plus*65plus*65plus*(+ (eval 24) (eval ))(+ (eval 5) (eval 6))101. Arithmetic calculator(plus* 24 (plus* 5 6))• What are the argument and return values of eval each time it is called in the evaluation of this expression?(eval '(plus* 24 (plus* 5 6)))(eval-sum '(plus* 24 (plus* 5 6)))(eval 24) (eval '(plus* 5 6))(eval-sum '(plus* 5 6))(eval 5) (eval 6)245 611113535111. Things to observe• cond determines the expression type• No work to do on numbers• Scheme's reader has already done the work• It converts a sequence of characters like "24" to an internal binary representation of the number 24• eval-sum recursively calls eval on both argument expressions122. Names• Extend the calculator to store intermediate results as named values(define* x* (plus* 4 5)) store result as x*(plus* x* 2) use that result• Store bindings between names and values in a table313(define (define? exp) (tag-check exp 'define*))(define (eval exp)(cond((number? exp) exp)((sum? exp) (eval-sum exp))((symbol? exp) (lookup exp))((define? exp) (eval-define exp))(else(error "unknown expression " exp)))); table ADT from prior lecture:; make-table void -> table; table-get table, symbol -> (binding | null); table-put! table, symbol, anytype -> undef; binding-value binding -> anytype(define environment (make-table))2. Names14(define (lookup name) (let ((binding (table-get environment name)))(if (null? binding)(error "unbound variable: " name)(binding-value binding))))(define (eval-define exp)(let ((name (cadr exp))(defined-to-be (caddr exp)))(table-put! environment name (eval defined-to-be))'undefined))(eval '(define* x* (plus* 4 5)))(eval '(plus* x* 2))2. Names …How many times is eval called in these two evaluations?4 evals – define*, plus*, 4, 53 evals – plus*, x*, 215Evaluation of page 2 lines 36 and 37(eval '(define* x* (plus* 4 5)))(eval '(plus* 4 5))(eval 4) ==> 4(eval 5) ==> 5==> 9names valuesx* 9==> undefined(eval '(plus* x* 2))(eval 'x*) ==> 9(eval 2) ==> 2==> 11• Show argument and return values of eval for each call• Show the environment each time it changesenvironment162. Things to observe• Use scheme function symbol? to check for a name• the reader converts sequences of characters like "x*"to symbols in the parse tree• Can use any implementation of the table ADT• eval-define recursively calls eval on the second subtree but not on the first one• eval-define returns a special undefined value173. Conditionals and if• Extend the calculator to handle predicates and if:(if* (greater* y* 6) (plus* y* 2) 15)greater* an operation that returns a booleanif* an operation that evaluates the first subexp,and checks if its value is true or false• What are the argument and return values of eval each time it is called in the expression above?18(define (greater? exp) (tag-check exp 'greater*))(define (if? exp) (tag-check exp 'if*))(define (eval exp)(cond ...((greater? exp) (eval-greater exp))((if? exp) (eval-if exp))(else (error "unknown expression " exp))))(define (eval-greater exp)(> (eval (cadr exp)) (eval (caddr exp))))(define (eval-if exp)(let ((predicate (cadr exp))(consequent (caddr exp))(alternative (cadddr exp)))(let ((test (eval predicate)))(cond((eq? test #t) (eval consequent))((eq? test #f) (eval alternative))(else (error "predicate not boolean: "predicate))))))(eval '(define* y* 9))(eval '(if* (greater* y* 6) (plus* y* 2) 15))3. Conditionals and IfNote: if* is stricterthan Scheme’s if419We are just walking through a tree …(eval )6y*greater*if*6y*greater* 2y*plus*15Then (eval ) or (eval 15 )2y*plus*20Evaluation of page 3 line 32(eval '(if* (greater* y* 6) (plus* y* 2) 15))(eval '(greater* y* 6))(eval 'y*) ==> 9(eval 6) ==> 6==> #t(eval '(plus* y* 2))(eval 'y*) ==> 9(eval 2) ==> 2==> 11==> 11213. Things to observe• eval-greater is just like eval-sum from page 1• recursively call eval on both argument expressions• call Scheme > to compute value • eval-if does not call eval on all argument expressions:• call eval on the predicate• call eval either
View Full Document
Unlocking...