CS 61A Week 4 solutions LAB 1 ASSIGNMENT 2.62. Union-set in Theta(n) time. The key is to realize the differences between union-set and intersection-set. The null case for union-set will be different, because if one of the sets is empty, the result must be the other set. In the element comparisons, one element will always be added to the result set. So the expressions with the element will be the same as intersection-set, only with a cons added. Here's the solution: (define (union-set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) (else (let ((x1 (car set1)) (x2 (car set2))) (cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2)))) ((< x1 x2) (cons x1 (union-set (cdr set1) set2))) ((< x2 x1) (cons x2 (union-set set1 (cdr set2))))))))) Trees on page 156: (define tree1 (adjoin-set 1 (adjoin-set 5 (adjoin-set 11 (adjoin-set 3 (adjoin-set 9 (adjoin-set 7 '()))))))) (define tree2 (adjoin-set 11 (adjoin-set 5 (adjoin-set 9 (adjoin-set 1 (adjoin-set 7 (adjoin-set 3 '()))))))) (define tree3 (adjoin-set 1 (adjoin-set 7 (adjoin-set 11 (adjoin-set 3 (adjoin-set 9 (adjoin-set 5 '()))))))) Other orders are possible; the constraint is that each node must be added before any node below it. So in each case we first adjoin the root node, then adjoin the children of the root, etc. To make sure this is clear, here's an alternative way to create tree1: (define tree1 (adjoin-set 11 (adjoin-set 9 (adjoin-set 5 (adjoin-set 1 (adjoin-set 3 (adjoin-set 7 '()))))))) 2.74 (Insatiable Enterprises): (a) Each division will have a private get-record operation, so each division's package will look like this: (define (install-research-division) ... (define (get-record employee file) ...) ... (put 'get-record 'research get-record) ...) Then we can write a global get-record procedure like this: (define (get-record employee division-file) ((get 'get-record (type-tag division-file)) employee (contents division-file))) It'll be invoked, for example, like this: (get-record '(Alan Perlis) research-personnel-list) For this to work, each division's file must include a type tag specifying which division it is. If, for example, a particular division file is a sequence of records, one per employee, and if the employee name is the CAR of each record, then that division can use ASSOC as its get-record procedure, by saying (put 'get-record 'manufacturing assoc) in its package-installation procedure. (b) The salary field might be in a different place in each division's files, so we have to use the right selector based on the division tag. (define (get-salary record) (apply-generic 'salary record)) Each division's package must include a salary selector, comparable to the magnitude selectors in the complex number example. Why did I use GET directly in (a) but apply-generic in (b)? In the case of get-salary, the argument is a type-tagged datum. But in the case of get-record, there are two arguments, only one of which (the division file) has a type tag. The employee name, I'm assuming, is not tagged. (c) Find an employee in any division (define (find-employee-record employee divisions) (cond ((null? divisions) (error "No such employee")) ((get-record employee (car divisions))) (else (find-employee-record employee (cdr divisions))))) This uses the feature that a cond clause with only one expression returns the value of that expression if it's not false. (d) To add a new division, you must create a package for the division, make sure the division's personnel file is tagged with the division name, and add the division's file to the list of files used as argument to find-employee-record. LAB 2 Assignment: 1. Add REPEAT to person class. (define-class (person name) (INSTANCE-VARS (OLD-TEXT '())) (method (say stuff) (SET! OLD-TEXT STUFF) stuff) (method (ask stuff) (ask self 'say (se '(would you please) stuff))) (method (greet) (ask self 'say (se '(hello my name is) name))) (METHOD (REPEAT) OLD-TEXT)) Notice that the ASK and GREET methods don't have to set old-text, because they use the SAY method. 2. Which double-talkers work? (define-class (double-talker name) (parent (person name)) (method (say stuff) (se (usual 'say stuff) (ask self 'repeat))) ) There are two things wrong with this approach. One is that it assumes that the two arguments to SE are evaluated left-to-right, since the use of REPEAT assumes that we've just said the new stuff. That might work in some versions of Scheme but not in others. The second problem is that the value remembered in old-text will be a single copy of the argument, rather than two copies; therefore, if we ask this double-talker to repeat, it'll only say the thing once. (define-class (double-talker name) (parent (person name)) (method (say stuff) (se stuff stuff)) ) This would work except for the REPEAT feature. We can ask a double-talker to ASK or to GREET and it will correctly say the right thing twice. But if we ask this double-talker to REPEAT, it won't say anything at all, because it never remembered the stuff in old-text. (define-class (double-talker name) (parent (person name)) (method (say stuff) (usual 'say (se stuff stuff))) ) This one works as desired. HOMEWORK: 1. Exercises 2.75 Message-passing version of make-from-mag-ang : (define (make-from-mag-ang r a) (lambda (mesg) (cond ((eq? mesg 'real-part) (* r (cos a))) ((eq? mesg 'imag-part) (* r (sin a))) ((eq? mesg 'magnitude) r) ((eq? mesg 'angle) a) (else (error "Unknown op -- Polar form number" mesg)) )) ) Note that the formal parameter names X and Y that the book uses in make-from-real-imag (p. 186) are relatively sensible because they are indeed the x and y coordinates of a point in the plane. X and Y are confusing as names for polar coordinates! I used R and A, for Radius and Angle, but MAGNITUDE and ANGLE would be okay, too. I could have used an internal definition, as they do, instead of lambda; the two forms are equivalent. 2.76 Compare conventional, data-directed, and message-passing. To add a new operator: First we must write a low-level procedure for that operator for each type, like (magnitude-rectangular) and (magnitude-polar) if we're adding the operator magnitude. (If we're using a package system, we can add a local definition of MAGNITUDE to each package.) Then... For conventional style, we write a generic operator procedure (magnitude) that invokes the appropriate lower-level procedure depending on the type of its operand. For data-directed style, we use PUT to insert entries in the procedure matrix for each low-level procedure; there is no new high-level procedure required. For message-passing style, we modify each of the type dispatch procedures to accept a new message corresponding to the new operator, dispatching to the appropriate low-level procedure. To add a new type: First we must write a low-level procedure for that type for each operator, like (real-part-polar), (imag-part-polar), (magnitude-polar), and (angle-polar) if we're inventing the polar type. (If we're using a package system, we can create a new POLAR package with local definitions of REAL-PART, etc.) Then... For conventional style, we modify each of the generic operator procedures (real-part), (imaginary-part), etc. to know about the new type, dispatching to the appropriate lower-level procedures. For data-directed style, we use PUT to insert entries, as for a new operator. For message-passing style, we write a new type dispatch procedure that accepts messages 'real-part, 'imag-part, etc. and dispatches to the appropriate lower-level procedure. Which is most appropriate: Conventional style is certainly INappropriate when many new types will be invented, because lots of existing procedures need to be modified. Similarly, message-passing is INappropriate when many new operators will be invented and applied to existing types. Data-directed programming is a possible solution in either case, and is probably the best choice if both new types and new operators are likely. It's also a good choice if the number of types or operators is large in the first place, whether or not new ones will be invented, because it minimizes the total number of procedures needed (leaving out the generic dispatch procedures for each type or operator) and thereby reduces the chances for error. As you'll see in chapter 3, message-passing style takes on new importance when a data object needs to keep track of local state. But you'll see later in the chapter (mutable data) that there are other solutions to the local state problem, too. Message-passing is also sometimes sensible when there are lots of types, each of which has its own separate set of operators with unique names, so that a data-directed array would be mostly empty. 2.77 Starting with (magnitude '(complex rectangular 3 . 4)) we call MAGNITUDE giving (apply-generic 'magnitude '(complex rectangular 3 . 4)) The apply-generic function (see pg. 184) just uses GET to find the entry corresponding to 'magnitude and '(complex), and gets the same function MAGNITUDE that we invoked in the first place. This time, however, the argument to MAGNITUDE is (CONTENTS OBJ) so that the first type flag (COMPLEX) is removed. In other words, we end up calling (magnitude '(rectangular 3 . 4)) Calling the function MAGNITUDE again, this becomes : (apply-generic 'magnitude '(rectangular 3 . 4)) The apply-generic function now looks up the entry for 'magnitude and '(rectangular) and finds the MAGNITUDE function from the RECTANGULAR package; that function is called with '(3 . 4) as its argument, which yields the final answer... (sqrt (square 3) (square 4)) ==> 5 2.79 equ? (define (equ? a b) (apply-generic 'equ? a b)) In the scheme-number package: (put 'equ? '(scheme-number scheme-number) =) In the rational package: (define (equ-rat? x y) (and (= (numer x) (numer y)) (= (denom x) (denom y)))) ... (put 'equ? '(rational rational) equ-rat?) In the complex package: (define (equ-complex? x y) (and (= (real-part x) (real-part y)) (= (imag-part x) (imag-part y)))) ... (put 'equ? '(complex complex) equ-complex?) This technique has the advantage that you can compare for equality a complex number in rectangular form with a complex number in polar form, since the latter is implicitly converted to rectangular by equ-complex?. But it has the disadvantage that when comparing two complex numbers in polar form, it needlessly does the arithmetic to convert them both to rectangular coordinates. (On the other hand, if you want a polar-specific version of equ?, you have to remember that the angles can differ by a multiple of 2*pi and the numbers are still equal!) 2.81 Louis messes up again (a) This will result in an infinite loop. Suppose we have two complex numbers c1 and c2, and we try (exp c1 c2). Apply-generic will end up trying to compute (apply-generic 'exp (complex->complex c1) c2) but this is the same as (apply-generic 'exp c1 c2) which is what we started with. (b) Louis is wrong. If we have a complex exponentiation procedure and we PUT it into the table, then apply-generic won't try to convert the complex arguments. And if we don't have a complex exponentiation procedure, then apply-generic correctly gives an error message; there's nothing better it can do. (Once we invent the idea of raising, it would be possible to modify apply-generic so that if it can't find a function for the given type(s), it tries raising the operand(s) just in case the operation is implemented for a more general type. For instance, if we try to apply EXP to two rational numbers, apply-generic could raise them to real and then the version of EXP for the scheme-number type will work. But it's tricky to get this right, especially when there are two operands -- should we raise one of them, or both?) 2.83 Implementation of "raise" operators taking numbers to the next level "up" in the hierarchy -- i.e. the next more general type: integer -> rational -> real -> complex The package system as presented in the text has to be modified a little, because now instead of having a scheme-number type we want two separate types integer and real. So start by imagining we have two separate packages, one for integer and one for real. In each package we need an operation to raise that kind of number to the next type up: In the integer package: (define (integer->rational int) (make-rational int 1)) (put 'raise '(integer) integer->rational) In the rational package: (define (rational->real rat) (make-real (/ (numer rat) (denom rat)))) (put 'raise '(rational) rational->real) In the real package: (define (real->complex Real) (make-complex-from-real-imag real 0)) (put 'raise '(real) real->complex) And then we can make this global definition: (define (raise num) (apply-generic 'raise num)) 2. random number generator object (define-class (random-generator range) (instance-vars (count 0)) (method (number) (set! count (1+ count)) (random range) )) ; We don't need to say (method (count) ...) because we automatically get a ; method to examine each instance variable (and instantiate variable as well). 3. Coke machine. (define-class (coke-machine size price) (instance-vars (cokes 0) (money 0)) (method (deposit coin) (set! money (+ money coin)) ) (method (coke) (cond ((= cokes 0) (error "Machine empty")) ((< money price) (error "Not enough money")) (else (let ((change (- money price))) (set! money 0) (set! cokes (-1+ cokes)) change )) )) (method (fill number) (let ((new (+ cokes number))) (set! cokes (if (> new size) size new))))) 4. polite objects (define-class (miss-manners object) (method (please message arg) (ask object message arg))) ; Note that the original object is not a parent of the miss-manners ; object! That would defeat the whole purpose, because the new object ; would then respond to all the same messages as the old one. We want ; it to respond ONLY to the "please" message. ; We simplified the problem by restricting it to messages with exactly ; one argument, but of course we can generalize that with dot notation: (define-class (miss-manners object) (method (please message . args) (apply ask object messages args))) EXTRA PRACTACE 1. 2.80 =zero? (define (=zero? num) (apply-generic '=zero? num)) In the scheme-number package: (put '=zero? '(scheme-number) zero?) In the rational package: (put '=zero? '(rational) (lambda (n) (equ? n (make-rational 0 1)))) In the complex package: (put '=zero? '(complex) (lambda (n) (equ? n (make-complex-from-real-imag 0 0)))) Of course I could have used internal defines instead of lambda here. And of course once we invent raising it gets even easier; I can just say (define (=zero? num) (equ? num (make-scheme-number 0))) because then mixed-type equ? calls will be okay. 2. Deck of cards (define-class (deck) (instance-vars (the-deck (shuffle ordered-deck))) (method (deal) (if (null? the-deck) '() (let ((top-card (car the-deck))) (set! the-deck (cdr the-deck)) top-card))) (method (empty?) (null? the-deck)) ) ; I called the instance variable the-deck to avoid giving it the same name ; as the class itself. EXTRA FOR EXPERTS: 1. First of all, there's no reason this shouldn't work for anonymous procedures too... (define (inferred-types def) (cond ((eq? (car def) 'define) (inf-typ (cdadr def) (caddr def))) ((eq? (car def) 'lambda) (inf-typ (cadr def) (caddr def))) (else (error "not a definition")))) Then the key point is that this is a tree recursion. For an expression such as (append (a b) c '(b c)) we have to note that C is a list, but we also have to process the subexpression (a b) to discover that A is a procedure. All of the procedures in this program return an association list as their result. We start by creating a list of the form ((a ?) (b ?) (c ?) (d ?) (e ?) (f ?)) and then create modified versions as we learn more about the types. (define (inf-typ params body) (inf-typ-helper (map (lambda (name) (list name '?)) params) body)) (define (inf-typ-helper alist body) (cond ((not (pair? body)) alist) ((assoc (car body) alist) (inf-typ-seq (typ-subst (car body) 'procedure alist) (cdr body))) ((eq? (car body) 'map) (inf-map alist body 'list)) ((eq? (car body) 'every) (inf-map alist body 'sentence-or-word)) ((eq? (car body) 'member) (typ-subst (caddr body) 'list alist)) ((memq (car body) '(+ - max min)) (seq-subst (cdr body) 'number alist)) ((memq (car body) '(append car cdr)) (seq-subst (cdr body) 'list alist)) ((memq (car body) '(first butfirst bf sentence se member?)) (seq-subst (cdr body) 'sentence-or-word alist)) ((eq? (car body) 'quote) alist) ((eq? (car body) 'lambda) (inf-lambda alist body)) (else (inf-typ-seq alist (cdr body))))) (define (typ-subst name type alist) (cond ((null? alist) '()) ((eq? (caar alist) name) (cons (list name (if (or (eq? (cadar alist) '?) (eq? (cadar alist) type)) type 'x)) (cdr alist))) (else (cons (car alist) (typ-subst name type (cdr alist)))))) (define (inf-typ-seq alist seq) (if (null? seq) alist (inf-typ-seq (inf-typ-helper alist (car seq)) (cdr seq)))) (define (inf-map alist body type) (if (pair? (cadr body)) (inf-typ-helper (typ-subst (caddr body) type alist) (cadr body)) (typ-subst (cadr body) 'procedure (typ-subst (caddr body) type alist)))) (define (seq-subst seq type alist) (cond ((null? seq) alist) ((pair? (car seq)) (seq-subst (cdr seq) type (inf-typ-helper alist (car seq)))) (else (seq-subst (cdr seq) type (typ-subst (car seq) type alist))))) (define (inf-lambda alist exp) ((repeated cdr (length (cadr exp))) (inf-typ-helper (append (map (lambda (name) (list name '?)) (cadr exp)) alist) (caddr exp)))) Note -- the check for lambda in inf-typ-helper is meant to handle cases like the following: > (inferred-types '(lambda (a b) (map (lambda (a x) (append x a)) b))) ((a ?) (b list)) The (append x a) inside the inner lambda does NOT tell us anything about the parameter A of the outer lambda! 2. Probably the easiest example to understand is one in which BOTH parents inherit from the same grandparent, like this: +------------+ | GP | | | | methods: | | A, B, C | +------------+ / \ / \ / \ +------------+ +------------+ | Parent1 | | Parent2 | | | | | | methods: | | methods: | | B, C | | A, C | +------------+ +------------+ \ / \ / \ / +------------+ | Child | +------------+ The methods in the classes Parent1 and Parent2 override more generic methods in the grandparent GP. Suppose we ask an instance of the Child class to use method A. Which method should it use? Since the Parent1 class doesn't have its own method A, it inherits the GP method A, which is the most generic version. Method A in the Parent2 class is more specific, so probably a better choice for the Child class.