CS61A(11): Data Abstraction

Posted on | In |

This is the lecture note of CS61A - Lecture 11.

We've already learnt function, which is an abstraction of computation process.

In today's lecture, let's learn a new way of abstaction —— data abstraction.

Data Abstraction

Most value are compound values.

Let's look at an example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Rational arithmetic

# How to use data?

def add_rational(x, y):
    """The sum of rational numbers X and Y."""
    nx, dx = numer(x), denom(x)
    ny, dy = numer(y), denom(y)
    return rational(nx * dy + ny * dx, dx * dy)

def mul_rational(x, y):
    """The product of rational numbers X and Y."""
    return rational(numer(x) * numer(y), denom(x) * denom(y))

def equal_rational(x, y):
    """True iff rational numbers X and Y are equal."""
    return numer(x) * denom(y) == numer(y) * denom(x)

def print_rational(x):
    """Print rational X."""
    print(numer(x), "/", denom(x))

"""
When we implement the arithemtic rules of rational numbers, we don't care about how to implement 
rational numbers, we only care about how to use it.
"""
  • rational(n, d): returns a rational number
  • numer(x): returns the numerator
  • denom(x): returns the denominator

These three functions implement an abstract data type for rational numbers.

Q: How to implement these three functions?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# How to represent data?

# Constructor and selectors
def rational(n, d):
    """A representation of the rational number N/D."""
    return [n, d]

def numer(x):
    """Return the numerator of rational number X."""
    return x[0]

def denom(x):
    """Return the denominator of rational number X."""
    return x[1]

"""
When we implement rational numbers, we care about how to represent them with some data structures.
We don't care about how to use them.
"""

The above code need some improvements. Think about the following examples:

  • 3/2 * 5/3 = 15/6 = 5/2
  • 2/5 + 1/10 = 25/50 = 1/2

The numerator and denominator of a rational number should be relatively prime.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Improved implementation

from math import gcd    # greatest common divisor

def rational(n, d):
    """A representation of the rational number N/D.
       gcd: greatest common divisor
    """
    g = gcd(n, d)
    return [n//g, d//g]

def numer(x):
    """Return the numerator of rational number X in lowest terms and having
    the sign of X."""
    return x[0]

def denom(x):
    """Return the denominator of rational number X in lowest terms and positive."""
    return x[1]

Abstraction Barriers

The purpose of maintaining abstraction barriers, is so that you can change your data representation without having to rewrite your entire program.

Let's take a look at another example.

Here, we use function instead of built-in list to implement rational data. We only change data representation whereas keeping data manipulations. The outcome is still correct!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Functional implementation

def rational(n, d):
    """A representation of the rational number N/D."""
    g = gcd(n, d)
    n, d = n//g, d//g
    def select(name):
        if name == 'n':
            return n
        elif name == 'd':
            return d
    return select

def numer(x):
    """Return the numerator of rational number X in lowest terms and having
    the sign of X."""
    return x('n')

def denom(x):
    """Return the denominator of rational number X in lowest terms and positive."""
    return x('d')

"""
>>> x, y = rational(1, 2), rational(3, 8)
>>> x
<function rational.<local>.select>
>>> print_rational(mul_rational(x, y))
3 / 16
"""

Dictionaries

A dictionary allows you to associate values with keys.

👻 Dictionary doesn't have order inheritantly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
>>> numerals = {'I': 1, 'V': 5, 'X': 10}
{'I': 1, 'X': 10, 'V': 5}
>>> numerals['X']   # lookup through keys
10
>>> numerals[10]    # cannot through values
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 10

>>> numerals.keys()
dict_keys(['I', 'V', 'X'])
>>> numerals.values()
dict_values([1, 5, 10])
>>> items = numerals.items()
>>> items
dict_items([('I', 1), ('V', 5), ('X', 10)])
>>> dict(items)
{'I': 1, 'V': 5, 'X': 10}
>>> dict(items)['X']
10

>>> 'X' in numerals
True
>>> numerals.get('X', 0)        # if 'X' is the key of dictionary, return it's value
10
>>> numerals.get('X-ray', 0)    # otherwise, return 0
0

Dictionary Comprehension

1
2
>>> {x: x*x for x in range(10) if x < 5}
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16}