Lecture $4$: Data Abstraction

Practice abstraction barriers with rationals and pairs: predict normalized representations, trace closure-based pairs, and implement rational subtraction that survives a representation swap.

0. Predict Normalization Results (SICP Ex 2.1)

**Predict the output** (write it down before running).

This `make_rat` reduces by `gcd` and normalizes the sign so the denominator is always positive.

```python
from math import gcd

def make_rat(n, d):
    if d == 0:
        raise ZeroDivisionError
    g = gcd(n, d)
    n //= g
    d //= g
    if d < 0:
        n, d = -n, -d
    return (n, d)

def numer(r):
    return r[0]

def denom(r):
    return r[1]

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

def rat_str(r):
    return f"{numer(r)}/{denom(r)}"

print(make_rat(2, 4))
print(rat_str(make_rat(1, -2)))
print(rat_str(add_rat(make_rat(1, 3), make_rat(1, 6))))
```

What are the three printed lines (in order)?

from math import gcd

def make_rat(n, d):
    if d == 0:
        raise ZeroDivisionError
    g = gcd(n, d)
    n //= g
    d //= g
    if d < 0:
        n, d = -n, -d
    return (n, d)

def numer(r):
    return r[0]

def denom(r):
    return r[1]

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

def rat_str(r):
    return f"{numer(r)}/{denom(r)}"

# Prediction (before running):
# Line 1: 
# Line 2: 
# Line 3: 

# Uncomment to check:
# print(make_rat(2, 4))
# print(rat_str(make_rat(1, -2)))
# print(rat_str(add_rat(make_rat(1, 3), make_rat(1, 6))))

Normalization means the *stored* pair might not match the inputs.

Reduction: divide numerator and denominator by gcd(n, d).

Sign rule: the denominator ends up positive; the sign (if any) goes on the numerator.

The prints are:
(1, 2)
-1/2
1/2

Because make_rat(2,4) reduces to (1,2); make_rat(1,-2) normalizes sign to (-1,2); and 1/3 + 1/6 = 1/2, then make_rat reduces/normalizes.

1. Trace Message-Passing Pairs (SICP Ex 2.4)

This is a *procedural* (closure) representation of pairs.

1) **Predict** what the final `print` outputs.
2) **Trace** the evaluation of `car(p)` using the substitution model: show what `p` is, what function gets called, and which value is returned.

```python
def cons(x, y):
    return lambda m: m(x, y)

def car(z):
    return z(lambda p, q: p)

def cdr(z):
    return z(lambda p, q: q)

p = cons(3, 4)
print(car(p) + cdr(p))
```

Write your trace as comments in the starter code.

def cons(x, y):
    return lambda m: m(x, y)

def car(z):
    return z(lambda p, q: p)

def cdr(z):
    return z(lambda p, q: q)

p = cons(3, 4)

# Prediction:
# print(...) will output: 

# Trace (substitution-style) for car(p):
# 1. p is ...
# 2. car(p) = p(lambda p,q: p)
# 3. then ...
# 4. returns ...

print(car(p) + cdr(p))

In this representation, a 'pair' is a function that takes a selector function `m`.

`car` passes in a function that returns its first argument; `cdr` passes in one that returns its second argument.

For tracing: expand `p = cons(3, 4)` into a lambda that closes over `x=3` and `y=4`.

Prediction: it prints 7.

Trace sketch:
- p = cons(3,4) = (lambda m: m(3,4)) with x=3,y=4 closed over.
- car(p) = p(lambda p,q: p)
- so (lambda m: m(3,4))(lambda p,q: p)
- => (lambda p,q: p)(3,4)
- => 3.
Similarly, cdr(p) => 4, so 3+4 = 7.

2. Implement sub_rat and Swap Representations Without Breaking Users

You will do two things:

1) **Implement** `sub_rat(x, y)` using *only* `make_rat`, `numer`, and `denom` (stay above the abstraction barrier).
2) **Extend** the system by implementing `install_closure_repr()` so rationals are represented using *closures*, not tuples — without changing `add_rat`, `mul_rat`, `sub_rat`, or `equal_rat`.

Rules:
- `sub_rat` must not use tuple indexing like `x[0]`.
- After calling `install_closure_repr()`, existing arithmetic functions must still work.

Starter code already provides tuple-based rationals via `install_tuple_repr()`.

**Goal:** The same rational arithmetic code works under both representations.

from math import gcd

# --- Rational operations (ABOVE the barrier): do not change these. ---

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)

def sub_rat(x, y):
    """Return x - y using ONLY make_rat, numer, denom."""
    # YOUR CODE HERE
    raise NotImplementedError

# --- Representation installers (BELOW the barrier): you may change these. ---

def _normalize(n, d):
    if d == 0:
        raise ZeroDivisionError("denominator cannot be 0")
    g = gcd(n, d)
    n //= g
    d //= g
    if d < 0:
        n, d = -n, -d
    return n, d


def install_tuple_repr():
    """Install tuple-based representation (n, d)."""
    global make_rat, numer, denom, rat_str

    def make_rat(n, d):
        n, d = _normalize(n, d)
        return (n, d)

    def numer(r):
        return r[0]

    def denom(r):
        return r[1]

    def rat_str(r):
        return f"{numer(r)}/{denom(r)}"


def install_closure_repr():
    """Install closure-based representation.

    After installing, a rational r should be a function (a closure) that
    'remembers' its normalized numerator and denominator.

    You must set the globals: make_rat, numer, denom, rat_str.
    """
    # YOUR CODE HERE
    raise NotImplementedError


# Default to tuple repr for interactive experimenting
install_tuple_repr()

# Try it (after you implement):
# x = make_rat(1, 3)
# y = make_rat(1, 6)
# print(rat_str(sub_rat(x, y)))  # expected 1/6
# install_closure_repr()
# x = make_rat(1, 3)
# y = make_rat(1, 6)
# print(rat_str(sub_rat(x, y)))  # expected 1/6

For subtraction: x - y = (n1/d1) - (n2/d2) = (n1*d2 - n2*d1) / (d1*d2). Build the result with make_rat.

For closure repr, you can use a dispatch function that returns n when asked for 0 and d when asked for 1 (like the lecture's pair).

Keep normalization in the constructor: make_rat should call _normalize before storing n and d.

Only the installer should know whether rationals are tuples or closures.

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


def install_closure_repr():
    global make_rat, numer, denom, rat_str

    def make_rat(n, d):
        n, d = _normalize(n, d)

        def dispatch(m):
            if m == 0:
                return n
            if m == 1:
                return d
            raise ValueError('m must be 0 (numer) or 1 (denom)')

        return dispatch

    def numer(r):
        return r(0)

    def denom(r):
        return r(1)

    def rat_str(r):
        return f"{numer(r)}/{denom(r)}"

Lecture $4$: Data Abstraction — Lab

0. Predict Normalization Results (SICP Ex 2.1)

1. Trace Message-Passing Pairs (SICP Ex 2.4)

2. Implement sub_rat and Swap Representations Without Breaking Users