How to Start and SubmitData Directed ProgrammingMessage PassingSICP ExercisesFeedbackCS61A: Structure and Interpretation of Computer Programs Homework 3CS61A Summer 2010George Wang, Jonathan Kotker, Seshadri Mahalingam, Steven Tang, Eric TzengHomework 3Due: Monday, July 11 2010, at 7AMNote: The number of stars (F) besides a question represents the estimated relative difficulty of the problem:the more the number of stars, the harder the question.1 How to Start and SubmitFirst, download http://inst.eecs.berkeley.edu/~cs61a/su10/hw/hw3.scm and use it as a templatewhile filling out your procedures. See http://www-inst.eecs.berkeley.edu/~cs61a/su10/hw-faq.pdffor submission instructions.2 Data Directed Programming1. The University of California, Berkeley Library is made up of a group of smaller libraries, each ofwhich uses Scheme data structures to represent its collection. Unfortunately, each library has its ownmethod of cataloguing books (using pairs, lists, nested association lists, etc.). Each library is requiredto store a book’s title, author, and ISBN1. As the new head of IT for the centralized library system,you need to provide the librarians with a common method of accessing this data, and you decide touse Data-Directed Programming to accomplish this.You will be writing generic operators so that your program can work with any type of information. Ageneric operator is a procedure that can take in data of different types and perform its operation onany of these.For example, Moffitt Library implements its books as a list, like so:((anna karenina) (leo tolstoy) 0143035002)On the other hand, the Doe Library implements them as an association list. This means that they dothem like this:((title . 1984) (author . Orwell) (isbn . 0151010269))We call each of these a book record. Note that we need different accessors to get to each element. Forexample, for Moffitt, they would make the following call:(define (author book)(cadr book))Doe, on the other hand, would make this call:(define (author book)(cdr (assoc author book)))(a) FF Implement a get-book-record procedure that, given a library’s data file and book title,retrieves the corresponding book record. This procedure must work for any library’s data files.Each data file is a list of book records.1http://en.wikipedia.org/wiki/International_Standard_Book_NumberPage 1CS61A: Structure and Interpretation of Computer Programs Homework 3Assume that each library has called attach-tag for each piece of data belonging to it. For ex-ample, Moffitt has called (attach-tag ’Moffitt book-record). Furthermore, all the librarieshave added all the information to a table. For example, Moffitt has called (put ’Moffitt ’titlecaar).(b) F Implement a get-isbn-number procedure that returns the ISBN from a given book recordfrom any library’s data file. How should the book record be set up for your procedure to work?(c) FF Write a find-book procedure that, given a book title and a list of the book records of all ofthe libraries, retrieves the corresponding book record.(d) F The Berkeley Public Library (on Shattuck Ave.) decides to join the UC Berkeley Librarysystem. What do they need to do to put their database on the central system?3 Message Passing1. The procedures below implement a dispatch on type system for calculating the area and perimeterof shapes. This is also called Conventional Style. This is a reasonable solution for a system that islikely to encounter the addition of more methods/operators (eg. a number-of-sides procedure) thantypes (eg. triangles, rectangles).(define pi 3.141592654)(define (make-square side)(attach-tag ’square side))(define (make-circle radius)(attach-tag ’circle radius))(define (area shape)(cond ((equal? (type-tag shape) ’square)(* (contents shape) (contents shape)))((equal? (type-tag shape) ’circle)(* pi (contents shape) (contents shape)))(else (error "Unknown shape -- AREA"))))(define (perimeter shape)(cond ((equal? (type-tag shape) ’square)(* 4 (contents shape)))((equal? (type-tag shape) ’circle)(* 2 pi (contents shape)))(else (error "Unknown shape -- PERIMETER"))))But let’s say that I want to add another type of shape, triangle. In order to implement this newshape, I would need to create a new constructor, make-triangle, and modify both the area andperimeter procedures. If we were to add more operations, this would quickly become a lot of work!To solve this problem, let’s try a different way of representing our data. Specifically, I want to definethe area and perimeter procedures as follows:(define (area shape)(shape ’area))(define (perimeter shape)(shape ’perimeter))Page 2CS61A: Structure and Interpretation of Computer Programs Homework 3Under the old Conventional Style, our shapes were represented as tagged data, and the tag told thearea and perimeter procedures which formulas to use. However, under our new Message Passingstyle, our shapes now act as procedures that take a message (a word that is either area or perimeter)and return the appropriate value.(a) F Re-implement make-circle and make-square in message passing style to work with the newarea and perimeter procedures.(b) F We want to make a new type, e-triangle, that represents an equilateral triangle. Add thisnew type to your message passing system. Your e-triangle should work with the given areaand perimeter procedures, and you should NOT need to modify any of the code you’ve writtenfor part 1a! Note: The area of an equilateral triangle is given bys2√34.2. In a two-dimensional rectangular Cartesian coordinate system, we can represent a point as a pair of xand y values.(a) F Write a make-rectangular-point procedure that creates a rectangular-point in messagepassing style. A rectangular-point should accept the messages ’x and ’y, and return an errorfor any other message.(b) F Create a new message, distance, that your rectangular-points will understand. (my-point’distance) should return a procedure that takes another point as an argument and returns thedistance between the two points.(c) Points in a plane may also be represented in polar form, using a magnitude (r) and an angle (θ).Conversions from polar to rectangular coordinates use the equations:x = r · cos(θ)y = r · sin(θ)FF Write an analogous make-polar-point procedure that takes as input a magnitude andan angle. A polar-point should accept the ’x and ’y messages and return its correspondingrectangular coordinates. Any other messages should return an error.(d) F
View Full Document
Unlocking...