DOC PREVIEW
Berkeley COMPSCI 61A - Data Directed Programming

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:

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

Berkeley COMPSCI 61A - Data Directed Programming

Documents in this Course
Lecture 1

Lecture 1

68 pages

Midterm

Midterm

5 pages

Midterm

Midterm

6 pages

Lecture 35

Lecture 35

250 pages

Lecture 14

Lecture 14

125 pages

Lecture 2

Lecture 2

159 pages

Lecture 6

Lecture 6

113 pages

Lecture 3

Lecture 3

162 pages

Homework

Homework

25 pages

Lecture 13

Lecture 13

117 pages

Lecture 29

Lecture 29

104 pages

Lecture 11

Lecture 11

173 pages

Lecture 7

Lecture 7

104 pages

Midterm

Midterm

6 pages

Midterm

Midterm

6 pages

Lecture 8

Lecture 8

108 pages

Lab 4

Lab 4

4 pages

Lecture 7

Lecture 7

52 pages

Lecture 20

Lecture 20

129 pages

Lecture 15

Lecture 15

132 pages

Lecture 9

Lecture 9

95 pages

Lecture 30

Lecture 30

108 pages

Lecture 17

Lecture 17

106 pages

Load more
Download Data Directed Programming
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 Data Directed Programming 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 Data Directed Programming 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?