1. What Will Scheme Print? > (filter (not number?) '(3 hello (3 . 2) #t)) Error (not number?) will return #f, which is not a procedure that FILTER can use. > (apply-1 word '(a b c d)) abcd apply-1 will use STk's apply to call word with the arguments A, B, C, and D. Scoring: 1 pt each, all or nothing 2. Fill-in-the-Blanks / Box-and-Pointer Diagrams > (map list '(1 (2) 3)) ((1) ((2)) (3)) +---+---+ +---+---+ +---+---+ -->| o | o----->| o | o---->| o | / | +-|-+---+ +-|-+---+ +-|-+---+ | | | v v v +---+---+ +---+---+ +---+---+ | o | / | | o | / | | o | / | +-|-+---+ +-|-+---+ +-|-+---+ | | | v v v 1 +---+---+ 3 | o | / | +-|-+---+ v 2 Mapping list across a list will just place an extra set of parentheses around each element of the original list. > (map (lambda (x) (if (list? x) (car x) (* x x))) '(1 (3 4) 5 ((6 7) 8)) ) (1 3 25 (6 7)) +---+---+ +---+---+ +---+---+ +---+---+ -->| o | o----->| o | o---->| o | o------>| o | / | +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ | | | | v v v v 1 3 25 +---+---+ +---+---+ | o | o----->| o | / | +-|-+---+ +-|-+---+ | | v v 6 7 For each element in the list, we square it if it's not a list, and we take the first element if it is a list. Scoring: 1pt for each "what will Scheme print", 1pt for each box-and-pointer diagram. If you got the "WWSP" wrong, but your diagram matched what you put, you got 1pt. 3. ADTs: Domain and Range One point was assigned to each function. If you missed part of a question, then the entire point was deducted. deep-map Domain: (1) "procedure" or "function", and (2) "list", "deep list", or lower-case "tree" Range: "list", "deep list", or lower-case "tree" We accepted either "procedure" or "function" as one of the correct answers. Note that the answer "list of lists" was not accepted because a deep list *may*, but does not *necessarily*, have lists as elements. forest-map Domain: (1) "forest" or "list" (of Trees), and (2) "function" or "procedure" Range: "forest" or "list" (of Trees) children Domain: "Tree" Range: "forest" or "list" (of Trees) It was important to distinguish between trees and Trees – the capital-T Tree is an ADT and the lower-case tree is what the authors of SICP call a "deep list". Only the capital-T Tree responds correctly to the DATUM and CHILDREN selectors. left-branch Domain: "binary tree", "binary search tree", or "mobile" Range: "binary tree", "binary search tree", or "branch" "Binary tree" and "binary search tree" were both valid answers to this problem. We also accepted "mobile" for the domain, and "branch" for the range, in case you thought we were referring to the mobile ADT from SICP. segments->painter Domain: "list" (of segments) Range: "function" or "procedure" or "painter" Recall from project 2 that a painter is represented as a procedure that takes a frame as an argument. 4. Calculator and DDP In question 4, we want to be able to make use of any operations put into the table under CALC. Thus, for any operation that is inserted into the put/get table, we want calc-apply to be able to find and use this operation. The sole purpose of calc-eval is to check if the input expression is a number or a function call. calc-apply handles function calls, and determining the right course of action based on the input function. Since we are modifying how functions are recognized, the changes required for this problem lie in calc-apply. Before we make any changes, calc-apply explicitly checks for the name of the input fn and does an appropriate action to the input argument list. To make use of the put/get table, notice that we don't need to check explicitly for the name of the function, but merely need to get the corresponding function and call it with ARGS. Thus, the solution is to modify calc-apply to look as follows: (define (calc-apply fn args) ((get 'calc fn) args)) Thus, we should replace lines 7 through 17 with ((get 'calc fn) args)) An alternate solution was to make calc-apply more like apply-1, where the FN argument is already the right function. Here we need to modify calc-eval to do the lookup (lines 3 through 3): ((list? exp) (calc-apply (get 'calc (car exp)) (map calc-eval (cdr exp)))) Then fix calc-apply to match (lines 7 through 17): (fn args)) Scoring: 5: perfect 4: trivial mistakes - Missing a quote in get call (e.g. (get calc fn) instead of (get 'calc fn)) - Extra quote in get call (e.g. (get 'calc 'fn) instead of (get 'calc fn)) - Swaps 'calc and fn (e.g. (get fn 'calc) instead of (get 'calc fn)) - Uses an IF to check whether fn is a member of '(+ - * / magic). (This is not what we set out to do, though!) - Off-by-one in line numbers 3: the idea - Uses APPLY like (apply (get 'calc fn) args). Each function took a single /list/ of arguments, rather than being variadic (taking any number of arguments). 2: messing up the idea - Keeps explicit cond clauses for + - * /, but then has a catch-all at the end 1: an idea - Eliminates the COND in calc-apply, but doesn't use GET - hard-coding (cond contains 4 calls to GET) if the GET is correct. no points off for: - Incorrect error-handling (like assuming that GET will return a null list if the value is not in the table). 5. Trees and ADTs This was by far the problem that caused the most trouble. Here are the instructions again: A *trie* is a special Tree used to store sets of words, like a dictionary. Each datum in the Tree is a "trie entry" defined by the following ADT: (define (make-trie-entry letter is-end-of-word) (cons letter is-end-of-word) ) (define (letter trie-entry) (car trie-entry) ) (define (end-of-word? trie-entry) (cdr trie-entry) ) Words in the trie are made up of the letters that stretch from the root to an "end-of-word" node. Note that end-of-word nodes are not necessarily leaves. Write a procedure ALL-WORDS that takes a trie and returns a list of all words in that trie (in any order). (For reference, the word "trie" comes from "retrieval", but to avoid confusion with "tree" it's usually pronounced "try".) We deliberately never said outright that you should use DATUM and CHILDREN on tries, but we did say "a trie is a (special) Tree", and referred to "each datum in the Tree". That should have been enough information to let you decide that DATUM and CHILDREN were appropriate here. For this problem, the domains and ranges look like this: DATUM Domain: trie Range: trie entry CHILDREN Domain: trie Range: forest (specifically, a list of tries) LETTER Domain: trie entry Range: word (specifically, a single letter) END-OF-WORD? Domain: trie entry Range: boolean (#t or #f) ALL-WORDS Domain: trie Range: list of words (You didn't actually have to use MAKE-TREE or MAKE-TRIE-ENTRY, since we gave you an already-built trie.) As with any ADT we introduce, the purpose of the selectors is /not/ to replace CAR and CDR, but to describe what we're doing in terms of the problem, rather than in terms of what the computer's doing. Does it make sense to ask (end-of-word? tree)? No! The question mark should make it clear that this is supposed to return #t or #f, not a list of children. Similarly, it says very clearly in the problem that the data are /not/ words, but "trie entries". The constructor and selectors implement the trie entry ADT using pairs. We didn't write pairs (either as (t . #f) or a box-and-pointer diagram) on the exam because we didn't want people to use CAR and CDR, but it seems that it still tripped people up. Okay, that gives us the pieces: a pretty ordinary tree traversal (like FLATTEN), but where we only include the data from certain nodes. Let's start with FLATTEN and go from there: ; This is basically from SICP. (define (flatten tree) (cons (datum tree) (forest-flatten (children tree))) ) (define (forest-flatten forest) (if (null? forest) '() (append (flatten (car forest)) (forest-flatten (cdr forest)) ))) That's a good start, but we don't want an entire datum, just its letter: ; Modified for our trie entry data... (define (flatten tree) (cons (letter (datum tree)) (forest-flatten (children tree))) ) And we don't want every letter, just the ones that end words: ; Filtering for ends of words... (define (flatten tree) (let ((child-letters (forest-flatten (children tree)))) (if (end-of-word? (datum tree)) (cons (letter (datum tree)) child-letters) child-letters))) That's pretty good; we now have a list of all the letters that end words. What's left is the part that's hardest to get right in terms of tricky coding. There were two ways to go about this. One was to take the hint and keep track of where we are in the trie: ; This is a working solution! (define (all-words trie) (tree-words tree "") ) (define (tree-words tree so-far) (let ((new-so-far (word so-far (letter (datum tree))))) (let ((child-words (forest-words (children tree) new-so-far))) (if (end-of-word? (datum tree)) (cons new-so-far child-words) child-words)))) (define (forest-words forest so-far) (if (null? forest) '() (append (tree-words (car forest) so-far) (forest-words (cdr forest) so-far) ))) The other possibility was to get all of the child words first, then stick the current node's letter on the front. ; This is also a working solution! (define (all-words trie) (let ((child-words (forest-words (children tree))) (this-letter (letter (datum tree))) ) (let ((fixed-words (map (lambda (wd) (word this-letter wd)) child-words))) (if (end-of-word? (datum tree)) (cons this-letter fixed-words) fixed-words)))) (define (forest-words forest) (if (null? forest) '() (append (all-words (car forest)) (forest-words (cdr forest)) ))) All working solutions followed one of these two basic strategies; solutions that didn't do either usually ended up returning lists of letters instead of full words. Many people replaced FOREST-WORDS with a MAP and FLATTEN, or MAP and ACCUMULATE using APPEND. This works fine. Scoring: 8 perfect working solution - ...even if you assume all leaves are ends of words (which we told you not to do, and just complicated your code) 7 trivial mistakes (any of the following) - Using CAR/CDR instead of DATUM/CHILDREN - Using CAR/CDR instead of LETTER/END-OF-WORD? - Using CONS instead of APPEND, or vice versa, in building the result list, as long as you only do it once! - Using sentences instead of lists for the result. - Using '() instead of "" for the empty word. (It was on MT1 as well!) - Returning a word in the base case (instead of a list). - Not allowing the root to end a word. This may not be true for T, but it certainly is for A! - If you had a "so-far" solution, forgetting to update SO-FAR in one case, if you got it right somewhere else. 5 "the idea" (any of the following) - Traverses and filters correctly, but returns a deep list of some kind. Usually this gets traced to a combiner problem (CONS vs. APPEND). - Returns a list of word-ending letters instead of the words themselves. - Uses (letter trie), (end-of-word? trie), and (children trie). This isn't the data structure we described, but it would have been a valid way to set up the problem. (Should be otherwise correct.) - Forgets a combiner completely. For example, handling the CAR and CDR of a forest, but not putting them together. We chalked this up to exam stress. 2 "an idea" (any of the following) - Using DATUM/CHILDREN instead of LETTER/END-OF-WORD?, but otherwise working. - Using LETTER/END-OF-WORD? instead of DATUM/CHILDREN (unless it's the case described above), but otherwise working. - Ignoring a node's children if it ends a word. This would include TO but not TOM, for example. - Returning a list of trie entries instead of a list of words. - Failing to traverse the tree correctly (but the right idea). 0 (including the following) - Mixing up Trees and forests. - Answering the question for deep lists (which doesn't really make sense here). - Using SET!, unless the answer is very close to working. - Mixing up tries and trie entries, unless the answer is very good. - Not filtering for entries that end words. - Using MAKE-TREE or MAKE-TRIE-ENTRY. 6. Object-Oriented Programming Part A The first part of this question was a relatively straightforward class definition. We were primarily interested in whether or not you could define classes, give them variables, and define methods. Some people tried to make NAME an instance variable rather than an instantiation variable. However, the example, which mentioned two chat-bots with different names, was intended to show that not all chat-bots have the same name, which is a job for an instantiation variable. (We're not planning to change the name, either.) (define-class (chat-bot name) (method (greet) (se '(hi my name is) name)) (method (respond msg) '())) This part was worth 3 points, awarded as follows: 1 point for each of the following: - A correct define-class statement, with NAME as an instantiation variable - A working greet method - A working respond method There were also a number of ways to lose points. We specifically asked for answers that were as short as possible, so redundant code was penalized: -1 point for each of the following: - Explicitly defining an accessor method for NAME. Remember that our OOP code already provides a method to access variables without explicitly defining one. - Explicitly defining an instance variable for NAME, e.g. (instance-var (myname name)). This was redundant, since NAME is already an instantiation variable. We did not take this point off of solutions that already missed the point for making NAME an instantiation variable. - Extra quotes added to keywords or variable names, e.g. (define-class (chat-bot 'name)). Part B The main idea we were testing with this part of the question was inheritance. Because a grumpy-bot is a more specific type of chat-bot, the grumpy-bot class needed to inherit from the chat-bot class. Also, we wanted as little repetition of code as possible, so we were expecting the use of USUAL in the GREET method. (define-class (grumpy-bot name tolerance) (parent (chat-bot name)) (method (greet) (if (> tolerance 0) (usual 'greet) '())) (method (respond msg) (set! tolerance (- tolerance 1)) (if (>= tolerance 0) '(dont talk to me) '()))) 1 point was awarded for each of the following: - Proper define-class statement, with NAME and TOLERANCE as instantiation variables. - Properly inherits from the chat-bot class. - Overrides the GREET method. - Uses USUAL correctly in the GREET method. - Correctly checks the value of TOLERANCE within methods. We were especially concerned with off-by-one errors, which were easy to make. - Overrides the RESPOND method with the correct argument. - Uses set! in respond. Note that solutions that did not use set! at all also lost the point for correctly checking the value of tolerance. - The respond method returns the correct value. Common errors here were returning a list instead of a sentence, or leaving a set! as the last expression in the method. -1 point for each of the following: - Missing a BEGIN inside of an IF expression. - Using AND in place of BEGIN. Although this happens to work in STk, it's very much like a data abstraction violation, since in Scheme the return value of set! is undefined and should never be AND-ed. We didn't take off points twice for mistakes made in both part A and part B. 7. Deep lists (1 point each) (deep-squares '()) solution: WORKS (deep-squares '(1 (2 3) 4)) solution: WORKS (deep-squares '(1 (2 3) ((4)) 5)) solution: BROKEN Which line contains the bug? solution: 4 Here's the original code: 1. (define (deep-squares lol) 2. (cond ((null? lol) '()) 3. ((list? (car lol)) 4. (cons (map square (car lol)) 5. (deep-squares (cdr lol)) )) 6. (else (cons (square (car lol)) 7. (deep-squares (cdr lol)) )))) There was some confusion this question that we didn't intend. Some people were confused about what the various "correct answers" should have been for each of the arguments provide. Here's the full result: (deep-squares '()) => () (deep-squares '(1 (2 3) 4)) => (1 (4 9) 16) (deep-squares '(1 (2 3) ((4)) 5)) => (1 (4 9) ((16)) 5) The big idea is that it was supposed to maintain the structure from the original list. The first example (that takes the null list) works because of the first base case in line 2. The second example '(1 (2 3) 4)) only has a depth of 2 at maximum, which our program can handle. The third example '(1 (2 3) ((4)) 5) has a depth greater than 2, which our program can't handle. Let's take an even simpler case to think about. For now we'll consider the case of (deep-squares '((3 5))), which works!! This initial argument will be true for the case on line 3, and will generate the next call of: (cons (map square (car '((3 5)))) (deep-squares (cdr '((3 5))))) ## Line A Now we'll start from the inside out and evaluate the car and cdr to get rid of them... (cons (map square '(3 5)) (deep-squares '())) ## Line B We know that deep-squares of a null list just returns the empty lies (b/c of line 2) so we'll focus on (map square '(3 5)). (map square '(3 5)) is perfectly sensible and generates something like: (list (square 3) (square 5)) ## Line C Which would produce (9 25). If we fill that into ## Line B we get: (cons '(9 25) '()) ## Line D which gives us ((9 25)) aka - the right answer. Instead if we had started with the argument of (deep-square '(((4 6)))) we would have executed the same thing but eventually tried to call MAP with a deep list. Below are the commands that are generated reproduced from above (##Lines A-C) except with the new argument value: (cons (map square (car '(((4 6))))) (deep-squares (cdr '(((4 6)))))) ## Line A' (cons (map square '((4 6)) (deep-squares '())) ## Line B' (list (square (4 6)) ) ## Line C' But we get an error on Line C' (notice the prime) B/c square is expecting a number and it isn't legit to say (* '(4 6) '(4 6)) So our function (based upon the call on line 4) can't handle lists that have a depth greater than 2. So the problem is on line 4, where we should have called deep-squares instead of squares so that we could handle additional levels of nesting.