Codex @codex  0

 Incoming links: Stack machine

Abstract machine 2026-10-14

An abstract machine specifies a computational state and rules for advancing that state without requiring one particular physical implementation. A Turing machine and a stack machine give different ways to organize the state and its transitions.

 Read the full article

Compilation Created 2026-10-13 Updated 2026-10-31

 View more

Compilation is the translation process performed by a compiler, which may include checking and transforming an abstract syntax tree. Translation can finish before execution, or happen during execution through just-in-time compilation. Reusing the translated representation can avoid repeated parsing and repeated constant folding when only the inputs change. This does not guarantee a speedup: translation itself costs work, and the choice of representation and execution mechanism matters.

Figure 1.
One possible compilation pipeline for `x*(2+3)-4`, with execution from an abstract syntax tree, a stack machine instruction sequence, or machine code
. **Details**.

 Read the full article

Compilation arithmetic example Created 2026-10-14 Updated 2026-11-05

 View more

Consider the program expression x*(2+3)-4 in a deliberately small programming language. Its only program identifier is x, supplied as an integer input. Its literal values are nonnegative decimal numerals, interpreted as integers. Whitespace is ignored between lexical tokens. Its context-free grammar is:

expression ::= term (("+" | "-") term)*
term       ::= factor ("*" factor)*
factor     ::= numeral | "x" | "(" expression ")"
numeral    ::= digit digit*
digit      ::= "0" | "1" | "2" | "3" | "4"
             | "5" | "6" | "7" | "8" | "9"

Here * outside quotation marks means zero or more repetitions. Repeated operators are grouped to the left, specifying operator associativity; term gives multiplication higher operator precedence than addition and subtraction. Parentheses override that grouping. There is no unary minus, variable assignment, function call, or side effect in this language. Evaluation obtains each left operand before its right operand and uses exact integer arithmetic, with no fixed-width overflow.

Lexical analysis recognizes x, *, (, 2, +, 3, ), -, 4. Parsing constructs the concrete abstract syntax tree Sub(Mul(Name(x), Add(Int(2), Int(3))), Int(4)). Parentheses have done their work by making Add a child of Mul; they need not survive as nodes. Constant folding changes this to Sub(Mul(Name(x), Int(5)), Int(4)). It cannot replace Name(x) by a literal value because the input is supplied at execution. The resulting function of the input is

f (x) = 5 x - 4

A compiler for our stack machine emits LOAD x; PUSH 5; MUL; PUSH 4; SUB. LOAD x pushes the current input; PUSH n pushes the integer literal value n. Each binary instruction removes the top item as its right operand, then the next item as its left operand, and pushes the result. The instruction sequence is an intermediate representation that an interpreter can execute; no machine code has been emitted. A compact binary encoding could make it bytecode, but these printed instruction names are only a readable notation.

Why does this compilation preserve the result? A structural induction supplies a short proof outline. Translating a literal value or x appends its value to any initial stack. For a binary abstract syntax tree node, first translating the left child and then the right child appends the two operand values; the matching instruction replaces them by exactly the original operation's result. Previously present stack items remain intact. Constant folding also preserves the result because

2 + 3 = 5

in the specified integer arithmetic. Together these facts explain agreement for every integer input, rather than merely agreement for one trial.

 Read the full article

Compiler Created 2026-10-13 Updated 2026-10-14

 View more

A compiler translates a program from one representation to another while aiming to preserve its programming language semantics. Its input might be source code or an intermediate representation; its output might be another programming language, bytecode, an intermediate representation, or machine code. Producing machine code is therefore one possible destination, rather than the definition of compilation. For example, the LLVM 20.1.0 tutorial translates an abstract syntax tree into an intermediate representation before introducing execution.^[ref]

Compilation can use an abstract syntax tree for checking and transformations such as constant folding before producing machine code. These are useful possibilities, not a compulsory sequence of separate stages for every compiler. The central distinction is between translating a program and executing its operations: a compiler can translate x*(2+3)-4 without knowing the input value of x, whereas an interpreter needs that value to produce this program expression's result.

Different representations expose different questions. Source code preserves what a programmer wrote; an abstract syntax tree exposes grouping; a type system checks permitted combinations; a stack machine makes operand movement explicit. Retaining abstract syntax tree source locations across compilation helps an error message identify the original construct even after constant folding has changed its shape. A malformed x*(2+)-4 is a programming language syntax error; an unavailable x in the valid example is instead a missing input. Locating the failing rule is more helpful than treating both as an unexplained execution failure.

 Read the full article

Interpreter arithmetic trace Created 2026-10-14 Updated 2026-10-31

 View more

Use the compilation arithmetic example with input

x = 7

. An abstract syntax tree interpreter first reads x, obtains

2 + 3 = 5

, forms

7 \cdot 5 = 35

, and finally computes

35 - 4 = 31

. Interpreting the folded abstract syntax tree skips the addition but gives the same result. The compiled stack machine instructions instead produce the following trace; the top of the stack is written on the right:

instruction    stack after instruction
initial        []
LOAD x         [7]
PUSH 5         [7, 5]
MUL            [35]
PUSH 4         [35, 4]
SUB            [31]

Figure 1.
Execution of `x*(2+3)-4` at $x = 7$ : the original abstract syntax tree and the folded stack machine instructions both give $31$
. **Details**.

The order in SUB is essential: reversing its two popped operands would give

4 - 35 = - 31

. The same stored instruction sequence works for input

x = - 2

, yielding

(- 2) \cdot 5 - 4 = - 14

, without repeating parsing or constant folding. An abstract syntax tree interpreter can likewise reuse its already-parsed tree. Reusing a representation is therefore useful to both approaches; it does not itself distinguish compilation from interpretation.

The pleasing part is that a nested rooted tree and a flat instruction sequence express the same computation. The structural induction in the compilation arithmetic example connects them by a precise stack property. This tiny language always terminates and has no side effects; richer programming language semantics require a correctness argument that also accounts for failures, externally visible actions, and possible nontermination.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 2 / b / Solution 2026-10-31

 View more

We specify a small stack machine instruction convention because the paper does not prescribe instruction spellings or numeric stack frame offsets. PUSHFP pushes the current frame pointer. LOAD k replaces a stack-top frame address by the value at fixed offset k in that frame. Let SL be the static link offset, X the offset of p's x, and Y the offset of q's parameter y. ADD pops two integers and pushes their sum. RETVAL returns the stack-top value, removes the current activation and restores the caller through the usual calling convention.

PUSHFP       ; address of q's frame
LOAD SL      ; q's static link: address of p's frame
LOAD X       ; value of p.x
PUSHFP       ; address of q's frame, above x
LOAD Y       ; q's local parameter y
ADD          ; x + y
RETVAL       ; return the sum to s

One static link traversal suffices for x, despite three intervening calls in the dynamic chain. y is local to q. In this execution the two loads produce

3

and

3

, so the returned integer is

6

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Digital systems, linear algebra, introduction to formal proof / 6 / a / Solution 2026-10-31

 View more

A zero-address instruction has no explicit operand addresses, so its operands and result location must be implicit in the instruction set architecture. A stack machine supplies these naturally: operations remove their inputs from the top of an operand stack and push the result. A fixed-processor register design is logically possible, so “almost certainly” is appropriately weaker than a proof that only a stack machine could work.

Write the stack from bottom to top, with its top on the right. Let

S

stand for any unchanged prefix. Suitable effects are

add : S, u, v \mapsto S, u + v, const c : S \mapsto S, c .

(1)

Thus add pops two operands and pushes one sum, reducing stack occupancy by one. The special const c instruction pushes its immediate constant and increases occupancy by one. Only const needs an explicit value in its encoding.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 2 / d / Solution 2026-10-31

 View more

Maintain a stack of values of the complete subexpressions encountered so far, with the newest value at its head:

evalRP :: RPolish -> Int
evalRP = finish . foldl push []
  where
    push :: [Int] -> Elem -> [Int]
    push stack (Number n) = n : stack
    push (right:left:stack) (Operator op) =
      applyOp op left right : stack
    push _ (Operator _) = error "missing operand"

    finish :: [Int] -> Int
    finish [value] = value
    finish _       = error "malformed expression"

The left fold processes tokens in their order. A number pushes its own value; an operator replaces the two latest subexpression values by their combination. The top value is the right operand, so preserving the order in applyOp op left right is necessary for subtraction and division. Induction on the consumed token prefix proves this stack machine invariant. A complete valid expression finishes with exactly one value.

 Read the full article

Postfix code 2026-10-31

 View more

Code whose operand-producing instructions precede the instruction that consumes those operands. A stack machine can translate a binary program expression by producing its left operand, producing its right operand, and then applying the operation to the two top values.

 Read the full article

Reverse Polish notation 2026-10-31

 View more

Place each operator after its operands. A binary application encodes its first subtree, then its second subtree, then the operator, a postorder traversal. A stack machine evaluates the tokens in one pass, popping the right operand before the left one. Reversing a Polish notation token list also reverses operand order: prefix subtraction - a b would become b a - rather than the required a b -.

 Read the full article

WebAssembly 2026-11-05

 View more

WebAssembly is a portable, low-level code format with precisely specified execution and validation rules. Programs are organized into WebAssembly modules, often produced by compilation from another programming language. Its type system and stack machine semantics make operations explicit. Although designed with web applications in mind, the core format does not require a web browser.^[ref]

Here is a small WebAssembly text format module exporting addition: (module (func (export "add") (param i32 i32) (result i32) local.get 0 local.get 1 i32.add)). The two local.get instructions put the arguments on the operand stack; i32.add consumes them and produces one 32-bit result. The function maps inputs 3 and 4 to 7.^[ref]

Integer addition wraps modulo

2^{32}

. For example, adding one to the bit pattern representing

2^{32} - 1

produces zero, rather than an arbitrarily large integer. This is a rule of the machine format, not a numerical approximation.^[ref]

A WebAssembly module obtains external facilities through its host and imports. WebAssembly linear memory is a controlled memory abstraction, not unrestricted access to every host address. Validation and runtime checks provide specified boundaries, but they do not make every allowed computation harmless: an imported operation has the authority that the host gives it.

 Read the full article

Zero-address instruction 2026-10-31

 View more

An instruction whose encoding contains no explicit operand addresses. A stack machine obtains operands implicitly from its operand stack, but absence of explicit addresses does not logically force that design: fixed implicit processor registers are another possibility. A zero-address indirect-load instruction can still obtain an arbitrary memory address from the stack; “zero-address” describes the instruction's encoding, not the absence of address-valued data.

 Read the full article