Due: 4pm on Monday, 4/30
Fill in the skeletons provided in ~cs61a/lib/hw/hw13.py and ~cs61a/lib/hw/hw13.scm with your answers.
Q1. Augment the Stream class with an __iter__ method that returns a generator over the elements of the stream, and a __getitem__ method that returns the kth item of a stream, for non-negative integer index k.
Q2. Define a function scale_stream that returns a stream over each element of an input stream, scaled by a constant k. [Very easy: take a look at what we've given you in the skeleton.]
Q3. A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, we can build a stream of such numbers. Let us call the required stream of numbers s and notice the following facts about it:
- s begins with 1.
- The elements of scale_stream(s, 2) are also elements of s.
- The same is true for scale_stream(s, 3) and scale-stream(s, 5).
- These are all of the elements of s.
Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions.
Fill in the definitions of merge and make_s:
def merge(s0, s1):
"""Return a stream over the elements of s0 and s1, removing repeats.
>>> ints = make_integer_stream(1)
>>> twos = scale_stream(ints, 2)
>>> threes = scale_stream(ints, 3)
>>> m = merge(twos, threes)
>>> [m[i] for i in range(10)]
[2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
"""
def make_s():
"""Return a stream over all positive integers with only
factors 2, 3, & 5.
>>> s = make_s()
>>> [s[i] for i in range(20)]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24,
25, 27, 30, 32, 36]"""
Q4. Use the Prolog-in-Scheme language presented in lecture to define a predicate eval such that (eval E V) is true if E is a Scheme expression that evaluates to V, where V is an integer in the range 0 to 6. Add your solution to the skeleton file hw13.scm. The only Scheme expressions we allow are:
- Integer literals from 0 to 6.
- Expressions (op E1 E2) where E1 and E2 are expressions and op is either of the symbols + or *.
For example, you should be able to get behavior like this:
scmlog scmlog (Prolog in Scheme), v. 0.1 Type 'help' for help; 'quit' to exit. ?- load hw13.scm ?- (? (eval (+ 2 (+ 1 2)) _x)) _x : 5 More? n ?- (? (eval (+ 2 (+ _a 1)) 5)) _a : 2 More? _a : (+ 0 2) More? n
WARNING: This system is quite slow. You'll need a certain amount of patience in waiting for results!
There is an implementation of the The Prolog-in-Scheme language presented in lecture on the instructional machines as the program scmlog. Type in help to this program to get a quick description of the commands. The Python source code for the system (which borrows from the Project 4 skeleton) is in ~cs61a/lib/scmlog; the main program is in prolog.py
Q5. Chances are that if you tried the following query on your implementation of the eval predicate in Q3, you'd get an infinite loop:
?- (? (eval (+ _x (* _y _z)) 5) (num _x) (num _y) (num _z))
(i.e., "find numerals _x, _y, and _z such that _x+_y*_z = 5.) On the other hand, the query:
?- (? (num _x) (num _y) (num _z) (eval (+ _x (* _y _z)) 5))
will find solutions (albeit very slowly: expect minutes). Explain this discrepency. Why does the ordering of the query matter? It doesn't in logic, after all.
Q6. [A general programming problem, not necessarily related to the week's material] Write a function unabbrev that, given a possibly abbreviated word, w and a vocabulary (a set of words) V, returns the shortest member of V for which w might be an abbreviation (that is, the shortest word in V that could be turned into w by removing letters.) If there are no such words in V or more than one shortest one, unabbrev should return w.
Q7. Extra for Experts Implement the complementary function abbrev, which given V and w in V, returns a shortest possible word that will unabbreviate to w.
Q8. Extra for Experts An iterator can enumerate the items in a tree as well as a sequence. Implement values, which interleaves the values of the branches of a tree.
Implement values using the helper function interleave, described in the skeleton file. Both of these functions, values and interleave, should return generators that yield values incrementally rather than constructing a sequence.
Hint: The itertools module provides functions and recipes that may be helpful.