1David Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceLecture 21: Think Globally, Mutate LocallyMost Beautifulest Snowflake in the worldby Jordan Buller, Jon Faulkner 2Lecture 21: Think Globally, Mutate LocallyReview: Names, Places, Mutation• A name is a place for storing a value.• A define creates a new place• A cons application creates two new places, the car and the cdr• A frame is a collection of places• An environment is a frame and a pointer to a parent environment• (set! name expr) changes the value in the place nameto the value of expr3Lecture 21: Think Globally, Mutate LocallyEnvironmentsglobalenvironment> (define x 3)+ : #<primitive:+>null? : #<primitive:null?>The global environment points to the outermost frame. It starts with all Scheme primitives.x : 34Lecture 21: Think Globally, Mutate LocallyProceduresglobalenvironment> (define double (lambda (x) (+ x x)))+ : #<primitive:+>null? : #<primitive:null?>double: ??x : 35Lecture 21: Think Globally, Mutate LocallyHow to Draw a Procedure• A procedure needs both code and an environment– We’ll see why soon• We draw procedures like this:EnvironmentpointerCode pointerparameters: xbody: (+ x x)6Lecture 21: Think Globally, Mutate LocallyHow to Draw a Procedure (for artists only)Environmentpointerx(+ x x)Input parameters(in mouth)Procedure Body27Lecture 21: Think Globally, Mutate LocallyProceduresglobalenvironment> (define double (lambda (x) (+ x x)))+ : #<primitive:+>null? : #<primitive:null?>double: x : 3parameters: xbody: (+ x x)8Lecture 21: Think Globally, Mutate LocallyApplication• Old rule: (Substitution model)Apply Rule 2: Compounds. If the procedure is a compound procedure, evaluate the body of the procedure with each formal parameter replaced by the corresponding actual argument expression value.9Lecture 21: Think Globally, Mutate LocallyNew Rule: Application1. Construct a new frame, enclosed in the environment of this procedure2. Create places in that frame with the names of each parameter3. Put the values of the parameters in those places4. Evaluate the body in the new environment10Lecture 21: Think Globally, Mutate Locally1. Construct a new frame, enclosed in the environment of this procedure2. Make places in that frame with the names of each parameter3. Put the values of the parameters in those places4. Evaluate the body in the new environmentglobalenvironment> (double 4)8+ : #<primitive:+>double: x : 3parameters: xbody: (+ x x)x : 4(+ x x)(+ 4 4)811Lecture 21: Think Globally, Mutate Locallyglobalenvironment+ : #<primitive:+>nest: x : 3parameter: xbody: (lambda (x) (+ x x))x : 3(define nest (lambda (x)(lambda (x)(+ x x))))> ((nest 3) 4)((lambda (x) (+ x x)) 4)x : 4(+ x x)12Lecture 21: Think Globally, Mutate LocallyEvaluation Rule 2 (Names)If the expression is a name, it evaluates to the value associated with that name.To find the value associated with a name, look for the name in the frame pointed to by the evaluation environment. If it contains a place with that name, use the value in that place. If it doesn’t, evaluate the name using the frame’s parent environment as the new evaluation environment. If the frame has no parent, error (name is not a place).313Lecture 21: Think Globally, Mutate Locallyevaluate-name(define (evaluate-name name env)(if (null? env) (error “Undefined name: …”)(if (frame-contains name (get-frame env))(lookup name (get-frame env))(evaluate-name name (parent-environment (get-frame env))))))Hmm…maybe we can define a Scheme interpreter in Scheme!14Lecture 21: Think Globally, Mutate LocallyCharge• PS5 due
View Full Document
Unlocking...