Slide 1NoticesEvaluation Rule 2: NamesNames and PlacesBang!set! should make you nervousDefining nextxEvaluation Rulesset-car! and set-cdr!Slide 10Slide 11mapImperative SolutionProgramming with MutationMutation Changes Everything!Why Substitution Fails?Slide 17Lambda and PlacesLocation, Location, LocationEnvironmentsSlide 21ProceduresHow to Draw a ProcedureHow to Draw a Procedure (for artists only)Slide 25ApplicationNew Application Rule 2:Slide 28ChargeDavid Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceLecture 19: Programming with State2Lecture 19: MutationNotices•Today: normal lab hours (4-5:30pm)•Thursday’s lab hours will be 5-7pm (instead of normally scheduled times)•Spring Break – there will not be normally scheduled lab hours or office hours between March 3 and March 10. Normal lab hours resume Sunday, March 11. •Exam 1 will be returned at end of today’s class•Schedule for rest of semester is updated on the course web (www.cs.virginia.edu/schedule/)3Lecture 19: MutationEvaluation Rule 2: NamesIf the expression is a name, it evaluates to the value associated with that name.> (define two 2)> two2From Lecture 3:4Lecture 19: MutationNames and Places•A name is not just a value, it is a place for storing a value.•define creates a new place, associates a name with that place, and stores a value in that placex: 3(define x 3)5Lecture 19: MutationBang!set! (“set bang”) changes the value associated with a place> (define x 3)> x3> (set! x 7)> x7x: 376Lecture 19: Mutationset! should make you nervous> (define x 2)> (nextx)3> (nextx)4> x4Before set! all procedures were functions (except for some with side-effects). The value of (f) was the same every time you evaluate it. Now it might be different!7Lecture 19: MutationDefining nextx(define (nextx) (set! x (+ x 1)) x)(define nextx (lambda () (begin (set! x (+ x 1)) x))))syntactic sugar for8Lecture 19: MutationEvaluation Rules> (define x 3)> (+ (nextx) x)7or 8> (+ x (nextx))9or 10DrScheme evaluates application subexpressions left to right, but Scheme evaluation rules allow any order.9Lecture 19: Mutationset-car! and set-cdr!(set-car! p v)Replaces the car of the cons p with v.(set-cdr! p v)Replaces the cdr of the cons p with v.These should scare you even more then set!!10Lecture 19: Mutation> (define pair (cons 1 2))> pair(1 . 2)pair: 1211Lecture 19: Mutation> (define pair (cons 1 2))> pair(1 . 2)> (set-car! pair 0)> (car pair)0> (cdr pair)2> (set-cdr! pair 1)> pair(0 . 1)pair: 120112Lecture 19: MutationmapFunctional Solution: A procedure that takes a procedure of one argument and a list, and returns a list of the results produced by applying the procedure to each element in the list.(defineD(mapDprocDlst)DD(ifD(null?Dlst) nullDDDDDD(consD(procD(carDlst))DDDDDDDDDDDD(mapDprocD(cdrDlst)))))13Lecture 19: MutationImperative SolutionA procedure that takes a procedure and list as arguments, and replaces each element in the list with the value of the procedure applied to that element.(define (map! f lst) (if (null? lst) (void) (begin (set-car! lst (f (car lst))) (map! f (cdr lst)))))(defineD(mapDprocDlst)DD(ifD(null?Dlst) nullDDDDDD(consD(procD(carDlst))DDDDDDDDDDDD(mapDprocD(cdrDlst)))))14Lecture 19: MutationProgramming with Mutation> (map! square (intsto 4))> (define i4 (intsto 4))> (map! square i4)> i4(1 4 9 16)> (define i4 (intsto 4))> (map square i4)(1 4 9 16)> i4(1 2 3 4)FunctionalImperative15Lecture 19: MutationMutation Changes Everything!•We can no longer talk about the “value of an expression”–The value of a give expression can change!–We need to talk about “the value of an expression in an execution environment ”•The order in which expressions are evaluated now matters16Lecture 19: MutationWhy Substitution Fails?> (define (nextx) (set! x (+ x 1)) x)> (define x 0)> ((lambda (x) (+ x x)) (nextx))2Substitution model:(+ (nextx) (nextx))(+ (begin (set! x (+ x 1)) x) (begin (set! x (+ x 1)) x))(+ (begin (set! 0 (+ 0 1)) 0) (begin (set! 0 (+ 0 1)) 0))(+ 0 0)017Lecture 19: MutationNames and Places•A name is a place for storing a value.•define creates a new place•cons creates two new places, the car and the cdr•(set! name expr) changes the value in the place name to the value of expr•(set-car! pair expr) changes the value in the car place of pair to the value of expr18Lecture 19: MutationLambda and Places•(lambda (x) …) also creates a new place named x•The passed argument is put in that place> (define x 3)> ((lambda (x) x) 4)4> x3How are theseplaces different?x : 3x : 419Lecture 19: MutationLocation, Location, Location•Places live in frames•An environment is a frame and a pointer to a parent environment•All environments except the global environment have exactly one parent environment, global environment has no parent•Application creates a new environment20Lecture 19: MutationEnvironmentsglobalenvironment> (define x 3)+ : #<primitive:+>null? : #<primitive:null?>The global environment points to the outermost frame. It starts with all Scheme primitives.x : 321Lecture 19: MutationEvaluation Rule 2: NamesA name expression evaluates to the value associated with that name.To find the value associated with a name, look for the name in the frame associated with the evaluation environment. If it contains a place with that name, the value of the name expression is the value in that place. If it doesn’t, the value of the name expression is the value of the name expression evaluated in the parent environment if the current environment has a parent. Otherwise, the name expression evaluates to an error (the name is not defined).22Lecture 19: MutationProceduresglobalenvironment> (define double (lambda (x) (+ x x)))+ : #<primitive:+>null? : #<primitive:null?>double: ??x : 323Lecture 19: MutationHow to Draw a Procedure•A procedure needs both code and an environment–We’ll see why soon•We draw procedures like this:Environmentpointerenvironment: parameters: xbody: (+ x x)24Lecture 19: MutationHow to Draw a Procedure (for artists only)Environmentpointerx(+ x x)Input parameters(in mouth)Procedure Body25Lecture 19: MutationProceduresglobalenvironment> (define double (lambda (x) (+ x x)))+ : #<primitive:+>null? : #<primitive:null?>double: x : 3environment:parameters: xbody: (+ x x)26Lecture 19: MutationApplication•Old rule: (Substitution model)Apply Rule 2: Constructed Procedures. To apply a constructed