List of abstractions (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.

General programming abstractions and their usage

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).

Common data structures and their usage

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.

Functional programming abstractions and their usage

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.

Concurrency models and related concepts

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.

Design patterns and their descriptions

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.

Programming paradigms and their key characteristics

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.

Software engineering abstractions and concepts

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.

References

Textbook reference:

• Keller, Robert M. Computer Science: Abstraction to Implementation. Harvey Mudd College, September 2001.