 | This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "List of abstractions" computer science – news · newspapers · books · scholar · JSTOR (May 2024) |
| Computer science |
|---|
 |
Abstractions are fundamental building blocks of computer science, enabling complex systems and ideas to be simplified into more manageable and relatable concepts.
General Programming Abstractions
General programming abstractions are foundational concepts that underlie virtually all of the programming tasks that software developers engage in. By providing a layer of separation from the specifics of the underlying hardware and system details, these abstractions allow for the creation of complex logic in a more approachable and manageable form. They emerge as a consensus on best practices for expressing and solving programming problems in efficient and logically sound ways. From the simplicity of a variable to the structured flow of control structures, these abstractions are the building blocks that constitute high-level programming languages and give rise to detailed software implementations.
| Abstraction | Definition | Usage |
|---|---|---|
| Variable | A storage location paired with an associated symbolic name that contains some known or unknown quantity of information referred to as a value. | Typically used in all programming paradigms. |
| Function | An abstraction representing a set of instructions that can be applied to input data to produce output. | Central to procedural and functional programming; present in all programming paradigms. |
| Algorithm | A step-by-step procedure or formula for solving a problem. | Fundamental for algorithm design and analysis in various domains. |
| Data type | A classification identifying one of various types of data, indicating the possible values for that type, the operations that can be done on that type, and the way the data of that type can be stored. | Present in the majority of programming languages, serving as the foundation for type systems. |
| Control Structure | Constructs that determine the direction of flow of program execution (e.g., if, while, for, switch). | Present in almost all programming languages to control the flow of execution. |
| Subroutine (or Method) | A set of instructions designed to perform a frequently used operation within a program. | Foundational for structuring code in both procedural and object-oriented programming. |
| Class | A blueprint for creating objects, providing initial values for state (member variables or attributes) and implementations of behavior (member functions or methods). | The foundation of class-based object-oriented programming. |
| Interface | A group of related methods with empty bodies, used to define methods that can be applied to different data types. | Widely used in object-oriented programming for abstraction and multiple inheritance. |
| Module | A self-contained component that groups together related variables, functions, classes, or types. | Used to encapsulate code, promoting reusability and maintainability. |
| Recursion | A method where the solution to a problem depends on solutions to smaller instances of the same problem. | A key technique in functional programming and algorithm design. |
| Exception handling | The process of responding to the occurrence, during computation, of exceptions – anomalous or exceptional conditions requiring special processing. | Present in structured programming languages for error handling and control flow management. |
Data Structures
In the context of data structures, the term "abstraction" refers to the way in which a data structure represents and organizes data. Each data structure provides a particular way of organizing data in memory so that it can be accessed and modified according to specific rules. The data structure itself is an abstraction because it hides the details of how the data is stored in memory and provides a set of operations or interfaces for working with the data (e.g., push and pop for a stack, insert and delete for a binary search tree).
| Data Structure | Definition | Usage |
|---|---|---|
| Array | A fixed-size collection of elements of the same data type, accessible by indices. | General-purpose storage and retrieval, basis of many more complex structures. |
| List | An abstract data type that represents a sequence of values, where the same value may occur more than once. | Data order maintenance, implementation of stacks, queues, etc. |
| Stack | A collection that supports a last-in, first-out access pattern. | Function calls/recursive calls, undo mechanisms in applications. |
| Queue | A collection where entities are added at one end ("rear") and removed from the other ("front"). | Sequencing processes, buffering in resource allocation. |
| Tree | A data structure consisting of nodes with a parent-child relationship. | Hierarchical data representation, such as file systems, UI layouts. |
| Binary Tree | A tree where each node has, at most, two children. | Binary Search Trees (BSTs), decision processes, sorting algorithms. |
| Graph | A set of vertices together with a set of edges that connect pairs of vertices. | Network routing, social networks, molecular modeling. |
| Hash Table | A data structure that maps keys to values, using a hash function to compute an index into an array of slots. | Efficient data retrieval, unique item storage, indexing data. |
| Heap | A tree-based data structure that satisfies the heap property; in max-heaps, parent nodes have values greater than or equal to children. | Implementing priority queues, scheduling, sorting algorithms. |
| Priority Queue | An abstract type similar to a regular queue where each element has a priority. | CPU and disk scheduling, managing events in simulations. |
Functional Programming Abstractions
In the world of functional programming, abstraction is not just a tool but a core principle that influences the entire programming model. The abstractions used in functional programming are designed to enhance expressiveness, provide greater modularity, and enable transformative operations that are both concise and predictable. By treating computation as the evaluation of mathematical functions, functional programming moves away from the mutable state and side effects that are typical in imperative programming, presenting a declarative approach to problem-solving.
| Abstraction | Definition | Usage |
|---|---|---|
| Closure | A data structure that captures a function along with its lexical environment. | Enabling functions to be first-class citizens, carrying state along with them. |
| Monad | A design pattern used to encapsulate computation with sequential processing, side effects, or other operational contexts. | Modeling complex behaviors like state, exceptions, or I/O within the purity of functional programming. |
| Immutable data | Data that cannot be modified after it's created. | Ensures predictability and facilitates parallelism in functional programs. |
| Pure function | A function where the return value is determined only by its input values, without side effects. | Core concept for functional programming, allowing for easier reasoning and optimization. |
| Recursion | A method where functions are defined in terms of themselves, used to perform repeated or chained calculations. | Often used in place of iterative loops to solve complex problems. |
| Higher-order function | A function that takes one or more functions as arguments, returns a function as its result, or both. | Commonly used for abstractions like map, reduce, and filter, which are building blocks for manipulating collections. |
| Lambda expression | An anonymous function that provides a simple way to create functions "on the fly" without defining them with a name. | Useful for creating inline operations, especially with higher-order functions. |
| Tail call optimization | An optimization strategy where the last action of a function is a call to the function itself, which can be optimized by the compiler. | Avoids stack overflow in recursive functions, making them as memory-efficient as iterations. |
| Currying | The process of transforming a function that takes multiple arguments into a sequence of functions each with a single argument. | Simplifies the creation of specialized functions from more general ones and enhances function composition. |
| Lazy evaluation | A strategy of delaying the evaluation of an expression until its value is needed. | Can improve performance by not computing unnecessary values, making infinite data structures like streams possible. |
Concurrency Models
Concurrency models are critical abstractions in computer science that facilitate the management of multiple processes or threads executing simultaneously. These models provide the architectural framework needed to handle concurrent operations efficiently and safely in applications ranging from operating systems to high-throughput data processing and network servers. The key challenge they address is the coordination of computational tasks that can potentially interfere with one another, ensuring data integrity and optimizing resource usage without sacrificing performance.
| Model | Key Abstractions | Description |
|---|---|---|
| Threads | Thread, Mutual Exclusion (mutex), Lock, Semaphore | Concurrency within a single process where multiple threads can run code simultaneously and share resources. |
| Actor model | Actor, Message Passing, Mailbox | A mathematical model that treats "actors" as the fundamental units of concurrency, with each actor processing messages asynchronously. |
| Parallel computing | Process, Task, Synchronization, Data Parallelism, Task Parallelism | Performing computations in parallel across multiple processing elements or computers to improve speed. |
| Event-driven programming | Event Loop, Event Handler, Callback, Non-blocking I/O | An approach where program flow is determined by events or changes in state. |
| Coroutines | Coroutine, Yield, Resume | Functions which can be paused and resumed, allowing for cooperative multitasking and simpler async behavior. |
| Asynchronous programming | Future, Promise, Async/Await | A program execution model that facilitates non-blocking operations, often with the use of futures or promises for results that are yet to be computed. |
| Software Transactional Memory (STM) | Atomic transaction, Rollback, STM variable | A strategy that allows for composing sequences of read/write operations that should appear atomic without using locks. |
| Communicating Sequential Processes (CSP) | Process, Channel, Message | A formal language for describing interactions in concurrent systems, focusing on message passing between processes. |
| Lock-free and wait-free algorithms | Non-blocking algorithm, Atomic operation | Algorithms that achieve concurrent operations without traditional locking strategies, avoiding issues like deadlock. |
| Reactive programming | Observable, Observer, Stream, Signal | A programming model designed around data flows and the propagation of changes, often used for developing highly responsive systems with async data streams. |
Design Patterns
Design patterns in computer science represent abstract solutions to common software design problems. While they are not abstractions in the same sense as data structures or mathematical concepts, design patterns provide a high-level language for software developers to communicate and implement solutions in a consistent and recognizable way.
Each design pattern abstracts the complexity of a particular design scenario or problem by providing a tested, proven development paradigm.
| Pattern | Description |
|---|---|
| Singleton pattern | Ensures that a class has only one instance and provides a global point of access to it. |
| Factory method pattern | Defines an interface for creating an object, but defers instantiation to subclasses. |
| Abstract Factory pattern | Provides an interface for creating families of related or dependent objects without specifying their concrete classes. |
| Builder pattern | Allows for the step-by-step construction of complex objects, separating the construction process from its representation. |
| Prototype pattern | Creates new objects by copying an existing object, known as the prototype. |
| Adapter pattern | Allows two incompatible interfaces to work together by converting the interface of one class into an interface expected by the clients. |
| Bridge pattern | Separates an object’s abstraction from its implementation so that the two can vary independently. |
| Composite pattern | Composes objects into tree structures to represent whole-part hierarchies, allowing clients to treat individual objects and compositions uniformly. |
| Decorator pattern | Attaches additional responsibilities to an object dynamically, providing a flexible alternative to subclassing for extending functionality. |
| Facade pattern | Provides a simplified interface to a complex subsystem, making the subsystem easier to use. |
| Flyweight pattern | Minimizes memory usage by sharing as much data as possible with other similar objects. |
| Proxy pattern | Provides a surrogate or placeholder for another object to control access to it. |
| Chain of Responsibility pattern | Passes a request along a chain of handlers, allowing for decoupled systems and dynamic handling. |
| Command pattern | Encapsulates a request as an object, allowing for parameterization of clients with queues, requests, or operations. |
| Interpreter pattern | Implements a specialized language, using classes to represent grammar rules. |
| Iterator pattern | Provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation. |
| Mediator pattern | Defines an object that encapsulates interaction between a set of objects, promoting loose coupling by keeping them from referring to each other explicitly. |
| Memento pattern | Allows for capturing and externalizing an object’s internal state so that it can be restored later, all without violating encapsulation. |
| Observer pattern | Defines a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically. |
| State pattern | Allows an object to change its behavior when its internal state changes. The object will appear to change its class. |
| Strategy pattern | Defines a family of algorithms, encapsulates each one, and makes them interchangeable. Strategy lets the algorithm vary independently from clients that use it. |
| Template Method pattern | Defines the skeleton of an algorithm in an operation, deferring some steps to subclasses. |
| Visitor pattern | Represents an operation to be performed on the elements of an object structure, allowing for a new operation to be defined without changing the classes of the elements. |
Programming Paradigms
Programming paradigms constitute the theoretical frameworks that shape the way software constructs are created and executed. Each paradigm embodies a unique approach to organizing and structuring programming logic, often promoting particular forms of abstraction and compositional structures that align with their underlying principles.
| Paradigm | Key Abstractions | Description |
|---|---|---|
| Procedural programming | Procedure, Function, Subroutine | Based on the concept of procedure calls. It structures code with sequences of statements and reusable subroutines or functions. |
| Object-oriented programming | Class, Object, Inheritance, Polymorphism, Encapsulation | Models the world as interacting objects with associated data and behavior, using classes as blueprints. Encourages encapsulation and reuse. |
| Functional programming | Function, Pure Function, Lambda, Higher-order Function, Recursion | Treats computation as the evaluation of mathematical functions, avoiding changing-state and mutable data. Functions are first-class citizens. |
| Logic programming | Predicate, Fact, Rule, Goal | Uses formal logic to express computations. Algorithms are written as a set of logic statements, and computation is performed through logical deduction. |
| Event-driven programming | Event, Event Handler, Callback | Focuses on the flow of the program being determined by events. Often used for user interfaces, real-time systems, and handling asynchronous I/O. |
| Imperative programming | Variable, Loop, Conditional | Explicitly details the steps a program must take to reach a desired state through statements that change program state. |
| Declarative programming | Expression, Declaration | Describes the desired result or computation without explicitly listing commands or steps that must be performed. |
| Aspect-oriented programming | Aspect, Join Point, Advice, Pointcut | Breaks down program logic into distinct parts (concerns), unrelated to the main object-oriented model, aiming to increase modularity. |
| Concurrent programming | Thread, Concurrent Process, Lock, Synchronization | Manages multiple computations which may be executed in parallel—whether in the same processor, or distributed across a network. |
| Data-driven programming | Data flow, Data schema, Data transformation | Revolves around data structures and designing systems to process large volumes of data, with functions that depend heavily on data inputs. |
Software Engineering Abstractions
Software engineering abstractions are conceptual tools that simplify the complex reality of software systems, enabling developers to focus on high-level problems and manage software complexity. These abstractions are often about hiding the underlying implementation details through encapsulation, defining clear interfaces, and establishing interaction protocols.
| Concept | Description |
|---|---|
| Module | Encapsulates a set of related functions, procedures, or classes, and provides an interface while hiding complexity. |
| Software design pattern | General repeatable solutions to commonly occurring problems in software design, described in templates. |
| Software framework | A robust platform of reusable components or systems that provides particular functionality and is designed to facilitate software development. |
| Middleware | Software that sits between applications or systems software and facilitates communication or data management. |
| Interface | A clearly defined means of communication between different software components, often in the form of functions or protocols. |
| Service | Independently deployable functional units that encapsulate a set of operations and expose functionality through interfaces. |
| Component | Reusable and interchangeable software units that interact to form a functional system, typically exposing interfaces and hiding implementation. |
| API | Specifications for routines, data structures, object classes, and protocols used to communicate between consumer and implementer of the API. |
| Protocol | An agreed-upon format for data exchange between systems, enabling software components to communicate smoothly. |
Notes
References
Textbook reference:
- Keller, Robert M. Computer Science: Abstraction to Implementation. Harvey Mudd College, September 2001.