Software Design Lecture Notes
Fall 2004

For next time:

1) Read Chapter 13


Exam 1 Solutions
----------------

Vocabulary:

== tests equivalence (or equality or deep equality)

is tests identity (or shallow equality or aliasing, but not sameness)

A constructor is a special method (or function)...

A key is like and index and a value (or key-value pair) is like a element.

More than one name is aliasing, which is relatively safe with things
that are immutable.

Debugging:

def join_backwards(t):
    for item in t.reverse():    # runtime: reverse returns None
        s = s + item            # runtime: s is uninitialized
    return s


def avoids(word, forbidden):
    for c in word:
        if c in forbidden:
            return False
        else:
            return True         # semantic: can't return True until
                                # we've seen the whole word


def beam(t  n  height):         # syntax: need commas in param list
    lt(t)
    fdrt(t, n * height)
    fdbk(t, n)                  # semantic: this function doesn't
    ltbk(t, n * height)         # do exactly what the comments say
    rt(t)


Refactoring:

def step(t, d):
# draw a single step with length d
    fd(t, d)
    lt(t)
    fd(t, d)
    rt(t)

def steps(t, d, n):
# draw n steps with length d
    for i in range(n):
        step(t, d)

def boxes(t, d, n):
# draw n boxes along a diagonal
    for i in range(2):
        steps(t, d, n)	
        lt(t, 180)

bob = Turtle(world)
boxes(bob, 40, 4)

Important features here include:

1) describing the function using higher-level abstractions
   (steps and boxes)

2) the turnaround box should not be special case


A little programming:

def unique_list(t):
    d = {}
    for x in t:
        d[x] = 1
    u = d.keys()
    u.sort()
    return u

Remember:

1) dictionaries are good for enforcing uniqueness

2) it's ok to allocate temporary space!

3) list methods are modifiers that return None

4) functions_without_parameters_still_need_parentheses()


Alternative:

def unique_list(t):
    u = []
    for x in t:
        if x not in u:
	    u.append(x)
    u.sort()
    return u

Performance issue:

keys() values() and items() create new lists every time;
avoid calling them inside a loop.

Correctness issue:

Never modify a data structure while you are traversing it!


Stack diagram:

Let's make a stack diagram!



Four ways to make programming hard
----------------------------------

1) Do everything yourself.

   Taking advantage of built-in functions is for sissies.

2) Solve problems in one complicated step.

   Avoid using a sequence of simple steps.

3) Never allocate space.

   Avoid creating temporary data structures.


Remember: It's better to be fast than correct.


Three debugging modes
---------------------

1) examine code

2) collect more data

3) think about the data you have

If you are stuck in one mode, switch to another!


Homework 5 Tips
---------------

Important to think and talk about the program in terms of
appropriate abstractions, like prefixes, suffixes, and windows.

Text: "Make the common case fast; make the rare case correct."

Level 1 Analysis: for every word in the text, create a list of
the words that might follow.

make --> the
the --> common, rare
common --> case
case --> fast, correct
rare --> case

Level 2 Analysis: for every prefix of two words, create a list
of words that might follow.

make the --> common, rare
the common --> case
common case --> fast
case fast --> make
fast make --> the
the rare --> case
rare case --> correct

Generate random text by choosing a random prefix and then
choosing from the list of words that follow.

Then form a new prefix and choose again.


Name that novel
---------------

1) James Gatz--that was really, or at least one of the fundamental
decencies is parcelled out unequally at birth. And, after boasting
this way of finding out what your 'drug-stores' were." He turned his
attention to Tom. "I'd like to know who came here in front; only the
children and the servants came in she jumped up and down upon some
vivid scene with an utterly abandoned feeling, and asked for
information and urged him to come out on the wall.

2) And the fruitful fields of clover and the word meant, but Squealer
spoke so persuasively, and the air of having something important to
say. At one end of the young pigs, which was the only boar on the farm
from now onwards. After this they went hungry, it was needful to
prevent the return of the kind had been finished punctually to the
last atom of our Leader, Comrade Napoleon, I have had no more
debates. In spite of their future doom.

3) I have come legally to man's estate. I am doing well. But what is
the family, there were moments of deep meaning, that several people on
the arm he left Moscow had been to sleep in a few moments of
life. Whether it was a numble person like Jane." "Ah! madam," cried
he, affronted in his guest, give way to its native fields." Napoleon
rode over there, do you give me a last look she watched him smilingly,
and he turned toward him which not only of the Russian ladies are
great observers, sir.'


List comprehensions
-------------------

Try this:

>>> t = range(10)

>>> t2 = [x**2 for x in t]

>>> t3 = [chr(ord('a') + x) for x in t]

>>> z = zip(t3, t)

>>> d = dict(z)

>>> [d[key] for key in d]

>>> u = [(value, key) for (key, value) in d.items()]

>>> u.sort()

>>> u.reverse()

>>> print u