DOC PREVIEW
MIT 6 001 - Environment model

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

11/356.001 SICPEnvironment model; Can you figure out why this code works?(define make-counter (lambda (n)(lambda () (set! n (+ n 1))n )))(define ca (make-counter 0))(ca) ==> 1(ca) ==> 2(define cb (make-counter 0))(cb) ==> 1(ca) ==> 3 ; ca and cb are independent2/35The Environment Model is:• A precise, completely mechanical description of:• name-rule looking up the value of a variable• define-rule creating a new definition of a var• set!-rule changing the value of a variable• lambda-rule creating a procedure• application applying a procedure•Basis for implementing a scheme interpreter•for now: draw EM state with boxes and pointers•later on: implement with code•Enables analyzing arbitrary scheme code:•Example: make-counter3/35A shift in viewpoint• As we introduce the environment model, we are going to shift our viewpoint on computation• Variable: • OLD – name for value• NEW – place into which one can store things• Procedure:• OLD – functional description• NEW – object with inherited context• Expressions•Now only have meaning with respect to an environment4/35Frame: a table of bindings• Binding: a pairing of a name and a valueExample: x is bound to 15 in frame Ay is bound to (1 2) in frame Athe value of the variable x in frame A is 1521x: 15Ay:5/35Environment: a sequence of frames• Environment E1 consists of frames A and Bz: 10BE1E2x: 15A21y:this arrow is calledthe enclosingenvironment pointer• Environment E2 consists of frame B only• A frame may be shared by multiple environments6/35Evaluation in the environment model• All evaluation occurs in an environment• The current environment changes when theinterpreter applies a procedure•To evaluate a combination•Evaluate the subexpressions in the current environment•Apply the value of the first to the values of the rest•The top environment is called the global environment (GE)•Only the GE has no enclosing environment27/35Name-rule• A name X evaluated in environment E givesthe value of X in the first frame of E where X is boundx: 15A21z: 10x: 3BE1GEy:• In E1, the binding of x in frame A shadows the binding of x in B•x |GE==> 3•z |GE==> 10 z |E1==> 10 x |E1==> 158/35Define-rule• A define special form evaluated in environment Ecreates or replaces a binding in the first frame of E(define z 25) |E1(define z 20) |GEz: 25z: 20x: 15A21z: 10x: 3BE1GEy:z |GE==> 20z |E1==> 259/35Set!-rule• A set! of variable X evaluated in environment E changes the binding of X in the first frame of E where X is bound(set! z 25) |E1(set! z 20) |GE2025x: 15A21z: 10x: 3BE1GEy:10/35Compare define versus set!(define z 25) |E1(define z 20) |GEz: 25z: 20x: 15A21z: 10x: 3BE1GEy:(set! z 25) |E1(set! z 20) |GE2025x: 15A21z: 10x: 3BE1GEy:11/35Your turn: evaluate the following in order(+ z 1) |E1 ==> (set! z (+ z 1)) |E1(modify EM)(define z (+ z 1)) |E1 (modify EM)(set! y (+ z 1)) |GE (modify EM)x: 15A21z: 10x: 3BE1GEy:12/35Your turn: evaluate the following in order(+ z 1) |E1 ==> (set! z (+ z 1)) |E1(modify EM)(define z (+ z 1)) |E1 (modify EM)(set! y (+ z 1)) |GE (modify EM)x: 15A21z: 10x: 3BE1GEy:1111z: 12Error:unbound variable: y313/35Double bubble: how to draw a procedure(lambda (x) (* x x))evallambda-ruleA compound procthat squares itsargument#[compound-...]printEnvironmentpointerCode pointerparameters: xbody: (* x x)14/35Lambda-rule• A lambda special form evaluated in environment Ecreates a procedure whose environment pointer is Ex: 15Az: 10x: 3BE1parameters: xbody: (* x x)square:(define square (lambda (x) (* x x))) |E1environment pointerpoints to frame Abecause the lambdawas evaluated in E1and E1 → AEvaluating a lambda actually returns a pointer to the procedure object15/35To apply a compound procedure P to arguments:1. Create a new frame A2. Make A into an environment E:A's enclosing environment pointer goes to the same frame as the environment pointer of P3. In A, bind the parameters of P to the argument values4. Evaluate the body of P with E as the current environmentYou mustmemorize thesefour steps!!16/35(square 4) |GEx: 10GEparameters: xbody: (* x x)square:AE1x: 4(* x x) |E1*: #[prim]==> 16* |E1==> #[prim]x |E1==> 4square |GE==> #[proc]17/35Example: inc-squareGEp: xb: (* x x)square:inc-square:p: yb: (+ 1 (square y))(define square (lambda (x) (* x x))) |GE(define inc-square (lambda (y) (+ 1 (square y))) |GE18/35Example cont'd: (inc-square 4) |GEGEp: xb: (* x x)square:inc-square:p: yb: (+ 1 (square y))E1y: 4(+ 1 (square y)) |E1+ |E1==> #[prim]inc-square |GE==> #[compound-proc ...](square y) |E1419/35Example cont'd: (square y) |E1E2x: 4(* x x) |E2* |E2==> #[prim] x |E2 ==> 4GEp: xb: (* x x)square:inc-square:p: yb: (+ 1 (square y))E1y: 4==> 16(+ 1 16) ==> 17y |E1==> 4square |E1==> #[compound]20/35Lessons from the inc-square example• EM doesn't show the complete state of the interpreter• missing the stack of pending operations• The GE contains all standard bindings (*, cons, etc)• omitted from EM drawings• Useful to link environment pointer of each frame to the procedure that created it21/35Example: make-counter• Counter: something which counts up from a number(define make-counter (lambda (n)(lambda () (set! n (+ n 1))n)))(define ca (make-counter 0))(ca) ==> 1(ca) ==> 2(define cb (make-counter 0))(cb) ==> 1(ca) ==> 3(cb) ==> 2 ; ca and cb are independent22/35(define ca (make-counter 0)) |GEGEp: nb:(lambda ()(set! n(+ n 1))n)make-counter:E1n: 0(lambda () (set! n (+ n 1)) n) |E1p: b:(set! n (+ n 1)) nca:environment pointerpoints to E1because the lambdawas evaluated in E123/35(ca) |GE(set! n (+ n 1)) |E21n |E2 ==> 1 E2emptyGEp: nb:(lambda ()(set! n(+ n 1))n)make-counter:E1n: 0p: b:(set! n (+ n 1)) nca:==> 124/35E3(ca) |GE(set! n (+ n 1)) |E3GEp: nb:(lambda ()(set! n(+ n 1))n)make-counter:E1n: 0p: b:(set! n (+ n 1)) nca:1n |E3 ==> 2 empty==> 22525/35(define cb (make-counter 0)) |GE(lambda () (set! n (+ n 1)) n) |E4n: 0E4p: b:(set! n (+ n 1)) ncb:GEp: nb:(lambda ()(set! n(+ n 1))n)make-counter:E1n: 2p: b:(set! n (+ n 1)) nca:E326/35(cb) |GE1n: 0E4p: b:(set! n (+ n 1)) ncb:GEp: nb:(lambda ()(set! n(+ n 1))n)make-counter:E1n: 2p: b:(set! n (+ n 1)) nca:E2==> 1E527/35Capturing state in local frames & proceduresn: 1E4p: b:(set! n (+ n 1)) ncb:GEp: nb:(lambda ()(set! n(+ n 1))n)make-counter:E1n: 2p: b:(set! n (+ n 1)) nca:28/35Lessons from the make-counter example• Environment diagrams get complicated very


View Full Document

MIT 6 001 - Environment model

Documents in this Course
Quiz 1

Quiz 1

6 pages

Databases

Databases

12 pages

rec20

rec20

2 pages

Quiz II

Quiz II

15 pages

Streams

Streams

5 pages

Load more
Download Environment model
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Environment model 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 Environment model 2 2 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?