---

name: abstraction description: "Abstraction and LSP"

Barbara Liskov Principles

Applying Barbara Liskov's foundational work on data abstraction and behavioral subtyping from CLU, Argus, and the Liskov Substitution Principle. The "L" in SOLID.

---

Core Philosophy

The Liskov Substitution Principle

"If for each object o1 of type S there is an object o2 of type T such that for all programs P defined in terms of T, the behavior of P is unchanged when o1 is substituted for o2, then S is a subtype of T."

In plain terms: Subtypes must be substitutable for their base types without breaking program correctness.

// VIOLATION: Square breaks Rectangle's contract
class Rectangle {
    protected int width, height;

    public void setWidth(int w) { width = w; }
    public void setHeight(int h) { height = h; }
    public int area() { return width * height; }
}

class Square extends Rectangle {
    // Violates LSP: changes behavior of setWidth/setHeight
    @Override
    public void setWidth(int w) { width = height = w; }
    @Override
    public void setHeight(int h) { width = height = h; }
}

// This test FAILS for Square but PASSES for Rectangle
void testRectangle(Rectangle r) {
    r.setWidth(5);
    r.setHeight(4);
    assert r.area() == 20; // Square returns 16!
}

// CORRECT: Don't use inheritance for "is-a" that violates behavior
interface Shape {
    int area();
}

class Rectangle implements Shape {
    private final int width, height;
    public Rectangle(int w, int h) { width = w; height = h; }
    public int area() { return width * height; }
}

class Square implements Shape {
    private final int side;
    public Square(int s) { side = s; }
    public int area() { return side * side; }
}

Behavioral Subtyping Rules

A subtype must satisfy:

1. Signature Rule: Method signatures compatible (covariant returns, contravariant parameters)
2. Methods Rule: Subtype methods preserve supertype behavior
3. Properties Rule: Subtype preserves supertype invariants

// The contract includes MORE than just types
interface Stack<T> {
    void push(T item);  // Post: size increases by 1
    T pop();            // Pre: !isEmpty(). Post: size decreases by 1
    boolean isEmpty();
    int size();
}

// Any implementation MUST honor those contracts
class BoundedStack<T> implements Stack<T> {
    // Can ADD preconditions only if they're weaker
    // Can ADD postconditions only if they're stronger
    // Must preserve: push then pop returns same item
}

---

Data Abstraction

Abstract Data Types (ADTs)

From CLU: Define types by their operations, not their representation.

# ADT: What operations exist, not how data is stored
class Set:
    """
    Abstract Data Type: Set of unique elements

    Operations:
        add(element) -> None      # Adds element if not present
        remove(element) -> None   # Removes element if present
        contains(element) -> bool # True if element in set
        size() -> int            # Number of elements

    Invariants:
        - No duplicates
        - size() >= 0
        - add(x) then contains(x) == True
        - remove(x) then contains(x) == False
    """

    def __init__(self):
        self._elements = []  # Implementation hidden

    def add(self, element):
        if element not in self._elements:
            self._elements.append(element)

    # Could change to hash table without changing interface

Information Hiding

The representation is PRIVATE. Only operations are PUBLIC.

// BAD: Exposes representation
public class Account {
    public double balance;  // Anyone can set to -1000000
}

// GOOD: Hides representation, exposes operations
public class Account {
    private double balance;

    public void deposit(double amount) {
        if (amount <= 0) throw new IllegalArgumentException();
        balance += amount;
    }

    public void withdraw(double amount) {
        if (amount <= 0 || amount > balance)
            throw new IllegalArgumentException();
        balance -= amount;
    }

    public double getBalance() { return balance; }
}

---

Specification & Contracts

Pre/Post Conditions

Every operation has a contract:

/**
 * Finds the index of the first occurrence of target.
 *
 * @param arr the array to search (PRECONDITION: arr != null)
 * @param target the value to find
 * @return index of target, or -1 if not found
 *         (POSTCONDITION: result == -1 || arr[result] == target)
 */
public int indexOf(int[] arr, int target) {
    // Precondition check
    if (arr == null) throw new NullPointerException();

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Class Invariants

Properties that must ALWAYS be true (between method calls):

public class SortedList<T extends Comparable<T>> {
    private List<T> elements = new ArrayList<>();

    // INVARIANT: elements is always sorted

    public void add(T item) {
        int pos = Collections.binarySearch(elements, item);
        if (pos < 0) pos = -(pos + 1);
        elements.add(pos, item);
        // Invariant preserved: still sorted
    }

    public T get(int index) {
        return elements.get(index);
        // Invariant preserved: read-only
    }

    // WRONG: Would break invariant
    // public List<T> getElements() { return elements; }

    // RIGHT: Defensive copy preserves invariant
    public List<T> getElements() {
        return new ArrayList<>(elements);
    }
}

---

Inheritance Guidelines

When to Use Inheritance

YES: True behavioral subtyping

// InputStream defines contract, FileInputStream honors it
class FileInputStream extends InputStream {
    // All InputStream contracts preserved
}

NO: Implementation reuse without behavioral compatibility

// DON'T: Stack is not a Vector (different contracts)
class Stack extends Vector { } // Java's mistake

// DO: Composition for implementation reuse
class Stack<T> {
    private List<T> items = new ArrayList<>();
    public void push(T item) { items.add(item); }
    public T pop() { return items.remove(items.size() - 1); }
}

The Liskov Test

Before creating class S extends T, ask:

1. Can S be used everywhere T is expected?
2. Does S preserve all of T's invariants?
3. Does S honor all of T's method contracts?
4. Would a client using T be surprised by S's behavior?

If ANY answer is "no" or "maybe", don't inherit.

---

CLU Innovations (Historical Context)

Liskov's CLU language (1974-1977) pioneered:

CLU Feature	Modern Equivalent
Clusters (ADTs)	Classes with private fields
Iterators	Python generators, Java Iterators
Exception handling	try/catch/throw
Parameterized types	Generics/Templates
Multiple return values	Tuples, destructuring

% CLU cluster (abstract data type)
int_set = cluster is create, insert, member, size
    rep = array[int]

    create = proc() returns (cvt)
        return (rep$new())
    end create

    insert = proc(s: cvt, i: int)
        if ~member(up(s), i) then rep$addh(s, i) end
    end insert

    member = proc(s: cvt, i: int) returns (bool)
        for x: int in rep$elements(s) do
            if x = i then return (true) end
        end
        return (false)
    end member
end int_set

---

Review Checklist

When reviewing type hierarchies:

Substitutability

• Can subtype instances replace supertype in all contexts?
• Do subtypes preserve supertype invariants?
• Are method contracts (pre/post conditions) honored?
• No surprises: would users of supertype expect subtype behavior?

Abstraction Quality

• Is representation hidden (private fields)?
• Are operations the only public interface?
• Could implementation change without breaking clients?
• Are invariants documented and enforced?

Contract Clarity

• Preconditions documented and checked?
• Postconditions documented and tested?
• Invariants explicitly stated?
• Exception conditions specified?

---

When to Apply

Scenario	Apply Liskov
Designing inheritance hierarchy	Yes - LSP is mandatory
Defining interfaces/contracts	Yes - specify behavior
Reviewing OO design	Yes - check substitutability
Creating ADTs	Yes - information hiding
Performance optimization	No - see optimization
Implementation patterns	Partially - see design-patterns

---

Source Material

• "A Behavioral Notion of Subtyping" (1994) - Liskov & Wing
• "Data Abstraction and Hierarchy" (1987) - OOPSLA keynote
• "Abstraction and Specification in Program Development" (1986) - Liskov & Guttag
• "CLU Reference Manual" (1981)
• Turing Award Lecture (2008)