A Computer Science Glossary

Note: this glossary is a work in progress! Entries that are not bolded are not finished, and 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.

memory
syntax
metaprogramming
object oriented programming
functional programming
type systems
data

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.

See also [[stack (data structure)]]

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:

Generally: A term broadly meaning “done at compile time”.
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.
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 can be considered a form of garbage collection, although it is frequently distinguished due to its determinism, generally worse performance, and drastically simpler 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. Read more in the Rust book.

cycle breaker

weak references: A method of dealing with [cyclical references]

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 types of the parameters, 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: A language construct that allows simple substitution of code at compile time.

macro: 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:

state:

actor:

event:

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:

Generally: a variable containing a set of values.
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:

In object-oriented programming: a function defined as part of a class, and subsequently attached to an object.
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:

A general term.
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.

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:

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.
In functional programming: A [procedure] guaranteed to not have [[side effects]].
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.

in rust, for example: the Option monad abstracts over a value that may or may not exist, and can be accessed with .unwrap().
in javascript: the Promise construct (while technically not a monad) is exceedingly similar by way of abstracting over an asynchronous operation.
in haskell: the IO monad abstracts over input/output operations and the risk of failure and nondeterminism there.

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

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,

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

trait: A language…

In Rust:
In Scala:

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: In Rust:

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:

data

byte: A simple type that…

character: A simple type that represents a character in the ASCII encoding set. Under the hood, chars are typically implemented as integers 0-127,

boolean: A simple 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 simple 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, through two’s complement or otherwise.

float: A simple type representing a decimal number. These are almost always approximate, due to low-level limitations: which can lead to… https://0.30000000000000004.com/

double: A term for a “double-precision float”.

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

array: An indexed collection of values. These values are traditionally zero-indexed and accessible with square brackets (array[2]). Memory limitations mean arrays are more often than not fixed-length, with their elements all of the same type.

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

set:

In mathematics: a collection of different things.
In computer science: data structures and fast functions to check if a value is in a set or not, makes them often useful. Their defining property of only having one value in a set makes them useful, and are often a basic data type.

dictionary: A data structure that’s a

value type:

reference type:

primitive type:

struct: a grouping of multiple data types

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

algebraic data type:

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

tree:

binary tree:

n-ary tree:

graph:

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

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

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: