Abstract Data Type¶

Version: v1 · 2026-08-24 · History
Prime #: 611
Origin domain: Computer Science & Software Engineering
Subdomain: programming language theory → Computer Science & Software Engineering
Aliases: Adt

Core Idea¶

An abstract data type is the structural pattern of specifying a component by its externally observable behaviour while suppressing its internal implementation. The defining commitment is the decoupling of two things that naive description conflates: what the component does — its interface, the operations it supports, the invariants it preserves, the relations between its operations — and how it does it — the data structures, algorithms, and resources it uses internally. The pattern makes the what the contract and renders the how substitutable.

The commitment is sharper than abstraction in general. Plain abstraction is the suppression of detail; the abstract-data-type discipline is the specific move of naming a behavioural specification (signature plus the relations its operations must satisfy), guaranteeing that any implementation honours it, and making any conforming implementation interchangeable from the outside. The contract becomes the load-bearing artefact: clients depend on the contract, implementations satisfy the contract, and the boundary between them is the only place where coupling is permitted. Nothing about a client's correctness is allowed to rest on which conforming implementation is in place.

The pattern is cross-substrate in a strong sense: any system in which a role is specified independently of its occupant exhibits the same structural force. The role-versus-occupant split appears in software (interface, protocol), in legal and political systems (the office versus the office-holder), in organisations (job description versus incumbent), in biology (functional role versus molecular implementation), in mechanism design (the mechanism versus its instantiating institution), and in standards (the specification versus the implementing product).^[1] In each case the structural moves are identical: write the contract, verify that implementations conform, and substitute implementations behind the contract without disturbing anything that depends only on it.

How would you explain it like I'm…

The Remote Control Trick

Think about a TV remote: you press the buttons and the TV does what you want, and you don't need to know any of the wires and chips inside. You only need to know what the buttons do. An Abstract Data Type is like that — you say what something should do from the outside, and hide all the messy inside stuff. As long as the buttons work the same, the insides can change and you won't even notice.

The Vending Machine Promise

An Abstract Data Type is a way of describing something by what it DOES on the outside, while hiding how it works on the inside. Think of a vending machine: you put in money and press a button, and a snack comes out. You don't care about the motors and tracks inside — you only care about the promise: 'press this, get that.' That promise is a contract. As long as a machine keeps the contract, the company can swap out all the inside parts for different ones and you'd never know. The whole point is to split 'what it promises to do' from 'how it pulls it off' so the insides become replaceable.

Contract, Not Contents

An Abstract Data Type is the pattern of specifying a thing by its externally observable behavior while suppressing how it's built inside. It decouples two things that everyday descriptions blur together: what the component does — its interface, the operations it supports, the rules (invariants) it keeps, how its operations relate — and how it does it — the internal data structures, algorithms, and resources. The 'what' becomes the contract; the 'how' becomes swappable. This is sharper than abstraction in general, which just means leaving out detail. Here the specific move is to name a behavioral specification, guarantee that any build honors it, and make any conforming build interchangeable from the outside. The contract is load-bearing: nothing about a user's correctness is allowed to depend on which conforming implementation is plugged in.

An abstract data type is the structural pattern of specifying a component by its externally observable behavior while suppressing its internal implementation. The defining commitment is decoupling two things naive description conflates: what the component does — its interface, the operations it supports, the invariants it preserves, the relations among its operations — and how it does it — the data structures, algorithms, and resources used internally. The pattern makes the what the contract and renders the how substitutable. This is sharper than abstraction in general: plain abstraction is the suppression of detail, whereas the ADT discipline is the specific move of naming a behavioral specification (signature plus the relations its operations must satisfy), guaranteeing that any implementation honors it, and making any conforming implementation interchangeable from the outside. The contract becomes the load-bearing artifact: clients depend on the contract, implementations satisfy it, and that boundary is the only place coupling is permitted — no client's correctness may rest on which conforming implementation is in place. The pattern is strongly cross-substrate: any system where a role is specified independently of its occupant shows the same force — interface vs. protocol in software, office vs. office-holder in politics, job description vs. incumbent in organizations, functional role vs. molecular implementation in biology, specification vs. implementing product in standards. The moves are always identical: write the contract, verify conformance, substitute behind it.

Structural Signature¶

the behavioural contract (the what) — the suppressed implementation (the how) — the boundary at which the two are decoupled — the conformance relation each implementation must satisfy — the client depending only on the contract — the substitutability guarantee that any conforming implementation is interchangeable

The pattern is present when each of the following holds:

A behavioural contract. A component is specified by what it does — its operations, the invariants they preserve, the relations among them — stated in terms a user can depend on.
A suppressed implementation. How the component does it — the internal structures, algorithms, and resources — is deliberately hidden behind the contract.
A decoupling boundary. The contract and the implementation are separated at an explicit line that is the only place coupling is permitted.
A conformance relation. Any implementation must honour the contract; conformance is verifiable (by typing, tests, or audit), and a non-conforming candidate is not a valid occupant.
A contract-only dependence. Clients are permitted to rest their correctness only on the contract, never on implementation details; depending on a leaked detail is a violation of the discipline.
A substitutability guarantee. Two implementations satisfying the same contract are interchangeable from the outside; swapping them leaves contract-only clients unaffected — the substitution diagnostic that locates faults precisely on one side of the boundary.

These compose into a role-versus-occupant split: the contract is the role, the implementation the occupant, and the pattern's payoff — the substitution dividend, independent evolution of internals behind a stable contract — follows from forbidding clients to depend on anything but the role.

What It Is Not¶

Not interface. An interface is the boundary specification — the set of operations exposed. The abstract data type is the fuller discipline of contract plus suppressed implementation plus substitutability guarantee: a behavioural contract (signatures and the invariants/laws they satisfy) with the conformance and interchangeability that make any conforming occupant swappable.
Not information_hiding. Information hiding is the principle of concealing internal decisions; the abstract data type is the structural pattern that puts the principle to work — a named contract clients depend on while the hidden implementation stays substitutable. Hiding is the why; ADT is the structure.
Not modularity. Modularity is the general division of a system into parts with limited interaction; the ADT is the specific role-versus-occupant contract that makes one part's internals substitutable behind a behavioural specification. A module need not expose a substitutability-guaranteeing contract.
Not substitutability alone. The embedding-nearest prime, substitutability, is the consequence — conforming implementations are interchangeable. The ADT is the full apparatus (contract, conformance relation, contract-only dependence) that produces and disciplines that substitutability.
Not black_box_vs_white_box_distinction. That distinction concerns whether internals are visible for inspection; the ADT concerns whether clients may depend on internals — a stronger, prescriptive discipline (contract-only dependence) with a conformance relation and a substitution guarantee, not merely an observability stance.
Common misclassification. Placing an implementation detail in the contract (freezing the internals) or letting a needed guarantee live only in the implementation (so clients cannot depend on it). The tell: for each requirement, must a client rely on it (contract) or is it an internal freedom (implementation)?

Broad Use¶

Software engineering — the origin: behavioural specification of components, information-hiding as the design discipline, and modern interfaces, protocols, and abstract base classes as the implementing mechanisms.
Legal and political systems — the office-versus-officer distinction: an office is specified by powers and duties while the incumbent is interchangeable, and succession is the substitution of an occupant behind a stable contract.^[2]
Organisational design — job descriptions and role specifications separate the role (expected behaviour, deliverables, decision rights) from the incumbent, so the organisation survives individual departures.
Biology — enzyme and receptor functional roles specified by reaction or binding type independent of molecular implementation, with multiple distinct molecules occupying the same functional role.^[3]
Standards and protocols — specifications that state what a conforming implementation must do without prescribing how, leaving implementations interchangeable behind the contract.
Mathematical structures and modular products — algebraic structures defined by axioms on operations, and standardised physical interfaces, where any instance satisfying the specification is interchangeable.^[4]

Clarity¶

Naming the pattern clarifies a load-bearing distinction routinely muddled in system description: between the contract and the implementation. Many disputes about systems — software, organisational, biological, legal — become tractable once the question is reframed as "is this requirement on the contract or on the implementation?" Implementation requirements over-constrain the system; contract requirements specify what must be true while leaving freedom in how to achieve it. Sorting requirements onto the right side of that line is often the whole of the design problem.

The clarification also exposes a substitution diagnostic: if two implementations both satisfy the contract, swapping them should leave clients unaffected. When a swap breaks something, either the swap-target does not actually conform, or the client was depending on implementation details rather than the contract — a violation of the discipline. The same diagnostic applies across substrates: an organisation that cannot replace an incumbent without disruption has been depending on the person rather than the role, just as a program that breaks when a conforming component is swapped has been depending on the implementation rather than the interface. The diagnostic turns a vague worry about coupling into a concrete test — substitute and see what breaks — and locates the fault precisely on one side of the contract boundary.

Manages Complexity¶

The pattern compresses a wide family of role-specification phenomena — software interfaces, legal offices, organisational roles, biological functions, communication protocols, mechanism designs, modular product specifications — into one diagnostic family: behavioural contract separated from substitutable implementation. Cross-cutting design problems — interface design, contract completeness, hidden coupling, leaky abstractions, substitutability violations — become legible as one problem family, which is the compression a prime supplies.

The intervention space compresses to a small set of moves on the contract boundary. Tighten the contract by specifying more invariants. Loosen it by removing over-specification that needlessly constrains implementations. Strengthen enforcement through type checking, conformance tests, or audits that verify implementations actually satisfy the contract. Or refactor implementations behind an unchanged contract, reaping what may be called the substitution dividend: independent evolution of the internals without disturbing clients. Each move acts on the same structural feature — the line between contract and implementation — and the menu is the same whether the component is a data structure, an office, a role, an enzyme, or a standard. The deepest payoff is the substitution dividend itself: because clients depend only on the contract, implementations can be replaced or improved independently, which is what makes large systems — technical, organisational, institutional — evolvable rather than frozen around their current internals.

Abstract Reasoning¶

Recognising the pattern enables reasoning about the contract-versus-implementation split: for any system, identify what is contract (visible to and depended on by clients) and what is implementation (internal, freely substitutable), and notice that many redesign opportunities open when the split is moved — promoting an implementation detail into the contract, or demoting part of the contract into implementation. It enables reasoning about the substitutability guarantee: if two implementations satisfy the same contract, clients depending only on the contract are invariant to the substitution, and this is the same structural guarantee whether the swap is one data structure for another, one office-holder for another, or one enzyme for another.

Two further inferences sharpen real systems. The leaky-abstraction failure mode: implementations often under-specify and over-leak, so clients come to depend on observable side effects — performance, ordering, layout — that are not in the contract, which is structurally the same as an office-holder whose written role does not match what they actually do. And the contract-evolution problem: contracts must change as needs change, and doing so without breaking clients is a structural problem common to interface design, statute amendment, role redefinition, and protocol versioning, with substrate-independent patterns (deprecation, versioning, backward compatibility). Each inference is reached from the structure — a behavioural contract separating clients from substitutable implementations — rather than from any substrate, which is why the pattern is among the most cleanly cross-substrate in the catalogue, its computing vocabulary a local label on a role-occupant split recognised across biology, law, and organisations.

Knowledge Transfer¶

The transfers are substantive and structurally faithful, because the contract-as-coupling, implementation-as-substitutable structure is the same wherever a role is specified apart from its occupant. Specification discipline into object-oriented and service design: the behavioural-contract discipline transferred from its origin into object-oriented programming and from there into all modern interface design, with the substitutability principle a direct restatement; the same discipline transferred again to the architecture level, where network services are contracts that hide their implementations. Office-versus-officer into modern institutions: the rational-legal distinction between an office and its holder transferred into constitutional and corporate design, where succession rules, impeachment, and succession-planning all rely on the role-versus-incumbent split, so the institution persists through changes of occupant.^[2]

The pattern ports further. Enzyme functional roles into pharmacology: the function-versus-mechanism split transferred into drug design, where targets are specified by functional role and candidate molecules are evaluated against the functional contract.^[5] Standards practice across industries: the discipline of conformance to a specification transferred across standards bodies, carrying the same contract-versus-implementation separation. Mechanism specification into protocol design: specifying a mechanism by its function rather than its instantiation transferred into the design of decentralised protocols.^[6] The transferable core, stripped of computing vocabulary, is one sentence: a contract that specifies what a component does, in terms a user depends on, while leaving the internal how-it-does-it interchangeable. That sentence does real work in legal design, organisational role specification, molecular biology, standards practice, mechanism design, modular product design, and abstract algebra. The pattern's vocabulary carries a computing origin, but the underlying role-occupant split is recognised rather than imported in each new substrate, which is why it reads as mixed-structural — a substrate-neutral structure wearing a discipline-specific name.

Examples¶

Formal/abstract¶

The stack as an abstract data type is the textbook worked case and exhibits the contract-versus-implementation split cleanly. The behavioural contract is the operation signature plus the relations the operations must satisfy: push(x) then pop() returns x and restores the prior state; pop on an empty stack is an error; the algebraic law that governs the type is last-in-first-out ordering.^[1] This contract says what a stack does without saying how. The suppressed implementation is the internal representation, and there are several conforming ones: a contiguous array with a top index, or a singly-linked list with the head as the top.^[7] The decoupling boundary is the operation interface — the only place a client touches the type. The conformance relation is verifiable: any candidate implementation must satisfy the LIFO laws, checkable by a test suite that exercises the algebraic relations, and a structure that returned items first-in-first-out is simply not a valid occupant of the stack contract.^[1] The contract-only dependence is the discipline: client code may rely only on the LIFO behaviour, never on whether the internals are an array or a list. The substitutability guarantee is the payoff — swap the array implementation for the linked-list one and every contract-only client is unaffected; this is the substitution diagnostic that locates faults precisely (if a swap breaks a client, either the new implementation does not conform, or the client illegitimately depended on a leaked detail like the array's contiguous memory layout). The intervention the structure enables is the substitution dividend: the internals can be re-optimised (say, to a growable array for cache locality) behind the unchanged contract, with no client disturbed.

Mapped back: The LIFO operation laws are the behavioural contract, the array-or-list choice is the suppressed implementation, the interface is the decoupling boundary, and the swap-without-breaking-clients property is the substitutability guarantee — the abstract-data-type role-versus-occupant split in its origin domain.

Applied/industry¶

A constitutional public office instantiates the identical structure with the office as the contract and the office-holder as the substitutable implementation. The behavioural contract is the office's specification: the powers it may exercise, the duties it must discharge, the decision rights it carries, and the invariants it must preserve — stated in law, independent of any particular person. The suppressed implementation is the incumbent: the specific individual currently occupying the office, with their idiosyncratic style and methods. The decoupling boundary is the office's defined interface to the rest of the system — the formal channels through which it acts. The conformance relation is the eligibility-and-oath structure: a candidate must satisfy the constitutional requirements to occupy the office, an auditable check, and someone who does not meet them is not a valid occupant.^[2] The contract-only dependence is the rule of law: other institutions are entitled to rely only on the office's defined powers and duties, never on the personal characteristics of the incumbent. The substitutability guarantee is what makes the institution survive succession — when the office-holder changes, every institution depending only on the office is unaffected, which is exactly the substitution dividend. The substitution diagnostic is sharp here: an organisation that cannot replace an incumbent without disruption has been depending on the person rather than the role, just as a program breaks when it depended on the implementation rather than the interface — and the cure is to move the leaked dependency back behind the contract (write down the implicit duties the departing person actually performed). The same role-occupant structure governs an enzyme's functional role (specified by the reaction it catalyses, with multiple distinct molecules conforming) and an industry standard (specifying what a conforming product must do without prescribing how, leaving implementations interchangeable).^[3]

Mapped back: The office's powers and duties are the behavioural contract, the incumbent is the suppressed implementation, eligibility is the conformance relation, and surviving succession is the substitutability guarantee — the abstract-data-type discipline in institutional design, where the office is the role and the holder the occupant.

Structural Tensions¶

T1 — Contract versus Implementation (scopal). The whole discipline turns on sorting every requirement onto the right side of one line: contract requirements specify what must be true while leaving freedom in how, and implementation requirements over-constrain. The boundary is that line. The characteristic failure is placing an implementation detail in the contract (freezing the internals) or letting a needed guarantee live only in the implementation (so clients cannot depend on it). Diagnostic: for each requirement, ask whether a client must be able to rely on it (contract) or whether it is an internal freedom (implementation) — mis-sorting is the root design error the prime exists to catch.

T2 — Tight Contract versus Loose Contract (scalar). A contract can be over-specified (tight, needlessly constraining implementations and blocking optimisation) or under-specified (loose, leaving clients unable to do their jobs). The boundary is sufficiency-without-excess. The failure mode is tightening a contract with invariants clients never needed — freezing internals that should have stayed substitutable — or loosening it until conformance no longer guarantees usable behaviour. Diagnostic: does the contract expose exactly the invariants clients depend on, no fewer (under-specified, clients stuck) and no more (over-specified, implementations frozen)? Both directions are failures of the same sufficiency calibration.

T3 — Declared Contract versus Leaked Behaviour (measurement). Implementations under-specify and over-leak, so clients come to depend on observable side effects — performance, ordering, memory layout — that are not in the contract, structurally identical to an office-holder whose written role does not match what they actually do. The boundary is the declared interface versus the observable behaviour. The failure mode is a swap that breaks clients because they depended on a leaked detail the contract never promised. Diagnostic: run the substitution test — swap a conforming implementation; if a client breaks, it depended on a leak, and the leaked dependency must be moved back behind the contract or made explicit in it.

T4 — Stable Contract versus Contract Evolution (temporal). The substitutability dividend depends on a stable contract, yet contracts must change as needs change, and doing so without breaking clients is the recurring evolution problem (deprecation, versioning, backward compatibility). The boundary is the tension between stability and change. The failure mode is evolving a contract as if it were stable — breaking every client that depended on the old guarantees — or freezing it permanently to preserve clients and blocking all adaptation. Diagnostic: is there a versioning and deprecation discipline that lets the contract change while existing clients keep working? Without one, evolution and the substitutability guarantee are in direct conflict.

T5 — Verified Conformance versus Assumed Conformance (measurement). The substitutability guarantee holds only for implementations that actually satisfy the contract, and conformance must be verified (typing, tests, audit), not assumed. The boundary is the strength of enforcement. The failure mode is treating a candidate as a valid occupant because it superficially fits the signature, when it violates an invariant the contract requires — a structure that returns items out of order is not a valid stack however much it resembles one. Diagnostic: is conformance checked against the contract's invariants, or merely against its surface signature? Unverified conformance silently breaks the substitution guarantee.

T6 — Substitution Dividend versus Coupling Cost (coupling). Forbidding clients to depend on anything but the contract yields the substitution dividend — independent evolution of internals — but enforcing that boundary has a cost: every cross-boundary interaction must route through the contract, which can be less efficient or expressive than direct coupling. The boundary is where decoupling pays. The failure mode is imposing the full ADT discipline where the components never needed to vary independently, paying the indirection cost for a substitutability never exercised. Diagnostic: will the implementation actually be substituted or evolved behind this contract? If not, the decoupling overhead buys a dividend that is never collected.

Structural–Framed Character¶

Abstract Data Type sits on the structural side of the structural–framed spectrum, at the mixed-structural mark — aggregate 0.3. The pattern underneath is a role-versus-occupant split: a behavioural contract, a suppressed implementation, a conformance relation, contract-only dependence, and a substitutability guarantee. That split is substance-blind by construction, and the prime is among the cleanest cross-substrate patterns in the catalogue precisely because none of its machinery inspects the inside of an object — which is what holds the aggregate near the structural end.

Two diagnostics read fully structural. Evaluative_weight is 0: the contract-implementation split carries no inherent approval — it is a value-neutral structural arrangement, useful or not depending on whether substitution is actually exercised. Human_practice_bound is 0 because the role-occupant split runs in non-human substrates indifferently: an enzyme's functional role is specified by the reaction it catalyses, with multiple distinct molecules conforming to the same functional contract, no human practice required for the structure to hold. The three residual 0.5 scores record only the computing-origin film. Vocab_travels is 0.5 because the home register — interface, contract, conformance, substitutability — has a programming-language-theory accent (Liskov 1974) that needs light translation into the legal office or biological setting, even though the underlying split is recognised everywhere. Institutional_origin is 0.5 because the named discipline arose in computer science rather than as a pre-existing formal regularity. Import_vs_recognize is 0.5 because invoking it brings a contract-design lens — sort each requirement onto the right side of the boundary, verify conformance — though what it points at is a role-occupant split already present in the system. The substance-blind core and the two zeros keep it firmly structural; the CS vocabulary is the only thing lifting the aggregate off zero, exactly as the mixed-structural 0.3 records.

Substrate Independence¶

Abstract Data Type is a maximally substrate-independent prime — composite 5 / 5 on the substrate-independence scale. The pattern underneath is a role-versus-occupant split — a behavioural contract, a suppressed implementation, a conformance relation, contract-only dependence, and a substitutability guarantee — and it is substance-blind by construction, since none of its machinery inspects the inside of an object. That is why it is recognised rather than translated across software interfaces and protocols, Weberian offices versus office-holders, organisational job-descriptions versus incumbents, biological enzyme and receptor functional roles versus their molecular implementations, standards-versus-products, mechanism-versus-institution, and algebraic structures defined by axioms. The breadth crosses the physical/biological line cleanly — an enzyme's functional role is specified by the reaction it catalyses with multiple distinct molecules conforming to the same contract, no human practice required — which anchors the top composite. The transfer is substantive and structurally faithful: the substitution diagnostic (swap a conforming occupant; if a client breaks, it depended on a leak) is the same move whether the swap is one data structure for another, one office-holder for another, or one enzyme for another. The only non-structural residue is a programming-language-theory accent on the home vocabulary that needs light translation into the legal or biological setting, but the underlying split is recognised everywhere, so every component reads at the ceiling.

Composite substrate independence — 5 / 5
Domain breadth — 5 / 5
Structural abstraction — 5 / 5
Transfer evidence — 5 / 5

Relationships to Other Abstractions¶

Current abstraction Abstract Data Type Prime

Parents (2) — more general patterns this builds on

Abstract Data Type presupposes, typical Information Hiding Prime

Abstract Data Type typically presupposes Information Hiding, whose structure must already obtain for the child mechanism to be meaningful or operational.
Abstract Data Type presupposes Interface Prime

An ADT 'includes the interface but is richer' — a behavioural contract (interface signatures PLUS invariants/laws) with a conformance relation and substitutability guarantee.

Children (5) — more specific cases that build on this

Container (type theory) Domain-specific is a kind of Abstract Data Type

The proposed strict upward parent is prime:abstract_data_type.
Graph Data Type Domain-specific is a kind of Abstract Data Type

A graph data type is an abstract data type specialized to node-edge traversal, mutation, and query contracts over swappable representations.
Object-Oriented Operating System Domain-specific is a kind of Abstract Data Type

The minimal prospective placement is an instantiation of prime:abstract_data_type.

▸ Show 2 more

Hierarchy paths (3) — routes to 2 parentless roots

Abstract Data Type → Information Hiding → Abstraction

Show alternative paths (2)

Neighborhood in Abstraction Space¶

Abstract Data Type sits among the more crowded primes in the catalog (24^th percentile for distinctiveness): several abstractions describe nearly the same structure, so a description that fits it will tend to fit its neighbors too — transporting it usually means disambiguating within this family rather than landing on it exactly.

Family — Interfaces, Contracts & Hidden Implementation (22 primes)

Nearest neighbors

Substitutability — 0.79
Interface — 0.75
Compatibility — 0.73
Observable Surface Becomes Contract — 0.72
Layering — 0.72

Computed from structural-signature embeddings · 2026-09-10

Not to Be Confused With¶

The embedding-nearest prime is substitutability, and the two are so close that the distinction is best framed as apparatus versus consequence. Substitutability is the property that one thing can stand in for another without disturbing the surrounding system — a conforming implementation, an interchangeable part, a replaceable office-holder. The abstract data type is the structural discipline that produces and guarantees that substitutability for a component: a behavioural contract, a verifiable conformance relation, a rule forbidding clients to depend on anything but the contract, and the resulting substitution guarantee. Substitutability names the dividend; the ADT names the whole machine that pays it. The difference matters because substitutability can hold accidentally (two things happen to be interchangeable in a given context) whereas the ADT makes it structural and enforced (any conforming occupant is interchangeable by construction, and the substitution diagnostic locates faults precisely on one side of the contract boundary). One can have substitutability without the ADT discipline (lucky interchangeability that breaks when context shifts), and the ADT exists precisely to convert that luck into a guarantee. Treating them as identical loses the contract-and-conformance apparatus that is the prime's actual content.

A second genuine confusion is with interface, its other near-neighbour. An interface is the boundary specification — the set of operations, signatures, and types a component exposes. The ADT includes the interface but is richer in two ways. First, its contract is behavioural, not merely syntactic: it specifies the invariants and algebraic laws the operations must satisfy (a stack's LIFO ordering, not just push and pop signatures), and conformance means honouring those laws, so a structure with the right signatures but wrong behaviour is not a valid occupant. Second, the ADT carries the substitutability guarantee and the contract-only-dependence rule as part of the discipline — the interface is the surface, the ADT is the surface plus the conformance relation plus the prohibition on depending past it. A leaky abstraction — clients depending on observable side effects (performance, ordering) the interface never promised — is precisely the failure of the ADT discipline even when the interface signature is honoured, which shows the two are not the same: the interface can be satisfied while the ADT discipline is violated.

A third worth drawing is against information_hiding. Information hiding is a design principle — conceal the decisions most likely to change so that change stays local. The ADT is the structural pattern that operationalises the principle into a role-versus-occupant split with a published contract and a substitution guarantee. Information hiding tells you why to conceal the implementation (to localise change); the ADT tells you how the concealment is structured so that conforming implementations are interchangeable behind a stable contract. One can hide information without the full ADT apparatus (encapsulating internals without a behavioural contract or a conformance check), and the ADT is what turns the hiding into a substitutability dividend. The principle is the motivation; the prime is the mechanism.

For a practitioner the distinctions clarify what is actually being relied on. Confusing the ADT with bare substitutability lets accidental interchangeability pass for a guarantee until context shifts and it breaks; confusing it with interface lets clients depend on leaked behaviour the syntactic surface never promised; and confusing it with information_hiding keeps the motivation while dropping the contract-and-conformance mechanism that makes substitution safe. Asking "is there a behavioural contract, a verified conformance relation, and a rule that clients depend on nothing else?" is what distinguishes the full ADT discipline from its lighter neighbours.

Solution Archetypes¶

Solution archetypes in the catalog that build on this prime — directly (this prime is a source ingredient) or as a related prime.

Built directly on this prime (3)

Also a related prime in 4 archetypes

Behavior-Preserving Refactoring: Improve the inside without changing what the outside can validly observe or rely on.
Organization–Artifact Topology Alignment: When the structure of a produced artifact is likely to mirror the collective that built it, map both topologies and redesign either the artifact boundaries, the team boundaries, or the communication paths instead of letting the mirror form accidentally.
Request–Response Capability Provisioning: Make a scarce or specialized capability addressable as a service that many independent clients can request and receive responses from under explicit capacity and failure rules.
Specification-to-Execution Lowering: Lower a what-level specification into an executable how through explicit refinement stages, carrying forward the contract, assumptions, invariants, evidence obligations, and trace needed to justify that the result actually realizes the intent.

References¶

[1] Liskov, Barbara, and Stephen Zilles. "Programming with Abstract Data Types". In Proceedings of the ACM SIGPLAN Symposium on Very High Level Languages, 50–59. New York: ACM, 1974. Foundational statement of the abstract data type: a component specified by the behaviour of its operations while the implementation is hidden and substitutable, illustrated with stack-like examples; states the conformance/abstraction-function idea that any implementation must honour the specified behaviour. registry ↩a ↩b ↩c

[2] Weber, Max. Wirtschaft und Gesellschaft (Economy and Society). Tübingen: Mohr, 1922 (Eng. trans. Roth and Wittich, University of California Press, 1978). States the rational-legal distinction between an office — defined by impersonal powers and duties, with obedience owed to the impersonal legal order — and its interchangeable office-holder, the basis for succession as substitution of an occupant behind a stable role, with eligibility/appointment as the conformance condition. registry ↩a ↩b ↩c

[3] Galperin, Michael Y., D. Roland Walker, and Eugene V. Koonin. "Analogous Enzymes: Independent Inventions in Enzyme Evolution". Genome Research 8, no. 8 (1998): 779–790. Documents non-homologous (analogous) enzymes — structurally distinct molecules with different folds that independently occupy the same catalytic functional role (same EC number), the biological case of multiple implementations conforming to one functional contract. registry ↩a ↩b

[4] van der Waerden, B. L. Moderne Algebra. Berlin: Springer, 1930. Canonical exposition of the axiomatic method in which algebraic structures (groups, rings, fields) are defined by axioms on their operations, so any instance satisfying the axioms is interchangeable behind the same specification. registry ↩

[5] Drews, Jürgen. "Drug Discovery: A Historical Perspective". Science 287, no. 5460 (2000): 1960–1964. Describes the shift to target-based drug discovery, in which a drug target is specified by its functional/molecular role and candidate molecules are evaluated against that functional specification. registry ↩

[6] Maskin, Eric, and Tomas Sjöström. "Implementation Theory". In Handbook of Social Choice and Welfare, vol. 1, edited by K. J. Arrow, A. K. Sen, and K. Suzumura, 237–288. Amsterdam: Elsevier, 2002. Canonical statement of mechanism design / implementation theory: a desired social-choice goal is specified as a function (the what) and then implemented by some mechanism (the how), so the mechanism is specified by its function independent of any particular instantiating institution. registry ↩

[7] Knuth, Donald E. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Reading, MA: Addison-Wesley, 1968. Standard reference presenting both sequential (array) and linked-list (linked-allocation) implementations of stacks as interchangeable representations of the same abstract stack operations. registry ↩