Abstract Data Type Interface¶
An interface contract — instantiates Operation-Weighted Data Structure Design
Fixes the operations and guarantees a structure must offer while hiding how it stores them, so callers depend on behaviour, not representation.
Every sibling in this archetype commits to a representation — a hash, a matrix, a column store. Abstract Data Type Interface is the one that commits to none. It specifies a data type purely by the operations it offers, the guarantees those operations keep, and an encapsulation boundary that forbids callers from touching the storage underneath. Its defining move is the separation of what from how: because callers are bound only to the contract, the concrete structure behind it can be chosen — and later re-chosen — against the real operation mix without a single caller changing. It is the mechanism that makes the archetype's core promise (design the structure to the workload) survivable, by giving the workload a stable surface to hang on while the representation moves.
Example¶
A team building a scheduling library exposes a PriorityQueue type through five operations — insert(item, priority), peekMin(), extractMin(), size(), isEmpty() — with one standing guarantee: extractMin always returns the lowest-priority item currently held. Application code is written against those operations and nothing else. The first release stores the queue as a sorted array; months later, profiling shows the workload is extract-heavy, so the team swaps the innards for a binary heap and extractMin drops from O(n) to O(log n). Not one caller is edited, because the contract and its invariant never moved — only the hidden representation did. The interface is precisely what let the structure be re-fitted to the measured operation mix instead of frozen at the first guess.
How it works¶
- Name the operations with their pre/post-conditions and, optionally, their complexity promises — this is the contract callers may rely on.
- State the invariants the operations jointly preserve (here, "the minimum is always returned"), expressed without reference to any storage layout.
- Draw the encapsulation boundary so callers may touch only the operations, never the representation.
- Leave the representation unbound, to be selected and re-selected by a concrete sibling against the profiled workload.
What distinguishes it: it specifies behaviour and actively forbids representation coupling. It stores nothing itself.
Tuning parameters¶
- Interface width — a few essential operations versus a broad convenience surface. Wider is friendlier to callers but pins down more behaviour and rules out more representations.
- Invariant strength — how much the contract promises (ordering? uniqueness? iteration stability?). Stronger guarantees help callers but foreclose otherwise-cheaper structures.
- Complexity commitment — whether Big-O bounds are part of the promise or left to the implementation. Naming them protects callers' performance assumptions but locks out representations that miss them.
- Boundary tightness — how completely the representation is hidden. A deliberate leak (say, exposing an iterator over internal order) buys convenience at the cost of re-coupling callers to storage.
When it helps, and when it misleads¶
Its strength is that it lets a system pick and later swap the concrete structure against the measured operation mix with no caller migration — the whole reason the archetype can tune structure to workload — and it makes a family of implementations substitutable and testable against one contract.
It misleads at the two edges of the boundary. An interface that promises too little forces callers to reach around it and re-couple to the representation; one that promises too much — leaking internal order, exposing internals — quietly freezes the representation it was meant to free, exactly the leak that information hiding warns against.[n1] The classic misuse is a "contract" reverse-engineered from one implementation's incidental behaviour, which then silently forbids every other representation. The discipline that guards against it: derive the contract from the operations the workload needs, and test implementations against the contract, never against each other.
How it implements the components¶
Abstract Data Type Interface fills only the specification side of the archetype — the components that say what a structure must satisfy, not how it performs:
interface_contract— it is the contract: the named operations and the guarantees callers may depend on.representation_boundary— it draws the encapsulation line, exposing behaviour and concealing storage.structural_invariant_set— it states the invariants the operations must preserve, in representation-independent terms.
It implements nothing physical: the actual access paths and space-time cost are set by concrete structures such as Hash Table or Key-Value Store or Tree or B-Tree Index, and the operation mix it fronts is profiled by Workload Benchmark and Trace. This interface only says what they must satisfy.
Related¶
- Instantiates: Operation-Weighted Data Structure Design — it fixes the operation contract the archetype then optimises a representation for.
- Sibling mechanisms: Hash Table or Key-Value Store · Tree or B-Tree Index · Adjacency List or Matrix · Columnar or Row Layout · Entity-Relationship Schema · Materialized View or Cache · Normalized / Denormalized Schema Pair · Serialization Format and Codec · Schema Migration Runbook · Workload Benchmark and Trace
Editorial Notes¶
Form Classification¶
Form family: Structure, Architecture & Configuration
Rationale: The mechanism fixes the operations and guarantees a structure must offer while hiding how it stores them, so callers depend on behaviour, not representation, so its operative form is an enduring topology, boundary, or configured arrangement.
Independent corroboration: The frozen evidence defines Abstract Data Type Interface as 'Fixes the operations and guarantees a structure must offer while hiding how it stores them, so callers depend on behaviour, not representation', so its operative form is Structure, Architecture & Configuration.
Nearest alternative: Rule, Policy & Commitment — The operation set and hidden representation form an enduring technical boundary, while its guarantees are declarative constraints on that boundary.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Abstract data types, representation independence, invariants, and complexity contracts are foundational programming-language and data-structure concepts in computer science.
Related originating lineages:
- Mathematics — Algebraic specification and abstract structure materially informed formal ADT theory.
Review resolution: Computer science is unequivocally primary; algebraic specification and abstract structure materially informed formal ADT theory, so mathematics is retained as an alternate lineage.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
The interface is upstream of representation choice, not a representation itself. That position is exactly what makes the archetype's "re-choose the structure against the profile" move safe: a stable contract absorbs the change, so re-fitting storage to a shifting workload never becomes a caller-facing migration. Weaken or leak the contract and that shock absorber is gone.
[n1] Information hiding — David Parnas's principle that a module should expose only what callers need and conceal the design decisions (here, the representation) most likely to change, so those decisions can change without rippling outward. ↩