FREE CONTRIBUTION CHRONOLOGY · 1948–1957

Machines translate languages

How can one program translate another program without changing its intended meaning?

The historical question

Assemblers, routine libraries, compilers, and FORTRAN moved programming above raw opcodes. The machine could now perform the repetitive translation work that programmers had done by hand.

A translator preserves a source program’s meaning while changing its representation and resolving details required by the target machine.

Preserve meaning across representations

Translate the assignment x = y + 2 into a simple machine sequence: load y into a register, add the constant 2, and store the result into x. The correctness claim is relational: for every permitted initial state, the translated sequence must produce the state required by the source operation, subject to the language’s defined behavior. Matching a familiar-looking instruction sequence is not a proof.

Representation details matter. If y is the largest signed integer, does addition wrap, trap, use arbitrary precision, or fall outside the language’s defined behavior? A translator cannot silently choose whichever outcome is convenient. The source and target contracts determine which transformations are allowed. Name resolution and storage layout also determine which memory locations x and y denote.

Historically, routine assembly, symbolic assembly, and high-level compilation are distinct steps, not interchangeable names for one event. Hopper’s A-0 selected and combined prewritten routines and parameters; later systems developed richer source notation and translation. FORTRAN’s practical success also depended on useful numerical programs and generated-code quality. The general lesson is preservation of an explicitly specified meaning across representations.

What the evidence does not establish

Avoid the absolute “first compiler”. Define what each translator did and compare earlier, parallel, and later systems on the same criteria.

Reconstruction exercise

Specify a translation for x = y + 2 under 8-bit unsigned wrapping arithmetic. Evaluate it when y = 255 and identify a boundary test.

Worked solution

An 8-bit unsigned result is reduced modulo 256, so 255 + 2 becomes 1. The translation must preserve that wraparound contract. Tests should include y=253 giving 255, y=254 giving 0, and y=255 giving 1. A target operation that traps on overflow would require additional work to implement the specified source semantics. Do not assume the same-looking plus symbol promises identical arithmetic everywhere.

Test the limits and transfer the idea

1. Semantic counterexample · allow 25 minutes

A familiar algebraic optimization can change a comparison

A source language uses eight-bit unsigned wrapping addition and ordinary comparison of the resulting values 0–255. A compiler replaces (y+1)>y with true. Find every y for which the replacement is wrong and prove your characterization. Then compare a source language with arbitrary-precision integers. Explain why the same source-looking expression can permit different optimizations.

Get a starting hint

Separate y=255 from the range in which adding one stays representable.

Compare your reasoning with the worked solution

For 0≤y≤254, the wrapped result is y+1, which is greater than y. For y=255, addition wraps to zero and the comparison is false. Thus 255 is the unique counterexample in the eight-bit domain. Under arbitrary-precision integer semantics, y+1 is always greater than y, so the replacement is valid for all integers. If a language instead traps on overflow, eliminating the addition may suppress a required trap and still be invalid. A translator preserves the source contract, not whichever mathematical domain seems convenient. Hopper's participant interview and later museum accounts illuminate historical automatic programming, but the optimization proof must be grounded in the explicitly stated toy-language semantics.

Check your reasoning

Finds the unique boundary counterexample.
Proves the result over the rest of the input domain.
Distinguishes wrapping, arbitrary precision and trapping semantics.

2. Control-flow trace · allow 25 minutes

Translation must preserve which operations execute

An invented source language evaluates y != 0 AND 10/y > 2 from left to right with short-circuit AND; integer division by zero traps. A target translator always evaluates both operands before applying AND. Trace y=0 and y=2, then give branch-based pseudocode preserving the source behavior. Explain why merely matching truth tables for already computed Boolean inputs misses the bug.

Get a starting hint

The operands are computations with possible failure, not two Boolean values already in registers.

Compare your reasoning with the worked solution

For y=0, the source's left operand is false, so division is skipped and the expression returns false. The eager target divides by zero and traps. For y=2, both evaluate 10/2=5 and return true. Correct pseudocode is: if y==0, result=false; otherwise compute q=10/y and set result=(q>2). A Boolean truth table describes how AND combines two values, but does not specify whether, when or how its operand computations run. Translation must preserve required evaluation order, exceptions and side effects in addition to final values on successful runs. This exercise concerns a stipulated language; it should not be read as evidence that A-0 already implemented modern short-circuit expressions or exception semantics.

Check your reasoning

Traces the divergence on zero and agreement on two.
Uses a branch to avoid the forbidden evaluation.
Explains the distinction between Boolean algebra and evaluation semantics.

Check your understanding

Why must overflow behavior be part of a translation argument?

Source and target arithmetic may define different outcomes
Compilers never translate addition
Overflow affects only printed comments

Explanation

Sources and further reading

Grace Hopper oral history: Computer History Museum
COBOL: Smithsonian American Women’s History Museum