Programming

---

The gap between human intent and machine execution is bridged by programming languages, which vary in how much abstraction (aka. context) they provide over the underlying hardware. The sequence of instructions written in a language constitutes a program, and the tools that translate it into something the machine can execute determine how that program runs.

I

---

1.1. Programming Language

A program is a sequence of instructions which directs a computer to perform a task. They can be classified as system programs which provide OS utilities and the programming environment (e.g. compilers, shells, daemons), or application programs that solve end-user problems (e.g. web browsers, text editors), both running in user space. For instance, Unix commands under /usr/bin/, such as cat and lsd (i.e. whether pre- or user-installed), are compiled binaries invoked by a shell (403 §2.1) which is itself a system program. Terminal emulators (e.g. Ghostty) and file browsers (e.g. Finder) are application programs that provide interfaces to the same underlying tools.

A programming language (PL) is a formal system of syntax and semantics for expressing such instructions. Like mathematical notation, every construct must resolve to exactly one interpretation since machines have no capacity for contextual inference, though they have historically served different purposes. Mathematical notation expresses “what is true” ($x^2 + y^2 = r^2$ defines a circle and $\pi r^2$ its area), whereas programs specify “what to do” (draw the circle pixel by pixel) under the constraints of finite memory, discrete representation, and execution order. For example, under IEEE 754, 0.1 + 0.2 yields 0.30000000000000004 as 0.1 has no exact binary representation.

PLs vary in how much control and overhead the programmer bears: from assembly (i.e. nearly one-to-one with machine instructions) through systems languages (e.g. C, Rust) that must pay high attention to data type and memory, to high-level languages (e.g. Python, JavaScript) abstracting many hardware details. The tools that translate source code into executables (§II-III) have co-evolved with PL, since Formula translating system (Fortran, 1957) appeared as the first compiled high-level PL. Yet as programs scaled to millions of lines, undisciplined use of goto and global state made them difficult to reason about, test, or modify (the software crisis, NATO 1968).

• [src]

Programming paradigms imposed discipline on program structures. Structured programming (Dijkstra, 1968) restricted control flow to sequence, selection, and iteration, which the Böhm-Jacopini theorem (1966) had proved sufficient for any flowchart program. Object-oriented programming (Simula, 1967; Smalltalk, 1980) organised programs around objects hiding state behind interfaces. Functional programming (lambda calculus, 1936; Lisp, 1958) favoured pure functions and immutable data which became useful for concurrency. PL designers shape syntax, type systems, and std. libraries around preferred paradigms, but the features often serve more than one.

For instance, languages must decide how scope (i.e. variable visibility) works. Dynamic scoping resolves a variable to the most recent binding on the call stack. Whereas, lexical scoping (ALGOL 60, 1960; Scheme, 1975) resolves by position in source text, so a function always sees the environment in which it was defined. Nearly all modern languages adopted lexical scoping for predictable reasoning, while lookup rules vary by PL (e.g. Python takes LEGB: Local, Enclosing, Global, Built-in). Combined with first-class functions, lexical scoping also yields closures, which underpin features such as higher-order functions, callbacks, and decorators (PEP 227, PEP 318).

• [src]

1.2. Type System

In a computer, every piece of data is a bit pattern, and the same 8 bits (01100001) can represent the integer 97 (admitting $+, -, \times$) or the character ‘a’ (admitting concatenation). A data type determines how the compiler interprets and stores the bits by declaring a set of values (i.e. domain) and the operations permitted on them. Primitive types (int, float, char, bool) have fixed representations while data structures (stack, list, tree, hash map) have internal state, and early languages such as C let any code access their state directly (e.g. s.data[50] on a stack struct). As codebases grew in the 1960s-70s, unintended modifications on internals silently broke dependents.

In 1974, Barbara Liskov introduced the abstract data type (ADT), a specification of operations and invariants (e.g. push, pop, peek for LIFO) independent of implementation (e.g. array or linked-list backed). Her language CLU (Turing Award, 2008) enforced this through the cluster, a construct that bundles a hidden representation with public operations, thus the compiler rejects access to internals. This achieved i) correctness; ii) modularity; and iii) substitutability (i.e. formalised as the Liskov Substitution Principle, 1987). Many modern languages inherit it as compiler-enforced access control, but Python allows the _ prefix merely as convention rather than enforcement.

An ADT’s domain, operations, and invariants correspond to what abstract algebra calls a carrier set $S$, operations ${o_i}$, and axioms $\mathcal{A}$, formalised independently (Goguen et al., 1977) as an algebraic structure $(S, {o_i}, \mathcal{A})$. The same axioms can govern different carriers under different operations, and the topic studies what is deducible from the axioms alone, thus a theorem proved once applies to every structure satisfying them. The uniqueness of inverses, for instance, follows from the group axioms and so holds in any group $(G, \cdot, e)$, such as $(\mathbb{Z}, +)$, $(S_n, \circ)$, and $(GL_n(\mathbb{R}), \times)$. In this light, both group and stack define what must hold, as specifications, without prescribing what carries it out. This correspondence enables equational reasoning about programs, generic programming over any type satisfying the axioms, and formal verification via proof assistants.

• Structure	Ops	Axioms	Example	What works	What doesn't
  monoid	one	associativity, identity	$(\mathbb{N}, +)$, $(\mathbb{N}, \max)$	$3 + 5 = 8$, $\max(3,5) = 5$	$(-5) \notin \mathbb{N}$, no inverse for $\max$
  group	one	monoid + inverses	$(\mathbb{Z}, +)$	$8 + (-5) = 3$	—
  ring	two	additive group, multiplicative monoid, distributivity	$(\mathbb{Z}, +, \times)$	$3 \times 5 = 15$	$5^{-1} \notin \mathbb{Z}$
  field	two	ring + commutativity + multiplicative inverses	$(\mathbb{R}, +, \times)$	$5x = 3 \Rightarrow x = 3 \cdot 5^{-1}$	—
  vector space	two	abelian group $(V,+)$ + scalar mult. from field $F$	$(\mathbb{R}^n, +, \cdot)$	$\vec{u} + \vec{v}$, $\alpha \vec{u}$	no vector $\times$ vector
  Hilbert space	three	vector space + inner product + completeness	$(L^2, +, \cdot, \langle\cdot,\cdot\rangle)$	$\langle f, g \rangle = \int f \bar{g}$	—

Implementations realise these specifications under finite hardware constraints. int32 approximates the ring $(\mathbb{Z}, +, \times)$ in 4 bytes with overflow at $2^{31}$. str approximates a free monoid $(\Sigma^\ast, \cdot, \varepsilon)$ (a monoid with no additional relations: no inverses, no commutativity) as a contiguous byte array bounded by memory, where concatenation is the operation (“ab” $\cdot$ “cd” $=$ “abcd”) and the empty string $\varepsilon$ is the identity. list approximates the same free monoid over a type $T$, $(T^\ast, \cdot, [])$, and list[str] is then $\Sigma^{\ast\ast}$ , the construction applied twice as char $\to$ str $\to$ list[str]. Each choice of storage and algorithm constitutes implementation details the ADT deliberately hides.

Types can also be composed through set-theoretic operations. A struct or tuple is a Cartesian product ($\text{String} \times \text{Int} = \Sigma^\ast \times \mathbb{Z}$), a tagged union or enum is a disjoint union (Rust’s $\text{Result}\langle T, E \rangle = T \sqcup E$), and a function type $A \to B$ has $|B|^{|A|}$ inhabitants . These are called algebraic data types because their cardinalities follow arithmetic ($|A \times B| = |A| \cdot |B|$, $|A \sqcup B| = |A| + |B|$). Type constructors like List go further as functors $\textbf{Type} \to \textbf{Type}$, sending any type $T$ to $T^\ast$ and lifting a function $f : A \to B$ to $\text{map}(f) : A^\ast \to B^\ast$ while preserving composition. Under the Curry-Howard correspondence, these same constructions carry logical meaning ($A \times B$ is conjunction, $A \sqcup B$ is disjunction, $A \to B$ is implication), which is why languages like Lean and Coq serve as both programming languages and theorem provers, where a program that type-checks constitutes a proof of the proposition encoded by its type.

• 	Mathematics	CS
  Object	element of a set ($3 \in \mathbb{Z}$, $f \in L^p$)	bit pattern with a type label
  Structure	carrier + operations + axioms (e.g. group, field)	ADT: carrier + signature (e.g. int, list)
  Implementation	—	data structure (e.g. hash map, BST)
  Context	implicit (mathematician tracks it)	explicit (type annotation or inference)
  Composition	$A \times B$, $A \sqcup B$, $A \to B$	product, sum, function types
  Cardinality	infinite ($\|\mathbb{Z}\| = \aleph_0$)	finite (int32 has $2^{32}$ values)
  Verification	peer review, proof	type checker, compiler

While types specify what is valid, the type discipline determines when violations are caught. Early Fortran assigned types implicitly by variable name {I-N: int, otherwise: float}, and a misspelled variable silently became a new binding. At scale, such bugs drove the split of static typing and dynamic typing: the former catches them at compile time, enabling optimisations (e.g. monomorphisation), while the latter defers to runtime for flexibility. Orthogonally, strong typing rejects implicit coercion (e.g. 2 + ‘2’ raises TypeError in Python), but weak typing permits it (e.g. 2 + ‘2’ yields ‘22’ in JavaScript). A language’s choice along these axes decides where its bugs surface.

Static typing was safe but verbose. Robin Milner (Turing Award, 1991) dissolved the tradeoff using Hindley-Milner (HM) type inference in Meta Language (ML), where let f x = x + 1 compiles to $f : \text{int} \to \text{int}$ without annotations. HM works because each use of a value constrains its type variable, and unification solves for the principal type (Damas and Milner, 1982). It enabled Haskell and influenced Rust, Swift, and Kotlin. Gradual typing (Siek and Taha, 2006) took the opposite path, retrofitting optional annotations as implemented in Python’s type hints (PEP 484), checked by external tools (e.g. mypy, pyright) but ignored at CPython runtime, e.g. def f(x: int) -> int.

• [src]

1.3. Memory Management

Static allocation, as in Fortran, confined programs to statically sized data. Dynamically sized data (e.g. variable-size lists, hash maps) became possible only when Lisp introduced heap allocation for data whose size and/or lifetime is unknown at compile time (403 §3.1). Whereas Lisp reclaimed memory via garbage collection (GC), C (1972) instead allowed programmers direct control with malloc/free, yet manual management proved error-prone at scale. Accordingly, Microsoft (MSRC, 2019) and the Chromium project (2020) reported that roughly 70% of security vulnerabilities in their C/C++ codebases are memory-related bugs (e.g. buffer overflow, use-after-free).

GC also takes several forms. Reference counting (§3.1) frees objects when their count drops to zero, and hence cannot handle cycles ($A \to B \to A$, both counts $> 0$). Instead, at the cost of pausing executions, the mark-and-sweep algorithm traces reachable objects (e.g. globals, stack variables) from roots and frees everything else. Generational collectors (e.g. Java, .NET) exploit the observation that most objects die young, collecting the youngest generation frequently to reduce pause times. GC automates reclamation at the cost of non-deterministic pause times. Ownership system and borrow checker in Rust prevent this, enforcing memory safety at compile time.

Essentially, how much type information a PL preserves at runtime shapes what it heap-allocates, automates, and its cost. As said, C, statically-typed language, erases types after compilation and places local variables on the stack as raw bits (e.g. int, 4 bytes), where the programmer manages reclamation manually to prevent memory leaks. Java, also statically-typed, heap-allocates its objects (e.g. Integer, ~16 bytes; GC-managed) but stack-allocates primitives (e.g. int, 4 bytes). Python, dynamically-typed, binds type information to every value as a heap-allocated PyObject (e.g. int, ~28 bytes) carrying per-value metadata (e.g. reference count, type ptr, payload).

• [src]

1.4. Error Handling

C functions signal failure by returning a sentinel value (-1, NULL, errno), and correctness depends entirely on the caller checking it. A single unchecked return propagates silently, and the failure surfaces far from its origin as a crash or corrupt output. Tony Hoare called his invention of the null reference (ALGOL W, 1965) a “billion-dollar mistake” because null inhabits every reference type, making every dereference a potential unhandled error. The Ariane 5 launch failure (1996, $370M) traced to an integer overflow in code reused from Ariane 4 whose error-handling assumptions no longer held on the new flight trajectory.

Exceptions, introduced in PL/I (1964, ON-conditions) and formalised in CLU (Liskov, 1975), unwind the call stack until a matching handler is found, keeping the happy path clean but making the set of possible failures invisible in the function signature. Go (2009) rejected this model, returning to explicit error codes that force the caller to handle failure at every call site (if err != nil), trading verbosity for visibility. Algebraic error types such as Haskell’s Either and Rust’s Result$\langle$T, E$\rangle$ unified both concerns by encoding success or failure in the type system, so the programmer must explicitly handle or propagate failure, and the compiler warns if a Result is silently discarded.

II

---

2.1. Compiler

A compiler translates source code into a lower-level language as a batch process before execution (e.g. C/C++: GCC, Clang, MSVC). Grace Hopper’s A-0 system (1952), the first program called a compiler, matched mathematical notation to pre-written machine-code subroutines. Fortran generated machine code from arbitrary expressions, proving compiled output can match hand-written assembly. The Chomsky hierarchy (1956) provided the formal foundation for parsing by classifying grammars by expressive power, Backus-Naur form (BNF, 1959) gave a notation for these grammars, and Lex and Yacc (1975, Bell Labs) automated lexer and parser generation.

These formalisms ground the front-end of the standard compilation pipeline, which performs i) lexical analysis: breaking source code into tokens; ii) parsing: building an abstract syntax tree (AST) from the grammar; iii) semantic analysis: checking types and resolving scopes; iv) intermediate representation (IR) generation. The middle-end optimises the resulting IR with static single assignment (SSA) form, where each variable is assigned exactly once to simplify data-flow analysis. The back-end lowers the optimised IR to machine code for a target ISA, and a linker combines object files into an executable bound to a specific OS and ISA.

• [src]

The partitioning of these stages has evolved through three generations. The GNU Compiler Collection (GCC, 1987), the first major free compiler, supported multiple languages and target ISAs. GCC is self-hosting, compiling its own source code through bootstrapping (an initial version written in another language is progressively recompiled by its own output). However, its architecture coupled front-ends to back-ends tightly (despite GIMPLE and RTL as intermediate representations), so supporting $N$ languages on $M$ targets required work proportional to $N \times M$. Its move to GPLv3 (2007) further discouraged adoption by proprietary toolchains.

Low-level virtual machine (LLVM, 2003) reduced this to $N + M$ by defining a stable, target-independent IR in SSA form (.ll text, .bc bitcode). It initially relied on GCC as its front-end (llvm-gcc), but Clang (2007) replaced it with a native C/C++/Objective-C front-end, emitting LLVM IR that the shared middle-end and back-end then process. In C, each stage is explicit: the preprocessor expands macros and #include directives (-E), the compiler emits assembly (-S), the assembler produces an object file (-c), and the linker combines object files into the executable. The back-end can compile the optimised IR ahead-of-time (AOT) via llc, or execute it directly via a just-in-time (JIT) compiler (lli).

• [src]
  how some projects can use multiple PLs

LLVM standardised everything below its IR (optimisation and code generation), but the IR operates near the abstraction level of C, too low to represent domain-specific semantics (e.g. tensor operations, ownership constraints, or protocol conformance). Optimisations at this level are inherently limited, since the compiler cannot reason about structure it does not encode: fusing two tensor operations into a single kernel, for instance, requires semantic knowledge that LLVM IR has already discarded. Without a shared framework above LLVM IR, each project constructed its own intermediate layer (Swift-SIL, Rust-MIR, TorchScript), duplicating pass infrastructure, lowering logic, and verification.

The multi-level intermediate representation (MLIR, llvm-project/mlir) addresses it by providing an open-source compiler infrastructure between AST and LLVM IR. A developer defines a dialect (a domain-specific set of operations and types), and MLIR provides the shared infrastructure (passes, verification, rewriting). A PyTorch tensor addition, for instance, progressively lowers from torch.aten.add (Torch dialect) to element-wise loops (linalg.generic) to scalar loads and arithmetic (llvm.fadd). Each step is a systematic dialect-to-dialect transformation. Built-in dialects (arith, linalg, gpu) are maintained by the LLVM community, while external projects define their own (e.g. torch-mlir for PyTorch, IREE for ML inference).

• [src]

The linker combines object files, potentially from different source languages, but the result is correct only if all were compiled against the same application binary interface (ABI), which specifies calling conventions, data type sizes, struct layout, and name mangling. Static linking embeds all dependencies into the executable, while dynamic linking defers resolution to shared libraries (e.g. .so, .dylib) at load time via a runtime linker (ld.so on Linux, dyld on macOS). ABI mismatches may silently corrupt data or crash at runtime, so a compiled binary targets a specific triple $(\text{ISA}, \text{vendor}, \text{OS})$. Translation layers such as Apple’s Rosetta 2 bridge ISA mismatches by translating x86_64 binaries to ARM (AOT at first launch, with JIT fallback for dynamically generated code).

On disk, the final executable takes an OS-specific format: Linux uses executable and linkable format (ELF), Windows uses portable executable (PE), and macOS uses Mach-O. On macOS, applications appear as single icons in Finder but are actually directories called bundles. A .app bundle (e.g. /Applications/Safari.app/) contains an Info.plist (metadata), a Resources/ directory (assets), and the actual Mach-O executable under Contents/MacOS/. The “program” in the strict sense is the Mach-O binary inside; the bundle is packaging that Finder renders as a clickable icon, and cd /Applications/Safari.app/Contents/MacOS/ reveals the executable directly.

• [src]
  ELF explained

2.2. Domain-Specific Compiler

The PLs discussed so far can refer general-purpose languages (GPL). A domain-specific language (DSL) confines its abstractions to a specific domain and encodes domain knowledge as primitives that a GPL must reconstruct by loops, conditionals, and data structures. For instance, a structured query language (SQL) compiles a declarative query into a physical execution plan, while regular expression (regex) compiles a pattern description into a finite automaton. Each DSL is backed by its own compiler or interpreter, but unlike a GPL compiler that emits standalone machine code, a DSL compiler targets its own executor (e.g. DB engine, regex engine, GPU runtime).

Compute unified device architecture (CUDA, 2006) extended C/C++ with GPU-specific constructs that work as an embedded DSL for NVIDIA hardware. When a .cu source file mixes host code (i.e. CPU logic) and device code (i.e. GPU kernels marked with __global__ or __device__), NVIDIA CUDA compiler (NVCC) splits them at compile time, delegates host code to the system compiler, and either compiles device code into parallel thread execution assembly (.ptx) or a directly executable CUDA binary (.cubin) via NVIDIA’s LLVM derivative (NVVM). CUDA exposes the hardware model directly, so requires manual coalescing, synchronisation, and SM scheduling.

Triton (2021) by OpenAI is a Python-based DSL for GPU tensor operations, built on LLVM-MLIR, which automates what CUDA leaves manual by replacing the per-thread SIMT model with tile-based programming over multi-dimensional blocks. Its compiler captures the AST of a kernel (i.e. decorated with @triton.jit) and progressively lowers it through MLIR dialects: Triton IR (TTIR, hardware-agnostic) → TritonGPU IR (TTGIR, hardware-specific) → LLVM IR → executable. It occupies the middle ground between eager-mode PyTorch (i.e. no kernel control) and raw CUDA (i.e. full manual control), with access to shared memory and HBM (but w/o thread-level scheduling).

• [src]

III

---

3.1. Interpreter (CPython)

Compilers and interpreters represent opposite trade-offs: the former compile to native machine code ahead of time for maximum runtime speed, while the latter execute source-level representations without producing a standalone binary, trading speed for immediacy and portability. Lisp pioneered the approach with its eval function which traversed S-expressions directly, and later formalised this into the read-eval-print loop (REPL) for interactive development. Modern interpreters (§3.1 P2 onward) typically compile to bytecode first, but the defining characteristic remains execution without ahead-of-time machine code generation. Interpreters also enable runtime dynamism (e.g. eval(“2+3”), exec(“x=10”), getattr(obj, “method”)) that AOT compilation cannot structurally support.

Early interpreters were tree-walking and traversed the AST recursively with per-node pointer-chasing overhead. Bytecode compilation replaced tree traversal with sequential dispatch, reducing per-instruction overhead. Just as machine code is bound to a specific ISA, bytecode is bound to a specific virtual machine (VM). Unlike an ISA, however, a VM is software and can be ported to any platform. Java (1995) popularised the model with its Java Virtual Machine (JVM) that became a compilation target of other languages (e.g. Scala, 2004). Register-based VMs (e.g. Lua) encode operand locations in each instruction, and stack-based VMs (e.g. JVM, CPython) push and pop operands on an implicit stack.

In particular, CPython (1991) serialises its bytecode into .pyc files as a sequence of operation codes (opcodes) paired with operands. Each opcode is a low-level instruction analogous to an assembly mnemonic (e.g. LOAD_FAST, BINARY_ADD, RETURN_VALUE), and its operand indexes into the code object’s tables (constants, variable names, or nested code objects). Compiled .pyc files are cached in __pycache__/ (PEP 3147), and CPython skips recompilation when the source file has not changed. Runtime type resolution on every operation makes CPython roughly 10-100x slower than compiled C for CPU-bound logic, though the gap narrows for I/O-bound workloads where wait time dominates execution.

• [src]

More explicitly, the compilation entry point (i.e. _PyAST_Compile in Python/compile.c) transforms the AST into a struct PyCodeObject that encapsulates the bytecode sequence (co_code), constants (co_consts), variable names, and closure references for a single code block (e.g. function, class). The Python virtual machine (PVM) executes bytecode in a dispatch loop (i.e. _PyEval_EvalFrameDefault in Python/ceval.c). Each iteration reads one opcode, dispatches via computed gotos to the corresponding handler (e.g. LOAD_FAST fetches a local variable and pushes it onto the operand stack), and advances the instruction pointer.

The PVM must also track runtime state while the dispatch loop executes instructions. For a function call, it creates a frame linked to its caller (f_back) and its bytecode (f_code), forming a linked list that mirrors the call stack. This is why CPython needs the reference-counting collector (§1.3), and why closures (§1.1, for capturing state), generators (PEP 255, for lazy iteration), and coroutines (PEP 492, for async I/O) can outlive the C stack. Each frame contains its own operand stack (the localsplus array), which is where the stack-based bytecode instructions push and pop values during execution.

• [src]

The adaptive interpreter (PEP 659) narrows the dispatch overhead by specialising frequently executed opcodes (e.g. BINARY_OP → BINARY_OP_ADD_INT), but does not close it for compute-heavy workloads. In practice, performance-critical Python bypasses the interpreter entirely through C extensions: NumPy delegates linear algebra to BLAS/LAPACK, PyTorch dispatches to CUDA kernels, and the standard library itself wraps C implementations (e.g. json, re, hashlib), with bindings via CPython’s C API, ctypes/cffi, Cython, or pybind11. Python handles orchestration while heavy computation runs at native speed, which is why it dominates ML and scientific computing despite its interpreter overhead.

• [src]

3.2. JIT Compiler

Even with adaptive specialisation (§3.1), bytecode dispatch remains the bottleneck for compute-heavy workloads. Just-in-time (JIT) compilation addresses this by compiling frequently executed code paths (“hot spots”) to native machine code at runtime, deferring the cost until the program’s actual behaviour reveals which paths are worth optimising. The Java Virtual Machine’s HotSpot compiler (1999) and the V8 engine for JavaScript (2008) pioneered multi-tiered JIT strategies, where code begins interpreted and is progressively compiled at higher optimisation levels as execution counts rise.

A JIT compiler instruments the interpreter to count how often each function or loop body executes. Once a threshold is crossed, the runtime compiles that region from bytecode (or an internal IR) into native machine code, patches the call site to jump directly to the compiled version, and subsequent invocations bypass the interpreter entirely. Because the JIT observes runtime types and values, it can apply speculative optimisations (e.g. inlining a method based on the observed receiver type) that an AOT compiler cannot. If an assumption is later violated, the JIT performs deoptimisation, discarding the compiled code and falling back to the interpreter for that path.

PyPy addressed CPython’s lack of JIT with a tracing JIT that records linear traces through hot loops rather than compiling entire functions, achieving 4-10x speedups but requiring a separate Python implementation. CPython 3.13 (2024) introduced an experimental copy-and-patch JIT (PEP 744) within CPython itself, choosing fast compilation and low implementation complexity over peak performance by copying precompiled templates and patching operand slots. GraalPy, built on the GraalVM framework, prioritises peak throughput via partial evaluation of the interpreter itself, at the cost of higher warm-up time and memory.

• [src]

---