Derived Semantics for Some Programming Language Constructs

Peter Henderson

TL;DR

Instead of proving a compiler matches a pre-existing formal specification, Peter Henderson proposes a "bottom-up" approach: define a simple stack machine and a translator, then mathematically derive the high-level language's meaning from its implementation. This allows researchers to evaluate if a language's behavior is "correct" by examining the functional descriptions that emerge from the code itself.

What Problem Does This Paper Address?

In the early days of formal computer science, proving that a compiler was "correct" was a Herculean task. The standard method (pioneered by John McCarthy) required you to first create a rigorous, abstract mathematical description of your source language's semantics a priori. Then, you had to prove that the machine code generated by your compiler behaved exactly like that abstract model.

Henderson argues that this is backwards. Defining high-level semantics from scratch is difficult and often arbitrary. He identifies a gap: can we instead define a language by how it is implemented on a hypothetical machine and then "extract" the math to see if it matches our intuition? This makes the implementation the "source of truth" and the derived math the tool for validation.

Methods

The paper employs a mix of graph theory, $\lambda$-calculus, and structural induction.

  1. The Hypothetical Machine: Henderson defines a simple computing device with an accumulator ($T$), a stack ($F$), and a "source environment" ($v$) representing the state of all variables.
  2. Property A: This is the core technical invariant. Henderson posits that a "well-behaved" expression, when evaluated, should:
  3. Save the current value of the accumulator on the stack.
  4. Leave the rest of the stack untouched.
  5. Produce a new value in the accumulator and a new environment that depend only on the previous environment.
  6. Inductive Derivation: Using this "Property A," the author takes three common constructs—sequences (begin...end), conditionals (if...then...else), and loops (while...do)—and translates them into machine instruction graphs. He then uses functional composition to collapse these graphs into single mathematical functions.
  7. The Fixed-Point Operator: To handle the "while" loop, which can run indefinitely, Henderson utilizes the "paradoxical combinator" ($Y$ operator) from $\lambda$-calculus to define the loop's behavior as a recursive functional mapping.

Datasets

Not discussed in the paper. As a theoretical computer science paper from 1971, it relies on formal proofs rather than empirical data or benchmarks.

Key Insights and Ideas

  • Everything is an Expression: Henderson simplifies the language by removing the distinction between "statements" (which do things) and "expressions" (which return values). In his model, an assignment statement is just an expression evaluated for its side effect. This unification makes the mathematical proofs much cleaner.
  • Post-hoc Validation: The "aha moment" is that correctness isn't a binary "yes/no" against a spec. Instead, correctness is the acceptance of the derived functional description. If the math derived from your compiler looks like nonsense, your language design is likely "irrational."
  • Implementation as Design Tool: By forcing the language to be representable through these functional mappings, the author argues that the demands of the proof actually help "rationalize" the language design, making it easier for both humans and machines to understand.

Key Results

The paper successfully derives formal functional mappings for the three target constructs:

  • Sequences: Shown to be a simple composition of the functions of their component expressions.
  • Conditionals: Derived as a selection function that chooses between two functional paths based on the state of the accumulator.
  • Loops: The most significant result is the derivation of the while loop's side-effect function. Henderson notes that this derived function is mathematically equivalent to the axiomatic definitions proposed by C.A.R. Hoare, providing a bridge between implementation-based semantics and logic-based semantics.

Limitations and Future Work

  • The "Sharing" Problem: The author admits that this model struggles with "vectors" (arrays) and the "sharing" of storage. When two different names point to the same memory location (aliasing), the simple state-vector model used here starts to break down.
  • Complexity of Functions: While the paper mentions the language ALEPH (which supports recursive functions and block structures), the specific derivations for complex function calls are left for "elsewhere."
  • Mechanical Handling: The notation used is intended to be "nominally oriented towards mechanical handling," but the paper itself is a manual mathematical exercise. Henderson concludes by noting he is still experimenting with making this process truly automated.

Summary updated

Abstract

The constructs of a simple programming language are introduced and described informally in terms of values and side-effects. A translator is defined which translates the language into flowcharts for a simple machine. The action of the machine in executing a flowchart is defined. A proof is constructed that the effect of translating and executing any program can be expressed solely in terms of the value and side-effect of the program. During the course of constructing the proof, formal definitions of the concepts of value and side-effect are derived in order to make the proof rigorous. Correctness of the implementation involves checking that the definitions derived in the step above are an acceptable formalization of the informal description given in the first step.
BibTeX
@inproceedings{henderson1971derived,
  author = {Peter Henderson},
  title = {{Derived Semantics for Some Programming Language Constructs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1971},
}
Figure