MIT 6 001 - Variations on a Scheme (7 pages)

Previewing pages 1, 2 of 7 page document View the full content.
View Full Document

Variations on a Scheme



Previewing pages 1, 2 of actual document.

View the full content.
View Full Document
View Full Document

Variations on a Scheme

146 views


Pages:
7
School:
Massachusetts Institute of Technology
Course:
6 001 - Structure and Interpretation of Computer Programs
Structure and Interpretation of Computer Programs Documents
Unformatted text preview:

Building up a language 6 001 SICP Variations on a Scheme 1 eval apply core Scheme Evaluator A Grand Tour Making the environment model concrete Defining eval defines the language Provides mechanism for unwinding abstractions 3 Techniques for language design 4 Interpretation eval apply Semantics vs syntax Syntactic transformations 5 Beyond Scheme designing language variants Lexical scoping vs Dynamic scoping 2 syntax procedures environment manipulation primitives and initial env read eval print loop 1 40 Stages of an interpreter input to each stage The Core Evaluator 1 average 4 5 5 Lexical analyzer Parser 2 40 average 5 4 5 Eval exp env proc args Apply Evaluator symbol average Environment Printer eval apply core define square x x x square 4 x 4 x x 4 symbol 5 5 Core evaluator eval dispatch on expression type apply eval args then apply operator 7 7 The Core Evaluator 3 40 1 Eval exp env proc args eval apply core define square x x x square x Apply Core evaluator eval dispatch on expression type apply eval args then apply operator 5 40 4 40 Meval define meval exp env primitives 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 special forms 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 application mapply meval operator exp env list of values operands exp env else error Unknown expression type EVAL exp 6 40 1 Basic Semantics m eval m apply Pieces 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 primitive expressions self evaluating quoted variables and the environment variable definition lookup and assignment conditionals if cond procedure creation sequences Begin procedure application 7 40 Pieces of Eval Apply 8 40 Mapply 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 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 9 40 Side comment procedure body 10 40 Pieces 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 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 11 40 12 40 2 Pieces of Eval Apply Pieces 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 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 13 40 Pieces of Eval Apply 14 40 Pieces 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 define eval if exp env if m eval if predicate exp env m eval if consequent exp env m eval if alternative exp env 15 40 2 Syntactic Abstraction Semantics What the language means Model of computation syntax procedures Basic 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 Syntax Particulars of writing expressions E g how to signal different expressions Routines to get information out of expressions Separation of syntax and semantics allows one to easily alter syntax eval apply 16 40 define operator app car app define operands app cdr app syntax procedures Routines to manipulate expressions 17 40 define no operands args null args define first operand args car args define rest operands args cdr args 18 40 3 Example Changing Syntax Implementing Syntactic Sugar Suppose you wanted a verbose application syntax i e instead of Idea Easy way to add alternative convenient syntax Implement a simpler core in the evaluator proc arg1 arg2 use let as sugared procedure application CALL proc ARGS arg1 arg2 Changes only in the syntax routines let name1 val1 name2 val2 body define application exp tagged list exp CALL define operator app cadr app define operands app cdddr app lambda name1 name2 val1 val2 body 19 40 Detect and Transform the Alternative Syntax 20 40 Let Syntax Transformation define m eval exp env cond self evaluating exp exp variable exp lookup variable value exp env quoted exp text of quotation exp let exp m eval let combination exp env application exp m apply m eval operator exp env list of values operands exp env else error Unknown expression exp FROM let x 23 y 15 dosomething x y TO lambda x y dosomething x y 23 15 21 40 Let Syntax Transformation 22 40 Defining Procedures define let exp tagged list exp let define foo lambda x body define foo x body define let bound variables let exp map car cadr let exp define let values let exp map cadr


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Variations on a Scheme and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Variations on a Scheme and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?