The museum of languages

The search engine of the last chapter threw all the code out of our textbooks: to a bag of words, a program is noise made of for and print. A program can’t be read that way. In the line a, b = b, a % b every symbol and every position matters: swap a and b on the right, and Euclid’s algorithm stops finding the divisor. How, then, does one program understand another, the way an interpreter understands our code and a compiler translates it into machine instructions? Before teaching a machine to read programs, we should see what it will have to read.

And there is a lot to read. Programming languages number far more than ten, and far more than a hundred.

HOPL, an online encyclopedia of the history of programming languages, lists languages from the 18th century to the present. How many does it hold?

about 300 about 2,000 almost 9,000 about 50,000

8,945 languages and about 7,800 links of the kind “who influenced whom.” Nobody has run most of them in a long time, but a few dozen are alive today, and the oldest of the living is almost seventy years old.

Why do people need so many languages, if any of them, as the basement will show, can compute whatever any other can? The exhibits are the place to look for the answer. This chapter is a museum. Every hall displays the same program: the greatest common divisor of 1071 and 462 by Euclid’s algorithm, which you already wrote in a task in Chapter 5. The answer everywhere is 21. Everything else changes: how the program is written, when and by whom it could have been written, and what in it matters most.

We start in the storeroom. Its exhibits have no labels yet: from the look of each program, guess the language and the year it was born. It is easier than it seems. Languages, like handwriting, carry the marks of their era: capital letters and line numbers, parentheses, unusual symbols, English words instead of signs.

The storeroom: exhibits without labels

The year is fairly easy to guess. Early programs shout in capital letters, since punched cards had no lowercase, and jump around by line numbers. Then come begin … end and curly braces, and later still arrows and neat indentation. But all of this is appearance, and languages differ more deeply. On to the halls.

Hall 1. FORTRAN, 1957: born of laziness

Here is our exhibit as it would have been written in the 1960s, in FORTRAN IV or FORTRAN 66, early standards of the language.

Each line is one punched card of 80 columns, and the columns have their roles. A C in the first column turns the card into a comment, columns 1–5 hold a label, a number that can be jumped to, and the statement itself goes from column 7 to column 72.

The program reads from top to bottom, like a recipe. M = 1071 is an order, not an equation: “put 1071 into cell M.” Line 10 is the famous arithmetic IF with three exits: if N is negative, jump to label 20; if it is zero, to 30; if positive, to 20. That one line writes the loop while n != 0: the lines from 20 to GO TO 10 are its body, and MOD is the remainder of division. The program doesn’t declare the types of its variables at all. In FORTRAN the first letter of the name set the type: variables starting with I, J, K, L, M or N were integers, all the others REAL. That is why the numbers live in M, N and K rather than in A and B: A = 1071 would have been a floating-point number.

This is what imperative programming looks like: a program is a sequence of commands, each of which changes the contents of memory, and jumps decide which command comes next. It is a portrait of the von Neumann machine from Chapter 32: cells, a program counter, jumps. FORTRAN hid the registers and addresses behind names and formulas, but it still asked you to think in commands. Twenty years later Backus himself came out against this: in his Turing Award lecture of 1977 he asked whether programming could be liberated from the “von Neumann style.” By then the answer had long been sought in the next hall.

Hall 2. Lisp, 1958: a program made of parentheses

We met John McCarthy in Chapter 10: in 1958, in the summer at IBM and from the fall at MIT, he was designing a language for problems of artificial intelligence and took Church’s λ-notation for writing functions. The paper on the new language came out in April 1960 in Communications of the ACM, titled Recursive Functions of Symbolic Expressions and Their Computation by Machine. Lisp is the second-oldest high-level language still in use; only FORTRAN is older. Here is our exhibit in Lisp’s modern descendant, Common Lisp. The function is called euclid because Common Lisp already has a built-in gcd.

The first things that catch the eye are the parentheses and the word order. Every expression in Lisp has the form (what-to-do with-what with-what): first the function, then its arguments. (mod a b) is the remainder, (= b 0) is a comparison; even the equals sign comes first. The second thing is harder to spot: the program has not a single assignment. FORTRAN changed the contents of cells M and N until N became zero. Lisp changes nothing. The function says that the GCD of the pair $(a, b)$ equals the GCD of the pair $(b, a \bmod b)$, and calls itself: the recursion of Chapter 9 in place of a loop. This is functional programming: a program describes how some values are obtained from others, and says nothing about the order in which memory is rewritten.

Yet Lisp stands in the museum for another reason. Read its program as data. Each pair of parentheses is a list, and inside it are words, numbers and other lists. The function definition is a list of four elements: defun, the name, the list of parameters and the body. The body is a list of four as well: if, the condition, the “yes” answer and the “no” answer. Here is the same thing written as Python lists and drawn.

A Lisp program is already an expression tree, like the ones we walked in Chapter 17. FORTRAN or Python text first has to be parsed: something has to work out that in a + b * c the multiplication comes first, and where a condition ends and a body begins. In Lisp there is almost nothing to parse. The parentheses are already in place, and a program can build and change other programs as ordinary lists. We will write a Lisp interpreter too, in Chapter 51.

Hall 3. COBOL, 1959: a language for the boss

The program is split into “divisions,” like an office memo. In the data division each variable is described as a field on a form: PIC 9(5) means five decimal digits, no more and no fewer. So the program will print GCD = 00021, with leading zeros, like an entry in a ledger column. The zeros aren’t there for looks: COBOL counts money in decimal digits, and not a cent is lost the way cents were lost in the binary fractions of Chapter 28. The procedure division holds almost-English sentences: “divide A by B giving the quotient Q and the remainder R, move B to A.” The loop PERFORM UNTIL … END-PERFORM arrived with the 1985 standard; in 1960 the same loop took more writing, with separate paragraphs serving as subroutines.

The paradigm is the same as FORTRAN’s, imperative, but the intended reader is different. FORTRAN was written for scientists. COBOL was written so that a program could be read by a department head who knows no formulas but knows what an account balance is. COBOL programs still run in banks: by a 1997 estimate from the firm Gartner, there were about 200 billion lines of them.

Hall 4. APL, 1962: everything at once

Kenneth Iverson taught at Harvard, and in 1957 he began devising a mathematical notation for algorithms: ordinary blackboard notation seemed too poor to him. In 1962 he published the book A Programming Language, which gave the language its name, and in 1966 the first full implementation, APL\360, went into service at IBM. It needed a special typeball for the IBM Selectric typewriter, because APL has more symbols than an ordinary keyboard has letters. In 1979 Iverson received the Turing Award, and his lecture was called Notation as a Tool of Thought.

This is the shortest exhibit in the museum. In modern APLs such as Dyalog APL, the symbol ∨ means “or” for logical values and the greatest common divisor for integers: Euclid is built into a single symbol. The second line is more interesting: ∨ is applied to four pairs of numbers at once, without any loop. APL works with arrays, and to APL a number is an array of one element. In the third line ∨/ puts ∨ between all the elements of a list, like reduce from Chapter 10. The fourth does write Euclid out by hand: ⍺ and ⍵ are the left and right arguments, ⍵|⍺ is the remainder of ⍺ divided by ⍵, ∇ calls the function itself, and the colon separates the condition from the answer.

This is array programming: the loop is hidden inside the operation. Python has the same style in the numpy library, which, as we saw in Chapter 33, runs its loops in C.

The array style has an oddity that shows how differently languages read familiar symbols. APL has no operator precedence. It has dozens of functions and one rule for all of them: an expression is evaluated from right to left.

What is 2×3+4 in APL?

10 14 an error: parentheses are required

From right to left: first 3+4 = 7, then 2×7 = 14. To get the school answer of 10, an APL programmer writes (2×3)+4, or 4+2×3.

Remember this 14. The symbols 2×3+4 are the same for a schoolchild and for APL, yet they mean different things. We will come back to this gap between notation and meaning in the hall of syntax, and the next chapter shows how operator precedence gets built into the grammar of a language.

Hall 5. C, 1972: closer to the hardware

You have already seen this hall from the inside. In Chapter 33 we X-rayed a function in C and watched it turn into machine instructions. Dennis Ritchie made the language at Bell Labs in 1972–1973 to rewrite the Unix operating system in it, and since then the kernels of almost all systems have been written in C, including the one the course sandbox runs on. The exhibit in this hall is alive: the module cs.c hands the text to the tcc compiler and runs the result.

The handwriting is familiar: curly braces around blocks, a semicolon after each statement, while with its condition in parentheses. C++, Java, C#, JavaScript, Go and dozens of other languages later put on these clothes, which is why a programmer in any of them can read this exhibit without a dictionary. The paradigm is imperative again, like FORTRAN’s, only without labels and jumps: the loop and the function have become words of the language. New in this hall are declarations. Each variable gets its type in advance: int a promises that a holds an integer of a fixed size, usually 32 bits, and the compiler checks the promise before the program ever runs. What follows from that will come out in the hall of types. The type int in C is whatever a processor register can do; C has no integers of unlimited size like Python’s. C describes the machine only a little more abstractly than assembly language does, and that is why it is fast.

Hall 6. Smalltalk, 1972: everything is an object

Chapter 12 told the beginning of the story of Alan Kay and Smalltalk. It went on like this. At Xerox PARC in 1972 Kay bet that the core of a language built on messages between objects, “the most powerful language in the world,” would fit on “a page of code.” A few days after the page was written, Dan Ingalls showed him a working interpreter built from it. The wider public saw the language only in 1981, when Byte magazine ran a whole series of articles about the Smalltalk-80 version. Smalltalk programs aren’t written in files: they are typed straight into the running system. A method is added to the class Integer, and every integer knows it at once.

It reads like correspondence. 1071 euclid: 462 sends the object 1071 the message euclid: with the argument 462, and the number itself knows how to answer, because its class has such a method. self is whoever received the message, := is assignment, \\ is the remainder, and ^ returns the answer. The most unusual thing is the loop. Smalltalk has no while statement. [b = 0] is a block object, a piece of code in square brackets, and it is sent the message whileFalse: with another block as the argument: “repeat this for as long as you are false.” Even b = 0 is the message = sent to the object b. The conditional is a message too: ifTrue: is sent to a truth value.

This is object-oriented programming in its pure form: a program is a collection of objects that keep their own state and send one another messages. Simula, where Chapter 12 began, invented classes, and Smalltalk carried the idea all the way: everything became an object. In this respect Python is closer to Smalltalk than it seems.

The % sign in Python is a polite way of writing the message __mod__ sent to a number. A number has methods, and a number, a function and the class int itself are all objects. Special methods of the same kind taught the rabbit in Chapter 12 to print itself.

Hall 7. Prolog, 1972: ask, don’t order

There is no function here that returns anything, and no loop. There are two statements about the relation “G is the greatest common divisor of A and B.” The first is a fact: the GCD of a number A and zero is A. The second is a rule: :- reads “if,” and the commas read “and.” The GCD of A and B is G if B is greater than zero, R is the remainder of A divided by B, and the GCD of B and R is G. Words starting with a capital letter are variables, and words starting with a lowercase one are names. The last line is a query: “for which G is gcd(1071, 462, G) true?” The program doesn’t say how to search for the answer. Prolog searches by itself: it tries the rules from top to bottom, substitutes values for the variables, and when it reaches a dead end, it goes back and tries the next rule.

This is logic programming, another branch of the declarative approach you know from the SQL of Chapter 45: describe what is true and leave the search to the machine. Try it yourself. Below is a small Prolog that runs right in your browser. It has two databases: our GCD, and a family tree of the museum’s languages built from Wikipedia’s data on who influenced whom.

The most interesting queries are the ones with unknowns. ancestor(X, python) asks “who are all the ancestors of Python?”, and Prolog lists them one after another: the same program text works in both directions. The query influenced(X, Y), influenced(Y, python) has two unknowns: Prolog looks for whoever influenced the languages that influenced Python. The “Swap the rules” button shows the flip side. The rule ancestor(X, Y) :- ancestor(X, Z), influenced(Z, Y) is logically correct, but to prove ancestor, Prolog first of all sets out to prove ancestor again, and so on without end, like a recursion without a base case from Chapter 9. The logic is the same, but the behavior depends on the order of the rules and of the goals inside them: a Prolog programmer still has to keep in mind how the machine searches.

Hall 8. Haskell, 1990: functions without consequences

By the mid-1980s there were so many functional languages (ML, Miranda, Hope, SASL) that researchers got in each other’s way, each writing in a language of their own. In 1987, at a conference on functional languages in Portland, a committee was formed to make a common, open language. Its first report came out in 1990. The language was named after the logician Haskell Curry, whose name is also carried by the technique called currying.

The program looks like a definition from a math textbook: two equations, and the right one is picked by matching the pattern of the arguments. If the second argument is zero, the answer is a; otherwise it is the GCD of the new pair. The first line is a type: euclid takes two integers and returns an integer. You needn’t write it, because the Haskell compiler infers the types by itself and checks them before the program runs; Chapter 53 tells how it does that.

Haskell finishes what Lisp started. Lisp does have assignment, even if it is rarely used. Haskell has none at all: a function can’t change anything, whether a variable, a file or the screen. Even printing here is a value of a special type, IO, a description of an action for the system to carry out. A second property comes with this one, laziness: since a computation changes nothing, it can be put off until its result is needed. The expression take 5 (filter even [1..]) takes the first five even numbers from the infinite list of all the natural numbers and calmly returns [2,4,6,8,10]; Python’s generators from Chapter 10 work on demand in the same way.

Hall 9. Python, 1989: a language for people

After eight halls this exhibit reads differently. The indentation instead of begin … end and braces comes from ABC. The loop and the assignment are the imperative legacy of FORTRAN and C. a, b = b, a % b assigns both variables at once, almost like the functional notation “the new pair is $(b, a \bmod b)$.” Elsewhere in this book you have met lambda, map and generators from the functional hall, classes and messages from the Smalltalk hall, and numpy, which brought in APL’s arrays. Python is a multi-paradigm language: you can write it in any of these styles. In its list of languages that influenced Python, Wikipedia names ABC, ALGOL 68, APL, C, C++, Haskell, Lisp, Standard ML and half a dozen more.

Five styles

After nine halls the exhibits can be sorted onto shelves. They look different, but beneath the parentheses and capital letters lies a deeper difference: the answer to the question of what a program is. The museum has turned up five answers, and they are called paradigms.

A paradigm is more a way of thinking than a property of a language, and in a multi-paradigm language you can watch one task change its style. Take a task simpler than the GCD: the sum of the squares of the odd numbers from 1 to 10.

165, four times over. The first version tells the machine what to do step by step, the second how some values come from others, the third what to do with the whole array at once. The fourth, a comprehension from Chapter 10, is closest to the mathematical notation $\sum_{x \le 10,\ x \text{ odd}} x^2$. An experienced Python programmer will choose the last one: it is shorter and reads like a definition. Still, it pays to know all four, because every language nudges you toward its own. Practice recognizing a style at first sight.

Syntax and meaning

In the APL hall the expression 2×3+4 gave 14, while a schoolchild gets 10. The same symbols, a different meaning. In programming languages, as in natural ones, we tell two things apart. Syntax is the rules of writing: which words and symbols may stand where. Semantics is the meaning of what is written: what happens when the program runs. All the exhibits in the museum differ in syntax and agree in semantics: they all compute 21. It also happens the other way round, when the same line is valid in several languages and means different things in each. Here are three such lines in Python and in C.

In C the sign / between integers means integer division, and 7 / 2 gives 3. In Python since version 3, / is always true division, and integer division is written //. But even their integer divisions differ: C drops the fractional part, rounding toward zero (−3.5 → −3), while Python rounds down (−3.5 → −4). The remainder adjusts to the quotient so that the equation $a = (a \mathbin{/\!/} b) \cdot b + a \bmod b$ holds: in C $-7 = (-2) \cdot 3 + (-1)$, in Python $-7 = (-3) \cdot 3 + 2$. Both semantics are reasonable. But a program carried over from one language to the other symbol for symbol will start going quietly wrong on negative numbers, for example when it computes the day of the week for dates before the epoch it counts from.

With JavaScript, the language that runs almost every website, the picture is more colorful still. Compare for yourself.

The sign = is especially treacherous. In FORTRAN, C and Python it is assignment: “put into the cell.” In Haskell it is definition: x = x + 1 there doesn’t add one, it defines x in terms of itself, and such an x can never be computed, so the program either loops or stops with a complaint about a loop. In Prolog = means “make the two sides the same by substituting values for variables.” ALGOL, Pascal and Smalltalk gave assignment a sign of its own, :=, so that nobody would confuse it with equality. In C, if (x = 0) assigns zero instead of comparing, and the condition is always false, yet the program compiles. Python closed this trap with syntax: there if x = 0: is a SyntaxError.

Who checks types, and when

The third thing languages differ in is their attitude to types. We have been meeting types since Chapter 2: "5" + 2 in Python is an error, because a string and a number don’t add. But when a language catches such an error, and whether it catches it at all, varies from language to language. These are two independent questions.

The first question is when. With static typing, every variable and function has a type, and the compiler checks the types from the text, before the program runs. With dynamic typing, the type belongs to the value rather than the variable, and the check happens at the moment a line is executed. Python is a dynamic language, and here is what follows from that.

The error was in the function all along, but the first two calls went through: execution never once entered the branch that holds it. The third call crashed. In a large program a branch like this can sleep for years, until a rare input comes along. A compiler for C, Haskell or Rust would have found it before the first run; that is the strength of static checking. It is paid for with declarations and with flexibility. A Python function doesn’t care what value it was given, as long as the value can do whatever is done with it; that is the duck typing of Chapter 12.

The second question is what to do when the types don’t match. Python refuses: a string and a number can’t be added. JavaScript turns the number into a string and glues the two together: "pioneer " + 1957 is "pioneer 1957". A language that quietly converts values to a suitable type instead of raising an error is said to have weak typing, and one that refuses, strong typing. And C, a language with static types, is weakly typed.

The C compiler knew the types of all the values, and still it quietly cut 1071.9 down to 1071, squeezed 1071 into a byte as 47, and added a number to a string, moving its start two letters along. The compiler isn’t broken: the rules of the language allow these conversions, and C keeps its weakness on purpose, for speed and for closeness to the hardware. Python, checking types as it goes, refused. That gives a table of four cells.

The cells are drawn more sharply than they are. “Strong” and “weak” are the two ends of a scale, and the scale has no generally accepted divisions. Even in Python True + True equals 2, and 1 + 2.5 quietly becomes a float: small concessions to weakness. The question “when are types checked,” on the other hand, always has a clear answer, and we will measure its price in Chapter 53, where types will stand trial and you will write a type checker yourself.

Compiler or interpreter: not a property of the language

People often call languages “compiled” or “interpreted.” That is inaccurate. In Chapter 33 we told apart a translator, who translates a book in advance, and an interpreter, who renders it sentence by sentence. The same book can be rendered by either. A language is the syntax and semantics set out in its description, while a compiler or an interpreter is an implementation, and one language can have many. CPython compiles Python into bytecode and interprets that; PyPy runs the same language by compiling the hot spots into machine code on the fly. C is usually compiled in advance, but tcc in our sandbox translates a program into memory and runs it at once. Lisp had both an interpreter and a compiler as early as the start of the 1960s.

So it is more useful to ask how easy a language is to compile. The more the language knows about a program before it runs (types, sizes, which functions get called), the better the machine code that can be built in advance. C knows almost everything, Python almost nothing, and this is one of the reasons for the difference in speed we measured in Chapter 33. And one of the languages in the basement has a compiler so simple that you can write it in an evening. Down we go.

The basement: esoterica

The museum’s basement keeps languages written to prove a point or to poke fun at something; nobody ever meant to work in them. They are called esoteric. The oldest is INTERCAL: in 1972 two Princeton students, Don Woods and James Lyon, made a parody of the languages of their day. The INTERCAL compiler refuses to compile a program if the word PLEASE appears in it too rarely, since the program is then “insufficiently polite,” and also if it appears too often, which makes the program “overly polite.”

There is nothing else in the language. A tape of 30,000 cells, each holding a byte from 0 to 255, a pointer to one of them, and eight commands; everything else in the text of a program is a comment. There are no variables, no numbers, no functions, not even an if: a condition is made from a loop that runs once.

The last exhibit in the basement is our GCD. Numbers above 255 don’t fit into a cell, so instead of 1071 and 462 the program gets 252 and 105 as input: they have the same greatest common divisor, 21. The program reads the numbers digit by digit, divides with a remainder by repeated subtraction, and prints the answer in decimal digits: 1,892 characters and more than two hundred thousand steps. Nobody writes such a thing by hand. The program was assembled by a generator in Python out of “macros” such as “copy a cell” and “if the cell is zero,” a little compiler into Brainfuck. How compilers translate from one language into another is the subject of Chapter 52.

A language like this stands in the museum because it answers the question we started with. Eight commands are enough to write down any computation that can be written in Python or C: Brainfuck, as the saying goes, is Turing complete. Back in 1964, the Italian mathematician Corrado Böhm described P′′, a tiny language for a machine with a tape, without input or output, and three of Brainfuck’s commands repeat its commands almost word for word. What “any computation” means and how such a thing is proved is the subject of Chapter 55. For now the conclusion will do: languages differ in how a computation is written down and thought about, and not in what can be computed in them. In computing power Brainfuck and Python are equal, but the GCD takes four lines in Python and 1,892 characters in Brainfuck.

Why there are thousands of languages

Now it is clear why there are thousands of languages. Every exhibit is fitted to three things at once. The machine: FORTRAN was made for the IBM 704, C for writing an operating system. The problem and whoever solves it: a scientist with formulas, an accounting department with ledgers, an artificial intelligence researcher with symbols, a mathematician with arrays. And an idea of what a program is: commands, functions, rules, objects, arrays. All three keep changing, and languages keep being born: Go in 2009, Rust in 2015.

Alan Perlis, the first winner of the Turing Award, wrote in 1982: “A language that doesn’t affect the way you think about programming, is not worth knowing.” Perlis wasn’t exaggerating. A programmer who has seen Lisp looks at recursion differently, one who has seen APL looks at loops differently, and after Prolog even search looks different. The museum also teaches you to read the unfamiliar.

Tasks

Three tasks: run someone else’s language, translate it into your own, and write one program in three styles.

Write bf(code, inp=""), an interpreter for Brainfuck. The function runs the program code and returns everything it printed as one string. The tape is 30,000 cells of zeros, and the pointer starts at cell 0. A cell holds a number from 0 to 255: + on 255 gives 0, and - on zero gives 255. The command . outputs the chr of the cell, and , puts into the cell the code of the next character of the string inp, or zero once the input has run out. Characters other than the eight commands are comments. If the brackets don’t match, raise a ValueError. The tests include the GCD program from the chapter and a loop of a million steps.

Six of the eight commands take a line each; they are in the chapter’s table. For , keep a counter of the characters read, k: if k < len(inp), put ord(inp[k]) into the cell, otherwise zero, and increase k either way.

The brackets. [ with a zero in the cell jumps past the matching ], and ] with a nonzero cell jumps back to the matching [. You could look for the matching bracket every time by counting the nesting, but it is faster to find all the pairs in advance, in one pass with a stack, like the bracket check in Chapter 15, and keep them in a dictionary “bracket position → position of its pair.” Unmatched brackets will turn up there as well.

After a jump, remember that the loop ends with pc += 1: if you set pc to the position of the matching bracket, the next command to run is the one right after it, which is what both cases need.

Forty lines, and you have an executor for a language in which, as we know, any computation can be written. It is built like the processor of Chapter 32 and the bytecode interpreter of Chapter 33: a program counter, fetch, execute, jump. The table of brackets built before the run is a first step toward compilation: we took the program apart once so as not to take it apart again at every step. The next task takes that step all the way.

The interpreter from the previous task works out anew at every step which command is in front of it. A compiler does that once. Write to_python(code), which translates a Brainfuck program into the text of a Python program. The text must contain a function program(inp) that does the same as bf(code, inp) and returns the output as a string. Each command becomes a line of Python, and [ becomes while tape[p]: with its body indented one level deeper. Unmatched brackets raise a ValueError. The tests execute the resulting text with exec and run a triple loop of 16 million turns in it, allowing five seconds; for the interpreter from the previous task such a loop costs several times more.

[ adds the line while tape[p]: and increases depth, and ] decreases it. If depth tries to drop below one, there is an extra ]; if it is greater than one at the end, a [ was left unclosed.

The loop [] has an empty body, and Python doesn’t allow an empty body. If the last line added ends with a colon, add pass before closing the loop.

The translation gets shorter and faster if you merge repeats: five pluses in a row become a single line tape[p] = (tape[p] + 5) % 256, and three > become p += 3. A line of Python costs the same however much it adds. The tests will fit into the time limit without this, but on programs with long chains of pluses the difference shows.

The translation of the GCD program comes to about 870 lines of Python and runs several times faster than the interpreter: all the work of taking the text apart is done once, before the run, and Python executes what remains as ordinary code. It is the same gain the translator had over the interpreter in Chapter 33. This is also the course’s first compiler into another high-level language, which is how, for example, translators from TypeScript to JavaScript work. The next step is to spot whole idioms in a program: [-] means “set the cell to zero,” and [->+<] means “add the cell to its neighbor.” That is what optimizing compilers do, and they are the subject of Chapter 52.

FizzBuzz is a children’s game about division that became a famous interview problem: the numbers from 1 to $n$, but with "Fizz" instead of multiples of three, "Buzz" instead of multiples of five, and "FizzBuzz" instead of multiples of fifteen. Write three functions, each returning a list of strings ["1", "2", "Fizz", "4", "Buzz", …], but each in its own style. fizzbuzz_loop(n) is imperative, with a for or while loop. fizzbuzz_func(n) is functional: inside it there are no loop statements, no assignments (no := either), and no append or other methods that change a list. fizzbuzz_noif(n) has not a single if: no statement, no … if … else …, no condition in a comprehension, and no match. The functions don’t call one another. The checker reads your code with the ast module, which is covered in the next chapter.

The functional style: map(function, range(1, n + 1)) applies a function to every number, and list(...) collects the results. The function for one number can be a lambda, with the condition inside it written as the expression … if … else …, which doesn’t count as an assignment. A comprehension [... for i in range(1, n + 1)] will do too: it is an expression, not a loop statement.

Without if there are two ways. Arithmetic: "Fizz" * True is "Fizz", and "Fizz" * False is the empty string; an empty string is false, so "" or "7" gives "7". Or a table: the answer depends only on i % 15, which means it can be taken by index from a tuple of fifteen elements.

The functional version glues “Fizz” and “Buzz” together by multiplying strings by truth values: True in Python arithmetic is 1, one of the small weaknesses of typing from the section on types. If neither applies, the result is the empty string, and or puts the number in its place. The version without if is a table: position 0 holds “FizzBuzz”, positions 3, 6, 9 and 12 hold “Fizz”, and positions 5 and 10 hold “Buzz”. Branching has turned into reading by index, which is how APL programmers think. Then again, or is branching too, hidden inside logic: the program still chooses between options, and only the notation has changed.

What next

Every exhibit in the museum is text. To compute anything, the machine has to understand how the text is built. In the basement that is easy: each Brainfuck character is a command of its own and everything else is skipped, so the interpreter from the task reads the program one letter at a time. Lisp is almost as easy: the parentheses are already in place, and the program lies there as a ready-made tree. But take the line 2 + 3 * (4 - 1), which Python, C and JavaScript all understand.

Python will say 11. So it understood that 4 - 1 in parentheses is computed first, that multiplication binds tighter than addition, and that 3 * (4 - 1) is a single whole, not “3 times 4, then minus 1.” APL would read the same symbols from right to left, and the answer would come out the same by coincidence. For a single formula we have already built such a parse, in Chapter 15, with Dijkstra’s shunting yard and a table of precedence. But Python has more than formulas: if inside for inside def, calls, lists, comprehensions. How does a program understand the structure of a text where everything is nested inside everything else? To answer that, we will have to work as linguists: the next chapter sends you on an expedition to the speakers of an unfamiliar language.