CS61A Lab 4: Data Abstraction

Week 4, 2012

Today we get to explore the ideas of DATA ABSTRACTION!

Exercise 1: Data Derping

Try typing these into python, and think about the results:

>>> x = (4, 5)
>>> x[0]
>>> x[1]
>>> x[2]
>>> y = ('hello', 'goodbye')
>>> z = (x, y)
>>> z[1]
>>> (z[1])[0]
>>> z[1][0]
>>> z[1][1]

Exercise 2: Data Herp Derping

Predict the result of each of these before you try it:

>>> z[0][1]
>>> (8, 3)[0]
>>> z[0]
>>> 3[0]

Exercise 3: Abstracting Rational Numbers

Enter these definitions into Python:

def make_rat(num, den):
    return (num, den)

def num(rat):
    return rat[0]

def den(rat):
    return rat[1]

def mul_rat(a, b):
    new_num = num(a) * num(b)
    new_den = den(a) * den(b)
    return make_rat(new_num, new_den)

def str_rat(x):  #from lecture notes
       """Return a string 'n/d' for numerator n and denominator d."""
       return '{0}/{1}'.format(num(x), den(x))

Now try this, be sure to predict the results first!

>>> str_rat(make_rat(2, 3))
>>> str_rat(mul_rat(make_rat(2, 3), make_rat(1, 4)))

Exercise 4: div_rat

Define a procedure div_rat to divide two rational numbers in the same style as mul_rat above


Exercise 5: Segments

Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints)


Exercise 6: Functional Pairs

Type this into Python

def make_pair(x, y):
       """Return a function that behaves like a pair."""
       def dispatch(m):
           if m == 0:
               return x
           elif m == 1:
               return y
       return dispatch

The above is a functional representation of pairs. The big idea here is something called message passing. Notice that when we call make_pair, what we actually get back is a procedure, specifically the dispatch procedure. That dispatch procedure can then be called with an argument, and based on the argument, it returns the correct part of the pair. You can think of the argument to the dispatch procedure as a message, that the procedure takes and dispatches to the right task, hence the idea of message passing. Study this representation carefully, and understand the alternatives it brings, message passing will come back bigger and better later.

Modify the make_pair procedure above to accept a pair message, so that you can return the original pair as a tuple. Also add some error checking to catch cases when we call a dispatch function with a bad message. Use an assert statement to raise an error if a message is not recognized.

>>> p = make_pair(2, 3)

>>> p(0)
>>> 2

>>> p(1)
>>> 3

>>> p('pair')
>>> (2, 3)

>>> p(3)
Traceback (most recent call last):
 File "", line 1, in 
AssertionError: Message not recognized

Exercise 7: Abstracting Rectangles

Implement a representation for rectangles in a plane. (Hint: You may want to make use of your procedures from exercise 5). Then, in terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle.


You are now a professional Data Abstracter! :D