Glossary

Specially formatted messages tagged with the @glossary label. Format should be word:definition.

3 Satisfiability: given a collection of clauses C each containing exactly 3 literals over a set of boolean variables V, is there a truth assignment to V such that each clause is satisfied?

ABA problem: a problem that occurs in multithreaded computing, when a location is read twice, has the same value for both reads, and "value is the same" indicates "nothing has changed". Meanwhile, in between reads, another thread can change that value, do work, and change the value back, thus meaning that things have changed.

ALU: arithmetic logic unit.

AMD: Advanced Micro Devices.

AVX: Advanced Vector Extensions.

Amdahl's Law: states that when increasing the speed of one part of the system, the effect on the overall system performance depends on both how significant this part was and how much it sped up.

Barrier: in parallel computing, a barrier is a type of synchronization method. A barrier for a group of threads or processes in the source code means any thread/process must stop at this point and cannot proceed until all other thread/processes reach this barrier.

CPU: central processing unit. the engine that interprets (or executes) instructions stored in main memory.

Chomsky Normal Form: right side of every rule has either exactly two nonterminals (X->YZ), or exactly one symbol (X->a).

Clique (Graph Theory): complete subgraph, each vertex pair has an edge between them. Densest possible subgraph.

Closure: A function-like constant you can store in a variable.

DMA: direct memory access.

DRAM: dynamic random access memory.

Decision Problems: problems whose answers are restricted to boolean true/false. It is convenient to reduce problems to these.

Foreign Function Interface (FFI): a way for a programming language to define functions and enable different (foreign) programming languages to call those functions.

Funnel: a synchronization primitive used in kernel development to protect system resources. It is a mutex mechanism that prevents more than one thread from accessing certain kernel resources at the same time.

Hardware Description Language (HDL): a textual notation that looks similar to a programming language but that is used to describe hardware structures rather than program behaviors.

ISA: instruction set architecture.

Iterators: a way of processing a series of elements

L1 cache: Cache that tens of thousands of bytes long, and can be accesed nearly as fast at the register file.

L2 cache: cache that is larger than L1 cache, with hundreds of thousands to millions of bytes and is connected to the processor by a special bus. It can be 5x slower than the L1 cache.

Linear List: sequence of nodes whose essential structure properties involve only the relative positions between items as they appear in a line.

MN Model: A threading model (green threads), where there are M green thread per N operating system threads. M and N are not necessarily the same number.

Memory-mapped I/O: MMIO and port-mapped I/O (PMIO) are methods of performing I/O between the CPU and peripheral devices in a computer.

PC relative: jumps that are encoded as the difference between the address of the target instruction and the address of the instruction immediately following the jump.

Quasiparallel processing: technique of using WAIT list or agenda to control sequencing of coroutines.

Refactoring: the act of improving design without changing behavior.

SSE: Streaming SIMD Instructions.

SipHash: default hash used in Rust, designed to be resilient against DoS attacks. This algorithm is a tradeoff of security over performance.

abstraction barriers: being able to isolate different levels of a system using abstraction.

active transformation: the object is transformed while the coordinate space remains stationary.

address-space layout randomization (ASLR): techniques that involve loading parts of a computer program into different regions of memory every time it is run.

affine transformation: a transformation that contains translation.

aliasing: in polar coordinate space, this happens when two numbers are different but point to the same place in space.

alignment restrictions: restrictions placed on allowable addresses for primitive data types in a computer system. typically must be a multiple of some value (2, 4, or 8).

angle-preserving: a transformation if the angle between two vectors is not altered in either magnitude or direction after transformation. Only translation, rotation, and uniform scale are angle-preserving transformations.

applicative-order evaluation: an evaluation method that evaluates the arguments and then applies. this is the method that the scheme interpreter uses.

articulatory inversion: the process of taking acoustic data and converting it back into vocal tract shapes.

atomicity: an instruction that is an indivisible and irreducable series of database operations such that either all occurs or none occurs.

backtrace: a list of all the functions that have been called to get to this point.

binary target: runnable program that is created if the crate has a src/main.rs file or another file speciefied as a binary, as opposed to a library target that isn't runnable on its own but is suitable for for including within other programs.

blanket implementations: implementations of a trait on any type that satisfies the trait bounds.

bounded parametric polymorphism: a type of polymorphism that abstracts over different possible types and trait bounds to impose constraints on what those types must provide.

branch prediction logic: a mechanism in modern processors use to try and guess whether or not each jump instruction will be followed.

buses: a collection of electrical conduits that carry bytes of information back and forth between components.

cache memory: smaller and faster storage devices that serve as temporary staging areas for information that the processor is likely to need in the near future.

camera space: the object space associated with the viewpoint used for rendering.

canary value: special value used in a stack protector.

case analysis: a special form in lisp that can make tests and perform different operations depending on the result of the test.

channel: a programming concept used to accomplish message-sending concurrency.

clause: in lisp, a parenthesized pair of expressions that follow the cond symbol.

cofactor: same as the corresponding minor, but with alternating minors negated.

column vector: a Nx1 matrix.

combinations: expressions in lisp formed by delimiting a list of expression within parentheses in order to denote procedure application.

compare and swap (CAS): an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory value with a given value, and if they are the same, modifies the contents of the memory location with a new given value.

concurrent programming: programming where different parts of a program execute independently.

concurrently: instructions of one process are interleaved with the instructions of another process.

consequent expression: the value of the corresponding expression associated with a predicate that is true. used in conditional expressions.

constructor: a function that creates an instance.

consuming adaptors: in the context of iterators, methods that use up the iterator when called. Methods that call "next" on an iterator are consuming adaptors.

context switching: the mechanism that the OS uses to interleave instructions from multiple processes.

context: the state information that the process needs in order to run.

controller/adapter: the means by which an IO device is connected to the IO bus. The distinction between a controller or an adapter is mainly one of packaging.

correctness: the extent to which code does what it is intended to do.

crate root: source file that the rust compiler starts from and makes up the root module of your crate.

crate: a binary or library.

create a new library restaurant: cargo new --lib restaurant.

critical section: a shared resource in concurrent programming that needs to be protected in ways that avoid concurrent access.

deadlock: a situation in concurrent computing where no member of some group entities can proceed because each waits for another member, including itself, to take action (usually releasing a lock, or sending a message).

deferred operations: in recursion, operations that are created while a process expands an expression, and are performed during the contraction.

dereference operator: in Rust, this is an operator represented with *. Implemented the Deref trait allows you to customize the trait of the derefernce operator.

destructor: a function that cleans up an instance.

determinant: a special scalar produced from square matrices that have useful properties in linear algebra, and also some interesting geometric interpretations.

diagonal elements: elements in a (square?) matrix for which the row and column indices are the same.

diagonal matrix: a matrix whose nondiagonal elements are zero.

documentation comment: in Rust, a particular comment format used for inline code documentation.

duck typing: a concept in dynamically typed languages. If it walks like a duck and quacks like a duck, then it must be a duck!

dynamic dispatch: when the compiler can't tell at compile time which method is being called.

effective address: in assembly, this is the computed address used to access a particular part of memory.

encapsulation: implementation details of an object aren't accessible to code using that object.

environment: some sort of memory in the interpreter that keeps track of name-object pairs. more precisely called the global environment.

exception handler: a procedure designed to handle the specific type of exception encountered.

exhaustive: in the context of rust pattern matching, meaning every possibility must be accounted for.

exploit code: a malicious program contained inside input to some program.

fearless concurrency: a core design philosophy of Rust, that emphasizes more compile-time errors of code rather than run-time errors.

fetch-and-add (FAA): an atomic instruction that increments a value at address x by a, and then returns the original value at x.

file: a sequence of bytes. nothing more. nothing less.

functional programming: programming without assignment (SICP).

grapheme cluster: a unit of measurement for strings in Rust. A close analagy would be a letter. Things like Devanagari script that use diacritics can have grapheme clusters with a variable number of bytes.

green thread: threads that are provided by the programming language, rather than through the OS API.

hyperthreading: a method to run two programs simultaneously on a single processor. First introduced in the x86 line with the Pentium 4E processor in 2004.

identity matrix: diagonal matrix whose diagonal values are all 1.

imperative description: "what" description. mathematics are concerned with this (vs "how to").

imperative descriptions: how-to descriptions. computer scientists are usually concerned with this (vs "what is").

imperitive programming: programming that makes extensive use of assignment. (SICP)

inheritance: a mechanism whereby an object can inherit from another object's definition, thus gaining the parents object data and behavior without having to define them again.

integration tests: check that many parts of the library work together correctly. Use the library's public API similar to how external code will use it.

interior mutability: a design pattern in Rust that allows you to mutate data even when there are immutable references to that data.

invertable: property of a transformation if there exists an opposite transformation.

irrefutable: in Rust, this refers to patterns that will match for any possible value passed.

iterative process: a process whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an optional end test that specifies conditions under which the process should terminate.

iterator adapter: other methods in the Iterator struct that allow you to change iterators into different kinds of iterators.

jump table: data structure used to efficiently implement switches. It is an array of addresses to jump to, using the index as a lookup.

lazy evaluation: also known as memoization, the ability for a closure to compute a value only when needed to, and to other wise use a cached value.

lifetime: the scope for which a reference is valid.

lifetimes: a generic in Rust that ensure that references are valid as long as they are needed to be.

linear iterative process: an interative process whose growth is linear.

linear recursive process: a recursive process that keeps track of a chain of deferred operations. This chain has linear growth.

load effective address: instruction that is a variant of the movq instruction, referred to as leaq. Commonly used to perform simple arithmetic.

locality: the tendency for programs to access data and code in localized regions.

lock contention: occurs when one process or thread attempts to acquire a lock held by another process or thread.

lock granularity: The granularity is a measure of the amount of data the lock is protecting.

lock overhead: the extra resources for using locks, like the memory space allocated for locks, the CPU time to initialize and destroy locks, and the time required for releasing locks.

main memory: a temporary storage device that holds both a program and the data it manipulates while the processor is executing the program.

match guard: an additional if condition specified after the pattern in a match arm that must also match, along with the pattern matching, for that arm to be chosen.

matrix chain problem: the problem of finding the parenthesization that minimizes the number of scalar multiplications.

means of abstraction: compound elements can be named and manipulated as units

means of combination: compound elements are built from simpler ones.

memory hierarchy: the way a computer system organizes memory by performance. moving from top to bottom, devices become slower, larger, and less costly per byte.

memory leak: a situation where memory is allocated but not cleaned up.

message passing: a style of programming found in languages such as LISP/Scheme which involve the ability to manipulate procedures as objects (which automatically provies the ability to represent compound data).

metacode: code that writes other code.

minor: the determinant of a submatrix.

mock objects: specific types of test doubles that record what happens during a test so you can assert that the correct actions took place.

modules (rust): thing that organizes code within a crate into groups for readability and easy reuse.

monomorphization: the process of turning generic code into specific code by filling in the concrete types that are used when compiled.

motherboard: systems main printed circuit board.

multiple producer, single consumer (mpsc): a channel in Rust. It can have multiple sending ends that produce values but only one receiving end that consumes those values.

mutex: an abbreviation for mutal exclusion. allows only one thread to access some data at any given time.

mutex: short for mutual exclusion. A synchronization primitive that enforces limits on access to a resource when there are many threads of execution.

nested: to have combinations whose elements are themselves combinations.

nop sled: a technique used by attackers that involve using a long sequence of nops. used to try and guess the address of the exploit code. used to try and bypass ASLR.

normal order evaluation: an evaluation method that fully expands and then reduces.

object space: coordinate space associated with a particular object.

oct word: what Intel refers to as a 16-byte quantity.

operand: the other elements following the operator.

operating system: the layer of software interposed between the application program and the hardware.

operator: the leftmost element in the list.

optimistic concurrency control: also known as optimistic locking. a concurrency control method applied to transactional systems such as relational database systems and software transactional memory.

order of growth: a notion used to describe the rate at which a process consumes computational resources. This is obtained via the gross measure of resources required by a process as the inputs become larger.

orphan rule: in Rust, a rule that states that a trait can be implemented on a type as long as either the trait or the type are local to the crate.

orthogonal: a term used to describe a matrix whose rows form an orthonormal basis.

package: one or more crates that provide a set of functionality.

parallel programming: programming where different parts of the program execute at the same time.

parity flag: in x86-64, a 1-bit flag that is set after an arithmetic or logical operation. PF is 1 when the lower 8 bits have an even number of 1s, 0 otherwise. This information is not directly accessible in C and requires machien-dependent assembly code.

pointer: a general concept for a variable that contains an address in memory.

polymorphism: the ability to substitute multiple objects for eachother at runtime if they share certain characteristics.

predicate: procedures that return true or false.

prefix notation: convention of placing operator to the left of the operands.

pretty-printing: a formatting convention in which each long combination is written so that the operands are aligned vertically.

primitive expression: the simplest entities the language is concerned with.

primitive obsession: using primitive values when a complex type would be more appopriate.

priority inversion: a scenario in scheduling in which a high priority task is indirectly superseded by a lower priority task, effectively inverting the assigned priorities of the tasks.

privacy (rust): in the context of modules, the determination whether an item can be used by outside code (public) or not.

privacy boundary: the line that encapsulates the implementation details isn't allowed to know about, or rely on.

procedure definitions: a compound operation that can be given a name and then referred as a unit.

process: the operating system's abstraction for a running program.

processor-memory gap: the growing gap between processor and memory performance. as semiconductor technology progresses over the years, this gap continues to increase.

program counter: a register that points at some machine language instruction in main memory.

programmer-visible state: refers to the part of a processor state that a program can read and modify.

race condition: a situation that arises when a computer program, to operate properly, depends on the sequence or timing of the program's threads.

read-eval-print loop: the operation cycle of interpreter. read an expression from the terminal, evalulate the expression, and print the result.

record locking: the technique of preventing simultaneous access to data in a database, to prevent inconsistent results.

recursive process: a process defined by a chain of deferred operations.

recursive type: a type whose value can have as part of itself another value of the same type.

recursive: evaluation rule that includes, as one of its steps, the need to invoke the rule itself.

reference counting (pointer type): a smart pointer type that enables you to have multiple owners of data by keeping track of the number of owners and, when no owners remain, cleaning up the data.

refutable: in the context of Rust pattern matching, refers to patterns that can fail to match for some possible value.

register file: contains 16 named locations storing 64-bit values, able to hold addresses or integer data.

register: a word-sized storage device.

release profile: predefined and customizable profile with different configurations that allow a programmer to have more control over various options for compiling code.

rigid body transformation: a rigid-body transformation is one that changes location and orientation of an object, but not its shape.

row vector: a 1xN matrix.

runtime (rust): code that is included by the language in every binary.

security monoculture: a phenomenon where many systems are vulnerable to the exact same strain of virus or exploit.

semaphore: a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system.

singular: a matrix that has no inverse. the determinant of an invertable matrix is nonzero.

smart pointer: data structures that not only act like a pointer but also have additional metadata and capabilities.

software transactional memory (STM): a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It is an alternative to lock-based synchronization.

special forms: exceptions to the general evaluation rule. define in scheme is an example of a special form.

spinlock: a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available.

square matrices: matrices with the same number of rows and columns.

stack protector: a mechanism uesd to detect stack corruption, implemented in recent versions of GCC.

stack randomization: the use of randomizing the stack position of a program from one run of a program to another.

state pattern: object oriented design pattern, where a value has some internal state, represented by state objects, and the value's behavior changes based on the internal state.

static dispatch: when the compiler knows what method you are calling at compile-time.

test double: a type used in place of another type during testing.

test-and-set: instruction used to write (set) 1 to a memory location, and return its old value as a single atomic operation.

trait bound: a special form in Rust that is used when traits are parameters. It's a long form, and often there's synactic sugar for it "impl Trait".

trait object: mechanism that points to both an instance of a type implementing a specified trait, as well as a table used to look up trait methods on that type at runtime.

trait: similar to interfaces in other languages, a mechanism used in Rust that tells the Rust compiler about the functionality a particular type has and can share with other types. Can be used to define shared behavior in an abstract way.

tree recursion: a common pattern of computation. A recursive process whose evolution looks like a tree. in (SICP), the fibonacci algorithm is used as an example of a process with tree recursion.

type annotation: in rust, this refers to explicitely labelling what something is, such as .

unit test: excersize different parts of a library separately. Can test private implementation details.

unrolling: an optimization that removes the overhead of the loop controlling code and instead generates repetitive code for each iteration of the loop.

unsafe superpowers: possible actions in unsafe Rust. Dereferencing a raw pointer, calling an unsafe functin, Access/modify a mutable static variable, implement an unsafe trait, and access fields of unions.

upright space: a convention used to help describe coordinate space transitions. The axes of upright space are parallel with the axes of world space, but the original is coincident with the origin of object space.

virtual address space: a uniform view of memory that each process has.

virtual memory: an abstraction that provides each process with the illusion that it has exclusive use of the main memory.

virus: a piece of code that adds itself to other programs, including operating systems.

volatile: the volatile is a keyword in languages like C/C++ and Java, that indicate that a value may change between different accesses, even if it does not appear to be modified. This prevents optimizing compilers from optimizing away subsequent reads or writes and thus incorrectly reusing a stale value or omitting writes.

word: a fixed size chunk of bytes. Most machines today have word sizes of 4 bytes or 8 bytes.

world coordinate system: a coordinate system that specifies the global reference frame for all other coordinate systems to be specified.

world coordinate system: coordinate system that establishes the "biggest" coordinate system in games, which is the "entire world".

worm: a program that can run by itself and can propogate a fully working version of itself to other machines.

zero vector: special vector that has zeroes in every position.

zero-cost abstraction: In the Rust Programming Language, an abstraction that imposes no additional runtime overhead.

zero-overhead: the term Bjarne Stroustrup uses in his book "Foundations of C++" (2012) to describe in C++ what Rustaceans would call "Zero-Cost".