j-james

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, don’t proceed at all.


Often [[overloaded]], often redundant, often contradictory names abound in the wonderful field of computer science.

memory

stack: One of two types of fundamental memory structures. Stack-based memory is quick to access, but cannot be grown. 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 collection] (which often is referred to as simply “garbage collection”), and [reference counting]. These systems are distinguished from manual memory management and move semantics by the latter happening at compile time and subsequently having no [runtime overhead].

tracing garbage collection:

reference counting: A system of memory management that provides memory safety by keeping a reference count next Reference counting can be considered a form of garbage collection, although it is typically 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:

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

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:

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

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)

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

type inference:

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:

  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/protocol:

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 (also C++). 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. Etymology not entirely clear.

functional programming

functional programming: A programming paradigm characterized by the avoidance of state (via variables, objects, and side effects) through the chaining of functions. Has roots in pure mathematics and 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.

curry:

functor:

closure:

context:

environment:

lambda calculus:

turing machine:

model of computation:

typing

type:

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

type system: A fundamental feature of every programming language to some extent, 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. For instance

concept: In C++ and Nim: Another name for a [typeclass].

trait: In Rust:

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]()

openarray: In Nim: A [generic] type that unifies arrays, dynamic arrays, strings, and … into one iterable type.

type safety:

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

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 can 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 Rust’s [traits]) can be considered duck-typed. If it walks like a duck…

data

byte:

char:

bool:

integer:

float:

double:

dictionary:

string: A collection of [[characters]] that form text. A very common generic data type. Some overhead results from strings being particularly more complex than raw numbers.

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

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,

product type:

generalized product type:

generalized sum type:

function type:

unit type:

bottom type:

record type: Another name for a [struct].

tree:

binary tree:

n-ary tree:

graph:

queue:

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: