apropos

A Computer Science Glossary

Note: this glossary is a work in progress! Entries that are not bolded are not finished, and many more terms may be missing. Proceed with low expectations, or, better yet, don’t proceed at all.


Often [overloaded], often redundant, often contradictory terms abound in the wonderful field of computer science. This glossary is an attempt to collect and subjectively define some.

memory

stack: One of two types of fundamental memory structures. Stack-based memory is quick to access, but cannot be grown. It follows a first-in-last-out (FILO)… Read more on Stack Overflow.

heap: One of two types of fundamental memory structures. Heap-based memory is slow to access, but can be allocated and deallocated on-demand. Read more on Stack Overflow.

static:

  1. Generally: A term broadly meaning “done at compile time”.
  2. In the context of keywords: Typically refers to a value that does not change throughout the lifetime of the program. For example, a static method is a method that does not depend on a class to be initialized in the program, and a static variable (or constant) is an immutable variable that is known at compile time.
  3. In the context of builds: When the code from a library or libraries is copied directly in rather than referenced by the final executable. Benefits of static builds are an avoidance of dependency hell and the production of a standalone binary, downsides are a larger file size and difficulty in providing (security) updates to said libraries.

memory management: Many kinds of memory management exist, from automated [garbage collection] and [reference counting] to compile-time [move semantics] and fully [manual memory management].

garbage collection: A system of memory management where a low-level algorithm or program automatically determines when to free memory (“garbage”) during the runtime of the program. Garbage collectors are typically split into two categories: [tracing garbage collectors] (which often is referred to as simply “garbage collection”), and [reference counting]. These systems are distinguished from other systems of memory management - namely, manual memory management and move semantics - by the latter happening at compile time and subsequently having no [runtime overhead].

tracing garbage collection: A system of memory management where…

reference counting: A system of memory management that provides memory safety by keeping a reference count next to an object’s data. This reference count is updated every time a new reference is made to the object, decremented every time a reference goes out of scope, and checked every time an object would be deallocated. Reference counting is a form of [[garbage collection]]. It is typically distinguished from [[tracing]] (and is in fact a dual of ) by its determinism, generally worse performance, and drastically simpler (when naive) algorithm.

reference cycle: A limitation of reference counting, where memory will never be freed from objects referring to each other under an algorithm without a [[cycle breaker]], [[weak references]], or similar methods of dealing with this. Reference cycles are a major cause of [[memory leaks]] when left unchecked but are technically memory safe. Read more in the Rust book.

cycle breaker:

weak references: A method of dealing with [cyclical references]. Read more on the Vale blog.

generational references: A modification of [[reference counting]] that incurs the reference check when accessing an object. Pioneered by and currently only implemented in Vale, the performance and complexity tradeoffs of this approach versus standard reference counting are unclear. Read more on the Vale blog.

ownership: A memory management system characterized by every piece of memory having a single owner

move semantics: Another name for [[ownership]] systems.

move:

destructors: Code that runs at the end of an object’s [[lifetime]].

lent: A concept in move semantics

lifetimes:

deterministic: Specifically: when the performance of a program is known at compile time. Often used in discussions about memory management, and the

nondeterministic: … Many things can introduce nondeterminism, including but not limited to random number generation, IO (reading/writing to files, network usage)

overhead: Additional memory usage or CPU cycles not present in alternative approaches to a problem. Typically refers to runtime overhead: particularly in the context of [[memory management]], but also can refer to compile times.

pass by value: A system where the parameter of a function is directly copied into the body of the function. These values are then typically immutable. As opposed to [[passing by reference]].

pass by reference: A system where a pointer “reference” to the value of a parameter is copied into the function body. These values then can be mutated. As opposed to [[passing by value]].

scope: global scope local scope

overflow:

underflow:

regions:

syntax

syntax sugar: Any syntax of a programming language that is redundant, but makes the language sweeter to use. An example is Nim’s (x) => (x+1) lamdba syntax: which is equivalent to func (x: int): int = (x+1), but considerably shorter.

uniform function calling syntax: A feature of several programming languages, most notably D and Nim, that treats the object a method is called on as an implicit first parameter. In other words, x.add(y) and add(x, y) are equivalent. This is based on the observation that both forms of syntax serve much the same purpose: and being able to pick one or the other is useful depending on the context. (in particular: x.add(y) allows arbitrary [[function chaining]])

type annotations: Markings in code which denote the [[type]] of variables or functions. In the vast majority of (typed) languages, many of these annotations can be elided (omitted) and instead inferred based on context by the compiled. These typically come directly before the associated identifier, or after following a colon: for example, as in C or Java: int foo = 5; or as in Python, Nim, and most modern languages: foo: int = 5.

signature: the syntax of a function: typically consisting of the function’s name, the parameters’ names, the parameters’ types (if present), and the function’s return type (if present). Certain languages may consider more items to be a part of a function signature, for example [[lifetimes]], or [[effects]]. A typical syntactical example is add(a: int, b: string) -> int

overloading: Where two or more functions share the same name, but a different number or type of parameters. See also: [default parameters] and [[generics]].

default parameters: A language feature that allows the omission of certain parameters when calling a function. When not specified, they are assumed to be their “default” value. A typical syntactical example is inc(num: int, step=1)

s-expressions: In Lisp: the syntax used to describe code and data in most Lisp dialects. They consist of either an atomic (singular) value, or a list of s-expressions separated by spaces and contained within parentheses. In practice, these often take the form (statement parameter parameter...).

m-expressions: In Lisp: an alternative syntax to [[s-expressions]]. Never implemented, they bore a closer resemblance to function calls and signatures in modern languages.

t-expressions: In Lisp: an alternative syntax to [[s-expressions]]. The parentheses in s-expressions are omitted, and instead inferred from whitespace and indentation. Implemented in the Sweet Racket syntax.

metaprogramming

metaprogramming: The act of writing code that operates on other code. This may take a variety of forms: from simple find-and-replace preprocessor [templates], to more powerful [macros], to self-modifying [reflection].

template:

  1. Generally: A language construct that allows simple substitution of code at compile time.
  2. In C++: The implementation of [[generics]].

macro:

  1. In C/C++:: [[templates]] (the first one).
  2. In pretty much every language other than C: A language construct that allows operation on an [abstract syntax tree] representing the program.

reflection: The inspection and modification of a program’s own code, typically but not necessarily at compile-time. Often used in languages lacking strong metaprogramming capabilities, such as Java or Go.

abstract syntax tree: A tree-like representation of source code. Useful for metaprogramming, and usually generated as an intermediate step of compilation.

hygienic macros:

programming paradigm:

inductive programming:

differentiable programming:

imperative programming: A programming style where a program is built from a series of step-by-step statements.

procedural programming: A programming style where a program is built from a number of functions (procedures).

declarative programming:

object-oriented programming

object-oriented programming: A programming paradigm characterized by the use of [classes]. Popularized by C++ and Java, object-oriented programming has been praised as decreasing codebase complexity by making code easier to reason about and criticized as increasing codebase complexity by making code harder to reason about.

class: In object-oriented programming: a way to associate variables/state with functions. These classes and [instances] of classes (known as “[objects]”) are the defining feature of [[object-oriented programming]].

object:

  1. Generally: a variable containing a set of values.
  2. In object-oriented programming: an instance of a class.

instance: In object-oriented programming: A [class] that has had its variables initialized with values. Instances can be assigned to variables and kept around, or immediately discarded after [construction]. Url(scheme: "https", ...)

construction: In object-oriented programming: The act of initializing an object / creating an instance of a class. Generally looks like Url(scheme: "https", ...)

method:

  1. In object-oriented programming: a function defined as part of a class, and subsequently attached to an object.
  2. Elsewhere: Occasionally used as a synonym for a [function].

member variable: In object-oriented programming: a variable defined as part of a class, and subsequently constructed as an object.

override: In object-oriented programming: The act of re-implementing a method that has already been defined by a previous class being extended. See also: [implementation].

implementation:

  1. A general term.
  2. In object-oriented programming: The act of writing the body of the function of a method that has only had its [[type signature]] defined (in an [abstract class] or an [interface]).

inheritance: The act of defining classes that inherit all the associated member variables and methods of the parent class. These variables and functions can then be [overridden] or added to, but typically not removed. This is also referred to as extending a class.

interface: Also known as protocols, interfaces are a language construct that

polymorphism:

ad hoc polymorphism:

parametric polymorphism:

prototype:

abstract class: A class that leaves some methods unimplemented by only providing their [signature]. In order to construct a typical [class], all of these methods must be [implemented].

getters: A [Design Pattern] (TM) in which variables of a class are made private (only accessible within the class) and separate methods, typically named getVariable, are created to provide access.

setters: A [Design Pattern] (TM) in which variables of a class are made private (only accessible within the class) and separate methods, typically named setState, are created to set individual or groups of variables. Purported to create a consistent place for logic related to the change of state, in practice a common source of [boilerplate] and repetitive code.

design patterns: General reusable solutions to frequent problems posed by the inadequacy of features in (Java) certain (Java) languages (it’s Java). The term comes from the book Design Patterns: Elements of Reusable Object-Oriented Software by the aptly-nicknamed “Gang of Four”.

boilerplate: Repetitive or highly verbose code. Typically found in [[object-oriented]] and Go codebases. Has an interesting etymology.

casting: Unsafe type coersion. A cast from X to Y tells the language “interpret the data at this memory address as Y regardless of it actually being of type X”.

state:

actor:

event:

functional programming

functional programming: A programming paradigm characterized by the avoidance of state (variables, objects, and side effects) through the chaining of pure functions. Has roots in pure mathematics and the lambda calculus, and is particularly useful for the formal verification of programs.

function:

  1. In mathematics: A relation where each element of the domain is assigned to exactly one element of the codomain. In other words, every input has exactly one output. See also: the Wikipedia article on bijection, injection, and surjection.
  2. In functional programming: A [procedure] guaranteed to not have [[side effects]].
  3. Elsewhere: The more commonly used name for a [procedure].

procedure: In functional languages, the [function] keyword is often reserved for functions that are guaranteed to not have side effects, and thus “procedure” refers to those routines that may have side effects. Typically, however, procedures are referred to as “functions”.

lambda: A function that is created without a name. These are often used as parameters to other functions, for example, in the map function, which takes a list and a function, and applies that function to every element of the list. The term “lambda” itself comes from Alonso Church’s lambda calculus, which is widely recognized as one of the foundations of computing as a science. list.map(func (x) = x+1)

anonymous function: Another name for a [lambda].

monad: a language construct that wraps a value by mapping together operations.

monoid:

morphism: In category theory: an abstract “arrow” between objects.

curry:

functor:

closure:

context:

environment:

lambda calculus:

turing machine:

model of computation: … Other models of computation have arisen since, such as the SKI combinator calculus, or the Iota, Jot, and Zot languages. Read more on Wikipedia.

side effect:

total function: A function that always terminates and returns a value for all possible inputs (of the appropriate type). Total functions have no side effects

partial function: … i.e. integer division

eager evaluation:

lazy evaluation:

type systems

type: A fundamental concept of computer science, types come about from the realization that values can be classified by their features, and lumped into neat groups.

term: A value that inhibits a type.

kind: A higher-level abstraction useful for reasoning about types: like a type of types. Useful when…

universe:

type system: A fundamental feature of every programming language to some extent. Type systems allow for the formalization of restrictions of operations on values

, much research has been made into them.

Type systems provide a way to express constraints on code, act as a form of self-documentation, safety…

typeclass: A method of defining types based on constraints that can be ensured at compile time. Introduced and pioneered by Haskell,

trait: A language…

concept: In C++ and Nim: An equivalent structure to a [typeclass]. These differ slightly in semantics from Haskell-style typeclasses by

generic: In strongly typed languages: a way to pass a parameter to a function without knowing its type. Depending on the function, there could be code that is valid for several different types, or type-dependent code could be split up with if statements. func add[T]()

T: a commonly used name for a placeholder type in function signatures, i.e. with generics.

openarray: In Nim: A [generic] type that unifies arrays, dynamic arrays, strings, and … into one iterable type. Being generic, it can only be used in parameters.

type safety:

statically typed: A type system where [type safety] is verified at compile-time. Some parts of type systems - like [[ranges]] - are difficult to enforce at compile time, so many languages also include a runtime type checker, to some extent.

dynamically typed: A type system where [type safety] is verified at runtime. This can lead to bugs not caught until every part of a program has been run.

strongly typed: A type system that disallows implicit type conversion. See also: [weak typing].

weakly typed: A language in which implicit type conversions can be made. For example, a string and an integer could be added together, in which case the integer is implicitly converted to a string. (In)famously weakly-typed languages include JavaScript and C.

duck typed: A type system characterized by types being defined by their properties ([methods], mostly) rather than having been explicitly declared as that type. Python, Ruby, and to a lesser extent Rust (as an interpretation of [traits]) can be considered duck-typed. If it walks like a duck…

generic associated types:

  1. In Haskell:
  2. In Rust:

const generics: In Rust: limited dependent types. being generic over constant values, a limited form of dependent types.

refinement types:

dependent types:

sized types:

linear types:

type inference: A feature of many typed programming languages that lets the programmer elide types in certain situations. Those types may then be accurately inferred from context by the compiler, through [[Hindley-Milner]] or [[bidirectional]] type checking.

bidirectional type checking:

hindley-milner type inference:

subtyping:

structural type system:

nominal type system:

data

bit: A single binary unit of information. 0 or 1.

byte: The smallest addressable size of memory on a computer. Near-universally 8 bits, but may be arbitrarily sized.

nibble: Also nybble, half a [[byte]].

word: Two [[bytes]].

primitive type:

character: A primitive type that represents a character in the ASCII encoding set. Under the hood, chars are typically represented by the integers 0-127, and implemented as a byte. Also known as a char.

boolean: A primitive type that represents a value that is either true or false. Under the hood, bools are typically implemented as integers (C, others) or enumerations (Rust, others).

integer: A primitive type representing a whole number (an integer). Languages frequently distinguish between signed and unsigned integers: signed integers take an extra bit of space to store their sign, via [[two’s complement]] or otherwise.

float: A primitive type representing a decimal (“floating point”) number. These are almost always approximate, due to low-level limitations: which can lead to unexpected rounding errors. They are rigorously defined to represent a subset of the reals by the IEEE 754 standard.

double: A term for a “double-precision float”. Floats historically are 32-bits in length, while doubles are typically 64.

array: An indexed collection of values. These values are traditionally zero-indexed and accessible with square brackets (array[2]), but may also be 1 or n-indexed. Memory limitations mean arrays are more often than not fixed-length, with their elements all of the same type (or at least of the same size). While “array” can refer to the abstract notion of an indexable array, the term is far more typically used to refer to the universally-used concrete implementation.

abstract data type: A type not defined by its implementation, which may vary, but rather by its behavior. Abstract data types often have multiple implementations each with their own sets of unique tradeoffs. Some examples of abstract data types are [[strings]], [[lists]], [[sets]], [[tables]], [[stacks]], [[heaps]], [[queues]], [[deques]], [[trees]], and [[graphs]].

string: An ordered collection of [characters] that form text. A very common [[abstract data type]]. Although they’re often conceptually identical to a [list] of [[chars]]

dynamic array: A widely used data structure similar to an array but with the ability to arbitrarily grow or shrink. Known by a variety of other names, including ArrayList / sequence / Vector / List / MutableArray

tensor: A multidimensional array.

set:

dictionary: Also known as maps, tables, symbol tables, or associative arrays. A data structure characterized by key-value pairs: where any key can be used to retrieve its associated value.

collection:

tree: binary tree: A [[tree]] where every branch has two associated nodes. n-ary tree: A [[tree]] where every branch has (at most) n associated nodes.

graph:

stack:

queue: A first-in-first-out (FIFO) data structure.

deque: A double-ended [queue]. A data structure with the ability to arbitrarily grow or shrink in either direction.

heap:

value type:

reference type: The term “reference” is often used in opposition to the term “[[pointer]]” to distinguish between [[managed]] and non-managed pointers.

algebraic data type: A

struct: a grouping of multiple data types

union: a struct that can only be one of its data types at a time. Useful for

sum type: Also known as variant types, tagged unions, choice types, disjoint unions, and many more monikers… Unions may be tagged: this allows the programmer or compiler to distinguish what the

product type: Also known as record types, structs, or (occasionally and confusingly) objects, they are a data type… Records may be ordered or unordered, while structs are typically ordered.

generalized product type:

generalized sum type:

function type:

unit type:

bottom type: A type that is a [[subtype]] of all other types. Typically represented as . As the bottom type must be substitutable for all other types, a term of the bottom type can never be constructed. Instead, the type itself can be used to signify an error in a program: in Rust, functions that do not return are marked of type bottom, and so any term constructed as such would clearly be faulty. Rust and TypeScript have support for explicitly denoting the bottom type with !/never.

top type: A type that is a [[supertype]] of all other types. Typically represented as .

pose: A data structure consisting of a position (often x and y coordinates) and an orientation (often radians). Commonly used terminology in computer graphics, along with [translations], [rotations], and [twists].

translation: As a data structure:

rotation: As a data structure:

twist: As a data structure: