11/406.001 SICPVariations on a Scheme• Scheme Evaluator – A Grand Tour• Making the environment model concrete• Defining eval defines the language– Provides mechanism for unwinding abstractions• Techniques for language design:• Interpretation: eval/apply• Semantics vs. syntax• Syntactic transformations• Beyond Scheme – designing language variants• Lexical scoping vs. Dynamic scoping2/40Building up a language...eval/applycore1.primitives andinitial env.4.environmentmanipulation3.read-eval-printloop5.syntaxprocedures2.3/40Stages of an interpreter"(average 4 (+ 5 5))"( average 4 (+ 5 5))4symbolaverage5symbol +57Lexical analyzerParserEvaluatorEnvironmentPrinter"7"input to each stage4/40The Core Evaluator• Core evaluator• eval: dispatch on expression type• apply: eval args then apply operatoreval/applycore1.Evalproc & argsexp &envApply(define (square x)(* x x))(square 4)x = 4(* x x)6/40How to describe Eval?exp valueHow to describe?EvalmicroprocessorevalMeval7/40Meval(define (meval exp env)(cond ((self-evaluating? exp) exp)((variable? exp) (lookup-variable-value exp env))((quoted? exp) (text-of-quotation exp))((assignment? exp) (eval-assignment exp env))((definition? exp) (eval-definition exp env))((if? exp) (eval-if exp env))((lambda? exp)(make-procedure (lambda-parameters exp) (lambda-body exp)env))((begin? exp) (eval-sequence (begin-actions exp) env))((cond? exp) (meval (cond->if exp) env))((application? exp)(mapply (meval (operator exp) env)(list-of-values (operands exp) env)))(else (error "Unknown expression type -- EVAL" exp))))primitivesspecial formsapplication28/40Basic Semantics: m-eval & m-apply• primitive expressions– self-evaluating, quoted• variables and the environment– variable definition, lookup, and assignment• conditionals– if, cond• procedure creation• sequences– Begin• procedure application9/40Pieces of Eval&Apply(define (meval exp env)(cond ((self-evaluating? exp) exp)((variable? exp) (lookup-variable-value exp env))((quoted? exp) (text-of-quotation exp))((assignment? exp) (eval-assignment exp env))((definition? exp) (eval-definition exp env))((if? exp) (eval-if exp env))((lambda? exp)(make-procedure (lambda-parameters exp) (lambda-body exp)env))((begin? exp) (eval-sequence (begin-actions exp) env))((cond? exp) (eval (cond->if exp) env))((application? exp)(mapply (meval (operator exp) env)(list-of-values (operands exp) env)))(else (error "Unknown expression type -- EVAL" exp))))10/40Pieces of Eval&Apply(define (list-of-values exps env)(cond ((no-operands? exps) ‘())(else (cons (m-eval (first-operand exps) env)(list-of-values (rest-operands exps) env)))))11/40Mapply(define (mapply procedure arguments)(cond ((primitive-procedure? procedure)(apply-primitive-procedure procedure arguments))((compound-procedure? procedure)(eval-sequence(procedure-body procedure)(extend-environment (procedure-parameters procedure)arguments(procedure-environment procedure))))(else (error "Unknown procedure type --APPLY" procedure))))12/40Side comment – procedure body• The procedure body is a sequence of one or more expressions:(define (foo x) (do-something (+ x 1))(* x 5))•In m-apply, we eval-sequence the procedure body.13/40Pieces of Eval&Apply(define (eval-sequence exps env)(cond ((last-exp? exps) (m-eval (first-exp exps) env))(else (m-eval (first-exp exps) env)(eval-sequence (rest-exps exps) env))))314/40Pieces of Eval&Apply(define (meval exp env)(cond ((self-evaluating? exp) exp)((variable? exp) (lookup-variable-value exp env))((quoted? exp) (text-of-quotation exp))((assignment? exp) (eval-assignment exp env))((definition? exp) (eval-definition exp env))((if? exp) (eval-if exp env))((lambda? exp)(make-procedure (lambda-parameters exp) (lambda-body exp)env))((begin? exp) (eval-sequence (begin-actions exp) env))((cond? exp) (eval (cond->if exp) env))((application? exp)(mapply (meval (operator exp) env)(list-of-values (operands exp) env)))(else (error "Unknown expression type -- EVAL" exp))))15/40Pieces of Eval&Apply(define (eval-assignment exp env)(set-variable-value! (assignment-variable exp)(meval (assignment-value exp) exp)env))(define (eval-definition exp env)(define-variable! (definition-variable exp)(meval (definition-value exp) env)env))16/40Pieces of Eval&Apply(define (meval exp env)(cond ((self-evaluating? exp) exp)((variable? exp) (lookup-variable-value exp env))((quoted? exp) (text-of-quotation exp))((assignment? exp) (eval-assignment exp env))((definition? exp) (eval-definition exp env))((if? exp) (eval-if exp env))((lambda? exp)(make-procedure (lambda-parameters exp) (lambda-body exp)env))((begin? exp) (eval-sequence (begin-actions exp) env))((cond? exp) (eval (cond->if exp) env))((application? exp)(mapply (meval (operator exp) env)(list-of-values (operands exp) env)))(else (error "Unknown expression type -- EVAL" exp))))17/40Pieces of Eval&Apply(define (eval-if exp env)(if (m-eval (if-predicate exp) env)(m-eval (if-consequent exp) env)(m-eval (if-alternative exp) env)))18/40Syntactic Abstraction• Semantics• What the language means• Model of computation•Syntax• Particulars of writing expressions• E.g. how to signal different expressions• Separation of syntax and semantics:allows one to easily alter syntax eval/applysyntaxproceduressyntaxprocedures2.19/40Basic Syntax(define (tagged-list? Exp tag)(and (pair? Exp) (eq? (car exp) tag)))• Routines to detect expressions(define (if? exp) (tagged-list? exp 'if))(define (lambda? exp) (tagged-list? exp 'lambda))(define (application? exp) (pair? exp))• Routines to get information out of expressions(define (operator app) (car app))(define (operands app) (cdr app))• Routines to manipulate expressions(define (no-operands? args) (null? args))(define (first-operand args) (car args))(define (rest-operands args) (cdr args))420/40Example – Changing Syntax• Suppose you wanted a "verbose" application syntax, i.e., instead of (<proc> <arg1> <arg2> . . .)use(CALL <proc> ARGS <arg1> <arg2> ...)• Changes – only in the syntax routines!(define (application? exp) (tagged-list? exp 'CALL))(define (operator app) (cadr app))(define (operands app) (cdddr app))21/40Implementing "Syntactic Sugar"• Idea:• Easy way to add alternative/convenient syntax • Implement a simpler "core" in the evaluator• "let" as sugared procedure application:(let ((<name1> <val1>)(<name2> <val2>))<body>)((lambda (<name1> <name2>) <body>)<val1> <val2>)22/40Detect and Transform the
View Full Document
Unlocking...