**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)andscale-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)whereE1andE2are expressions andopis 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.