30  R as mathematics

Take R and remove everything except function() and the ability to call functions. No numbers. No booleans. No if. No list(). No <- for naming recursive calls. From those two things alone, try to build integers, conditionals, pairs, lists, and recursion.

Surprisingly, it works. Every one of those things can be reconstructed from function() alone. The double <- function(x) x * 2 from Chapter 5, the recursive descents in Chapter 22, the closures that captured variables and carried them somewhere new, all of them are expressions in a formal system that predates computers by decades.

This chapter runs the experiment.

30.1 Lambda calculus in one page

Two expressions to start with:

(function(x) x + 1)(5)
#> [1] 6
(function(x) function(y) x + y)(3)(4)
#> [1] 7

The first builds a function and applies it in the same breath. The second builds a function that returns a function, applies it to 3, and applies the result to 4: a two-argument function rewritten as a chain of one-argument functions, the currying from Section 5.2. Both use exactly three things: a variable, function() to build an abstraction over it, and a call to apply one. Those three are the entire lambda calculus, the system Alonzo Church published in 1936 and that Chapter 1 introduced. Church wrote λx. body where R writes function(x) body, and (f a) where R writes f(a):

Lambda calculus R
λx. x function(x) x
λx. x + 1 function(x) x + 1
(λx. x + 1)(5) (function(x) x + 1)(5)
λx. λy. x + y function(x) function(y) x + y

No numbers, no booleans, no if, no loops, and Church showed that the three are enough to express any computation, the same class of functions Turing’s machine computes (Section 9.6).

The translation works because of a decision about scoping. When the inner function(y) x + y runs, it looks up x in the environment where it was created, not where it was called, which is what the lambda calculus requires: a variable refers to the nearest enclosing abstraction that binds it. R has had that rule, and unrestricted anonymous functions, since its first release (Section 2.5).

So what can you build on that foundation, using nothing else?

Exercises

  1. Write the lambda calculus expression λf. λx. f(f(x)) in R and apply it to sqrt and 256. What do you get?
  2. Write a curried power function: power <- function(n) function(x) x^n. Create square <- power(2) and cube <- power(3). Test them.
  3. What happens if you call (function(x) function(y) x)(1)(2)? Why? Think about which variable the inner function captures.

30.2 Church booleans

Suppose all you have is function(). How do you represent TRUE and FALSE? Start with two curried functions that differ in one letter:

ch_true  <- function(a) function(b) a
ch_false <- function(a) function(b) b
ch_true("yes")("no")
#> [1] "yes"
ch_false("yes")("no")
#> [1] "no"

ch_true takes a, returns a function that takes b and ignores it, and hands back a. ch_false ignores the first argument and returns the second. That is Church’s answer: a boolean is a function that chooses. Give it two things and TRUE picks the first, FALSE the second, which is already if/else. Call a Church boolean with the “then” branch and the “else” branch and it selects one, with no dispatch mechanism, no keyword, and no syntax.

ch_if <- function(cond) function(then_val) function(else_val) {
  cond(then_val)(else_val)
}

ch_if(ch_true)("heads")("tails")
#> [1] "heads"
ch_if(ch_false)("heads")("tails")
#> [1] "tails"

ch_if does almost nothing; it applies the boolean to the two branches, and the boolean does the work.

Now the logical connectives:

ch_and <- function(p) function(q) p(q)(p)
ch_or  <- function(p) function(q) p(p)(q)
ch_not <- function(p) function(a) function(b) p(b)(a)

Watch ch_and(p)(q): if p is true, it picks its first argument, which is q (so the result depends on whether q is also true); if p is false, it picks its second argument, which is p itself (false). The logic lives in the selection behaviour of the booleans themselves.

# TRUE AND FALSE -> FALSE
ch_and(ch_true)(ch_false)("yes")("no")
#> [1] "no"

# TRUE OR FALSE -> TRUE
ch_or(ch_true)(ch_false)("yes")("no")
#> [1] "yes"

# NOT TRUE -> FALSE
ch_not(ch_true)("yes")("no")
#> [1] "no"
TipOpinion

Church booleans make a quiet point about R: if/else is redundant. Conditional logic can be built from functions alone, because R’s built-in if is syntactic sugar for something that function() can already do. A language whose core primitive is powerful enough to subsume its own control flow has a different character from one that added lambdas later.

Exercises

  1. Implement ch_xor (exclusive or) using only Church booleans. Test it on all four input combinations.
  2. Implement ch_eq that checks whether two Church booleans are equal. (Hint: xor followed by not works, or find a direct encoding.)
  3. Write a function to_r_bool that converts a Church boolean back to R’s TRUE/FALSE.

30.3 Church numerals

Numbers are harder to believe. Here are four of them:

zero  <- function(f) function(x) x
one   <- function(f) function(x) f(x)
two   <- function(f) function(x) f(f(x))
three <- function(f) function(x) f(f(f(x)))

Each takes a function f and returns f composed with itself some number of times: zero never applies it, three applies it three times. To see what one of them means, pass it a concrete function and a starting value:

three(function(x) x + 1)(0)
#> [1] 3

Three applications of “add one” to zero gives three. That is the conversion from Church numeral to R integer:

to_int <- function(n) n(function(x) x + 1)(0)

to_int(zero)
#> [1] 0
to_int(two)
#> [1] 2
to_int(three)
#> [1] 3

The successor function adds one more application of f:

succ <- function(n) function(f) function(x) f(n(f)(x))

Read it this way: succ(n) returns a new numeral that, given f and x, first applies f n times (that is n(f)(x)), then applies f one more time on top.

four <- succ(three)
to_int(four)
#> [1] 4

Build higher numbers:

five <- succ(four)
six  <- succ(five)
to_int(six)
#> [1] 6

Addition could be succ repeated, but there is a direct form:

add <- function(m) function(n) function(f) function(x) m(f)(n(f)(x))

to_int(add(two)(three))
#> [1] 5

Read m(f)(n(f)(x)): apply f to x n times, then stack m more applications of f on top, giving m + n in total.

Multiplication: mult(m)(n) means “apply f n times, repeated m times.” Composing n copies of f gives a function that applies f n times; applying that composition m times gives m * n.

mult <- function(m) function(n) function(f) m(n(f))

to_int(mult(two)(three))
#> [1] 6
to_int(mult(three)(three))
#> [1] 9

Exponentiation falls out naturally:

power <- function(m) function(n) n(m)

to_int(power(two)(three))   # 2^3 = 8
#> [1] 8
to_int(power(three)(two))   # 3^2 = 9
#> [1] 9

power(m)(n) applies m, itself a function-repeater, n times: two applied three times is 2^3. The operation that felt most abstract has the shortest definition, because applying a repeater repeatedly is what exponentiation means. Building numbers up is only half the story, though. Can we ask whether a numeral is zero?

The test is short:

is_zero <- function(n) n(function(x) ch_false)(ch_true)

is_zero(zero)("yes")("no")
#> [1] "yes"
is_zero(three)("yes")("no")
#> [1] "no"

zero ignores f and returns x, so it returns ch_true. Any nonzero numeral applies f at least once, and since f always returns ch_false, a single application replaces ch_true with ch_false.

We can also convert R integers to Church numerals. A for loop that reassigns one variable would fall into the trap from Section 20.2, because succ(n) keeps n as a promise and forces it only later, by which time the variable holds the numeral that contains it. Recursion gives each succ its own n:

from_int <- function(n) if (n == 0) zero else succ(from_int(n - 1))

to_int(from_int(5))
#> [1] 5
to_int(add(from_int(3))(from_int(4)))
#> [1] 7

Exercises

  1. Compute mult(from_int(4))(from_int(5)) and convert back to an integer.
  2. Compute power(from_int(2))(from_int(9)) and convert it back. Then try from_int(10) in place of from_int(9). What happens, and why? (?options, under expressions, is the place to look.)
  3. The predecessor function (subtracting one) is famously tricky in Church encoding. Look it up, implement it in R, and test it. This was hard enough that Church himself struggled with it; his student Kleene figured it out, reportedly while getting anesthesia at the dentist.

30.4 Church pairs and lists

A pair is a container that holds two values. In Church encoding, a pair is a function that takes a selector and applies it to both values:

pair <- function(a) function(b) function(f) f(a)(b)
fst  <- function(p) p(function(a) function(b) a)
snd  <- function(p) p(function(a) function(b) b)

pair(a)(b) stores a and b inside a closure, and fst and snd extract them by passing the appropriate selector (which, if you look closely, is just ch_true and ch_false again):

p <- pair("hello")("world")
fst(p)
#> [1] "hello"
snd(p)
#> [1] "world"

From pairs, you can build linked lists. A list is either empty (nil) or a pair of a head and a tail:

nil     <- function(f) function(x) x   # same shape as zero
is_nil  <- function(l) l(function(h) function(t) function(x) ch_false)(ch_true)
cons    <- function(h) function(t) pair(h)(t)
head_of <- function(l) fst(l)
tail_of <- function(l) snd(l)

is_nil passes a selector that ignores both arguments and returns ch_false, then passes ch_true as the default. If l is nil, it behaves like zero: it ignores the selector and returns the default. If l is a cons cell, which is a pair, the selector runs on head and tail, ignores both, and returns ch_false. The structure of the data does the dispatching.

Build a list and walk it:

my_list <- cons("a")(cons("b")(cons("c")(nil)))

head_of(my_list)
#> [1] "a"
head_of(tail_of(my_list))
#> [1] "b"
head_of(tail_of(tail_of(my_list)))
#> [1] "c"

Three nested function calls, and you have a linked list. No vectors, no list(), no memory allocation beyond closures. But one thing is still missing: none of these structures can refer to themselves.

Exercises

  1. Write a length_of function that counts the elements in a Church-encoded list. Use to_int and Church numerals, or use R’s integers for simplicity.
  2. Write map_list that applies a function to every element of a Church list and returns a new Church list.
  3. Implement reverse_list. (Hint: fold from the left, consing onto an accumulator that starts as nil.)

30.5 The Z combinator

A recursive function refers to itself by name, but the lambda calculus has no names and no <-. Section 22.8 built the way around that: a template that takes the function to recurse on as an argument, and a fixed-point combinator that feeds the template to itself. The Y combinator there ran in R only because R hands arguments over as promises. The Z combinator makes the delay explicit by wrapping each self-application in a function of one argument, so it runs in strict languages too, and it is the version this chapter uses:

Z <- function(f) {
  (function(x) f(function(v) x(x)(v)))(
    function(x) f(function(v) x(x)(v))
  )
}

Z(f) builds a function x that, when called, applies f to a delayed version of the recursive call. function(v) x(x)(v) means “do not call x(x) yet; wait until v is provided.”

Use it to define factorial without ever naming the function:

fact <- Z(function(self) function(n) {
  if (n == 0) 1 else n * self(n - 1)
})

fact(5)
#> [1] 120
fact(10)
#> [1] 3628800

self is not a name the function gives itself. It is a parameter, injected by Z. The function never refers to fact; it only refers to self, which Z arranges to be the function itself.

Fibonacci:

fib <- Z(function(self) function(n) {
  if (n <= 1) n else self(n - 1) + self(n - 2)
})

sapply(0:10, fib)
#>  [1]  0  1  1  2  3  5  8 13 21 34 55

A recursive list-sum, using nothing but Church-encoded lists and the Z combinator:

church_sum <- Z(function(self) function(lst) {
  is_nil(lst)(0)(head_of(lst) + self(tail_of(lst)))
})

nums <- cons(10)(cons(20)(cons(30)(nil)))
church_sum(nums)
#> [1] 60

is_nil(lst) returns a Church boolean, and the boolean picks one of its two arguments. On the empty list it picks 0, and the recursive branch, head_of(lst) + self(tail_of(lst)), is never evaluated, because it arrived as a promise (Section 23.1) and nothing forced it. That is the only reason the recursion stops.

A language that evaluates every argument before the call would compute both branches, and the recursive one would run on the empty list, forever. The fix is the same one that turns Y into Z: wrap each branch in a function that takes a dummy argument, let the boolean choose a wrapper, and call the winner.

church_sum_strict <- Z(function(self) function(lst) {
  is_nil(lst)(
    function(dummy) 0
  )(
    function(dummy) head_of(lst) + self(tail_of(lst))
  )("go")
})

church_sum_strict(nums)
#> [1] 60

The "go" argument is unused; it is the trigger that makes the chosen wrapper run.

No for, no while, no Recall(), no named recursion. Just function(), application, and the Z combinator.

TipOpinion

The Z combinator is not practical R code. Its value is conceptual: it proves that recursion is not a primitive operation. Self-reference can be derived from anonymous functions and application alone. That R can express this in code you can paste into a console and run is a direct consequence of its Scheme heritage.

Exercises

  1. Define a recursive length function using Z that counts the elements of a Church list (without converting to R types).
  2. Use Z to write a recursive map over Church lists.
  3. The Y combinator from Section 22.8 also runs in R. Rewrite church_sum with Y in place of Z. Then change Z so that it forces the self-application before calling f (function(x) { y <- x(x); f(y) }) and try again. Which version loops forever, and why?

30.6 The punchline

Here is the inventory. Starting from nothing but function() and function application:

  • Booleans: ch_true, ch_false, ch_and, ch_or, ch_not
  • Conditionals: ch_if (which turned out to be trivial, because booleans are conditionals)
  • Natural numbers: zero, succ, and arithmetic (add, mult, power)
  • Pairs and lists: pair, fst, snd, cons, nil
  • Recursion: the Z combinator

No R integers, no R booleans, no if, no list(), no named recursive functions. Every one of those features reconstructed from function() alone.

This is Church’s result from 1936. When Chapter 1 said that R descends from Church’s model of computation, this is what that means concretely: function() is a universal computational primitive, and everything else is convenience built on top. The requirements are specific: first-class functions, closures, and anonymous functions with no restriction on their bodies. R has all three from Scheme. A language that restricts any of them (Python’s one-expression lambda, C’s function pointers without closures) can run only part of this chapter.

The connection between R and mathematics extends further, into the type system itself.

30.7 Types as propositions

In Chapter 5 a logician noticed that the rules for combining function types looked like the rules for combining propositions. Decades later, in 1969, William Howard wrote the correspondence out in full for constructive logic and typed lambda calculus:

Logic Programming
Proposition Type
Proof Program
A implies B Function type A -> B
A and B Pair type (A, B)
A or B Sum type (either A or B)
True Unit type (a type with one value)
False Empty type (a type with no values)

When you write a function with signature A -> B, you are constructing a proof that if you have an A, you can produce a B. A function integer -> character proves that integers can be converted to characters. If no function of type A -> B can be written, the proposition “A implies B” has no proof.

R’s type system is too loose to enforce this correspondence strictly (every R function can error, which is like a proof that cheats). Haskell, Agda, and Coq take it seriously enough to use programs as machine-checked proofs of theorems. But the connection is there in R: every function you write is, in a formal sense, a small proof.

Under this reading, named the Curry-Howard correspondence for the two people who saw it, a type is a proposition about which values are possible and a function is evidence that a transformation exists. What happens when you start looking at the structure of those propositions and transformations?

30.8 Functors, monoids, and friends

Two of the patterns in this book already carry names from category theory: the functor from Section 19.3 and the monoid from Section 4.1. This section adds the laws that make them trustworthy, and a third pattern that connects them.

Run lapply() over a list:

x <- list(1, 4, 9, 16)
lapply(x, sqrt)
#> [[1]]
#> [1] 1
#> 
#> [[2]]
#> [1] 2
#> 
#> [[3]]
#> [1] 3
#> 
#> [[4]]
#> [1] 4

lapply() applied sqrt to each element and gave back a list of the same length. The container’s shape did not change; only the values inside it did. Strictly, the functor is the list construction itself: it sends a type T to “list of T” and a function f to “apply f to each element”, and lapply() (and purrr’s map()) is the part that lifts the function into the container.

What makes a functor trustworthy is that it obeys two laws. The identity law says mapping a do-nothing function changes nothing:

identical(lapply(x, identity), x)
#> [1] TRUE

The composition law says mapping two functions in sequence gives the same result as mapping their composition in one step:

identical(
  lapply(lapply(x, sqrt), log),    # map sqrt, then map log
  lapply(x, \(v) log(sqrt(v)))     # map the composition directly
)
#> [1] TRUE

A function that mapped elements but scrambled their relationships would break pipelines; chains of lapply() work reliably because both laws hold.

A monoid is a set with an associative operation and an identity element: addition with 0, string concatenation with "". Reduce() (Chapter 21) is the operation that collapses one:

Reduce(paste0, c("a", "b", "c"))
#> [1] "abc"
Reduce(`+`, 1:5)
#> [1] 15

It needs associativity so that the result does not depend on how the intermediate steps are grouped, and an identity element for the empty case. Subtraction fails the first requirement:

(5 - 3) - 1
#> [1] 1
5 - (3 - 1)
#> [1] 3

Different answers. The operations that fold cleanly are the monoids, and when Reduce() surprises you, check whether the operation is one; if it is not, the folding direction matters (Section 21.3).

The third pattern connects two functors. as.list() turns an atomic vector into a list. Map a function before or after the conversion:

x <- c(1, 4, 9)

# map then convert
a <- as.list(sqrt(x))

# convert then map
b <- lapply(as.list(x), sqrt)

identical(a, b)
#> [1] TRUE

The order does not matter. A conversion between containers that commutes with mapping in this way is a natural transformation, and the commuting itself is the naturality condition: as.list() changes the container without disturbing the relationship between the function and the data inside.

pivot_longer() and pivot_wider() (Section 16.2) go further: they are invertible, which makes them natural isomorphisms. Reversibility is a stronger property than naturality alone; it means no information is lost in the reshaping. You can pivot long and then pivot wide and arrive back where you started, because the transformation preserves everything.

None of this requires learning category theory. But these patterns keep showing up because they reflect mathematical structure, and R’s functional design makes them visible.

Exercises

  1. paste0 with Reduce: Reduce(paste0, c("a", "b", "c")) gives "abc". What is the identity element for paste0 as a monoid? Verify by adding it as the init argument: Reduce(paste0, character(0), accumulate = FALSE).
  2. Why is subtraction not a monoid? (Hint: check associativity.) What does this imply about using Reduce with -?
  3. lapply(list(1:3, 4:6, 7:9), rev) applies rev inside each list element. Verify both functor laws (identity and composition) for this example.

30.9 Practical mathematics in R

Church encodings prove R can do mathematics from nothing. But can it do mathematics that matters? Symbolic algebra, arbitrary precision, number theory: each requires capabilities that most R users never discover, because the packages that provide them sit outside the usual statistical workflow.

The Ryacas package connects R to the Yacas computer algebra system, which works with expressions rather than numbers:

library(Ryacas)

# Symbolic differentiation
yac_str("D(x) x^3 + 2*x")  # "3*x^2+2"

# Symbolic integration
yac_str("Integrate(x) x^2")  # "x^3/3"

# Simplification
yac_str("Simplify((x^2-1)/(x-1))")  # "x+1"

Where R’s floating-point arithmetic gives you 0.1 + 0.2 != 0.3 (Section 6.2), symbolic computation works with exact representations. There is no rounding because there are no decimals; expressions stay symbolic until you ask for a numerical result.

The gmp package provides big integers and big rationals:

library(gmp)

# Big integers
factorial(as.bigz(100))  # all 158 digits, exact

# Big rationals: 1/3 stays 1/3, no floating-point error
as.bigq(1, 3) + as.bigq(1, 6)  # 1/2, exactly

The numbers package has prime factorization, GCD, modular arithmetic, and related tools:

library(numbers)

primeFactors(2310)  # 2, 3, 5, 7, 11
GCD(48, 36)         # 12
isPrime(104729)     # TRUE

If you want to sharpen your R skills on mathematical puzzles, Project Euler is a good source. The first few problems are approachable with base R:

# Euler problem 1: sum of multiples of 3 or 5 below 1000
x <- 1:999
sum(x[x %% 3 == 0 | x %% 5 == 0])
#> [1] 233168
# Euler problem 6: difference between sum-of-squares and square-of-sum
n <- 1:100
sum(n)^2 - sum(n^2)
#> [1] 25164150

Both solutions are one-liners because R’s vectorized operations (Section 4.4) make arithmetic on sequences natural.

Exercises

  1. Solve Project Euler problem 2: find the sum of even Fibonacci numbers below four million. (Hint: generate Fibonacci numbers with a while loop or Reduce, filter, sum.)
  2. Install gmp and compute factorial(as.bigz(200)). How many digits does the result have? (Use nchar(as.character(...)).)
  3. 1/3 + 1/3 + 1/3 == 1 returns TRUE in R, but 0.1 + 0.1 + 0.1 == 0.3 returns FALSE. Why? (Review Section 6.2 if needed.)

30.10 The language is still moving

Base R is still absorbing functional idioms, and each addition shrinks the gap between what the language offers and what the lambda calculus requires.

R 4.1 (2021) introduced two changes. The first was \(x) x + 1 as shorthand for function(x) x + 1. Church wrote λ; R now writes \, and the one-character form makes anonymous functions cheap enough to use anywhere: inside lapply(), inside Reduce(), as arguments to Map(). Before R 4.1, the eight letters of function were a tax on every lambda expression.

The second was the native pipe |>. Before R 4.1 the pipe came from the magrittr package (%>%), a function that rewrote the call. The native pipe is syntax: x |> f() is parsed as f(x) before evaluation begins. Function composition is now part of R’s grammar.

R 4.4 (2024) added %||%, which rlang had provided for years. x %||% y returns x unless x is NULL, in which case it returns y: a default combinator, the null-coalescing operator of C#, Swift, and Kotlin, and a shorter spelling of if (is.null(x)) y else x.

Anonymous functions, composition, and null handling, three operations every functional language has, moved into R’s core syntax between 2021 and 2024. The language is still compressing toward its functional core.

30.11 The historical thread

Each idea in this chapter passed through specific hands. The chain is worth tracing because each link solved a problem that the previous link could not.

Could you reduce all of reasoning to calculation? In 1679 the man who had just co-invented calculus, Gottfried Wilhelm Leibniz, imagined a calculus ratiocinator, a formal system that would make thinking mechanical. The dream was premature by two centuries. By the 1870s mathematicians had spent decades making their own foundations rigorous, formalizing limits, infinity, and the number line, and a mathematician in Jena saw that logic could be next. Gottlob Frege’s Begriffsschrift (1879) introduced quantifiers, variables, and functions as logical primitives, the first formal notation for logic itself. Modern mathematical logic begins there. Church’s system of the 1930s kept three constructs, variable, abstraction, and application, and the Church numerals and Church booleans in this chapter are his demonstration that everything else can be built from them.

That was the theory. The question was whether anyone could make it run. McCarthy answered it in 1960 with LISP (Section 2.1), the first programming language where (lambda (x) (+ x 1)) was a direct encoding of Church’s λx. x + 1. But LISP had dynamic scoping, which meant closures did not work the way the theory said they should. Steele and Sussman fixed that in 1975 with Scheme: lexical scoping, first-class closures, and the “Lambda the Ultimate” papers that showed lambda expressions could replace goto, assignment, and most control structures.

In the 1970s, a statistician at Bell Labs who wanted to run a regression still had to write a Fortran program, compile it, and wait. S (Section 2.3) let them type an expression and see the result, with functions and expressions at its core and a computational style borrowed from Fortran. When Ihaka and Gentleman reimplemented S in Auckland in 1993, they gave it Scheme’s lexical scoping in place of S’s rules (Section 2.5). That choice is why closures work in R, why function factories work, and why every Church encoding in this chapter runs without modification.

So the experiment worked. Church showed it was possible, McCarthy made it run, and Ihaka and Gentleman, by choosing Scheme’s scoping rules, made it run in R without anyone asking them to.

30.12 References and sources

Lambda calculus in R:

  • Alonzo Church, “An Unsolvable Problem of Elementary Number Theory” (1936). The paper that started it all.
  • Hindley & Seldin, Lambda-Calculus and Combinators: An Introduction (2008). Accessible textbook covering Church encoding, beta reduction, fixed points.
  • Michaelson, An Introduction to Functional Programming Through Lambda Calculus (2011). Gentle path from lambda calculus to practical FP.
  • Benjamin Pierce, Types and Programming Languages (2002), chapters 5-9. Church booleans, numerals, pairs, recursion via fixed-point combinators.

Curry-Howard correspondence:

  • Howard, “The Formulae-as-Types Notion of Construction” (1969/1980). Types are propositions, programs are proofs.
  • Wadler, “Propositions as Types” (2015, Communications of the ACM). The most readable introduction.

Category theory connections:

  • Bartosz Milewski, Category Theory for Programmers (2019, free online). Accessible introduction with Haskell examples, translatable to R.
  • Mac Lane, Categories for the Working Mathematician (1971). The standard reference.

Recreational mathematics in R:

  • Project Euler. Mathematical puzzles solvable in any language.
  • Ryacas package: symbolic math via Yacas CAS.
  • gmp package: arbitrary precision arithmetic.
  • numbers package: prime factorization, GCD, modular arithmetic.

Historical:

  • Leibniz (1679): the dream of a calculus of reasoning.
  • Frege (1879): formal logic, Begriffsschrift.
  • Church (1936): lambda calculus.
  • Curry (1934 onward): combinatory logic, Curry-Howard correspondence.
  • McCarthy (1960): LISP, first practical lambda calculus.
  • Steele & Sussman (1975): Scheme, “Lambda the Ultimate” papers.
  • Chambers (1976 onward): S language.
  • Ihaka & Gentleman (1993): R, S reimplemented with Scheme’s scoping.