FORTRAN's 1957 compiler used random numbers to plan its use of three index registers

A compiler rolled the dice before handing over the program. In 1957. The computer industry has been trying to predict what our software will do for considerably longer than the current sales pitch suggests.

John Backus and his colleagues wanted scientists to express numerical procedures in a concise mathematical language and obtain efficient machine instructions. The difficult word in that promise was efficient. Trading time at the keyboard for more time on the computer could make the convenience a fairly expensive indulgence.

The team’s original paper documents a particularly odd solution. The compiler divided a program into blocks with a single entrance and exit, then estimated how often execution moved between them. Conditional decisions were sampled with a random-number generator, weighted by any FREQUENCY statements the programmer supplied.

The authors called this operation execution “in Monte-Carlo fashion.” It was a simulation of possible control flow during compilation. The scientist’s real computation still had to happen afterward; the compiler hadn’t become a fortune-teller with a punch-card slot.

Those estimates helped determine how to handle the machine’s three index registers. Frequently traveled paths deserved special attention because repeatedly moving values into and out of registers would waste work along the very routes the program used most.

The randomness helped choose where to concentrate an optimization. It didn’t make the scientific answer random, and it didn’t prove the eventual run would follow the sampled branches. Confusing those jobs would put the dice in precisely the wrong part of the machine.

A compiler can therefore spend more time thinking than typing, so to speak, when the expected savings justify it.

There is something pleasantly familiar about the practical bargain. A tool can spend extra effort preparing a result that will be used repeatedly. Whether that trade pays depends on how often the result runs and how much work the preparation saves. The useful comparison includes both bills.

For someone choosing a tool now, that suggests a concrete experiment. An application built once and run thousands of times has different priorities from a tiny program rebuilt after every edit. Measuring only the most flattering stage can make either option look wonderful. Vendor charts rarely object to wonderful.

A future compiler could make much more elaborate predictions and still face the same question from its user: how much time did the whole job save? The 1957 document is worth reading because its cleverness stays attached to that mundane problem, rather than floating away with the adjectives.

Three registers. Plenty to argue over.