CS61A Homework 11

Due by 11:59 PM on (that is, the end of) Saturday, 7/28

This homework must be submitted online. We do not require a paper copy. If you would like a reader to give you written feedback on your homework, submit a paper copy to the homework box.

To turn in the electronic copy, submit all of your answers in files named hw11.py and hw11.scm. Follow the instructions here to submit the electronic copy.

If you would like, you can use the template files hw11.py and hw11.scm. To copy these files to your lab account you can run the commands:

      cp ~cs61a/lib/hw/hw11/hw11.py .
      cp ~cs61a/lib/hw/hw11/hw11.scm .
      

to copy them into your current directory.

The Scheme template file, hw11.scm, contains procedure stubs and tests. Using STk, you can load and execute functions from this file with the commands (assuming you're in the same directory as hw11.scm):

      # stk
      STk> (load "hw11")
      okay
      STk> (check-all)   ; Runs a simple set of test cases.
      

In homeworks, we have three different categories of questions:

• Core Questions — Questions that we believe test a core concept of the course and should be your highest priority when attempting the homework.
• Reinforcement Questions — Questions that we believe have material that is either covered by other questions in this homework or in past homeworks, and can therefore be considered second priority after the core questions have been completed.
• Extra for Experts — As in earlier homeworks, these problems are completely optional. You are encouraged to try these questions once you have completed questions from the other two categories. However, these are questions that we consider either more difficult than what we would ask you on an exam or that focus on ideas we are not concerned with in this course, so please do not be discouraged if you do not solve them.

It is our hope that these categories will help guide you in deciding how to divide your time when working on the homeworks.

Core Questions

Q1. Using the OOP implementation shown in class, write the function make_change_class which defines and returns a class for representing amounts of money using nickels and dimes. The code for the OOP implementation shown in class can be found in oop.py.

      >>> Change = make_change_class()
      >>> erics_change = Change['new'](5, 6)
      >>> erics_change['get']('total')()
      31
      >>> erics_change['set']('nickels', 6)
      >>> erics_change['get']('total')()
      36
      >>> erics_change['set']('pennies', 7)
      >>> erics_change['get']('total')()
      37
      

Q2. Write the predicate ordered?, which takes a list of numbers and returns true if the numbers are in ascending order and false otherwise.

      STk> (ordered? '(1 2 3 4 5))
      #t
      STk> (ordered? '(1 5 2 4 3))
      #f
      

Q3. Write the function deep-map, which takes a function and a deep list (a list that might contain other lists) and returns a copy of the deep list with all items replaced with the result of applying fn onto each item. Make sure to perform this operation even for items in sublists.

      STk> (deep-map (lambda (x) (* x x)) '(1 2 (3 4 (5 6) 7 8) (9 10)))
      (1 4 (9 16 (25 36) 49 64) (81 100))
      STk> (deep-map (lambda (x) (word x 'y)) '(the (rain (in)) spain))
      (they (rainy (iny)) spainy)
      

Hint: You can use the predicate list? to check if something is a list.

      STk> (list? 2)
      #f
      STk> (list? '(1 2 3))
      #t
      

Reinforcement Questions

Q4. Rewrite the MissManners class from Homework 8 using the OOP implementation we saw in class. The code for the OOP implementation can be found in oop.py.

      >>> MissManners = make_miss_manners_class()
      >>> Change = make_change_class()
      >>> m = MissManners['new'](Change['new'](5, 1))
      >>> m['get']('ask')('total')
      'You must learn to say please.'
      >>> m['get']('ask')('please total')
      26
      

Q5. Write a procedure substitute that takes three arguments: a list, an old word, and a new word. It should return a copy of the list, but with every occurrence of the old word replaced by the new word, even in sublists. For example:

      STk> (substitute '((lead guitar) (bass guitar) (rhythm guitar) drums) 'guitar 'axe)
      ((lead axe) (bass axe) (rhythm axe) drums)
      

Q6. Using your solution to Q5, write substitute2 that takes a list, a list of old words, and a list of new words; the last two lists should be the same length. It should return a copy of the first argument, but with each word that occurs in the second argument replaced by the corresponding word of the third argument:

      STk> (substitute2 '((4 calling birds) (3 french hens) (2 turtle doves)) '(1 2 3 4) '(one two three four))
      ((four calling birds) (three french hens) (two turtle doves))
      

Extra for Experts

Q7. Add multiple inheritance to the object system that we implemented in class using dispatch dictionaries. You will need to make the following changes:

1. Allow a class to be created with an arbitrary number of base classes
2. Classes should respond to a message 'mro' that returns the method resolution order for the class
3. Looking up an attribute by name in a class (using the 'get' message) should follow the method resolution order

Choose a method resolution order from the three approaches that have been used in Python since its invention.