Lecture $4$: Data Abstraction

From recursion on numbers to programs that build data

• Previously: recursive structure on inputs like $n$
• New problem: representing compound objects like $n/d$
• Key tool: abstraction barrier via constructors $+$ selectors
• Destination: change the representation without changing the users

Why bother? Exactness and meaning

$$ \frac{1}{3} + \frac{1}{6} = \frac{1}{2} $$

• Rational number as one object: numerator $n$ + denominator $d$
• Goal: compute without assuming the storage shape
• Idea: define a contract, then implement it

Constructors and selectors: the public interface

• Constructor: make_rat($n$, $d$)
• Selectors: numer($r$), denom($r$)
• Operations above the barrier: add_rat, mul_rat, equal_rat
• Rule: no reaching through the barrier (no r[0])

Wishful thinking: write arithmetic before representation

$$ \frac{n_1}{d_1}+\frac{n_2}{d_2}=\frac{n_1 d_2+n_2 d_1}{d_1 d_2} $$

def add_rat(x, y):
    return make_rat(
        numer(x) * denom(y) + numer(y) * denom(x),
        denom(x) * denom(y),
    )

def mul_rat(x, y):
    return make_rat(
        numer(x) * numer(y),
        denom(x) * denom(y),
    )

def equal_rat(x, y):
    return numer(x) * denom(y) == numer(y) * denom(x)

• Abstraction promise: all users call add_rat($x$, $y$)

The abstraction barrier: what changes, what does not

• Top layer: rational operations (add_rat, mul_rat, ...)
• Interface layer: make_rat, numer, denom
• Bottom layer: concrete representation (tuple, list, dict, closure)
• Checkpoint: swap tuples to lists; what code must change?

One implementation: tuples + normalization in mak$e_r$at

from math import gcd

def make_rat(n, d):
    if d == 0:
        raise ZeroDivisionError("denominator cannot be 0")

g = gcd(n, d)
    n //= g
    d //= g

# Normalize sign: denominator always positive
    if d < 0:
        n, d = -n, -d

• Payoff: add_rat improves automatically
• Danger: tuple indexing is now a private detail

Data without data structures: pairs as closures

def pair(x, y):
    def dispatch(m):
        if m == 0:
            return x
        elif m == 1:
            return y
        raise ValueError("m must be 0 or 1")

return dispatch

def first(p):
    return p(0)

def second(p):
    return p(1)

• Contract for a pair: first(pair($x$, $y$)) is $x$
• Same interface, new representation: message passing

Layered abstraction: segments built on points built on pairs

def make_point(x, y):
    return (x, y)

def x_coord(p):
    return p[0]

def y_coord(p):
    return p[1]

def make_segment(p1, p2):
    return (p1, p2)

• Each layer speaks only to the layer below
• Barrier violation example: using p[0] inside geometry code

The closure property: pairs of pairs become hierarchies

• Closure property: if $a$ and $b$ are data, then $(a,b)$ is data
• Nested pairs: trees, sequences, records
• Linked list idea: $(1,(2,(3,\text{None})))$
• Preview: in Chapter $2.2$, powerful operations on sequences

Exit ticket: respect the barrier

• Practice: define sub_rat($x$, $y$) using only make_rat, numer, denom
• Reflection: what future change breaks code that uses r[0]?