Seven famous programs

Ada Lovelace · 1843 · for Charles Babbage’s Analytical Engine

Note G

In 1842 the Italian engineer Luigi Menabrea published a description of Charles Babbage’s Analytical Engine, a mechanical, general-purpose computer that Babbage designed but never finished. Ada Lovelace, a mathematician and the daughter of Lord Byron, translated it into English and added notes of her own, labelled A to G, which came to about three times the length of the article. They were published in 1843.

Note G sets out, step by step, how the Engine would calculate the Bernoulli numbers: each operation, the variables it reads, and where it stores the result. It is usually called the first published computer program, a century before there was a computer to run it. She saw further than the arithmetic, too: the Engine, she wrote, might act on things other than numbers, and even compose music.

Modern readers have spotted that the fourth operation divides its two variables the wrong way round. Arguably, it is the first bug as well.

John McCarthy · MIT, 1960 · LISP

LISP’s eval

At MIT in 1958, John McCarthy, who a few years earlier had coined the term “artificial intelligence”, began designing a language for working with symbols rather than numbers. He published it in 1960, in a paper called “Recursive Functions of Symbolic Expressions and Their Computation by Machine”. To show the language could express anything, he wrote eval: a LISP function that runs any LISP program. LISP, described in itself.

McCarthy meant it as theory. Steve Russell, one of the programmers working with him, realised that eval could be translated by hand into machine code, did it, and LISP had its first interpreter. The version here is from the LISP 1.5 Programmer’s Manual of 1962, where it fits in half a page. Alan Kay later called it the Maxwell’s equations of software.

MIT Instrumentation Laboratory · 1969 · the Apollo Guidance Computer

Apollo 11’s landing code

When Apollo 11’s lunar module, Eagle, landed on the Moon on 20 July 1969, it was flown by software from the MIT Instrumentation Laboratory, where Margaret Hamilton led the team that wrote the on-board flight software. Luminary 099 was the version flown in the lunar module, written in the Apollo Guidance Computer’s own assembly language.

During the descent the computer raised its 1202 and 1201 alarms: it was being asked to do more than it had time for. The software had been built to drop its least important work and keep the vital tasks running, so the landing went on. The programmers’ humour runs all through the listing: the master ignition routine is BURN, BABY, BURN, a heading reads HONI SOIT QUI MAL Y PENSE, and a comment asks the astronaut to please crank the silly thing around.

Printed listings of the code were scanned and transcribed by volunteers, and since 2016 the whole program has been on GitHub for anyone to read.

Ken Thompson & Dennis Ritchie · Bell Labs, 1975 · Unix, Sixth Edition

“You are not expected to understand this”

Unix was written at Bell Labs by Ken Thompson and Dennis Ritchie, and its Sixth Edition, from 1975, was the first to be widely used outside the lab. The whole kernel was under ten thousand lines, small enough for one person to read. In 1976 John Lions, at the University of New South Wales here in Sydney, wrote a line-by-line commentary on it for his students, and it was photocopied and passed around the world for twenty years.

In the function that switches the computer from one running program to another sits the most famous comment in computing: You are not expected to understand this. It explains a subtle trick with the stack. Dennis Ritchie later said it was meant in the spirit of “this won’t be on the exam”, not as a dare.

Commodore · 1982 · Commodore 64 BASIC

10 PRINT

The Commodore 64, launched in 1982, became the best-selling single computer model ever made, and it switched on straight into BASIC. One line written for it became famous: 10 PRINT CHR$(205.5+RND(1)); : GOTO 10. Run it, and the screen fills with a maze that never ends.

How it works: on the Commodore, characters 205 and 206 are two diagonal lines. RND(1) gives a random number between 0 and 1, so 205.5 plus it is as likely to become 205 as 206. PRINT prints that character, the semicolon keeps the next one on the same line, and GOTO 10 does it again, forever. In 2012 ten authors wrote a whole book about this one line, published by MIT Press and named after it.

id Software · 1999 · Quake III Arena

The fast inverse square root

Quake III Arena, from id Software in 1999, had to light its 3D worlds at speed, and lighting needs one over the square root of a number again and again, to keep vectors the right length. Square roots and divisions were slow on the processors of the day. So, in its maths library, a few lines treat the bits of a floating-point number as an integer, subtract them from a magic constant, 0x5f3759df, and get an estimate so close that one round of Newton’s method makes it good enough.

When id released the Quake III source under the GPL in 2005, programmers found the function and its two famous comments (one of them softened here), and went looking for its author. It was not John Carmack’s: the trick was traced back through several programmers to the late 1980s. Processors now have an instruction that does the job, but the magic number is still the most famous in programming.

Satoshi Nakamoto · 2009 · Bitcoin v0.1

The genesis block

On 3 January 2009 someone calling themselves Satoshi Nakamoto created the first block of Bitcoin, the genesis block, and a few days later released the software that runs it. Into that first block, in a place where miners may write anything, Satoshi put the front-page headline of that day’s Times of London: Chancellor on brink of second bailout for banks.

The headline proves the block was not made before that day, and it says something about why Bitcoin was made, in the depths of the financial crisis. The 50 bitcoins the genesis block created can never be spent. Who Satoshi is remains unknown; they stepped away from the project in 2011.