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.
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.
- 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.
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.
move semantics: Another name for [[ownership]] systems.
ownership: A memory management system characterized by every piece of memory having a single owner
destructors: Code that runs at the end of an object’s [[lifetime]].
lent: A concept in move semantics
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
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,
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: 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.
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).
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]].
- 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", ...)
- 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].
- 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
ad hoc polymorphism:
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: 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.
- 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
Optionmonad abstracts over a value that may or may not exist, and can be accessed with
Promiseconstruct (while technically not a monad) is exceedingly similar by way of abstracting over an asynchronous operation.
- in haskell: the
IOmonad abstracts over input/output operations and the risk of failure and nondeterminism there.
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.
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: 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…
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
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.
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].
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:
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:
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
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). 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
- 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
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:
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
top type: A type that is a [[supertype]] of all other types. Typically represented as
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: