CS61A Summer 2003 Midterm 2 Review 1. ACCUMULATE/REDUCE Use ACCUMULATE or REDUCE to define REMOVE-DUPLS, which takes a list and returns the same list with each list element appearing exactly once. It should work like this: STk> (remove-dupls '(a b a b c b a f)) (c b a f) STk> (remove-dupls '(1 2 3 3)) (1 2 3) STk> (remove-dupls '()) () Fill in *exactly one* of the following: (define (remove-dupls lst) (accumulate __________________________________________ __________________________________________ lst)) (define (remove-dupls lst) (reduce __________________________________________ __________________________________________)) 2. LIKE SUBSETS Given N dice, each with a (possibly) different number of sides, we would like to determine all possible outcomes of tossing them. We will represent N dice as a list of N numbers, each of which is the number of sides. For example, the list (2 5 3) consists of three die. The first one has two sides; the second has five, and the third has three. When you take these dice and drop them on the floor, many different outcomes are possible: ((2 5 3) (2 5 2) (2 5 1) (2 4 3) (2 4 2) (2 4 1) (2 3 3) (2 3 2) (2 3 1) (2 2 3) (2 2 2) (2 2 1) (2 1 3) (2 1 2) (2 1 1) (1 5 3) (1 5 2) (1 5 1) (1 4 3) (1 4 2) (1 4 1) (1 3 3) (1 3 2) (1 3 1) (1 2 3) (1 2 2) (1 2 1) (1 1 3) (1 1 2) (1 1 1)) Outcomes that are not possible include: o (3 3 3) -- The first die only has two sides. o (2 0 1) -- The sides are numbered from one, not zero. o (1 5) -- You can't "lose" a die in the proccess. We'd like to write a function TOSS that takes a non-empty list of dice and returns a list of all the possible outcomes that may be obtained by throwing them. Here is the desired behavior: STk> (toss '(2 1 3)) ((2 1 1) (2 1 2) (2 1 3) (1 1 1) (1 1 2) (1 1 3)) STk> (toss '(5 3)) ((5 1) (5 2) (5 3) (4 1) (4 2) (4 3) (3 1) (3 2) (3 3) (2 1) (2 2) (2 3) (1 1) (1 2) (1 3)) STk> (toss '(3)) ((1) (2) (3)) As you can imagine, increasing the number of die in the list, or the number of sides of any die, exponentially increases the number of outcomes: STk> (toss '(2 2 2 2 2)) ((2 2 2 2 2) (2 2 2 2 1) (2 2 2 1 2) (2 2 2 1 1) (2 2 1 2 2) (2 2 1 2 1) (2 2 1 1 2) (2 2 1 1 1) (2 1 2 2 2) (2 1 2 2 1) (2 1 2 1 2) (2 1 2 1 1) (2 1 1 2 2) (2 1 1 2 1) (2 1 1 1 2) (2 1 1 1 1) (1 2 2 2 2) (1 2 2 2 1) (1 2 2 1 2) (1 2 2 1 1) (1 2 1 2 2) (1 2 1 2 1) (1 2 1 1 2) (1 2 1 1 1) (1 1 2 2 2) (1 1 2 2 1) (1 1 2 1 2) (1 1 2 1 1) (1 1 1 2 2) (1 1 1 2 1) (1 1 1 1 2) (1 1 1 1 1)) Below is a version of the TOSS function. There is one bug in it and/or its helpers. (define (toss die-list) (if (null? die-list) '() (little-help (car die-list) (toss (cdr die-list))))) (define (little-help n outcomes) (if (= n 0) '() (append (prepend-every n outcomes) (little-help (- n 1) outcomes)))) (define (prepend-every elt lst) (map (lambda (l) (cons elt l)) lst)) Figure out what the following returns: (toss '(1 2)) ____________________________________________________________ Fix the bug in the fewest number of changes. Change line ______ to ________________________________________ Change line ______ to ________________________________________ Change line ______ to ________________________________________ 3. LOCAL STATE When STk starts up, a file called "berkeley.scm" is automatically loaded. This file defines many of the procedures we treat as Scheme primitives in CS61A and CS3, such as FIRST, BF, LAST, BL, etc. One such procedure is the predicate function SENTENCE?, which tests if its argument is a sentence: STk> (sentence? 4) #f STk> (sentence? '(the problem is choice)) #t STk> (sentence? '(a (nested) (list))) #f Here is the code, verbatim: (define sentence? (let ((null? null?) (pair? pair?) (word? word?) (car car) (cdr cdr)) (define (list-of-words? l) (cond ((null? l) #t) ((pair? l) (and (word? (car l)) (list-of-words? (cdr l)))) (else #f))) list-of-words?)) As you can see, the LIST-OF-WORDS? helper does the actual checking of the argument. But that LET sure looks funny! Clearly describe the purpose of the LET. 4. OOP We want to create a class to represent a computer. We should be able to "install" programs on it, also represented by a general Program class. Thus, the Computer class should have a method INSTALL that takes a program object and a name for it. It should also have a RUN method that takes a name and a *list* of arguments, and runs that program with the given arguments, returning the result. Assumedly, the programs will be functional, to simplify things. Also, conveniently, the programs will be written in scheme. The Program class should take a procedure as an instantiation variable, and the rest is up to you. Examples (with return values omitted): STk> (define apple-ii (instantiate computer)) STk> (define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1))))) STk> (define fact-program (instantiate program factorial)) STk> (define multiply-program (instantiate program *)) STk> (ask apple-ii 'install fact-program 'factorial) ok STk> (ask apple-ii 'install multiply-program 'multiply) ok STk> (ask apple-ii 'run 'multiply (list 3 4 5)) 60 STk> (ask apple-ii 'run 'square (list 4)) *** Error: no such program: square Now we want to make this computer a little more self-managing. We want to set it up to remove programs that are not frequently used. Keep track of which programs have been run recently. If a particular program has not been run in the last 10 program runs, it should be removed in such a way that actually saves storage data, and so it is impossible to access again without being re-installed. For example, if we have the same setup as above: STk> (map (lambda (n) (ask apple-ii 'run 'factorial (list n))) (enumerate-interval 1 10)) (1 2 6 24 120 ... ) STk> (ask apple-ii 'run 'multiply (list 3 10)) *** Error: no such program: multiply 5. APPLY/FRIENDS Given, (define (mystery x . args) (if (list? x) args (apply mystery (map list args)))) What does (mystery 'a 'b 'c 'd) return? 6. ENVIRONMENT DIAGRAM Draw this baby, but stop drawing when you have a feel for how things will work out in the end. (define x 4) (define (define-x x) (define x x) x) (define (confusing x y) (let ((z (x y))) (set! confusing z)) (set! x 10) (confusing)) (confusing define-x (let ((total 0)) (lambda () (set! total (+ total x)) (confusing))))