CS61A—Summer 2011—Eric, Phill, Hamilton, Stephanie, Kevin—Notes Courtesy of Justin Chen CS61A Notes – Disc 6: Scheme1, Data Directed Programming (solutions) You Are Scheme – and don’t let anyone tell you otherwise QUESTIONS 1. Try it yourself: trace each call to eval-1 and apply-1 for the expression (+ 3 (- 8 5)). eval-1 with exp = (+ 3 (- 8 5)) eval-1 with exp = +; returns #[closure ... 0] eval-1 with exp = 3; returns 3 eval-1 with exp = (- 8 5) eval-1 with exp = -; returns #[closure ... 1] eval-1 with exp = 8; returns 8 eval-1 with exp = 5; returns 5 apply-1 with proc = #[closure ... 1], args = (8 5); returns 3 eval-1 returns 3 apply-1 with proc = #[closure ... 0], args = (3 3); returns 6 eval-1 returns 6 2. How about for(+ 3 ((lambda (x) (- x 1)) 5))? eval-1 with exp = (+ 3 ((lambda (x) (- x 1)) 5)) eval-1 with exp = +; returns #[closure ... 0] eval-1 with exp = 3; returns 3 eval-1 with exp = ((lambda (x) (- x 1)) 5) eval-1 with exp = (lambda (x) (- x 1)); returns (lambda (x) (- x 1)) eval-1 with exp = 5; returns 5 apply-1 with proc = (lambda (x) (- x 1)), args = (5) eval-1 with exp = (- 5 1) eval-1 with exp = -; returns #[closure ... 1] eval-1 with exp = 5; returns 5 eval-1 with exp = 1; returns 1 apply-1 with proc = #[closure ... 1], args = (5 1); returns 4 eval-1 returns 4 apply-1 returns 4 eval-1 returns 4 apply-1 with proc = #[closure ... 0], args = (3 4); returns 7 eval-1 returns 7 3. If I type this into STk, I get an unbound variable error: (eval-1 'x) This surprises me a bit, since I expected eval-1 to return x, unquoted. Why did this happen? What should I have typed in instead? The quote in front of x protects x from STk, but not from Scheme1. Recall that eval-1 is just a procedure, and for STk to make that procedure call, it first evaluates all its arguments – including (quote x) – before passing the argument to eval-1. Then, when eval-1 sees the symbol x, it tries to call eval on it, throwing an unbound variable error. The problem, then, is that the expression „x is evaluated TWICE – once by the STk evaluator, and once by eval-1. Thus, to protect it twice, you need two quotes:CS61A—Summer 2011—Eric, Phill, Hamilton, Stephanie, Kevin—Notes Courtesy of Justin Chen (eval-1 „„x) Note that if you type just „x into Scheme1, it works: Scheme1: „x x Make sure you understand the difference, and why you don‟t need double-quote there (because STk is never told to evaluate „x, unlike the previous case). 4. Hacking Scheme1: For some reason, the following expression works: (‘(lambda(x) (* x x)) 3) Note the quote in front of the lambda expression. Well, it’s not supposed to! Why does it work? What fact about Scheme1 does this exploit? When eval-1 sees the procedure call and tries to evaluate the procedure, it sees that it is a quoted expression, and unquotes it. Then, the procedure is passed to apply-1, which sees that it is a lambda expression, and uses it as such. This exploits the fact that in Scheme1, a compound procedure is represented as a list that looks exactly like the lambda expression that created it. Thus, even though we never evaluated the lambda expression into a procedure value, Scheme1 is still fooled into thinking it‟s a valid procedure. QUESTION: The TAs have broken out in a cold war; apparently, at the last midterm-grading session, someone ate the last potsticker and refused to admit it. It is near the end of the semester, and Colleen really needs to enter the grades. Unfortunately, the TAs represent the grades of their students differently, and refuse to change their representation to someone else’s. Colleen is far too busy to work with five different sets of procedures and five sets of student data, so for educational purposes, you have been tasked to solve this problem for her. The TAs have agreed to type-tag each student record with their first name, conforming to the following standard: (define type-tag car) (define content cdr) It’s up to you to combine their representations into a single interface for Colleen to use. IN CLASS: Write a procedure, (make-tagged-record ta-name record), that takes in a TA’s student record, and type-tags it so it’s consistent with the type-tag and content accessor procedures defined above. (define make-tagged-record cons) Why not list?CS61A—Summer 2011—Eric, Phill, Hamilton, Stephanie, Kevin—Notes Courtesy of Justin Chen A student record consists of two things: a “name” item and a “grade” item. Each TA represents a student record differently. Hamilton uses a list, whose first element is a name item, and the second element the grade item. Eric uses a cons pair, whose car is the name item, and the cdr the grade item. Write get-name and get-grade procedures that take in a student record and return the name or grade items, respectively. We will do this in three different ways: a. Conventional-style type tagging (define (get-name tagged-record) (cond ((equal? (type-tag tagged-record) „Hamilton) (car (content tagged-record))) ((equal? (type-tag tagged-record) „Eric) (car (content tagged-record))))) (define (get-grade tagged-record) (cond ((equal? (type-tag tagged-record) „Hamilton) (cadr (content (tagged-record))) ((equal? (type-tag tagged-record) „Eric) (cdr (content tagged-record))))) b. Data-directed programming (put „Hamilton „get-name car) (put „Hamilton „get-grade cadr) (put „Eric „get-name car) (put „Eric „get-grade cdr) (define (get-name tagged-record) ((get (type-tag tagged-record) „get-name) (content tagged-record))) (define (get-grade tagged-record) ((get (type-tag tagged-record) „get-grade) (content tagged-record))) As you can see, the above two look very similar, so we can define a generic, “operate” procedure: (define (operate op tagged-record) ((get (type-tag tagged-record) op) (content tagged-record))) Then, we can just do: (define (get-name tagged-record) (operate „get-name tagged-record)) (define (get-grade tagged-record) (operate „get-grade tagged-record)) c. Message passing – this one's a little different. Instead of going off an existing TA's implementation, you now have the chance to create your own. Create an implementation
View Full Document