On this page
In the early 1950s, programming a computer meant writing long lists of machine instructions by hand, and finding the mistakes took longer than solving the science. John Backus, a programmer at IBM, proposed a language in which a scientist could write something close to a formula and let the machine produce the instructions. The result was Fortran. This post covers what Backus set out to do, using his team's own 1957 paper, works through the grammar notation that carries his name, and draws a lesson from his career.
Who was John Backus?
The ACM's Turing Award biography records that John Warner Backus was born on 3 December 1924 in Philadelphia. He was, in its words, "not a good student". He was expelled from the University of Virginia for poor attendance, served in the US Army, and left medical school because, he said, "all you had to do was memorize stuff". After the war a radio technician course led him to mathematics at Columbia University.
In spring 1949, just before graduating, he walked past IBM's computing centre on Madison Avenue, mentioned to a guide that he was interested in the computer there, and was hired as a programmer on the spot. He died on 17 March 2007 in Ashland, Oregon.
Why did Fortran need to exist?
Backus and his colleagues set out the problem in The FORTRAN automatic coding system, presented at the Western Joint Computer Conference in February 1957. The project began in the summer of 1954, aimed at IBM's next large computer, the 704. They wrote that about two-thirds of the cost of solving most scientific and engineering problems on large computers was the cost of problem preparation, and that more than 90 per cent of the elapsed time usually went on planning, writing and debugging the program.
Their goal was to let a programmer specify a numerical procedure "using a concise language like that of mathematics" and obtain from it an efficient 704 program. They expected this to cut the coding and debugging task to less than one-fifth of what it had been.
The word "efficient" mattered. The paper frames the question as whether the 704 could code problems for itself and produce programs as good as human coders, but without the errors. The ACM biography notes that the translator, which we would now call a compiler, ran to over 25,000 lines of machine language, that every IBM 704 sold came with it, and that Fortran became the dominant language for scientific work for decades.
Backus did not invent the compiler. Our post on Grace Hopper covers her 1952 work. His team's contribution was a formula language whose translated programs were good enough for scientists to adopt.
What is Backus-Naur Form?
Backus later joined the international committee that designed ALGOL 58 and ALGOL 60. To describe ALGOL's grammar exactly, he and Peter Naur developed a notation now called Backus-Naur Form, or BNF, which the ACM biography calls a significant milestone in making programming languages formal. His 1977 Turing Award citation honours his work on Fortran "and for seminal publication of formal procedures for the specification of programming languages".
Worked example: reading a BNF grammar
Here is a small grammar in BNF style for whole numbers. Real BNF puts each name, such as digit, inside angle brackets; they are left out here to keep it readable.
`digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9`
`number ::= digit | number digit`
Read `::=` as "is defined as" and `|` as "or". The second rule is recursive: a number is either one digit, or a number followed by a digit.
Is 472 a valid number? Build it up:
4 is a digit, so 4 is a number (first choice).
4 is a number and 7 is a digit, so 47 is a number (second choice).
47 is a number and 2 is a digit, so 472 is a number.
Now try 4a2. Step 1 works, but "a" is not in the digit list, so no rule can produce 4a. The string is rejected, which is what a compiler does when it reports a syntax error.
What mistakes do students make with grammars like this?
Missing the base case. Without `number ::= digit`, the recursive rule never stops.
Reading `|` as "and". It separates alternatives.
Confusing form with meaning. A grammar says whether 472 is well formed, not what it is worth.
The same base-case idea appears in recursion questions; see our post on recursion in ISC Java. If you want your working checked one step at a time, the Fermi Problem Library has a step-by-step solver that explains the reasoning rather than printing an answer.
What can a student learn from how Backus worked?
Backus was open about disliking memorising, and his work kept attacking drudgery: first his own, then that of every scientist writing machine code. In his Turing Award lecture, published in 1978 as Can programming be liberated from the von Neumann style?, he went further and criticised the languages that had grown up since, arguing for a functional style of programming. A habit worth copying is that his team measured the problem first, two-thirds of the cost and nine-tenths of the time, before proposing a fix.
Try it now: write a BNF rule for a signed number that may begin with + or −, and use it to check whether −305 is valid.
