Language Design, Semantics and Conformance

Learning Objectives

Distinguish syntax from semantics; describe operational semantics (big-step and small-step), evaluation order, side effects and short-circuit evaluation.

Compare integer overflow, floating-point, equality and comparison, scoping, exception and concurrency semantics across languages.

Classify undefined, unspecified, implementation-defined and implementation-specific behaviour; use specifications, conformance suites, versioning, feature flags, deprecation and differential tests; reason about design trade-offs and formal models for a toy language.

Plain-Language Explanation

Two languages can look alike and still mean different things: 1 + 1 can wrap around, grow without limit or lose precision depending on the language; arguments may be evaluated left to right or in any order; some programs are simply not allowed to have a defined meaning. A language's semantics writes all of this down precisely so that every implementation behaves the same.

Precise Technical Explanation

Syntax versus semantics Syntax: which texts are programs (grammar). Semantics: what they mean (values, effects, errors).

Defines meaning by describing execution as rules over program states — the natural fit for interpreters (a tree-walker is an executable big-step semantics).

Big-step and small-step semantics Big-step (natural) semantics relates an expression directly to its final value: e ⇓ v. Small-step semantics rewrites an expression one step at a time: e → e' → … → v, exposing intermediate states, evaluation order and non-termination.

MiniLang, Java, C#, JavaScript and Python evaluate operands left to right; C and C++ leave many orders unspecified (and some unsequenced modifications undefined).

Effects (output, assignment, I/O) make evaluation order observable.

and/or (&&/||) evaluate the right operand only if needed — part of the semantics, not an optimisation.

Integer overflow semantics Wrap-around (Java int, C# unchecked, Wasm i32), exceptions (C# checked, Rust debug builds panic), arbitrary precision (Python), floating-point only (JavaScript numbers, MiniLang), or undefined behaviour (signed overflow in C/C++).

IEEE-754: rounding (0.1 + 0.2 != 0.3), NaN != NaN, signed zero, infinities; languages differ in which operations are strict and whether fused multiply-add is allowed.

Equality and comparison semantics Reference versus value equality, coercing (== in JavaScript) versus strict, NaN, string comparison by code units versus code points versus collation.

Lexical versus dynamic, block versus function scope (var versus let in JavaScript), hoisting, global creation on assignment.

Which operations throw, propagation order, finally interactions, exceptions in destructors.

Concurrency semantics overview Memory models define which writes reads may see across threads (JMM, C++11, ECMAScript's for SharedArrayBuffer) — see the Concurrency course.

Undefined, unspecified, implementation-defined, and implementation-specific behavior

Undefined (C/C++): no requirements at all — the compiler may assume it never happens. Unspecified: one of several allowed behaviours, not documented (C argument evaluation order). Implementation-defined: one of several, and the implementation must document it (size of int). Implementation-specific (informal): details outside the specification altogether (CPython bytecode).

Language specifications and conformance suites ECMAScript has Test262; Java has the TCK; WebAssembly has the spec test suite; Python relies on CPython's test suite and PEPs.

Versioning and compatibility Language versions (--release 21, <LangVersion>, "use strict", from __future__), runtime versions, and editions (Rust).

Feature flags and experimental language features Preview features (--enable-preview in Java), TypeScript and Babel proposals, CPython's free-threaded build: opt-in until stable.

The strongest constraint on language evolution (JavaScript "don't break the web").

Deprecation and migration Warnings, then removal over several versions, with migration tools (Python 2→3, Java module encapsulation).

PyPy versus CPython (GC timing, __del__), engines' Array.prototype.sort stability before ES2019, JIT-dependent floating-point (rare, but x87 historically).

Test suites and differential tests Conformance suites check the specification; differential tests compare implementations (Module 23).

Language design trade-offs Simplicity versus expressiveness, safety versus control, static versus dynamic checking, performance versus portability (MiniLang chose: no implicit conversion, 0 truthy, errors over Infinity).

Formal models for a toy language Write MiniLang's expressions as a small-step relation and execute it (below) — the basis for proofs and for generating tests.

Why It Matters in Real Systems

Semantics decide whether code is portable and correct: overflow bugs, floating-point surprises, evaluation-order bugs and undefined behaviour are classic sources of security issues and production incidents.

Key Terms

Big-step / small-step Whole-evaluation / one-step-at-a-time semantics No requirements on the implementation Implementation chooses and documents

Tests checking adherence to the specification Edition / version Unit of language evolution

Diagram, Execution Trace or State Transition

small-step reduction of (1 + 2) * (3 + 4), left to right:
  (1 + 2) * (3 + 4)
→ 3 * (3 + 4)
→ 3 * 7
→ 21

Syntax or Instruction Format

Inference-rule notation (illustrative):

e1 → e1'                       v1 + v2 = v (numbers)
-------------------- (ctx-L)     ---------------------- (add)
e1 + e2 → e1' + e2                     v1 + v2 → v

Complete Example

An executable small-step semantics for MiniLang-style arithmetic, printing every step (CPython 3.13.1):

Evaluation order and short-circuiting are observable through side effects (MiniLang, both back ends):

The same "add one to the largest integer" in four languages — four different semantics (Temurin JDK 21, CPython 3.13.1, Node.js 24.18 and MiniLang):

Undefined behaviour in C: signed overflow cannot happen in a valid program, so the optimiser may delete an overflow check written in terms of it (GCC 11.2 on WSL2 x86-64; the result is specific to this compiler and flags — that is the point):

def is_value(e):
    return isinstance(e, (int, float))


def step(e):
    """One left-to-right reduction step on (op, left, right) trees."""
    op, left, right = e
    if not is_value(left):
        return (op, step(left), right)
    if not is_value(right):
        return (op, left, step(right))
    if op == "/" and right == 0:
        raise ZeroDivisionError("stuck: division by zero")
    return {"+": left + right, "-": left - right, "*": left * right, "/": left / right}[op]


def show(e):
    return str(e) if is_value(e) else f"({show(e[1])} {e[0]} {show(e[2])})"


expr = ("*", ("+", 1, 2), ("+", 3, 4))
print("  " + show(expr))
while not is_value(expr):
    expr = step(expr)
    print("→ " + show(expr))
e = ("+", 1, ("/", 2, ("-", 3, 3)))
print("  " + show(e))
try:
    while not is_value(e):
        e = step(e)
        print("→ " + show(e))
except ZeroDivisionError as err:
    print(err)

((1 + 2) * (3 + 4))
→ (3 * (3 + 4))
→ (3 * 7)
→ 21
  (1 + (2 / (3 - 3)))
→ (1 + (2 / 0))
stuck: division by zero

fun trace(label, value) { print(label); return value; }
print(trace("left", 1) + trace("right", 2));
print(trace("A", false) and trace("B", true));
print(trace("C", nil) or trace("D", "fallback"));

left
right
3
A
false
C
D
fallback

public class Overflow {
    public static void main(String[] args) {
        int max = Integer.MAX_VALUE;
        System.out.println("Java int: " + max + " + 1 = " + (max + 1) + " (wraps)");
        try {
            Math.addExact(max, 1);
        } catch (ArithmeticException e) {
            System.out.println("Math.addExact: " + e.getMessage());
        }
        System.out.println("0.1 + 0.2 == 0.3? " + (0.1 + 0.2 == 0.3));
    }
}

Java int: 2147483647 + 1 = -2147483648 (wraps)
Math.addExact: integer overflow
0.1 + 0.2 == 0.3? false

print("Python int:", 2**63 - 1, "+ 1 =", 2**63, "(arbitrary precision)")
print("2**53 + 1 as float:", float(2**53 + 1), "| exact int:", 2**53 + 1)
print("nan == nan?", float("nan") == float("nan"))

Python int: 9223372036854775807 + 1 = 9223372036854775808 (arbitrary precision)
2**53 + 1 as float: 9007199254740992.0 | exact int: 9007199254740993
nan == nan? False

console.log("JS number: 2**53 + 1 =", 2 ** 53 + 1, "(not representable; rounds)");
console.log("BigInt: 2n**53n + 1n =", (2n ** 53n + 1n).toString());
console.log("'1' == 1:", "1" == 1, "| '1' === 1:", "1" === 1);

JS number: 2**53 + 1 = 9007199254740992 (not representable; rounds)
BigInt: 2n**53n + 1n = 9007199254740993
'1' == 1: true | '1' === 1: false

Line-by-Line Explanation

Small-step: each step reduces the leftmost reducible sub-expression; the printed sequence *is* the evaluation order. Division by zero leaves the expression "stuck" — the semantics' way of saying "runtime error".

MiniLang: left prints before right (left-to-right); B never prints (and short-circuits); D prints because nil is falsy.

Overflow: Java wraps (and offers Math.addExact); Python integers grow; JavaScript numbers lose precision above 2⁵³ (BigInt does not); MiniLang matches JavaScript's doubles but never converts strings.

C: with -O2, GCC treats x + 1 < x as always false (signed overflow is undefined, so it "cannot happen") and the UB-based check prints 0; the well-defined check prints 1.

Expected Output

As shown; the C result depends on the compiler and optimisation level.

Step-by-Step Runtime Behavior

(1 + 2) * (3 + 4): reduce the left operand to 3, then the right to 7, then the product to 21 — three steps.

Common Misconceptions

"Undefined behaviour means 'whatever the hardware does'." It means the compiler may assume it never happens.

"Floating-point is broken." It is precisely specified rounding arithmetic.

"Evaluation order is always left to right." Not in C/C++.

Common Bugs and Failure Modes

Overflow checks that rely on overflow, float equality comparisons, coercing equality in JavaScript, relying on unspecified order (C function arguments), assuming integer division and modulo signs agree across languages.

Corrected or Safer Patterns

Check before operating (or use checked/*Exact/__builtin_add_overflow), compare floats with tolerances or use decimal types, strict equality, explicit sequencing.

Debugging and Inspection Techniques

-fsanitize=undefined (UBSan) catches UB at run time; differential testing across implementations; small-step traces in teaching interpreters.

Performance Considerations

UB and unspecified behaviour give C compilers optimisation freedom; well-defined semantics (Java, Wasm) give portability at a small cost.

Security Considerations

Integer overflow and UB are root causes of many memory-safety vulnerabilities; prefer well-defined arithmetic and sanitizers in testing.

Portability and Version Caveats

Language versions change semantics deliberately (Python 3 division, ES2015 block scoping); the C example's output is compiler-specific.

Real-World Use Cases

Writing language specifications, conformance testing (Test262), compiler validation (CompCert's formal semantics), smart-contract languages with exact arithmetic.

Best Practices

Specify semantics before implementing, test them with executable models and differential tests, avoid UB, and document every implementation-defined choice.

Exercises

E1 · Beginner. What does MiniLang print for print(trace("x", true) or trace("y", false));?

Answer: x then true — or short-circuits on a truthy left operand, so y is never printed.

E2 · Intermediate. Classify: (a) C sizeof(long), (b) C argument evaluation order, (c) C signed overflow, (d) CPython's bytecode.

Answer: (a) implementation-defined, (b) unspecified, (c) undefined, (d) implementation-specific (outside the Python language specification).

E3 · Advanced challenge. Extend the small-step semantics with variables and let.

Answer: Make the state a pair (expression, environment); add a rule that steps a variable to its value from the environment and a let x = v in e rule that extends the environment and continues with e; values and stuck states are as before.

Quiz

? What does GCC at -O2 do with `x + 1 < x` for a signed int x?
+ It may treat it as always false, because signed overflow is undefined. :: The real run printed 0.
- It always evaluates it at run time with wrap-around. :: Not guaranteed.
- It reports a compile error. :: It compiles (warnings depend on flags).
- It converts x to unsigned. :: No.

? Which language's integers never overflow?
+ Python (arbitrary precision ints) :: They grow as needed.
- Java int :: Wraps.
- C int :: Undefined on overflow.
- JavaScript numbers :: Lose precision above 2^53.

? Which are semantics (not syntax)? (select all that apply)
+ Evaluation order of operands :: Observable through side effects.
+ Whether `and` evaluates its right operand :: Short-circuit rule.
- Whether `let` needs a semicolon :: Syntax.
+ What happens on division by zero :: Runtime semantics.

Summary and Key Takeaways

Semantics specify values, effects, order and errors — formally with big- or small-step rules, practically with tests and reference implementations. Overflow, floating point, equality, scoping and exceptions differ across languages; undefined, unspecified and implementation-defined behaviour must be known and avoided or documented.