Community hub
Recent from talks
Contribute something
Nothing was collected or created yet.
Abstract type
View on Wikipedia | This article needs additional citations for verification. (January 2022) |
| Type systems |
|---|
| General concepts |
| Major categories |
|
| Minor categories |
In programming languages, an abstract type (also known as existential types)[1] is a type in a nominative type system that cannot be instantiated directly; by contrast, a concrete type can be instantiated directly. Instantiation of an abstract type can occur only indirectly, via a concrete subtype.
An abstract type may provide no implementation, or an incomplete implementation. In some languages, abstract types with no implementation (rather than an incomplete implementation) are known as protocols, interfaces, signatures, or class types. In class-based object-oriented programming, abstract types are implemented as abstract classes (also known as abstract base classes), and concrete types as concrete classes. In generic programming, the analogous notion is a concept, which similarly specifies syntax and semantics, but does not require a subtype relationship: two unrelated types may satisfy the same concept.
Often, abstract types will have one or more implementations provided separately, for example, in the form of concrete subtypes that can be instantiated. In object-oriented programming, an abstract class may include abstract methods or abstract properties[2] that are shared by its subclasses. Other names for language features that are (or may be) used to implement abstract types include traits, mixins, flavors, roles, or type classes.[citation needed]
Abstract types may also include any number of non-abstract methods and properties, such as when implementing the Template Method Pattern which uses a mixture of invariant methods with fixed implementations and hook methods which can be overridden in concrete subclasses to provide custonised logic.
Creation
[edit]Abstract classes can be created, signified, or simulated in several ways:
- By use of the explicit keyword
abstractin the class definition, as in Java, D or C#. - By including, in the class definition, one or more abstract methods (called pure virtual functions in C++), which the class is declared to accept as part of its protocol, but for which no implementation is provided.
- By inheriting from an abstract type, and not overriding all missing features necessary to complete the class definition. In other words, a child type that does not implement all abstract methods from its parent becomes abstract itself.[2][3]
- In many dynamically typed languages such as Smalltalk, any class that sends a particular method to this, but does not implement that method, can be considered abstract. (However, in many such languages, like Objective-C, the error is not detected until the class is used, and the message returns results in an exception error message such as "Does not recognize selector: xxx" as
- [NSObject doesNotRecognizeSelector:(SEL)selector]is invoked upon detection of an unimplemented method).
Examples
[edit]Java
[edit]By default, all methods in all classes are concrete, unless the abstract keyword is used. An abstract class may include abstract methods, which have no implementation. By default, all methods in all interfaces are abstract, unless the default keyword is used. The default keyword can be used to specify a concrete method in an interface.
//By default, all methods in all classes are concrete, unless the abstract keyword is used.
public abstract class Demo {
// An abstract class may include abstract methods, which have no implementation.
public abstract int sum(int x, int y);
// An abstract class may also include concrete methods.
public int product(int x, int y) {
return x * y;
}
}
//By default, all methods in all interfaces are abstract, unless the default keyword is used.
interface DemoInterface {
int getLength(); //The abstract keyword can be used here, though is completely useless
//The default keyword can be used in this context to specify a concrete method in an interface
default int product(int x, int y) {
return x * y;
}
}
Usage
[edit]Abstract types are an important feature in statically typed OOP languages. Many dynamically typed languages have no equivalent feature (although the use of duck typing makes abstract types unnecessary); however traits are found in some modern dynamically-typed languages.[citation needed]
Some authors argue that classes should be leaf classes (have no subtypes), or else be abstract.[4][5]
Abstract types are useful in that they can be used to define and enforce a protocol; a set of operations that all objects implementing the protocol must support.[citation needed]
Abstract types are also an essential part of the template method pattern.
See also
[edit]
References
[edit]- ^ Mitchell, John C.; Plotkin, Gordon D.; Abstract Types Have Existential Type, ACM Transactions on Programming Languages and Systems, Vol. 10, No. 3, July 1988, pp. 470–502
- ^ a b "Abstract Methods and Classes (The Java Tutorials > Learning the Java Language > Interfaces and Inheritance)". Oracle.com. Retrieved 2019-08-14.
- ^ "Pure Virtual Functions and Abstract Classes in C++". GeeksforGeeks.org. 15 July 2014.
- ^ Riel, Arthur (1996). Object-Oriented Design Heuristics. Addison-Wesley Professional. p. 89. ISBN 0-201-63385-X.
- ^ Meyers, Scott (1996). More Effective C++. Addison-Wesley Professional. p. 258. ISBN 0-201-63371-X.
Make non-leaf classes abstract
Further reading
[edit]- Head First Java. O'Reilly Media. 2003. pp. 688. ISBN 0-596-00920-8.
- Core Java: An Integrated Approach by R. Nageswara Rao
External links
[edit]- "Abstract or Skeletal Interfaces Explained" [1]
- Types and Programming Languages by Benjamin Pierce (MIT Press 2002) [2]
- Abstract type at Rosetta Code
Abstract type
View on Grokipediaabstype keyword and object-oriented systems through abstract classes, leverage it to enforce disciplined programming practices.[2] Subsequent work has extended the model to open existential types, accommodating dynamic extension of type interfaces while preserving abstraction guarantees.[4]
Fundamentals
Definition
An abstract data type (ADT), also known as an abstract type, is a mathematical model for a data type where the type is defined solely by its behavioral semantics and a set of operations, without reference to any specific internal representation or implementation details.[5] This approach treats the data type as a black box, specifying what the type can do from the perspective of its users, rather than how it achieves those behaviors.[6] The core components of an ADT include a domain of possible values, which forms the set of objects that the type can represent, and a collection of operations defined over that domain.[6] These operations typically encompass constructors to create values, queries to inspect them without modification, and modifiers to alter them, with each operation's behavior governed by axioms, preconditions, or postconditions that ensure consistent and predictable results.[6] For instance, the axioms might specify equations relating operations, such as the effect of applying a modifier followed by a query returning a particular value.[6] In contrast to concrete types, such as built-in primitives like integers whose representations are directly accessible and fixed by the language, ADTs deliberately hide their internal structure to enforce separation between interface and implementation.[5] This encapsulation promotes modularity by allowing the internal details to change without affecting dependent code, thereby enhancing reusability across different programs or contexts.[5] The primary motivation for ADTs lies in abstraction as a mechanism to manage the inherent complexity of large-scale program design, enabling developers to decompose problems into manageable units focused on functionality rather than low-level details.[7] By defining types through their observable behaviors, ADTs facilitate clearer reasoning about program correctness and maintainability.[7]Key Characteristics
Abstract types, also known as abstract data types (ADTs), are distinguished by their emphasis on information hiding, which encapsulates the internal representation of data within a module while exposing only a well-defined interface of operations to clients.[8] This encapsulation allows implementers to modify the underlying structure—such as changing from an array-based to a linked-list representation—without affecting client code that relies solely on the interface.[9] For instance, in a stack ADT, clients interact via push and pop operations without accessing the internal storage mechanism, promoting modularity and maintainability.[10] A core property of abstract types is the maintenance of invariants, which are logical constraints that must hold true for every valid instance of the type across its entire lifecycle, including after every operation.[11] These invariants ensure the type's behavioral consistency; for example, in a bounded stack, an invariant might stipulate that the current size never exceeds the maximum capacity, a property established by the constructor and preserved by mutator operations like push.[12] Invariants are typically not directly enforceable by language mechanisms but are assumed to be upheld by the implementation, providing a foundation for reasoning about the type's reliability.[8] Representation independence refers to the guarantee that all operations on an abstract type preserve its abstract properties, irrespective of changes to the concrete representation.[10] This property enables multiple valid implementations of the same abstract type, such as a queue realized via a circular array or a linked list, both of which must adhere to the same behavioral semantics like first-in-first-out ordering.[8] As articulated in early foundational work, this invariance supports the abstraction's independence from implementation details, allowing evolution of the type without breaking existing uses.[9] Abstract types operate at distinct levels of abstraction: the abstract view focuses on the intended behavior and observable effects of operations, while the representational view concerns the specific data structures and algorithms used internally.[12] This separation, often formalized through specifications, ensures that clients reason only about the behavioral model—such as the commutative property of set union—without needing knowledge of representational choices like hash tables or trees.[11] Such layering facilitates verification and reuse, as the abstract level defines the "what" independently of the "how."[10] To ensure reliable behavior, abstract types employ preconditions and postconditions as part of their operational specifications, which delineate valid inputs and guaranteed outputs for each operation.[8] A precondition specifies requirements that must be met before an operation executes, such as a non-empty stack for a pop operation, while a postcondition describes the state after execution, like the removal of the top element without altering the rest of the stack.[11] These contracts enable error handling by allowing clients to check preconditions explicitly and implementers to assume their validity, thereby preventing undefined behaviors and facilitating debugging through assertion mechanisms.[12] In practice, violations of preconditions might raise exceptions, reinforcing the type's robustness.[10]Historical Context
Origins in Computer Science
The concept of abstract types, also known as abstract data types (ADTs), emerged in the late 1960s and early 1970s as part of efforts to enhance program modularity and reliability amid growing software complexity. Early work emphasized data abstraction as a fundamental principle alongside sequencing, conditionality, and iteration in program design, with Edsger Dijkstra highlighting its role in structured programming to separate concerns and manage intricate systems.[13] Concurrently, the ALGOL 68 team introduced mechanisms like modes, allowing programmers to define custom data types and localize their representations, marking one of the first language supports for user-defined abstractions beyond built-in primitives.[13] This development was deeply influenced by the limitations of procedural and structured programming paradigms prevalent in the era, which excelled at control flow but struggled with encapsulating complex data manipulations, often leading to tightly coupled code and maintenance challenges. Abstract types addressed these shortcomings by providing a way to specify data behaviors and operations independently of their internal implementations, promoting reusability and verification.[13] A seminal contribution came in 1974 with the paper "Programming with Abstract Data Types" by Barbara Liskov and Stephen Zilles, which formalized ADTs in the design of the CLU programming language at MIT, framing them as clusters of operations on object classes to support reliable, high-level programming.[14] Initial applications of abstract types appeared in the 1970s within system software, particularly for abstracting file operations in early database systems, where they enabled logical data views decoupled from physical storage details.[15] In compiler design, ADTs were employed to model symbol tables, encapsulating lookup and insertion operations for identifiers in block-structured languages without exposing representational choices like hash tables or trees.[16] These uses demonstrated how abstract types facilitated modular construction of complex tools, influencing subsequent language and system developments.Evolution and Standardization
In the 1980s, abstract types gained prominence through their integration into object-oriented programming paradigms, particularly in languages like Smalltalk and C++, where they facilitated polymorphism and encapsulation of data behaviors independent of implementation details. Smalltalk-80, released in 1980, advanced this by treating all values as objects with abstract interfaces, enabling polymorphic method dispatch that hid internal representations.[17] Similarly, C++ evolved from "C with Classes," developed starting in 1979 and renamed in 1983, to support abstract classes and virtual functions by the mid-1980s, allowing developers to define interfaces for abstract types that multiple concrete classes could implement, thus promoting reusable and extensible designs.[18] A key theoretical advancement came in 1985 with the paper "Abstract Types Have Existential Type" by John C. Mitchell and Gordon D. Plotkin, which provided a formal model for abstract types using existential quantification in second-order lambda calculus, influencing the design of type systems in languages like ML and Ada.[2] Standardization efforts in the 1980s further solidified abstract types in formal language specifications, with Ada's 1983 ANSI standard (later adopted as ISO 8652 in 1987) introducing packages as a mechanism for encapsulating abstract data types, including private types that concealed representations while exposing operations. This approach influenced subsequent standards and design practices, notably contributing to the conceptualization of abstract factory and template method patterns in object-oriented design, which rely on abstract types for flexible system architectures. By the early 1990s, these ideas permeated ISO standards for other languages, emphasizing modularity and type safety in large-scale software development.[19][20] The 1990s and 2000s saw abstract types expand beyond imperative paradigms into functional languages and data interchange standards, enhancing modularity in diverse contexts. In Standard ML, the module system formalized in the 1997 revision (SML'97) used signatures to define abstract types within functors, allowing parametric abstraction and hiding of implementations to support reusable components in functional programming.[21] Concurrently, the W3C's XML Schema 1.0 standard, published in 2001, incorporated abstract types through complexType definitions with abstract attributes, enabling schema authors to specify extensible data structures for reliable information exchange in web services and documents. These developments broadened abstract types' role in ensuring interoperability across heterogeneous systems.[22] As of November 2025, abstract types continue to evolve in modern type systems, with Rust's traits providing compile-time abstraction for behavior specification, integrated with Send and Sync markers to enforce memory safety and concurrency guarantees without runtime overhead.[23] TypeScript's interfaces, enhanced in versions 5.0 through 5.9 (2023–2025), offer structural typing for abstract contracts in JavaScript ecosystems, supporting advanced features like mapped types and inference for scalable, type-safe web applications.[24] These trends underscore abstract types' adaptation to contemporary demands for secure, performant software in concurrent and distributed environments.Formal Specification
Algebraic Specification
Algebraic specification defines abstract data types through a mathematical framework that separates syntax from semantics, enabling precise, implementation-independent descriptions. The syntax is captured by a signature, which specifies the sorts (carrier sets representing types), operations, and their arities. For instance, sorts denote the domains such as integers or stacks, while operations are functions with input and output sorts; a signature might include sorts like Stack and Element, with operations such as push: Stack × Element → Stack and pop: Stack → Stack.[25][26] The semantics are provided by axioms, which are equational statements defining the behavior of operations through equalities that must hold for all instances of the abstract data type. These equations form an equational specification, allowing derivations of complex behaviors from basic axioms. A classic example is the stack abstract data type, with sorts Stack and Integer, and operations new: → Stack, push: Stack × Integer → Stack, pop: Stack → Stack, and top: Stack → Integer. The key axioms are: These enable derivations, for nested pushes like top(pop(push(push(new(), 1), 2))) = 1: apply pop(push(push(new(), 1), 2)) = push(new(), 1) by the first axiom, followed by top(push(new(), 1)) = 1 by the second axiom.[27][28] Specification languages facilitate the formalization of these algebraic descriptions. OBJ, developed in the 1970s, supports equational rewriting and modular specifications for abstract data types, allowing hierarchical definitions where modules extend base sorts and operations. CASL (Common Algebraic Specification Language), introduced in the 1990s as a standard, provides expressive constructs for sorted signatures, conditional equations, and structured specifications, superseding earlier languages by integrating features like hidden sorts and parameterization for reusable abstract data types.[29][30] Algebraic specifications support formal verification by enabling proofs of correctness through term rewriting systems, where axioms serve as rewrite rules to simplify terms and establish equivalences. This allows semi-automated checking that implementations satisfy the equations, ensuring properties like congruence (operations preserve equalities) without relying on concrete representations. For example, rewriting with stack axioms can prove that repeated push-pop operations yield the initial state, validating behavioral correctness.[6][31]Operational Semantics
Operational semantics for abstract data types (ADTs) provide a formal description of their behavior through the execution steps of an abstract machine, focusing on how operations transform the internal state to produce observable outputs. Unlike denotational semantics, which map syntactic constructs to mathematical domains representing the "meaning" of computations, operational semantics emphasize the dynamic process of state evolution and the mapping of ADT operations to concrete, step-by-step behaviors. This approach is particularly suited for imperative views of ADTs, where mutability and sequential execution are central. State-based models represent ADTs using transition systems or abstract machines, where the state is modeled as a configuration (e.g., a partial algebra or data structure), and operations are defined as transitions between states labeled by inputs and outputs. For instance, a queue ADT can be specified with states as sequences of elements; an enqueue operation transitions from state to upon input , while dequeue transitions from (with ) to and outputs . Such models extend algebraic specifications by introducing dynamic layers of state changes via conditional rules or term rewriting, ensuring well-defined reductions for error-prone operations.[32] Model checkers like SPIN facilitate verification of ADT operations against these specifications by exhaustively exploring state spaces in Promela models, detecting violations such as deadlocks or incorrect transitions in concurrent settings. SPIN supports data abstractions to represent ADT states compactly, allowing proofs of properties like safety and liveness for operations such as queue enqueues and dequeues. For concurrent ADTs, operational semantics address non-determinism by specifying transitions that ensure atomicity, preventing race conditions where interleaved operations lead to inconsistent states. Linearizability provides a key correctness criterion, requiring that concurrent operations appear to take effect instantaneously at some point between invocation and response, consistent with a sequential execution of the ADT's serial specification.[33] This handles races by enforcing that non-atomic implementations (e.g., lock-free queues) preserve the observable behavior of atomic transitions, even under non-deterministic scheduling.[34]Implementation Approaches
In Object-Oriented Languages
In object-oriented languages, abstract data types (ADTs) are commonly implemented using abstract classes and interfaces to define the behavioral contract of the type, specifying operations without revealing or committing to a particular internal representation. Abstract classes provide a blueprint that may include both abstract methods—declarations without implementations—and concrete methods that offer shared functionality for subclasses, allowing partial realization of the ADT while deferring full details to concrete implementations. Interfaces, in contrast, consist solely of abstract method signatures and constants, enforcing a strict contract that multiple classes must fulfill to adhere to the ADT's operations, such as those for a stack (push, pop, isEmpty). This approach enables the separation of the ADT's specification from its implementation, promoting reusability across different concrete classes.[35][36] These constructs facilitate polymorphism, where instances of concrete classes implementing the same abstract class or interface can be substituted interchangeably, treating them uniformly as the ADT type. Central to this is the Liskov Substitution Principle, which states that objects of a subtype must be substitutable for objects of the supertype without altering the program's desirable properties, ensuring that the behavioral expectations of the ADT—such as maintaining state invariants—are preserved across implementations. For instance, a list ADT's operations must behave consistently whether implemented as an array or linked structure, upholding the principle's preconditions, postconditions, and invariants. This polymorphic behavior allows clients to interact with the ADT through its abstract interface, oblivious to the underlying representation.[37][37] Encapsulation in object-oriented implementations of ADTs is enforced through private fields for internal state and access modifiers (such as public, protected, and private) that control visibility, preventing direct manipulation of representation details and exposing only the necessary operations via public methods. By restricting access to the hidden data—often stored in private instance variables—developers ensure that the ADT's integrity is maintained solely through its defined interface, aligning with the principle of information hiding. This mechanism protects the abstraction by allowing internal changes without affecting client code that relies on the public contract.[38] To support flexible instantiation and integration of ADT implementations, design patterns such as the Adapter and Factory are frequently employed. The Adapter pattern wraps an existing class with an incompatible interface to conform to the ADT's contract, enabling legacy or third-party components to serve as valid implementations without modification. Meanwhile, the Factory pattern, including variants like Abstract Factory, provides an interface for creating concrete ADT instances while concealing the specific classes used, allowing clients to obtain objects polymorphically based on context or configuration. These patterns enhance modularity by decoupling ADT usage from concrete details, as outlined in foundational object-oriented design literature.[39][40]In Functional and Other Paradigms
In functional programming languages, abstract data types (ADTs) are often implemented using modules and signatures to encapsulate data representations and operations, promoting modularity and information hiding. In Haskell, for instance, modules define ADTs by exporting type names and associated functions while concealing constructors, allowing users to interact solely through abstract interfaces such as creation, access, and manipulation predicates.[41] Similarly, Standard ML supports abstract types through theabstype declaration, which defines a new type with its operations while hiding the underlying concrete datatype representation, even within the module, to enforce strict abstraction.[42] Type classes further enhance this by providing polymorphic operations over ADTs, enabling generic behaviors like equality or ordering without exposing internal structures, as seen in the definition of classes such as Eq or Ord applied to custom types. This approach ensures that ADTs remain implementation-independent, facilitating reuse and maintenance across programs.
In procedural languages like C, ADTs are realized through function libraries combined with opaque pointers, which hide the underlying structure details from client code. An opaque type is declared as an incomplete struct in public headers (e.g., typedef struct string_mx string_mx;), with full definitions confined to implementation files, forcing interactions via provided functions for allocation, deallocation, and operations.[43] This technique enforces encapsulation, reduces coupling, and minimizes vulnerabilities by preventing direct memory access, as exemplified in libraries like standard I/O with FILE* pointers.[43]
Hybrid paradigms extend ADT concepts beyond pure functional or procedural styles. In logic programming, such as Prolog, functors serve as constructors for compound terms that model ADTs, representing structured data with operations defined via predicates for querying and transformation; in extensions like ALS Prolog, tools such as defStruct can generate accessors to abstract slot manipulations without numeric indexing.[44] Similarly, in concurrent models like Erlang, the actor model—implemented via behaviors such as gen_server—encapsulates state within lightweight processes, exposing ADTs through message-passing interfaces that handle synchronous calls and casts for state updates, ensuring isolation and fault tolerance.[45]
A key emphasis in functional ADTs is immutability, where data structures are treated as unchanging values, and operations return new instances rather than modifying existing ones, achieved through pure functions that avoid side effects and depend solely on inputs.[46] This design eliminates mutable state issues like race conditions, supports referential transparency for easier reasoning and optimization, and aligns with declarative paradigms by composing transformations over persistent data.[46]
Practical Examples
Java Implementation
In Java, abstract types are commonly implemented using interfaces to define the contract of an abstract data type (ADT) and abstract classes to provide partial implementations that enforce invariants across concrete subclasses. A canonical example is the Stack ADT, which follows the last-in-first-out (LIFO) principle, allowing elements to be pushed onto the top and popped from the top. The interface specifies the essential operations without detailing the underlying representation, enabling multiple implementations such as array-based or linked-list-based stacks. The following Java interface defines the Stack ADT, including Javadoc documentation that specifies preconditions and postconditions for each method:import java.util.EmptyStackException;
/**
* A Stack ADT that supports the LIFO principle.
*
* @author Inspired by Goodrich et al. (2014)
* @param <E> the type of elements stored in the stack
*/
public interface Stack<E> {
/**
* Returns the number of elements in the stack.
* Postcondition: Returns the current size of the stack.
*
* @return number of elements in the stack
*/
int size();
/**
* Tests whether the stack is empty.
* Postcondition: Returns true if the stack has no elements.
*
* @return true if the stack is empty, false otherwise
*/
boolean isEmpty();
/**
* Inserts an element at the top of the stack.
* Precondition: The element is not null (if null elements are disallowed).
* Postcondition: The stack size increases by 1, and the element is at the top.
*
* @param e the element to be inserted
*/
void push(E e);
/**
* Removes and returns the element at the top of the stack.
* Precondition: The stack is not empty.
* Postcondition: The stack size decreases by 1, and the top element is removed.
*
* @return element removed from the top of the stack
* @throws EmptyStackException if the stack is empty
*/
E pop();
}
import java.util.EmptyStackException;
/**
* A Stack ADT that supports the LIFO principle.
*
* @author Inspired by Goodrich et al. (2014)
* @param <E> the type of elements stored in the stack
*/
public interface Stack<E> {
/**
* Returns the number of elements in the stack.
* Postcondition: Returns the current size of the stack.
*
* @return number of elements in the stack
*/
int size();
/**
* Tests whether the stack is empty.
* Postcondition: Returns true if the stack has no elements.
*
* @return true if the stack is empty, false otherwise
*/
boolean isEmpty();
/**
* Inserts an element at the top of the stack.
* Precondition: The element is not null (if null elements are disallowed).
* Postcondition: The stack size increases by 1, and the element is at the top.
*
* @param e the element to be inserted
*/
void push(E e);
/**
* Removes and returns the element at the top of the stack.
* Precondition: The stack is not empty.
* Postcondition: The stack size decreases by 1, and the top element is removed.
*
* @return element removed from the top of the stack
* @throws EmptyStackException if the stack is empty
*/
E pop();
}
EmptyStackException for error handling when operations are attempted on an empty stack.
To provide a partial implementation, an abstract class can extend the interface by enforcing the invariant that the size field accurately reflects the number of elements, while leaving storage-specific operations abstract. Subclasses must implement the core push and pop logic but call protected methods to update the size, ensuring consistency. Here's an example abstract class:
import java.util.EmptyStackException;
/**
* Abstract implementation of the Stack interface with size invariant enforcement.
*
* @author Based on principles from Goodrich et al. (2014)
* @param <E> the type of elements stored in the stack
*/
public abstract class AbstractStack<E> implements Stack<E> {
protected int size = 0;
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* Template method for push: subclasses implement storage insertion.
* Precondition: The stack may or may not be empty.
* Postcondition: Element is added to storage; size is incremented.
*
* @param e the element to insert
*/
public void push(E e) {
pushToStorage(e);
size++;
}
/**
* Template method for pop: checks emptiness and delegates to subclass.
* Precondition: The stack is not empty (enforced here).
* Postcondition: Top element is removed from storage; size is decremented.
*
* @return the removed element
* @throws EmptyStackException if the stack is empty
*/
@Override
public E pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
E element = popFromStorage();
size--;
return element;
}
/**
* Subclasses must implement: insert element into the underlying storage.
*
* @param e the element to insert
*/
protected abstract void pushToStorage(E e);
/**
* Subclasses must implement: remove and return the top element from storage.
*
* @return the top element
*/
protected abstract E popFromStorage();
}
import java.util.EmptyStackException;
/**
* Abstract implementation of the Stack interface with size invariant enforcement.
*
* @author Based on principles from Goodrich et al. (2014)
* @param <E> the type of elements stored in the stack
*/
public abstract class AbstractStack<E> implements Stack<E> {
protected int size = 0;
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* Template method for push: subclasses implement storage insertion.
* Precondition: The stack may or may not be empty.
* Postcondition: Element is added to storage; size is incremented.
*
* @param e the element to insert
*/
public void push(E e) {
pushToStorage(e);
size++;
}
/**
* Template method for pop: checks emptiness and delegates to subclass.
* Precondition: The stack is not empty (enforced here).
* Postcondition: Top element is removed from storage; size is decremented.
*
* @return the removed element
* @throws EmptyStackException if the stack is empty
*/
@Override
public E pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
E element = popFromStorage();
size--;
return element;
}
/**
* Subclasses must implement: insert element into the underlying storage.
*
* @param e the element to insert
*/
protected abstract void pushToStorage(E e);
/**
* Subclasses must implement: remove and return the top element from storage.
*
* @return the top element
*/
protected abstract E popFromStorage();
}
pushToStorage and popFromStorage isolate the storage details, adhering to object-oriented principles of abstraction.[47]
To verify the abstraction, unit tests can demonstrate polymorphism by exercising the interface with different concrete implementations, such as an array-based stack and a linked-list-based stack. Using a testing framework like JUnit, the outline might include:
- Create instances:
Stack<String> arrayStack = new ArrayStack<>();andStack<String> linkedStack = new LinkedListStack<>(); - Test push/pop cycles: Push elements, assert non-empty, pop and verify returned values match in LIFO order.
- Test edge cases: Attempt pop on empty stack, confirm
EmptyStackExceptionis thrown; verifyisEmpty()andsize()before/after operations. - Assert equivalence: Both implementations should behave identically under the interface contract, without exposing internal details.
Examples in Other Languages
In Standard ML, theabstype construct directly supports abstract types by hiding the internal representation and exposing only specified operations. A stack ADT can be implemented as follows, using a list internally but concealing it:
abstype 'a stack = stk of 'a [list](/page/List)
with
val emptyStack = stk []
fun isEmpty (stk []) = true
| isEmpty _ = false
fun push (x, stk l) = stk (x :: l)
fun top (stk (h :: _)) = h
| top _ = raise Empty
fun pop (stk (_ :: t)) = stk t
| pop _ = raise Empty
end
abstype 'a stack = stk of 'a [list](/page/List)
with
val emptyStack = stk []
fun isEmpty (stk []) = true
| isEmpty _ = false
fun push (x, stk l) = stk (x :: l)
fun top (stk (h :: _)) = h
| top _ = raise Empty
fun pop (stk (_ :: t)) = stk t
| pop _ = raise Empty
end
template <typename ItemType>
class QueBaseClass {
public:
virtual void Insert(const ItemType& Item) = 0;
virtual void Remove(ItemType& Item) = 0;
virtual bool Empty() const = 0;
virtual ~QueBaseClass() = default;
};
template <typename ItemType>
class QueBaseClass {
public:
virtual void Insert(const ItemType& Item) = 0;
virtual void Remove(ItemType& Item) = 0;
virtual bool Empty() const = 0;
virtual ~QueBaseClass() = default;
};
class Queue q where
empty :: q a
enqueue :: a -> q a -> q a
dequeue :: q a -> Maybe (a, q a)
isEmpty :: q a -> Bool
-- Example instance using lists (inefficient but illustrative)
instance Queue [] where
empty = []
enqueue x q = q ++ [x]
dequeue [] = Nothing
dequeue (x:xs) = Just (x, xs)
isEmpty = null
class Queue q where
empty :: q a
enqueue :: a -> q a -> q a
dequeue :: q a -> Maybe (a, q a)
isEmpty :: q a -> Bool
-- Example instance using lists (inefficient but illustrative)
instance Queue [] where
empty = []
enqueue x q = q ++ [x]
dequeue [] = Nothing
dequeue (x:xs) = Just (x, xs)
isEmpty = null
Monad typeclass, enabling do-notation for sequencing enqueue/dequeue operations, as seen in standard containers like lists for non-deterministic computations.[50][51]
In Python, the abc module facilitates abstract base classes for defining interfaces, with duck typing allowing flexible enforcement at runtime rather than compile time. For a set-like ADT, the collections.abc.Set provides a read-only set interface, which can be extended for mutable sets. An example implementation using a list (though not optimal for sets) is:
from collections.abc import Set
from [typing](/page/Typing) import Any
class ListBasedSet(Set[Any]):
def __init__(self, iterable):
self.elements = []
for x in iterable:
if x not in self.elements:
self.elements.append(x)
def __contains__(self, value: object) -> bool:
return value in self.elements
def __len__(self) -> int:
return len(self.elements)
def __iter__(self):
return iter(self.elements)
# Additional mixin methods like __and__, __or__ are inherited and implemented via containment checks
from collections.abc import Set
from [typing](/page/Typing) import Any
class ListBasedSet(Set[Any]):
def __init__(self, iterable):
self.elements = []
for x in iterable:
if x not in self.elements:
self.elements.append(x)
def __contains__(self, value: object) -> bool:
return value in self.elements
def __len__(self) -> int:
return len(self.elements)
def __iter__(self):
return iter(self.elements)
# Additional mixin methods like __and__, __or__ are inherited and implemented via containment checks
isinstance for compatibility, which relaxes strict typing compared to more rigid systems.[52]
These examples highlight contrasts in type system enforcement of ADT purity: Standard ML's abstype provides compile-time hiding of representation within modules; C++'s static inheritance ensures compile-time adherence to the abstract interface, promoting strong encapsulation; Haskell's typeclasses and purity laws enforce behavioral invariants through compile-time polymorphism and referential transparency, ideal for functional paradigms; Python's ABCs with duck typing offer runtime flexibility, allowing diverse implementations but potentially permitting violations if not checked explicitly. Unlike the Java stack example using interfaces for compile-time enforcement, these approaches adapt to each language's paradigms for varying degrees of abstraction and safety.