A programming language specifies how programs are written and what their execution means. Its type system describes which operations may be combined; an abstract syntax tree records the structure on which these rules act. The examples under type system use a small teaching language with integers, Boolean values and function types.
// Target: computer-science.bigb
A conversion inserted by the language's typing rules rather than an explicit conversion call in source code. Its availability depends on scope and the conversion rules; converting a method receiver and converting an argument are distinct uses. In Scala, an imported implicit conversion can supply a rational-number receiver for an integer expression lacking an applicable multiplication overload.
A language-defined conversion from a numeric type to another admitted numeric type, such as Scala's conversion of an Int argument to Double. It can make an overloaded method applicable even when the argument's static type differs from the parameter type. It does not imply a subtyping relationship between every pair of numeric types or exact representation of every source value; sufficiently large integers can lose precision in a floating-point target. [ref]
A call whose result is returned directly, with no further computation waiting in its caller. Its caller's activation record can therefore be replaced rather than retained. A recursive tail call gives tail recursion; an explicit loop updating the current arguments performs the same control transfer without requiring compiler optimization.
Probabilistic programming expresses a probability model as an executable program with random choices and observations. Executing the generative part induces a probability distribution; observations then restrict or weight executions, and inference computes the resulting conditional distribution. Program syntax and inference algorithm are separate choices: the same model can be evaluated by rejection sampling, importance sampling or Markov chain Monte Carlo.
A stochastic computation graph is a Directed acyclic graph combining deterministic transformations, random choices and costs. The changing probabilities of random choices contribute score-function gradient estimators, while differentiable deterministic paths contribute pathwise gradients. This accounts for both sources of a parameter's effect on an expected cost.[ref]
A probabilistic program maps elementary random choices to outputs and observation weights. Its mathematical meaning can be specified by the pushforward measure on outputs, normalized after conditioning when the observation has finite positive mass. Different random-choice spaces can implement the same output law.
Let a model have parameter prior density , observation probability and conditional binary-query probability after observation. Draw and an independent uniform random variable . Accept exactly when , then output whether . At fixed , the accepted true and false intervals have lengths and . Integrating against and dividing by the positive evidence proves equality of the joint posterior law of parameters and answer. This can replace many latent choices by one auxiliary coordinate. It preserves that joint law, not unreported latent traces. More generally the bounded factor must be a probability or first be divided by a valid common rejection envelope.
Selecting a branch and binding components according to a value's constructor structure. In Haskell, matching a constructor can demand the outer constructor without demanding every field; a failed or undefined match has distinct consequences from an irrefutable pattern.
A pattern that does not force its matched value merely to establish the match. A Haskell pattern written with ~ can defer evaluation of a recursive pair until one component is demanded. This can preserve productivity in definitions involving lazy evaluation. It does not make every later use of the components terminate.
A systems programming language supporting explicit memory access, arrays, and implementation-dependent integer widths. Signed integer overflow is not generally specified as modular arithmetic; correctness arguments must state the relevant range assumptions.
Volatile-qualified objects in C are objects whose accesses must follow the implementation's observable-access rules even when the optimizer cannot see an ordinary program dependency. They are commonly used for device registers and state changed by an interrupt handler, under the target compiler's embedded execution model. volatile does not by itself provide atomic multiword access, mutual exclusion or inter-thread synchronization. Protecting a shared snapshot still requires a suitable critical section or another synchronization protocol.[ref]
For a -bit unsigned integer type without padding, C programming language arithmetic on that type reduces results modulo . In particular, subtracting two uint32_t timestamps gives their modular difference when that subtraction is evaluated in the 32-bit unsigned type. Integer promotions must be checked for narrower types or unusual implementations. Signed integer overflow has different rules and must not be treated as the same operation.[ref]
A programming language expressing machine instructions through symbolic operation names, processor registers, labels and data directives. A concrete program must respect its instruction set's operand restrictions and the platform's calling convention.
A program that translates assembly language into machine code. A pseudo-instruction can expand into several instructions, for example to construct a constant that cannot fit one immediate operand.
An assembler convenience that expands into one or more actual machine instructions. Its expansion matters when counting instructions, reasoning about temporary registers, or filling a branch delay slot.
The agreement between a caller and a subroutine on argument and result placement, processor register preservation, and call stack organization. Callee-saved registers retain their incoming values across a call; caller-saved registers must be saved by the caller if their values are still needed afterwards.
The result a called procedure supplies to its caller on returning. A calling convention specifies the processor register or memory location carrying it, separately from the return address, which identifies where execution resumes. In the elementary MIPS architecture convention, an integer result is placed in $v0, while $ra carries the return address.
The saved instruction address at which execution resumes after a function returns. A recursive call must preserve the current return address before another call overwrites the link register.
The 32-bit calling convention for the ARM architecture family. Its base variant passes initial arguments in r0–r3, returns a word in r0, preserves r4–r8, r10, r11, and sp, and requires eight-byte stack pointer alignment at public calls.[ref]
A processor register that a subroutine may overwrite. A caller retaining a live value in such a processor register must preserve it elsewhere before calling. Argument and result processor registers commonly have this role.
A processor register whose incoming value a called subroutine must restore before returning if it modifies it. This lets a caller retain live values across calls, but the caller must in turn preserve its own caller's values when using these processor registers.
A type representing a finite sequence of characters or other specified text units. Its indexing and encoding conventions depend on the language. Immutable strings can be shared safely by a saved snapshot because later replacement of a variable does not mutate the saved string's contents.
A programming language supporting object-oriented programming and functional programming. Its traits support reusable mixin behavior, while type variance controls how parameterized types participate in subtyping. The Scala 2 and Scala 3 language versions differ in some syntax and typing details; examples should state the version relevant to a particular claim. Official documentation: docs.scala-lang.org
A Scala wrapper library for Java Swing interfaces. Its event system uses publishers, reactors and partial-function reactions. The examination supplies the central subscription and publication contract; archived and current official documentation corroborate that design without identifying an exact installed course library build.
The function zip :: [a] -> [b] -> [(a,b)] pairs corresponding list positions, stopping when either input ends. Pairing a finite list with [0..] attaches its zero-based indices without constructing an infinite result. With the unbounded Integer index type this avoids index overflow for arbitrarily long finite inputs.
The higher-order function takeWhile :: (a -> Bool) -> [a] -> [a] retains the longest initial segment whose elements all satisfy its predicate. It stops at the first failure and does not resume later. Thus it differs from a list filter, which tests later elements as well.
The higher-order function iterate :: (a -> a) -> a -> [a], satisfying iterate f x = x : iterate f (f x). Its result begins with the initial value and continues with successive applications. Lazy evaluation permits finite prefixes of this infinite list to be observed whenever the necessary applications terminate.
The higher-order function with type (a -> [b]) -> [a] -> [b] and value concat (map f xs). It replaces each input element by a list and concatenates those lists in input order. A direct definition is concatMap f = foldr (\x rest -> f x ++ rest) []. This formulation processes an input element's produced list once; it need not repeatedly append an already accumulated output prefix.
A partially applied infix operator: (a op) means \x -> a op x, and (op b) means \x -> x op b, subject to Haskell's syntax rules. In particular, (f .) maps a function g to the function composition f . g. Composing such a section with a curried binary function composes at two argument levels: ((f .) . g) x y = f (g x y) on total inputs.[ref]
The automatically available standard module of Haskell, supplying basic types, classes and operations such as list folds, arithmetic and list comprehension support. A program can explicitly hide an imported name when providing an alternative definition. The reference definitions specify behavior, rather than requiring a particular implementation strategy.[ref]
R is a programming language and environment for statistics, data analysis and graphics. For matrix algorithms, drop = FALSE preserves dimensions when extracting submatrices. To choose an element uniformly from a possibly singleton numeric vector indices, use indices[sample.int(length(indices), 1L)]: sample(indices, 1L) has a special interpretation when its first argument is a single positive number. Official documentation: Extraction and the drop argument and Sampling, including the singleton numeric argument rule.
For a binary operation , its Cartesian lifting sends lists to the list comprehension , with the right generator varying fastest. On finite lists this preserves associativity but need not preserve commutativity or idempotence, because list order and repeated entries matter.
A programming language whose program is an ordered list of positive rational numbers. Starting with a positive integer, multiply by the first listed fraction that produces an integer, then repeat; halt if none applies. Encoding registers as prime exponents relates this operation to a register machine.
A word selecting specified binary positions under a bitwise operation. To extract a stored bit at position , logically shift by and combine with the mask 1. Grouping thirty-two cells into one Java integer permits a compact representation of a Conway Game of Life board.
// Destination: computer-science.bigb
For a bit mask , the update visits its nonzero submasks in decreasing order. Every submask uses only positions set in , so a mask with set bits has submasks including zero.
A bitboard represents occupied positions on a finite board by the bits of an integer. Bitwise operations combine occupancy masks and test whether pieces overlap.
Bitwise OR combines binary representations position by position: an output bit is one exactly when at least one input bit is one. On bit masks representing sets, it computes their union.
A fixed-width left shift discards high bits and inserts low zeros. A logical right shift inserts high zeros; an arithmetic right shift propagates the sign bit. In Java, <<, >>> and >> distinguish these operations. Left shift by is multiplication by modulo the word modulus.
// Destination: computer-science.bigb
A bit rotation cyclically moves the bits of a fixed-width machine word: positions discarded at one end reappear at the other. A logical shift instead fills vacated positions with zero and discards outgoing bits. Consequently they have different wiring at the edge of a barrel shifter.
An arithmetic right shift propagates the sign bit into the vacated high positions. For a signed two's complement integer, its result is division by rounded down. This differs from C integer division on negative nonmultiples of , because that quotient truncates towards zero. Shifting an -bit word arithmetically by produces zero for a nonnegative value and the all-one word, representing , for a negative value.
A logical right shift moves bits toward less significant positions, discards those shifted out, and fills the high positions with zero. On the unsigned interpretation of a machine word, it computes the quotient in integer division by . Indeed, splitting the binary representation after its lowest bits gives with ; the retained upper bits represent . A fixed-width left bit shift by followed by a logical right shift by extracts precisely the low bits, giving the remainder.
A bit shift toward more significant positions, filling low positions with zeros. On an unbounded nonnegative integer, shifting left by places multiplies it by ; fixed-width representations may discard overflowing high bits.
For a fixed word width , signed integers have the same bit patterns as residues modulo . The leading bit has negative positional weight in the signed interpretation. Reading the same bits as unsigned gives for a negative signed integer .
// Destination: computer-science.bigb
To widen an -bit two's complement integer to bits, preserve the original low bits and fill the new high positions with the old sign bit . The change in signed positional weights is , so the represented signed value is unchanged. Zero extension instead preserves the unsigned interpretation, and changes the signed value of negative inputs.
Base-sixteen representation, with digit values zero through fifteen conventionally written 0 through 9 and a through f. A group of four binary digits selects one hexadecimal digit.
// Destination: computer-science.bigb
An abstract syntax tree is a rooted tree recording the meaningful syntactic pieces of a program and how they fit together. A program identifier such as x, a literal value such as 2, and a node representing addition have different roles. Their arrangement answers structural questions: which program expression supplies an operand, which name is a variable assignment target, and which construct encloses another. This makes an abstract syntax tree useful to a compiler, an interpreter, and the type system that checks a program.
The word "abstract" describes what is omitted. Lexical analysis first recognizes lexical tokens, such as x, =, 2, +, 3, *, 4. A concrete parse tree can retain grammar derivation structure, including punctuation and intermediate context-free grammar categories such as expression, term and factor. An abstract syntax tree usually keeps the operation and its operands without all those grammar scaffolds. Parentheses can determine its shape without surviving as separate nodes. A parser may construct the abstract syntax tree directly; it need not first allocate a concrete parse tree.
An abstract syntax tree records programming language syntax, but does not by itself supply all programming language semantics. In a+b, the names do not reveal their current values, and + might perform addition of integers or concatenate strings. The programming language rules, name bindings, and operand types determine the meaning. In Python, successfully calling ast.parse also does not guarantee that later compilation will accept the result: parsing return 42 succeeds, but compiling that statement outside a function fails. [ref]
An abstract syntax tree is not machine code. Its nodes describe language constructs. A compiler can check and transform this structure before translating it into executable instructions; an interpreter can evaluate an appropriate tree directly. The little evaluator below demonstrates this distinction without pretending to implement an entire programming language.
The syntax tree of a logical formula records its recursive construction. A propositional variable is a leaf, negation has one child, and binary implication has an ordered pair of children. A subformula occurrence corresponds to a node together with the subtree rooted there. Different occurrences may have identical formula strings.
The unique readability theorem asserts uniqueness of the outer formation rule and its immediate components in a logical formula. For the fully parenthesized language with negation and implication, every formula is uniquely a variable, a negation of one formula, or an implication between an ordered pair of formulas. It gives a well-defined syntax tree and licenses recursive definitions and structural induction on formulas.
In the grammar , no logical formula is a proper initial segment of another. A recursive parser reads one variable, or a negation followed by one formula, or a parenthesized pair of formulas separated by implication. Structural induction shows that this parser consumes precisely one whole formula. Its deterministic stopping position proves prefix-freeness. Consequently any formula substring in a valid formula coincides with the formula of a syntax subtree.
Consider Python programs x=2+3*4 and x=(2+3)*4. Operator precedence places multiplication inside the right operand of addition in the first abstract syntax tree. The parentheses instead place addition inside the left operand of multiplication in the second. Their right-hand sides evaluate to and . No rule that simply reads all operators left to right would recover both structures. [ref]
Figure 1.
Two abstract syntax trees for variable assignment: operator precedence gives x=2+3*4 the value , while parentheses give x=(2+3)*4 the value
. Details.
These are schematic views of Python trees: Module is omitted, and the Add/Mult and Store markers are written inside their owning nodes. In the actual schema, BinOp has left, op and right fields; Assign has a list of targets and a value. Name(id='x', ctx=Store()) marks the name as a variable assignment target. Reading x in a program expression instead uses Load. A variable assignment is a statement, not an equation asserting that two values are equal. [ref]
A restricted recursive evaluator can follow those fields. It accepts only integer literal values and binary addition, subtraction and multiplication; the surrounding variable assignment remains a separate action. Using type(value) is int excludes Boolean constants, even though Python treats bool as a subclass of int.
import ast

OPS = {ast.Add: lambda a, b: a + b,
       ast.Sub: lambda a, b: a - b,
       ast.Mult: lambda a, b: a * b}

def evaluate(node):
    if isinstance(node, ast.Constant) and type(node.value) is int:
        return node.value
    if isinstance(node, ast.BinOp) and type(node.op) in OPS:
        return OPS[type(node.op)](evaluate(node.left), evaluate(node.right))
    raise ValueError("outside the integer-expression language")

for source in ("x=2+3*4", "x=(2+3)*4"):
    tree = ast.parse(source, optimize=0)
    statement = tree.body[0]
    print(statement.targets[0].id, evaluate(statement.value))
# x 14
# x 20
The children in a rooted tree have ordered roles: left and right cannot be interchanged. For subtraction, 8-3 gives while 3-8 gives . Operator associativity also matters: 8-3-1 parses as (8-3)-1, giving , whereas 8-(3-1) gives . Here the syntax groups operators to the left; this does not assert the mathematical associativity of subtraction. Operator precedence determines grouping, rather than a general permission to reorder execution. For example, Python evaluates the calls in f()+g()*h() in the order f, g, h, although the multiplication result must be ready before the outer addition. [ref]
An abstract syntax tree traversal systematically visits its nodes. A depth-first traversal of a tree that processes each child before its parent is called postorder. For the program expression 2+3*4, the schematic postorder is 2, 3, 4, Mult, Add. This order lets an evaluator obtain each operand value before applying its operation. A traversal of the entire Python schema additionally visits marker nodes such as Add and Store; this shorter list concerns only the expression nodes drawn in the figures. Visiting an abstract syntax tree is a structural operation, and is not a general model of execution: a conditional may select only one branch, while a structural visitor examines both.
An abstract syntax tree transformation replaces or rearranges nodes. It can simplify a program expression, insert instrumentation, or translate a language construct into simpler constructs. When intended to preserve programming language semantics, it must preserve the relevant observable behavior, including values, side effects, and failures. A changed tree can be structurally valid while changing the program's meaning.
Constant folding replaces a program expression whose value is known during translation by a literal value. For x=2+3*4, first replace the multiplication subtree by Constant(value=12), then replace the addition subtree by Constant(value=14). The variable assignment and its Store target survive: the result still assigns to x. This illustrates why a bottom-up abstract syntax tree traversal is convenient: replacing one child can make its parent eligible for the next replacement.
Figure 1.
Constant folding and postorder abstract syntax tree traversal for 2+3*4: replace by , then by
. Details.
Here is a deliberately small Python transformer. Calling generic_visit first transforms the children; returning a node replaces the visited node. The location helpers retain or supply the metadata expected for compilation. [ref]
class FoldIntegers(ast.NodeTransformer):
    def visit_BinOp(self, node):
        self.generic_visit(node)
        if (isinstance(node.left, ast.Constant)
                and isinstance(node.right, ast.Constant)
                and type(node.left.value) is int
                and type(node.right.value) is int
                and type(node.op) in OPS):
            value = OPS[type(node.op)](node.left.value, node.right.value)
            return ast.copy_location(ast.Constant(value=value), node)
        return node

tree = ast.parse("x=2+3*4", optimize=0)
folded = ast.fix_missing_locations(FoldIntegers().visit(tree))
namespace = {}
exec(compile(folded, "<folded example>", "exec"), namespace)
assert namespace["x"] == 14
assert ast.unparse(folded) == "x = 14"
This transformer folds literal integer operands only. It leaves a+3*4 as a+12, without inventing a value for the program identifier a. It leaves calls intact: replacing 0*f() by 0 could discard a side effect or a failure. Nor does it reassociate floating-point arithmetic, where changing parentheses can change rounding. For the supported integer arithmetic, a short structural induction explains correctness: a retained literal value has the same value; at each folded binary node, the already-correct child values are combined by exactly the original operation in the original left/right order. This claim concerns the supported fragment's values, not unrestricted equivalence of arbitrary Python programs.
An abstract syntax tree can retain source locations even while omitting punctuation nodes. Python records one-based line numbers and zero-based UTF-8 byte offsets, with the end offset exclusive. In x=2+3*4, the multiplication node spans offsets through , and ast.get_source_segment returns 3*4. A copied location on a folded 12 describes the original span, not text newly present in the source. Such metadata supports error messages and editing tools without making an abstract syntax tree a lossless record of formatting. [ref]
// Target: computer-science.bigb
The rules for forming programs in a programming language. A parser checks and structures text according to these rules; an abstract syntax tree records the resulting constructs.
A language construct defined by expansion into other constructs. Its direct semantic equation can be derived by substituting the expansion into the existing programming language semantics.
Recognition of lexical tokens in program text before or during parsing.
A categorized piece of program text, such as a program identifier, a numeral denoting a literal value, or an operator symbol. Its spelling and category help a parser recognize the larger construct.
A parser recognizes how text fits a programming language syntax and can construct a parse tree or abstract syntax tree.
The recognition process performed by a parser, producing a structural description of text according to a programming language syntax.
A name used by a program, such as x in a variable assignment. An abstract syntax tree can record the name without determining which value it denotes.
A value written directly in program text, such as an integer numeral or a quoted string, rather than obtained through a program identifier. Distinct spellings can denote the same value.
A program construct that is evaluated to obtain a value, potentially with side effects or failure. An arithmetic mathematical expression is one example; its abstract syntax tree records how operands and operations nest.
The syntactic priority that resolves grouping when different operators occur together without parentheses. It determines the abstract syntax tree shape before evaluation.
The syntactic grouping convention for successive operators of the same precedence. Left grouping of subtraction makes a-b-c mean (a-b)-c; it does not make subtraction an associative operation.
A program action that associates a value with a target name. For Python x=2+3*4, evaluate the right-hand program expression and bind x to its result. [ref]
For an update , compute from , the values before any mutation. Stable snapshots ensure self-addition doubles the old value and self-subtraction produces zero. Building a replacement representation privately and committing it once can additionally preserve the receiver if validation or checked arithmetic fails. This makes the meaning of an update independent of iteration order and aliasing between its operands.
The meaning of constructs in a programming language, including their permitted values and execution behavior. Programming language syntax organizes constructs; a type system and execution rules give further constraints and meaning.
A mapping from identifiers to their semantic values. A programming closure retains its defining semantic environment; extending it for parameters preserves lexical scope and lets those parameters shadow outer bindings.
A representation of the rest of a computation. In continuation-passing style, a computation receives a function telling it how to use its result. An explicit computer memory argument can be supplied when the continuation is invoked, so capturing control need not capture a snapshot of computer memory.
A computation that can suspend and later resume. A first-class continuation can represent its suspended control state while mutable computer memory remains shared.
Tasks transfer control at explicit suspension points. A FIFO queue of runnable continuations implements round-robin scheduling; a task that never transfers control can prevent others from running.
A continuation represented as an ordinary language value that can be stored and later invoked. Whether it may be invoked once or repeatedly, and whether mutable program state is restored, are separate semantic choices.
Supply the current continuation to a user function. A language can expose this as an escape function or as a separate continuation value with its own invocation primitive; those interfaces need corresponding semantic definitions.
Pass the remaining computation explicitly as a continuation. Returning a value means invoking that continuation; a different control destination can be selected by invoking a different continuation.
A variable used within a procedure but declared outside it. Under lexical scope, its binding is determined by enclosing declarations and the associated runtime environment, often accessed through a static chain or programming closure.
Name resolution determined by the nesting of declarations in the source program. An activation of a nested procedure obtains its nonlocal variables from its defining environment, which can differ from the newest activation of the same enclosing procedure when procedural parameters are used.
A suspended computation together with the information needed to evaluate it later. In lazy evaluation by need, forcing a thunk computes and records its result, so subsequent demands can reuse it. Deferral and memoization are distinct: a merely delayed computation need not share its result unless its evaluation mechanism provides that sharing.
The convention relating a procedure's formal parameters to its arguments. Copying a large array at every recursive call can dominate running time, even when the procedure never modifies the argument.
Evaluate argument expressions before invoking a function. A monadic interpreter must also specify the order of those evaluations when its computational monad represents effects.
A parameter initialized from the actual argument's value. Whether passing an aggregate copies all elements or merely a reference is language-dependent; in whole-array copying semantics, a length- argument costs per call. This differs from a language that passes an object reference by value.
A parameter that designates the caller's actual storage, rather than a complete copied value. Read-only algorithms may use reference parameters to avoid copying, while their correctness arguments still prohibit writes. The VAR convention used in Oberon exam pseudocode has this purpose.
Evaluation that skips a later operand once an earlier operand determines the result. In Scala, p != null && p.field == x does not dereference p when it is null, and i < n && a(i) != x avoids an out-of-range access at . The order is part of the safety argument: exchanging these operands can preserve a Boolean formula in mathematics while changing whether a program raises an exception.
Evaluation delayed until a result is demanded, with sharing of the delayed computation's result. A lazy list can expose a constructor before computing its tail; this permits productive infinite structures and lazy feedback streams. A non-strict language can implement its semantics this way without making every function non-strict.
Represent a cursor by an underlying consuming iterator plus an optional cached head. Without a cache, its abstract sequence is the iterator's sequence; with cached , it is concatenated with the remaining iterator sequence. current fetches and caches exactly one value when needed, repeated reads reuse it, and advance discards it. Availability testing need not fetch a value, and construction need not query the input. This avoids forcing a future stream element that the client may never request.
An undefined or nonterminating computation in the denotational account of Haskell. A structured value may contain bottom values while retaining a defined outer constructor: undefined : [] is distinguishable from an entirely undefined list.[ref]
A description of the information needed to determine a program's next permitted step. In the summation loop verification, this includes the current variable values and the position in the instructions.
An integer arithmetic result outside the range of its chosen representation. A programming language may specify wrapping, trapping or another behavior; a proof over mathematical integers must account for that difference.
A system of rules for proving Hoare triples by following a program's structure. Variable assignment, sequential composition and loops have corresponding proof obligations.
A partial correctness claim connecting a precondition , a program and a postcondition : every terminating execution begun with ends with . State separately whether total correctness is intended.
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.
Choosing target-machine instructions to implement an intermediate representation. A memory operand using register-offset addressing can cover both an address addition and a load or store; computing the full address into a temporary variable can prevent that covering and add an unnecessary instruction.
Analysis of whether two accesses may designate the same storage location. Common subexpression elimination must not reuse a previously loaded value after a store that might change that location, unless an additional argument justifies it. A saved memory address can remain valid even though a value previously loaded at that address is invalidated.
A transformation that computes a repeated program expression once and reuses its saved result when the value is known not to have changed. A repeated load can be reused only when intervening stores, calls or other changes cannot alter the relevant location. Alias analysis helps establish that fact. Maximal address sharing can be counterproductive if instruction selection could otherwise fold an address addition into register-offset addressing.
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.
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 .
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 in the specified integer arithmetic. Together these facts explain agreement for every integer input, rather than merely agreement for one trial.
Articles were limited to the first 100 out of 278 total.

Ancestors (2)

  1. Computer science
  2. Home

Incoming links (28)

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)

Programming language by Ciro Santilli 40 Updated 2025-07-16
View more
A language that allows you to talk to and command a computer.
There is only space for two languages at most in the world: the compiled one, and the interpreted one.
For 2020 now, when you have a choice, you must go for:
Those two are languages not by any means perfect from a language design point of view, and there are likely already better alternatives, they are only chosen due to a pragmatic tradeoff between ecosystem and familiarity.
Ciro predicts that Python will become like Fortran in the future: a legacy hated by most who have moved to JavaScript long ago (which is slightly inferior, but too similar, and with too much web dominance to be replaced), but with too much dominance in certain applications like machine learning to be worth replacing, like Fortran dominates certain HPC applications. We'll see. Maybe non performance critical scripting languages are easier to replace.
C++ however is decent, and is evolving in very good directions in the 2010's, and will remain relevant in the foreseeable future.
Bash can also be used when you're lazy. But if the project goes on, you will sooner or later regret that choice.
The language syntax in itself does not matter. All that matters is how many useful libraries and tooling it has.
This is how other languages compare:
Read the full article
See all articles in the same topic Create my own version