*Due by 11:59pm on Wednesday, 11/26*

**Submission:** See
Lab 1 for
submission instructions. We have provided a hw9.py starter file for the questions below.

**Readings:** You might find the following references
useful:

- Question 1
- Question 2
- Question 3
- Question 4
- Question 5
- Question 6
- Question 7
- Question 8
- Question 9
- Question 10: Challenge Problem (optional)

**This extra-large homework is worth 6 points!** While graded on effort, you
should make progress on all problems to earn credit. Start early!

The Brackulator language shares an evaluator with the Calculator language, but uses a more concise syntax. Instead of using operator names or symbols, Brackulator indicates operations using different kinds of brackets:

`[]`

: add`()`

: subtract`<>`

: multiply`{}`

: divide

Operand expressions are separated by spaces within these brackets. The following Brackulator expressions are followed by their Calculator equivalents.

```
<1 2 3> (* 1 2 3)
(5) (- 5)
[2{4 8}] (+ 2 (/ 4 8))
<[2{12 6}](3 4 5)> (* (+ 2 (/ 12 6)) (- 3 4 5))
```

By solving the following problems, you will implement a parser,
`brack_read`

, that returns an expression for the `calc_eval`

evaluator
implemented in the Calculator example from lecture.

All of your solutions should be defined in terms of the following dictionaries of bracket types, which configure the parser to supply the correct operator for each bracket:

```
# A dictionary from pairs of matching brackets to the operators they indicate.
brackets = {('[', ']'): '+',
('(', ')'): '-',
('<', '>'): '*',
('{', '}'): '/'}
# A dictionary with left-bracket keys and corresponding right-bracket values.
left_to_right = {left: right for left, right in brackets}
# The set of all left and right brackets.
all_brackets = set(left_to_right.keys()).union(set(left_to_right.values()))
```

Complete `tokenize`

, which splits a Brackulator expression into tokens,
and raise a `ValueError`

if any token is not a number or a known
bracket. *Hint*: You can first surround each bracket with spaces using
`line.replace`

, then split on spaces. Afterward, check each token to
ensure that it is legal. The provided `coerce_to_number`

function may
prove useful:

```
def tokenize(line):
"""Convert a string into a list of tokens.
>>> tokenize('2.3')
[2.3]
>>> tokenize('(2 3)')
['(', 2, 3, ')']
>>> tokenize('<2 3)')
['<', 2, 3, ')']
>>> tokenize('<[2{12.5 6.0}](3 -4 5)>')
['<', '[', 2, '{', 12.5, 6.0, '}', ']', '(', 3, -4, 5, ')', '>']
>>> tokenize('2.3.4')
Traceback (most recent call last):
...
ValueError: invalid token 2.3.4
>>> tokenize('?')
Traceback (most recent call last):
...
ValueError: invalid token ?
>>> tokenize('hello')
Traceback (most recent call last):
...
ValueError: invalid token hello
>>> tokenize('<(GO BEARS)>')
Traceback (most recent call last):
...
ValueError: invalid token GO
"""
# Surround all brackets by spaces so that they are separated by split.
for b in all_brackets:
line = line.replace(b, ' ' + b + ' ')
# Convert numerals to numbers and raise ValueErrors for invalid tokens.
tokens = []
for t in line.split():
"*** YOUR CODE HERE ***"
return tokens
def coerce_to_number(token):
"""Coerce a string to a number or return None.
>>> coerce_to_number('-2.3')
-2.3
>>> print(coerce_to_number('('))
None
"""
try:
return int(token)
except (TypeError, ValueError):
try:
return float(token)
except (TypeError, ValueError):
return None
```

Implement `brack_read`

, which returns an expression tree for the first
valid Brackulator expression in a list of tokens. The expression tree
should contain Calculator operators that correspond to the bracket
types. Raise a `SyntaxError`

for any malformed expression. The `Pair`

class and `nil`

object from lecture appear at the bottom of this file.
This function is similar to `scheme_read`

from Calculator's
Scheme reader file.

*Hint*: Introduce another function `read_tail`

that reads the elements
in a combination until reaching a closing bracket. In `brack_read`

make sure that the closing bracket of an expression matches the opening
bracket. The `left_to_right`

dictionary defined above gives you the
matching right bracket for each type of left bracket. The `brackets`

dictionary gives you the corresponding operator (e.g. '+' for '[' and
']').

Once you complete this problem, you can place your homework file in the
same directory as `scalc.py`

(and its supporting files), then run
`read_eval_print_loop`

to interact with the Brackulator language:

```
def brack_read(tokens):
"""Return an expression tree for the first well-formed Brackulator
expression in tokens. Tokens in that expression are removed from tokens as
a side effect.
>>> brack_read(tokenize('100'))
100
>>> brack_read(tokenize('([])'))
Pair('-', Pair(Pair('+', nil), nil))
>>> print(brack_read(tokenize('<[2{12 6}](3 4 5)>')))
(* (+ 2 (/ 12 6)) (- 3 4 5))
>>> brack_read(tokenize('(1)(1)')) # More than one expression is ok
Pair('-', Pair(1, nil))
>>> brack_read(tokenize('[])')) # Junk after a valid expression is ok
Pair('+', nil)
>>> brack_read(tokenize('([]')) # Missing right bracket
Traceback (most recent call last):
...
SyntaxError: unexpected end of line
>>> brack_read(tokenize('[)]')) # Extra right bracket
Traceback (most recent call last):
...
SyntaxError: unexpected )
>>> brack_read(tokenize('([)]')) # Improper nesting
Traceback (most recent call last):
...
SyntaxError: unexpected )
>>> brack_read(tokenize('')) # No expression
Traceback (most recent call last):
...
SyntaxError: unexpected end of line
"""
if not tokens:
raise SyntaxError('unexpected end of line')
token = tokens.pop(0)
n = coerce_to_number(token)
if n != None:
return n
elif token in left_to_right:
"*** YOUR CODE HERE ***"
```

Support code for Brackulator (from the Calculator example):

```
###################################
# Support classes for Brackulator #
###################################
class Pair:
"""A pair has two instance attributes: first and second. For a Pair to be
a well-formed list, second is either a well-formed list or nil. Some
methods only apply to well-formed lists.
>>> s = Pair(1, Pair(2, nil))
>>> s
Pair(1, Pair(2, nil))
>>> print(s)
(1 2)
>>> len(s)
2
>>> s[1]
2
>>> print(s.map(lambda x: x+4))
(5 6)
"""
def __init__(self, first, second):
self.first = first
self.second = second
def __repr__(self):
return "Pair({0}, {1})".format(repr(self.first), repr(self.second))
def __str__(self):
s = "(" + str(self.first)
second = self.second
while isinstance(second, Pair):
s += " " + str(second.first)
second = second.second
if second is not nil:
s += " . " + str(second)
return s + ")"
def __len__(self):
n, second = 1, self.second
while isinstance(second, Pair):
n += 1
second = second.second
if second is not nil:
raise TypeError("length attempted on improper list")
return n
def __getitem__(self, k):
if k < 0:
raise IndexError("negative index into list")
y = self
for _ in range(k):
if y.second is nil:
raise IndexError("list index out of bounds")
elif not isinstance(y.second, Pair):
raise TypeError("ill-formed list")
y = y.second
return y.first
def map(self, fn):
"""Return a Scheme list after mapping Python function FN to SELF."""
mapped = fn(self.first)
if self.second is nil or isinstance(self.second, Pair):
return Pair(mapped, self.second.map(fn))
else:
raise TypeError("ill-formed list")
class nil:
"""The empty list"""
def __repr__(self):
return "nil"
def __str__(self):
return "()"
def __len__(self):
return 0
def __getitem__(self, k):
if k < 0:
raise IndexError("negative index into list")
raise IndexError("list index out of bounds")
def map(self, fn):
return self
nil = nil() # Assignment hides the nil class; there is only one instance
```

To use the following function, you will need to place your homework solution in the same directory as the files from the Calculator Example:

```
def read_eval_print_loop():
"""Run a read-eval-print loop for the Brackulator language."""
global Pair, nil
from scheme_reader import Pair, nil
from scalc import calc_eval
while True:
try:
src = tokenize(input('brack> '))
while len(src) > 0:
expression = brack_read(src)
print(calc_eval(expression))
except (SyntaxError, ValueError, TypeError, ZeroDivisionError) as err:
print(type(err).__name__ + ':', err)
except (KeyboardInterrupt, EOFError): # <Control>-D, etc.
return
```

A mobile
is a type of hanging sculpture. A simple binary mobile consists of two
branches, `left`

and `right`

. Each branch is a rod of a certain length,
from which hangs either a weight or another mobile.

Improve the classes for `Branch`

, `Weight`

, and `Mobile`

below in the
following ways:

- The
`left`

and`right`

attributes of a`Mobile`

should both be`Branch`

instances. Check that the types of constructor arguments for`Mobile`

are`Branch`

instances, and raise an appropriate`TypeError`

for incorrect argument types. See the doctest for`Mobile`

for exception details. - The
`length`

of a`Branch`

and the`weight`

of a`Weight`

should be positive numbers. Implement`check_positive`

to check if an object`x`

is a positive number. - Add a property
`weight`

that gives the total weight of the mobile. - A mobile is said to be balanced if the torque applied by its left
branch is equal to that applied by its right branch (that is, if the
length of the left rod multiplied by the weight hanging from that rod
is equal to the corresponding product for the right side) and if each
of the submobiles hanging off its branches is balanced. Implement the
method
`is_balanced`

that returns`True`

if and only if the`Mobile`

is balanced.

When you are finished, all doctests below should pass:

```
class Mobile:
"""A simple binary mobile that has branches of weights or other mobiles.
>>> Mobile(1, 2)
Traceback (most recent call last):
...
TypeError: 1 is not a Branch
>>> m = Mobile(Branch(1, Weight(2)), Branch(2, Weight(1)))
>>> m.weight
3
>>> m.is_balanced()
True
>>> m.left.contents = Mobile(Branch(1, Weight(1)), Branch(2, Weight(1)))
>>> m.weight
3
>>> m.left.contents.is_balanced()
False
>>> m.is_balanced() # All submobiles must be balanced for m to be balanced
False
>>> m.left.contents.right.contents.weight = 0.5
>>> m.left.contents.is_balanced()
True
>>> m.is_balanced()
False
>>> m.right.length = 1.5
>>> m.is_balanced()
True
"""
def __init__(self, left, right):
"*** YOUR CODE HERE ***"
self.left = left
self.right = right
@property
def weight(self):
"""The total weight of the mobile."""
"*** YOUR CODE HERE ***"
def is_balanced(self):
"""True if and only if the mobile is balanced."""
"*** YOUR CODE HERE ***"
def check_positive(x):
"""Check that x is a positive number, and raise an exception otherwise.
>>> check_positive(2)
>>> check_positive('hello')
Traceback (most recent call last):
...
TypeError: hello is not a number
>>> check_positive('1')
Traceback (most recent call last):
...
TypeError: 1 is not a number
>>> check_positive(-2)
Traceback (most recent call last):
...
ValueError: -2 <= 0
"""
"*** YOUR CODE HERE ***"
class Branch:
"""A branch of a simple binary mobile."""
def __init__(self, length, contents):
if type(contents) not in (Weight, Mobile):
raise TypeError(str(contents) + ' is not a Weight or Mobile')
check_positive(length)
self.length = length
self.contents = contents
@property
def torque(self):
"""The torque on the branch"""
return self.length * self.contents.weight
class Weight:
"""A weight."""
def __init__(self, weight):
check_positive(weight)
self.weight = weight
def is_balanced(self):
return True
```

Your partner designed a beautiful balanced Mobile, but forgot to fill
in the classes of each part, instead just writing `T`

.

`T(T(4,T(T(4,T(1)),T(1,T(4)))),T(2,T(10)))`

The built-in Python funciton `eval`

takes a string argument, evaluates
it as a Python expression, and returns its value.

Complete the definition of `interpret_mobile`

so that it returns a
well-formed mobile by guessing the class for each `T`

. The function
should exhaustively test all possible combinations of types, then
attempt to `eval`

the resulting string when no `T`

remains, handling
`TypeErrors`

until a correct series of types is found.

*Warning*: Interpreting a large mobile is quite slow (can you say
why?). You will want to remove the doctest for the large mobile during
development:

```
def interpret_mobile(s):
"""Return a Mobile described by string s by substituting one of the classes
Branch, Weight, or Mobile for each occurrenct of the letter T.
>>> simple = 'Mobile(T(2,T(1)), T(1,T(2)))'
>>> interpret_mobile(simple).weight
3
>>> interpret_mobile(simple).is_balanced()
True
>>> s = 'T(T(4,T(T(4,T(1)),T(1,T(4)))),T(2,T(10)))'
>>> m = interpret_mobile(s)
>>> m.weight
15
>>> m.is_balanced()
True
"""
next_T = s.find('T') # The index of the first 'T' in s.
if next_T == -1: # The string 'T' was not found in s
try:
return eval(s) # Interpret s
except TypeError as e:
return None # Return None if s is not a valid mobile
for t in ('Branch', 'Weight', 'Mobile'):
"*** YOUR CODE HERE ***"
return None
```

An enhancement of the `Stream`

class from lecture appears below, along
with a function that returns an infinite stream of integers. To extend
it, implement an `__iter__`

method using a `yield`

statement that
returns a generator over the elements of the stream. Also add a
`__getitem__`

method to support item selection.

```
class Stream:
"""A lazily computed linked list."""
class empty:
def __repr__(self):
return 'Stream.empty'
empty = empty()
def __init__(self, first, compute_rest=lambda: Stream.empty):
assert callable(compute_rest), 'compute_rest must be callable.'
self.first = first
self._compute_rest = compute_rest
@property
def rest(self):
"""Return the rest of the stream, computing it if necessary."""
if self._compute_rest is not None:
self._rest = self._compute_rest()
self._compute_rest = None
return self._rest
def __repr__(self):
return 'Stream({0}, <...>)'.format(repr(self.first))
def __iter__(self):
"""Return an iterator over the elements in the stream.
>>> it = iter(ints)
>>> [next(it) for _ in range(6)]
[1, 2, 3, 4, 5, 6]
"""
"*** YOUR CODE HERE ***"
def __getitem__(self, k):
"""Return the k-th element of the stream.
>>> ints[5]
6
>>> increment_stream(ints)[7]
9
>>> s = Stream(1, lambda: Stream(2))
>>> [s[i] for i in range(2)]
[1, 2]
>>> s[2]
Traceback (most recent call last):
...
IndexError: Stream index out of range
"""
"*** YOUR CODE HERE ***"
def increment_stream(s):
"""Increment all elements of a stream."""
return Stream(s.first+1, lambda: increment_stream(s.rest))
# The stream of consecutive integers starting at 1.
ints = Stream(1, lambda: increment_stream(ints))
```

Implement the function `scale_stream`

, which returns a stream over each
element of an input stream, scaled by `k`

:

```
def scale_stream(s, k):
"""Return a stream of the elements of S scaled by a number K.
>>> s = scale_stream(ints, 5)
>>> s.first
5
>>> s.rest
Stream(10, <...>)
>>> scale_stream(s.rest, 10)[2]
200
"""
"*** YOUR CODE HERE ***"
```

A famous problem, first raised by Richard Hamming, is to enumerate, in
ascending order with no repetitions, all positive integers with no
prime factors other than 2, 3, or 5. These are called
regular numbers.
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 the `merge`

function that combines two ordered streams into
one ordered result stream, eliminating repetitions.

Fill in the definition of `merge`

, then fill in the definition of
`make_s`

below:

```
def merge(s0, s1):
"""Return a stream over the elements of strictly increasing s0 and s1,
removing repeats. Assume that s0 and s1 have no repeats.
>>> 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]
"""
if s0 is Stream.empty:
return s1
elif s1 is Stream.empty:
return s0
e0, e1 = s0.first, s1.first
"*** YOUR CODE HERE ***"
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]
"""
def rest():
"*** YOUR CODE HERE ***"
s = Stream(1, rest)
return s
```

Implement a function `unique`

that takes a stream and returns a stream in
which duplicates of any value are filtered out. This should work for
infinite streams as well as finite ones.

```
def unique(s):
"""Return a stream of the unique elements in s in the order that they
first appear.
>>> s = unique(to_stream([1, 2, 2, 1, 0, 4, 2, 3, 1, 9, 0]))
>>> [s[i] for i in range(6)]
[1, 2, 0, 4, 3, 9]
"""
"*** YOUR CODE HERE ***"
def to_stream(lst):
if not lst:
return Stream.empty
return Stream(lst[0], lambda: to_stream(lst[1:]))
```

Run-length encoding is a very simple data compression technique,
whereby runs of data are compressed and stored as a single value. A
*run* is defined to be a contiguous sequence of the same number. For
example, in the (finite) sequence

`1, 1, 1, 1, 1, 6, 6, 6, 6, 2, 5, 5, 5`

there are four runs: one each of 1, 6, 2, and 5. We can represent the same sequence as a sequence of tuples:

`(5, 1), (4, 6), (1, 2), (3, 5)`

Notice that the first element of each tuple is the number of times a particular number appears in a run, and the second element is the number in the run.

We will extend this idea to (possibly infinite) streams. Write a
function called `rle`

that takes in a stream of data, and returns a
corresponding stream of tuples, which represents the run-length encoded
version of the stream. It will also take in the maximum size of any
given run (default 10) to prevent having to compress infinite runs.

```
def rle(s, max_run_length=10):
"""
>>> example_stream = to_stream([1, 1, 1, 2, 3, 3])
>>> encoded_example = rle(example_stream)
>>> [encoded_example[i] for i in range(3)]
[(3, 1), (1, 2), (2, 3)]
>>> shorter_encoded_example = rle(example_stream, 2)
>>> [shorter_encoded_example[i] for i in range(4)]
[(2, 1), (1, 1), (1, 2), (2, 3)]
>>> encoded_naturals = rle(ints)
>>> [encoded_naturals[i] for i in range(3)]
[(1, 1), (1, 2), (1, 3)]
>>> ones = Stream(1, lambda: ones)
>>> encoded_ones = rle(ones, max_run_length=3)
>>> [encoded_ones[i] for i in range(3)]
[(3, 1), (3, 1), (3, 1)]
"""
"*** YOUR CODE HERE ***"
```

The Python Challenge is a website designed to teach people the many features of the Python Library. Each page of the site is a puzzle that can be solved simply in Python. The solution to each puzzle gives the URL of the next.

There is a function stub below to include your solution to puzzle 4 (the one with the picture of a wood carving). You will have to complete puzzles 0, 1, 2, and 3 to reach 4. You can start on puzzle 0 here.

Some hints:

Puzzle 1. Try

`str.maketrans`

to make a dictionary and`str.translate`

to generate a new string. Letters are listed in the`string`

module.`>>> 'Borkozoy'.translate(str.maketrans('oz', 'el')) 'Berkeley' >>> import string >>> string.ascii_lowercase 'abcdefghijklmnopqrstuvwxyz'`

Puzzles 2 and 3. To view the source code of a web page in a browser, use

- Chrome: View > Developer > View Page Source
- Firefox: Tools > Web Developer > Page Source
- Safari: View > View Source

Uppercase letters are also in the

`string`

module.`>>> string.ascii_uppercase 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'`

Puzzle 4. Here's an example of fetching the source of a web page in Python. The address below links to an archive of the first WWW site.

`>>> base = 'http://www.w3.org/History/19921103-hypertext/hypertext' >>> addr = base + '/WWW/TheProject.html' >>> from urllib.request import urlopen >>> contents = urlopen(addr).read().decode() >>> contents.split('\n')[1] '<TITLE>The World Wide Web project</TITLE>'`

As you work on this puzzle, make sure to print the result of each step.

The comments on the puzzle page say: "urllib may help. DON'T TRY ALL NOTHINGS, since it will never end. 400 times is more than enough."

You can include your solution to puzzle 4 below:

```
from urllib.request import urlopen
def puzzle_4():
"""Return the soluton to puzzle 4."""
"*** YOUR CODE HERE ***"
```