Abstraction and LSP
Applying Barbara Liskov's foundational work on data abstraction and behavioral subtyping from CLU, Argus, and the Liskov Substitution Principle. The "L" in SOLID.
"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; }
}
A subtype must satisfy:
// 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
}
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
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; }
}
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;
}
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);
}
}
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); }
}
Before creating class S extends T, ask:
If ANY answer is "no" or "maybe", don't inherit.
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
When reviewing type hierarchies:
| 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 |