Abstraction & Computational Thinking

The word abstraction comes from the Latin abstrahere — to pull away, to separate. In computer science it means exactly this: you pull a name away from the details of how something works, and thereafter you can use the name without knowing (or caring about) those details.

Consider the humble sqrt function. When you write sqrt(2.0) you are not thinking about Newton's method, IEEE 754 floating-point representation, or cache lines. You know the contract: give it a non-negative number, get back its square root. The implementation is irrelevant to the caller. This separation — what something does vs. how it does it — is the defining move of abstraction.

Abelson and Sussman called this the black-box principle: a procedure should be usable as a module without knowledge of how it is implemented. The consequence is profound: you can replace the implementation (say, swap Newton's method for a lookup table) without any caller changing at all, as long as the contract is preserved.

Abstraction is not just about functions. It applies to data (a rational number is a pair of integers — you don't need to know which pair representation), to modules (a sort routine is a sorted sequence — you don't need to know if it's merge sort), and to entire systems (TCP gives you a reliable byte stream — you don't need to know about packet fragmentation).

# The caller knows NOTHING about how sqrt works.
import math

result = math.sqrt(2.0)   # Contract: returns √x for x ≥ 0
print(result)             # 1.4142135623730951

# We could swap the implementation entirely:
def my_sqrt(x, tol=1e-10):
    """Newton's method — same contract, different internals."""
    guess = x / 2.0
    while abs(guess * guess - x) > tol:
        guess = (guess + x / guess) / 2.0
    return guess

# Every caller works identically with either version.
print(my_sqrt(2.0))       # 1.4142135623730951

A abstraction barrier is a formal discipline: code in layer N is only allowed to use the interface exported by layer N-1, never the internals of layer N-1. When every layer respects this rule, the system has a stratified design — you can change the implementation of any layer without touching layers above or below it.

SICP makes this beautifully concrete with rational numbers. We define three procedures that form the abstraction barrier: make_rat(n, d) constructs a rational, numer(r) extracts the numerator, denom(r) extracts the denominator. Code that uses rational numbers is only allowed to call these three procedures. It is forbidden to reach inside and pull out the first element of a pair directly.

Why does this matter? Suppose you later decide to normalize the rational at construction time (reduce 4/6 to 2/3). If all callers go through the barrier, you change only make_rat. If callers reach inside the pair directly, you must hunt down every such call. The barrier localizes change.

This principle scales from tiny utility functions to OS kernel interfaces. The Linux kernel exports a set of system calls — that is the abstraction barrier between user space and kernel space. User programs are not allowed to directly manipulate kernel data structures. This means the kernel can be rewritten in any way, on any CPU architecture, without breaking user programs.

# Layer 0 (representation): a pair
def make_rat(n, d):
    g = gcd(abs(n), abs(d))
    return (n // g, d // g)   # normalize here — hidden from callers

def numer(r): return r[0]    # ← these three ARE the abstraction barrier
def denom(r): return r[1]

# Layer 1 (arithmetic): uses ONLY the barrier, never r[0]/r[1] directly
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))

# Layer 2 (display): uses only Layer 1
def print_rat(r):
    print(f"{numer(r)}/{denom(r)}")

print_rat(add_rat(make_rat(1, 3), make_rat(1, 6)))  # 1/2

Decomposition is the act of breaking a large problem into smaller sub-problems that can be solved independently and composed together. It is the prerequisite for abstraction: you can only draw a barrier around something you have first separated out.

Good decomposition has a specific property: the sub-problems are independent, meaning solving one does not require knowing the internal state of another. This is sometimes called separation of concerns. Each sub-problem has a clear, minimal interface — ideally just its inputs and outputs.

There are two dominant styles of decomposition in programming:

1. Functional decomposition (procedural/functional programming): break the task into functions. Each function takes inputs and returns outputs. The quintessential example is a Unix pipeline: cat file | grep pattern | sort | uniq -c | sort -rn. Each stage is a completely independent program; they compose through a minimal interface (a stream of bytes).
2. Data decomposition (object-oriented programming): break the problem by the kinds of things involved (objects), and give each object responsibility for its own state and behavior.

The best decomposition is one where, if you need to change one part, the changes do not ripple into other parts. This property — called low coupling, high cohesion — is the engineering criterion for judging a decomposition. Low coupling means modules depend minimally on each other. High cohesion means everything inside a module is closely related.

# Poorly decomposed: one giant function, everything entangled
def process_data_bad(filename):
    with open(filename) as f:
        lines = f.readlines()
    words = []
    for line in lines:
        for word in line.strip().split():
            words.append(word.lower())
    counts = {}
    for w in words:
        counts[w] = counts.get(w, 0) + 1
    return sorted(counts.items(), key=lambda x: -x[1])[:10]

# Well decomposed: independent, reusable stages
def read_lines(filename):               # I/O concern only
    with open(filename) as f:
        return f.readlines()

def tokenize(lines):                    # parsing concern only
    return [w.lower() for line in lines for w in line.strip().split()]

def count_items(items):                 # counting concern only
    counts = {}
    for item in items:
        counts[item] = counts.get(item, 0) + 1
    return counts

def top_n(counts, n=10):               # ranking concern only
    return sorted(counts.items(), key=lambda x: -x[1])[:n]

def process_data_good(filename):
    return top_n(count_items(tokenize(read_lines(filename))))

To reason about what a program does, you need a mental model of how expressions evaluate. The substitution model is the simplest correct such model — it is how MIT 6.001 teaches evaluation before introducing more complex models involving environments and mutation.

The rule is: to evaluate a combination (a procedure application), evaluate the operator and all operands to get values, then substitute the argument values for the formal parameters in the body of the procedure, and evaluate the resulting expression.

There are two strategies for when to evaluate arguments:

• Applicative-order (eager evaluation, used by Python, C, Java): evaluate arguments before substituting them into the body. Also called call-by-value.
• Normal-order (lazy evaluation, used by Haskell): substitute unevaluated argument expressions into the body and evaluate only when the value is actually needed. Also called call-by-name or call-by-need (when results are memoized).

For expressions without side effects, both orders produce the same result (this is the Church-Rosser theorem). For expressions with side effects, order matters enormously.

The substitution model is not how real interpreters work — they use environments (frames mapping names to values) for efficiency and to handle mutation. But the substitution model is a perfect tool for reasoning about pure functional code, and understanding it is the foundation for understanding environments, closures, and the full evaluator.

# Trace the substitution model step by step:

def square(x):
    return x * x

def sum_of_squares(a, b):
    return square(a) + square(b)

# Evaluating: sum_of_squares(3, 4)
# Step 1: evaluate operator → sum_of_squares procedure
# Step 2: evaluate operands → 3, 4
# Step 3: substitute into body:
#   square(3) + square(4)
# Step 4: evaluate square(3):
#   substitute x=3 into x*x → 3*3 → 9
# Step 5: evaluate square(4):
#   substitute x=4 into x*x → 4*4 → 16
# Step 6: 9 + 16 → 25

result = sum_of_squares(3, 4)  # 25

# Normal-order vs applicative-order:
def p(): return p()   # infinite loop

def test(x, y):
    if x == 0:
        return 0
    return y

# Applicative-order: evaluates p() FIRST → infinite loop
# Normal-order: substitutes p() but never evaluates it (x==0 short-circuits) → 0
# test(0, p())  ← applicative hangs; normal-order returns 0

The most powerful form of procedural abstraction is treating procedures themselves as values — passing them as arguments, returning them from functions, and storing them in data structures. This is the central idea of higher-order functions and is what makes functional programming expressive.

Consider summing integers, summing squares, and summing the reciprocals of integers. Each is a different computation, but they all share the structure of iterating over a range and accumulating. The abstraction is sigma(f, a, b) — the summation operator from mathematics, parameterized by the function f. This is not a clever trick; it is the direct translation of mathematical notation into code.

Higher-order functions express the skeleton of a computation (the control flow) while leaving the details (what to do at each step) as a parameter. This is the principle behind Python's map, filter, and reduce, Haskell's type classes, and sorting with a custom comparator. It is also the foundation of the strategy pattern in object-oriented design.

This idea also runs the other direction: a function can return a function, creating new procedures programmatically. This is the basis of currying (transforming a multi-argument function into a sequence of single-argument functions) and closures (functions that capture variables from their enclosing scope).

# The summation abstraction (SICP §1.3)
def summation(term, a, b, next_val):
    """Compute sum of term(a) + term(a+1) + ... + term(b)."""
    if a > b:
        return 0
    return term(a) + summation(term, next_val(a), b, next_val)

def identity(x): return x
def square(x):   return x * x
def inc(x):      return x + 1

sum_ints    = summation(identity, 1, 10, inc)  # 55
sum_squares = summation(square,   1, 5,  inc)  # 55

# Returning functions: make_adder is a function factory
def make_adder(n):
    def adder(x):    # adder CLOSES OVER n
        return x + n
    return adder

add5 = make_adder(5)
add5(3)   # 8  — add5 is a real first-class value

# Composing functions
def compose(f, g):
    return lambda x: f(g(x))

square_then_inc = compose(inc, square)
square_then_inc(4)  # 17

Just as we abstract procedures by naming them and hiding their implementation, we abstract data by specifying it through a constructor (how to build it), selectors (how to pull pieces out), and a contract (the axioms that hold for any valid representation).

The key insight is that the representation is irrelevant as long as the contract holds. A rational number (n, d) can be stored as a Python tuple, a list, a dictionary {'n': ..., 'd': ...}, or even encoded as a single integer via Gödel numbering. The arithmetic code built on top of the selectors doesn't care and doesn't need to.

This idea generalizes to abstract data types (ADTs): a type defined entirely by its operations and the algebraic laws those operations must satisfy, with no reference to any implementation. A stack, for instance, is defined by: push followed by pop returns the original stack and the pushed value; an empty stack raises an error on pop. These laws fully specify stack behavior. Any data structure satisfying the laws is a valid stack.

ADTs are the precursor to modern interfaces, type classes (Haskell), protocols (Swift), and traits (Rust) — all of which specify behavior contracts rather than implementation details.

# Data abstraction for a 2D point — three representations, one contract

# Contract: make_point(x,y) ; x_coord(p) == x ; y_coord(p) == y

# Representation 1: tuple
def make_point_tuple(x, y): return (x, y)
def x_coord_t(p):           return p[0]
def y_coord_t(p):           return p[1]

# Representation 2: closure (no data structure at all!)
def make_point_closure(x, y):
    def dispatch(msg):
        if msg == 'x': return x
        if msg == 'y': return y
        raise ValueError(msg)
    return dispatch
def x_coord_c(p): return p('x')
def y_coord_c(p): return p('y')

# The distance function works with EITHER representation
def distance(p, q, x_coord, y_coord):
    dx = x_coord(p) - x_coord(q)
    dy = y_coord(p) - y_coord(q)
    return (dx**2 + dy**2) ** 0.5

p1 = make_point_tuple(0, 0)
p2 = make_point_tuple(3, 4)
print(distance(p1, p2, x_coord_t, y_coord_t))  # 5.0

p3 = make_point_closure(0, 0)
p4 = make_point_closure(3, 4)
print(distance(p3, p4, x_coord_c, y_coord_c))  # 5.0

One of the most profound ideas in SICP — and in computer science generally — is that the most powerful way to solve a complex problem is often to design a language in which the problem is easy to express, and then write the solution in that language. This is the meta-linguistic approach to abstraction.

Every time you define a new set of functions that work together to speak about a particular domain — say, geometry, digital circuits, or financial derivatives — you are building a domain-specific language (DSL) embedded in your host language. The abstractions you define are the vocabulary, and the ways they compose are the grammar.

This is not metaphorical. Lisp (and its dialects like Scheme) made this literal: the language's syntax is homoiconic (code is data), so you can write macros that extend the language itself. When Scheme's SICP defines let as syntactic sugar for a lambda application, it is genuinely extending the language. Racket, Clojure, and Common Lisp are built on this principle.

Even without macros, this philosophy is powerful. SQL is a DSL for set-relational queries. Regular expressions are a DSL for string patterns. Pandas/NumPy is a DSL for array computation. React's JSX is a DSL for UI trees. Each is a language of increasing power built on a simpler substrate — and the key design question for each is: what are the primitives, what are the means of combination, and what are the means of abstraction?

# Sketch of a mini-DSL for simple circuits (SICP Chapter 3 style)
# Primitives: wires, signals
# Combination: and-gate, or-gate, inverter
# Abstraction: define new gates from primitives

class Wire:
    def __init__(self):
        self.signal = 0
        self.actions = []
    def get_signal(self):
        return self.signal
    def set_signal(self, new_value):
        if self.signal != new_value:
            self.signal = new_value
            for action in self.actions:
                action()
    def add_action(self, proc):
        self.actions.append(proc)
        proc()  # run immediately to initialize

def inverter(input_wire, output_wire):
    def invert_input():
        output_wire.set_signal(1 - input_wire.get_signal())
    input_wire.add_action(invert_input)

def and_gate(a, b, output):
    def and_action():
        output.set_signal(a.get_signal() & b.get_signal())
    a.add_action(and_action)
    b.add_action(and_action)

# Now we can define a NAND gate as a COMPOSED ABSTRACTION:
def nand_gate(a, b, output):
    mid = Wire()
    and_gate(a, b, mid)
    inverter(mid, output)

# The DSL lets us describe circuits in their own terms.

Recursion is not just a programming technique — it is a way of thinking about structure. A recursive definition says: this thing is either a base case (the smallest version of itself) or it is composed of smaller versions of itself. This is exactly how most interesting data structures and algorithms are naturally organized.

Consider a list: it is either empty, or it is a head (first element) followed by a tail (which is itself a list). This structural definition immediately suggests a recursive traversal: to process a list, handle the head and then recursively process the tail.

The process shape generated by a recursive procedure can be either:

• Recursive process: the call stack grows linearly; pending operations accumulate. Classic example: factorial(n) = n * factorial(n-1) — the multiplications pile up until the base case.
• Iterative process (tail-recursive): the call is the last thing done, so the compiler can optimize it to a loop — no stack growth. The key is to carry forward an accumulator that holds all state.

The critical insight from SICP is that the shape of the process (iterative vs. recursive) is determined by the procedure, not by whether the procedure calls itself. A tail-recursive procedure generates an iterative process even though it uses recursion syntactically.

# Recursive process: deferred multiplications accumulate on the stack
def factorial_recursive(n):
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)  # multiplication is DEFERRED
# factorial_recursive(5) expands to:
# 5 * (4 * (3 * (2 * (1 * 1))))
# — O(n) stack depth

# Iterative process: tail-recursive, O(1) stack depth
def factorial_iter(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_iter(n - 1, n * accumulator)  # NOTHING deferred
# factorial_iter(5) steps:
# (5, 1) → (4, 5) → (3, 20) → (2, 60) → (1, 120) → (0, 120) → 120

# Tree recursion: natural for tree-structured data
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)  # O(φ^n) time — exponential!

# Same result, iterative process, O(n) time:
def fib_iter(n, a=0, b=1):
    if n == 0: return a
    return fib_iter(n-1, b, a+b)

The substitution model is beautifully simple but breaks down the moment you introduce assignment (mutation). Once a variable can change its value, you cannot just substitute its current value — you need a place to store the current value and look it up. That place is an environment.

An environment is a sequence of frames, where each frame is a mapping from names to values. To look up a name, you search the current frame; if it is not there, you search the enclosing frame, and so on up to the global environment. This is exactly lexical scoping: the name resolution rule is determined by the textual structure of the program, not by the call stack at runtime.

A closure is a procedure paired with the environment in which it was created (not the environment in which it is called). When a function references a free variable (one not in its parameter list), it looks up that variable in its closure's environment. This is why make_adder(5) returns a function that remembers n=5 even after make_adder has returned.

Closures are the foundation of almost all powerful programming abstractions: iterators, generators, callbacks, monads, object systems (an object is just a closure with multiple entry points), and continuations. Understanding closures via the environment model is the key that unlocks all of modern programming language theory.

# Demonstrating closure / environment behavior

def make_counter(initial=0):
    count = [initial]   # mutable cell in the closure's environment
    def increment():
        count[0] += 1
        return count[0]
    def reset():
        count[0] = initial
    return increment, reset

inc, rst = make_counter(0)
print(inc())  # 1
print(inc())  # 2
print(inc())  # 3
rst()
print(inc())  # 1  — the closure's environment was mutated by reset()

# Two independent counters share NO state:
c1_inc, _ = make_counter()
c2_inc, _ = make_counter()
print(c1_inc(), c1_inc())  # 1 2
print(c2_inc())            # 1  — completely independent frame

One of the most practical habits taught in SICP is wish-driven design (Abelson and Sussman sometimes call it programming by wishful thinking). The idea: when solving a complex problem, write the top-level solution first, freely invoking helper procedures you wish existed but have not yet written. Once the high-level structure is clear and correct, implement each helper the same way — top-down, one level at a time.

This is the opposite of bottom-up programming, where you build tiny utilities first and then assemble them. Top-down programming keeps you focused on the problem structure rather than the implementation details, and it makes the high-level abstraction visible before any implementation decisions are made.

In practice, wish-driven design combined with abstraction barriers produces code that is almost self-documenting: result = top_n(count_items(tokenize(read_lines(filename)))) tells you the entire story of the computation at a glance. Each name is a wish that was fulfilled at the next level.

This technique directly combats one of the most common failure modes in programming: premature optimization and premature concretization — getting lost in low-level details before the overall structure is understood. Write the wish first; make it real second.

# Top-down design for a simple web scraper summary

# Level 0 (write this first, with wishes):
def summarize_url(url):
    raw_html   = fetch_page(url)           # wish
    text       = extract_text(raw_html)    # wish
    sentences  = split_sentences(text)     # wish
    important  = top_sentences(sentences, n=3)  # wish
    return ' '.join(important)

# Level 1 (fulfill the wishes):
def fetch_page(url):
    import urllib.request
    with urllib.request.urlopen(url) as r:
        return r.read().decode('utf-8')

def extract_text(html):
    import re
    return re.sub(r'<[^>]+>', ' ', html)  # strip tags (simplified)

def split_sentences(text):
    import re
    return [s.strip() for s in re.split(r'(?<=[.!?]) +', text) if s.strip()]

def top_sentences(sentences, n):
    # Simplified: return longest n sentences as proxy for importance
    return sorted(sentences, key=len, reverse=True)[:n]