2  R’s family tree

Consider this small program in R:

add_tax <- function(price, rate) price * (1 + rate)

prices <- c(10, 25, 8, 42)
with_tax <- sapply(prices, add_tax, rate = 0.2)
with_tax

Four ideas carry those five lines, and every one of them arrived in R from another language and another decade. By the end of this chapter you will be able to say which line came from where. You don’t need to be able to read the code yet.

Figure 2.1: R’s lineage: each language passed a core idea to the next.

2.1 Church’s lambda calculus becomes a programming language

By 1958, the only real option for writing programs was Fortran, which John Backus and his team at IBM had released the year before. Before Fortran, programming meant writing instructions in the machine’s own notation: numbers and abbreviations that corresponded directly to hardware operations. Backus wanted scientists to write something closer to mathematical formulas, and Fortran (short for “Formula Translation”) was the result, the first high-level programming language, fast at arithmetic and accessible to people who were not hardware specialists.

But a researcher at MIT wanted to write programs for artificial intelligence research, and he needed something Fortran could not do: a language that could manipulate symbols, build up complex structures, and treat its own programs as data.

He found his answer in Church’s lambda calculus (Section 1.2). John McCarthy took the idea (functions that take arguments and return values, nothing else) and turned it into a programming language called Lisp, short for “list processing.”

In Lisp, a function was a piece of data like any other. A program could build one, store it in a variable, pass it to another function, or return it as a result, and no other language in 1958 allowed any of that. A Lisp program was itself a list, the same structure the language manipulated, so a program could read and rewrite other programs (Chapter 26 does this in R). And Lisp managed memory on its own: the programmer never had to say “I’m done with this value, free it,” because the language noticed when nothing referred to a value any more and reclaimed the space. That mechanism, garbage collection, runs in every R session you have ever started.

McCarthy had written a mathematical description of how Lisp should evaluate expressions (a function called eval), intending it purely as a theoretical exercise. His graduate student Steve Russell read the paper and realized he could translate eval directly into machine code for the IBM 704. McCarthy later recalled: “Steve Russell said, look, why don’t I program this eval… and I said to him, ho, ho, you’re confusing theory with practice, this eval is intended for reading, not for computing. But he went ahead and did it.” The result was the first working Lisp interpreter.

What does this look like in R?

my_function <- function(x) x + 1
my_function(5)
#> [1] 6

my_function is a value. You could put it in a list, pass it to another function, or replace it with something else entirely. That idea came straight from Lisp. But Lisp itself had a problem: by the 1970s, it had grown enormous, splintered into competing dialects, and accumulated features nobody could agree on. Two people at MIT decided to strip it back to the bones.

2.2 Scheme strips it down

Gerald Jay Sussman was a professor at MIT’s AI Lab; Guy Lewis Steele Jr. was his graduate student. In 1975 they set out to understand Carl Hewitt’s Actor model, a theory of computation built on independent “actors” sending each other messages, and to test it they wrote a tiny Lisp of their own with everything inessential removed. Along the way the theory they were studying collapsed into the one they already had: an actor that receives a message and responds is a function that takes an argument and returns a value. The tiny Lisp was worth keeping. They called it Scheme.

Scheme settled a question older Lisps had left open. When a function refers to a variable, where does it look? Try this in R, and don’t worry about the details yet; just notice that it works:

make_adder <- function(n) {
  function(x) x + n
}

add_ten <- make_adder(10)
add_ten(3)
#> [1] 13

add_ten remembers that n was 10 when it was created, even though make_adder has already finished running. The function found n where it was defined, inside make_adder, and that rule is called lexical scoping. Older Lisps used the other rule, dynamic scoping, where a variable means whatever happens to be in scope at the moment the function is called, so the same function could behave differently depending on who called it. Scheme chose lexical scoping, S copied it, and R inherited it; Chapter 18 builds on it to make functions that remember things.

Scheme also showed that a language can be small. A handful of well-chosen pieces, all consistent with the lambda calculus, is enough to build everything else, and R’s core follows that pattern: most of what feels “built in” is an ordinary R function, and even + can be called as `+`(1, 2). That uniformity comes from Scheme.

Lisp and Scheme were built by computer scientists for computer scientists. Neither had anything to say about data: about columns of measurements and rows of observations, about the daily work of someone trying to understand an experiment. That gap was waiting for someone who did statistics for a living.

2.3 S makes it practical

In 1976, doing statistics at Bell Labs meant writing a Fortran program that called a library of statistical subroutines, compiling it, submitting it to the mainframe’s batch queue, and waiting. Every question about the data cost another round trip.

Rick Becker, John Chambers, Doug Dunn, and Allan Wilks held a series of meetings in the spring of that year, and the question they asked was simple: could they build something interactive, where a statistician types a command and gets an answer back immediately?

They could. The first working version of S ran that same year, as an interactive front end to the Fortran library, and over the next two decades it grew into a full programming language. In 1998 S won the ACM Software System Award, the same award given to Unix, TeX, and the World Wide Web.

Try this:

temperatures <- c(72, 85, 61, 90, 78)
temperatures - 32
#> [1] 40 53 29 58 46

You subtracted 32 from five numbers in one expression, with no loop and no index variable. In Fortran or C you would write the loop yourself and store each result somewhere. S made whole-vector operations the default because it was built for people who think about columns of data, and R kept that default; it is what the book calls vectorization from Chapter 4 onward.

Two smaller decisions from S are visible in every R script. The assignment arrow <- exists because the terminals at Bell Labs had a key that typed a left arrow as a single character, and Chambers used it for assignment, reserving = for named arguments in function calls. And when you “modify” a value in S, the language quietly makes a copy, so your original data is never destroyed. R does the same (Section 3.2), which is why you can always go back.

Functions in S are first-class values, and R kept that. Name lookup is the one place R broke with S: when a function body in S refers to a name it did not define, S looks in the top-level workspace, so make_adder(2) in S would hand back a function that goes looking for n in the workspace instead of remembering the 2. R’s rule for that lookup is Scheme’s, from the section above, and the choice was made in Auckland.

S was eventually sold as a commercial product called S-PLUS. But by then a free competitor was already growing, one that started with a corridor conversation in New Zealand.

2.4 R starts in Auckland

By 1991, S-PLUS was the only way to use the S language, and it was commercial software, expensive for a university department that needed every student to have a copy. In the Department of Statistics at the University of Auckland, students were stuck with clunky programs that made data analysis feel like filing taxes. Two lecturers in that department had a corridor conversation about the problem, and decided to solve it themselves by writing a new implementation of S from scratch.

They kept S’s design and rebuilt everything underneath it, with a different memory model, Scheme’s rule for looking up names, and, eventually, a different package system. They named it R, a play on their first initials and a nod to S. Ross Ihaka had studied at Berkeley and knew the S language inside out; Robert Gentleman brought computational statistics.

Two years after release, Martin Mächler at ETH Zurich convinced them to license it under the GNU General Public License. That decision made R free and open-source, which mattered more than anyone realized at the time: a core development group formed, CRAN started collecting contributed packages, and by the mid-2000s R had become the standard tool for statistical computing in academia.

R looks almost identical to S on the surface, but under the hood it is semantically closer to Scheme. So which pieces came from where?

2.5 What R inherited

Here is the chain, and what each link contributed:

Ancestor	Year	What R inherited
Church’s lambda calculus	1936	Everything is an expression. Functions take arguments and return values.
Lisp	1958	Functions as data. Code as data. Garbage collection.
Scheme	1975	Lexical scoping. Minimalism. Taking lambda calculus seriously.
S	1976	Vectorized operations. Interactive data analysis. <- assignment. Copy-on-modify. Formula objects.
R	1991	Free implementation. Package system (CRAN). Open-source community.

Look again at the five lines from the top of this chapter:

add_tax <- function(price, rate) price * (1 + rate)

prices <- c(10, 25, 8, 42)
with_tax <- sapply(prices, add_tax, rate = 0.2)
with_tax

function(price, rate) creates a function and stores it in a variable, the way you’d store a number: Lisp, 1958. prices * (1 + rate) inside the function operates on the whole vector at once, no loop: S, 1976. sapply(prices, add_tax, rate = 0.2) passes a function to another function: Church, 1936. And add_tax finds rate based on where it was defined, not where it’s called: Scheme, 1975.

The rest of this book is about what you can do with these features once you understand them, starting with the most fundamental one: in R, everything is an expression, and every expression has a value.