1  Two models of computation

Pick up a calculator. Type 3 + 5 + 2 + 8 and press equals. You get 18. Simple enough. But try to explain to someone how the calculator got there, and something interesting happens: there are two very different ways to tell the story.

Maybe the calculator kept a running total. It started at 0, added 3 to get 3, added 5 to get 8, added 2 to get 10, added 8 to get 18. The answer accumulated through a sequence of changes to a single number.

Or maybe 3 + 5 + 2 + 8 is just an expression, and 18 is its value. The calculator’s job was to evaluate that expression. Nothing changed along the way; the answer was already there, implicit in the expression itself, waiting to be worked out.

Notice the difference. The first story has time in it: first this happened, then that happened, then this. There is a running total, and it changes. The second story has no time. There is an expression, and it has a value; no variable was modified because there was no variable to modify.

This difference turns out to be surprisingly deep. In 1936, there were no computers. No transistors, no screens, no keyboards. But two mathematicians, working independently, each found a way to describe what “computation” means in precise mathematical terms. Both models turned out to be equally powerful (anything one can compute, the other can too), but the programming languages that grew out of them decades later look and feel completely different. Most programming languages grew out of the first model. R grew out of the second, and that is what this book is about.

1.1 Instructions and state

Alan Turing, a graduate student at Cambridge who would go on to break the Enigma code in World War II and become the father of modern computing, imagined computation as a machine operating on a tape. The machine reads a symbol from a cell, writes a new one, shifts left or right, and moves to a new internal state. Then it does it again. Turing proved that this simple device, given the right set of rules, can carry out any computation that can be precisely described.

What makes the Turing machine interesting for us is not the tape or the rules; it’s the picture of computation they imply. A Turing machine does things: it reads, writes, moves, changes. It has memory (the tape), and that memory changes over time. A program, in this view, is a sequence of instructions that progressively modify stored values until the answer emerges.

Here is what that looks like as pseudocode, for our summing problem:

total = 0
for each number in [3, 5, 2, 8]:
    total = total + number
return total

Watch total. It starts at 0, becomes 3, becomes 8, becomes 10, becomes 18. The variable varies; the answer lives in its final state. If you have written code in C or Python, this probably feels natural. It should: both languages were designed around exactly this view of computation.

C came out of Bell Labs in the early 1970s. Dennis Ritchie and Ken Thompson were building Unix, a new operating system, and they needed a language that stayed close to the hardware. Ritchie designed C so that the programmer allocates memory, reads from it, writes to it, and frees it when done. The language does not manage any of this for you. This directness made C enormously influential: Unix spread, C spread with it, and most operating systems, databases, and compilers written since have been written in C. R itself is written in C. The picture of computation that C embodies, a program as a sequence of instructions modifying stored values, became the default mental model for a generation of programmers.

Most of the popular languages that followed inherited that model, even when they made it friendlier. Guido van Rossum created Python in the late 1980s as a language that reads almost like pseudocode; it handles memory management automatically and lets you experiment one line at a time, but underneath, variables are still containers, and a program is still a sequence of instructions that changes what’s inside them. The for loop above could be Python with one character changed. Java, released by Sun Microsystems in 1995, added strict type-checking and automatic memory management for large engineering teams writing large systems. JavaScript was created at Netscape that same year, originally for adding interactivity to web pages; Brendan Eich wrote the first version in ten days, and it has since become the most widely used programming language in the world. All four languages share the same underlying picture of what computation is. They differ in how much they protect you from mistakes, but the instruction-and-state model is the same.

1.2 Expressions and functions

Alonzo Church, who happened to be Turing’s doctoral advisor at Princeton, was working on the same problem at the same time but from a completely different angle. Church built a notation called the lambda calculus. It has three things:

1. Variables: x
2. Functions: λx. x + 1 (take x, return x + 1)
3. Application: (λx. x + 1)(5) gives 6

No tape, no memory, no state that changes over time. You write an expression and simplify it by applying functions to arguments until you reach a value that can’t be simplified further. Church proved that this system, despite having no concept of memory or instructions, can compute exactly the same class of functions as Turing’s machine. The equivalence (known as the Church-Turing thesis) was one of the foundational results of 20th-century mathematics.

What does our summing problem look like in this world?

sum([3, 5, 2, 8])
= add(3, sum([5, 2, 8]))
= add(3, add(5, sum([2, 8])))
= add(3, add(5, add(2, 8)))
= add(3, add(5, 10))
= add(3, 15)
= 18

Look at what’s not there: no variable called total, nothing getting overwritten. The expression unfolds, each add consuming its arguments, until only 18 remains. The answer was implicit in the original expression; evaluation just made it explicit.

Where Turing’s model asks “what sequence of operations transforms my initial state into the answer?”, Church’s asks “what expression, when fully evaluated, gives the answer?” Same result, genuinely different way of thinking about how you got there.

1.3 What this has to do with R

R descends from Church’s model. The chain runs through four decades and several languages (Chapter 2 tells the full story), but you can see the result right now, without knowing any of that history. You don’t need to understand R syntax yet; just compare the shape of the code with the two models from earlier.

Suppose you have a list of exam scores and you want to know how many students scored above 70. In the instruction-and-state style, you would create a counter, loop through the scores, and increment the counter each time you find a score above 70:

scores <- c(65, 82, 71, 90, 55, 78)

count <- 0
for (s in scores) {
  if (s > 70) {
    count <- count + 1
  }
}
count

This works. R can do it. But notice the shape: there is a variable (count) that gets modified in a loop, one step at a time. count starts at 0, becomes 1, becomes 2, becomes 3, becomes 4. This is Turing’s model, transplanted into R. And it looks exactly like the first calculator story: a running total, changing with each step.

Now the expression-and-function style:

scores <- c(65, 82, 71, 90, 55, 78)

sum(scores > 70)

One line, no loop, no counter, no variable that changes. scores > 70 produces a vector of TRUE and FALSE values; sum() counts the TRUEs. There is an expression, and it has a value. This is the second calculator story: sum(scores > 70) and 3 + 5 + 2 + 8 work the same way. The calculator was doing Church’s model all along; R just lets you do it with data.

Both give the answer 4. But the second version is shorter, easier to read, and (as you’ll learn in Chapter 4) faster, because R was designed for it. The loop version works against the grain; the expression version works with it.

This pattern shows up everywhere in R:

• if/else returns a value, so you can assign its result directly. In most languages, if is a statement that does something; in R, it’s an expression that produces something (Chapter 3):

  y <- if (x > 0) "positive" else "negative"

• Functions are ordinary values. You can store a function in a variable, pass it to another function, or create one on the fly, the same way you’d pass around a number or a string (Section 5.4).

• x * 2 multiplies every element of x at once, with no loop and no index variable. Operations that in other languages require you to write a loop are built into R as expressions on whole vectors (Chapter 4).

• Pipe chains compose functions left to right, each one receiving the result of the previous one. This is function composition, the core operation of Church’s model, made into syntax (Chapter 15):

  data |> filter(x > 5) |> summarize(mean(y))

Chapter 2 follows the full chain (Church to Lisp to Scheme to S to R) and what each step added along the way.