 | This article relies largely or entirely on a single source .(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 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. |
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. |
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 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 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 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 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. |
Computer science is the study of computation, information, and automation. Computer science spans theoretical disciplines to applied disciplines.
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program.
Knowledge representation and reasoning is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as diagnosing a medical condition or having a dialog in a natural language. Knowledge representation incorporates findings from psychology about how humans solve problems and represent knowledge, in order to design formalisms that will make complex systems easier to design and build. Knowledge representation and reasoning also incorporates findings from logic to automate various kinds of reasoning.
Procedural programming is a programming paradigm, classified as imperative programming, that involves implementing the behavior of a computer program as procedures that call each other. The resulting program is a series of steps that forms a hierarchy of calls to its constituent procedures.
In software engineering and computer science, abstraction is the process of generalizing concrete details, such as attributes, away from the study of objects and systems to focus attention on details of greater importance. Abstraction is a fundamental concept in computer science and software engineering, especially within the object-oriented programming paradigm. Examples of this include:
In computer science, an abstract machine is a theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is similar to a mathematical function in that it receives inputs and produces outputs based on predefined rules. Abstract machines vary from literal machines in that they are expected to perform correctly and independently of hardware. Abstract machines are "machines" because they allow step-by-step execution of programmes; they are "abstract" because they ignore many aspects of actual (hardware) machines. A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former into the latter. They can be used for purely theoretical reasons as well as models for real-world computer systems. In the theory of computation, abstract machines are often used in thought experiments regarding computability or to analyse the complexity of algorithms. This use of abstract machines is fundamental to the field of computational complexity theory, such as finite state machines, Mealy machines, push-down automata, and Turing machines.
The facade pattern is a software design pattern commonly used in object-oriented programming. Analogous to a façade in architecture, it is an object that serves as a front-facing interface masking more complex underlying or structural code. A facade can:
A data model is an abstract model that organizes elements of data and standardizes how they relate to one another and to the properties of real-world entities. For instance, a data model may specify that the data element representing a car be composed of a number of other elements which, in turn, represent the color and size of the car and define its owner.
Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. One well known subject classification system for computer science is the ACM Computing Classification System devised by the Association for Computing Machinery.
Reconfigurable computing is a computer architecture combining some of the flexibility of software with the high performance of hardware by processing with flexible hardware platforms like field-programmable gate arrays (FPGAs). The principal difference when compared to using ordinary microprocessors is the ability to add custom computational blocks using FPGAs. On the other hand, the main difference from custom hardware, i.e. application-specific integrated circuits (ASICs) is the possibility to adapt the hardware during runtime by "loading" a new circuit on the reconfigurable fabric, thus providing new computational blocks without the need to manufacture and add new chips to the existing system.
A programming paradigm is a relatively high-level way to structure and conceptualize the implementation of a computer program. A programming language can be classified as supporting one or more paradigms.
Software design is the process of conceptualizing how a software system will work before it is implemented or modified. Software design also refers to the direct result of the design process – the concepts of how the software will work which consists of both design documentation and undocumented concepts.
Theoretical computer science is a subfield of computer science and mathematics that focuses on the abstract and mathematical foundations of computation, such as the theory of computation, formal language theory, the lambda calculus and type theory.
In computing, an abstraction layer or abstraction level is a way of hiding the working details of a subsystem. Examples of software models that use layers of abstraction include the OSI model for network protocols, OpenGL, and other graphics libraries, which allow the separation of concerns to facilitate interoperability and platform independence. Another example is Media Transfer Protocol and AWS CDK.
A database abstraction layer is an application programming interface which unifies the communication between a computer application and databases such as SQL Server, IBM Db2, MySQL, PostgreSQL, Oracle or SQLite. Traditionally, all database vendors provide their own interface that is tailored to their products. It is up to the application programmer to implement code for the database interfaces that will be supported by the application. Database abstraction layers reduce the amount of work by providing a consistent API to the developer and hide the database specifics behind this interface as much as possible. There exist many abstraction layers with different interfaces in numerous programming languages. If an application has such a layer built in, it is called database-agnostic.
Decomposition in computer science, also known as factoring, is breaking a complex problem or system into parts that are easier to conceive, understand, program, and maintain.
This is an alphabetical list of articles pertaining specifically to software engineering.
A view model or viewpoints framework in systems engineering, software engineering, and enterprise engineering is a framework which defines a coherent set of views to be used in the construction of a system architecture, software architecture, or enterprise architecture. A view is a representation of the whole system from the perspective of a related set of concerns.
Object-oriented programming (OOP) is a programming paradigm based on the concept of objects, which can contain data and code: data in the form of fields, and code in the form of procedures. In OOP, computer programs are designed by making them out of objects that interact with one another.
This glossary of computer science is a list of definitions of terms and concepts used in computer science, its sub-disciplines, and related fields, including terms relevant to software, data science, and computer programming.
Textbook reference: