Lambda Calculus in JavaScript

After watching Gabriel Lebec’s great talk on the fundamentals of lambda calculus, I decided to implement the types and combinators that he covered in JavaScript.

Lambda Calculus in JavaScript

tags: lambda calculusfunctional programming

After watching Gabriel Lebec’s excellent talk on the fundamentals of lambda calculus, I decided to implement all of the types and combinators that he covered.

His talk Lebec recommends a couple books, one of which is To Mock a Mockingbird, which I recently picked up.

You can also view this code in a gist, if you prefer.

1let { log } = console
2
3I = a => a
4M = f => f(f)
5K = a => b => a
6KI = a => b => b
7C = f => a => b => f(b)(a)
8
9I.inspect = () => "I := 𝝺a.a"
10M.inspect = () => "M := 𝝺f.ff"
11K.inspect = () => "K := 𝝺ab.a"
12KI.inspect = () => "KI := 𝝺ab.b"
13C.inspect = () => "C := 𝝺fab.fba"
14
15T = K
16F = KI
17T.inspect = () => "T / K"
18F.inspect = () => "F / KI"
19_ = () => "noop"
20
21/**********************************************/
22/*** (I) Idiot ~> I := 𝝺a.a ***/
23
24I(I) == I
25I(M) == M
26
27/**********************************************/
28/*** (M) Mockingbird ~> M := 𝝺f.ff ***/
29
30M(I) == I
31// What happens when we self-apply self-application (MM)?
32try {
33 M(M)
34} catch (e) {
35 log(e.message)
36}
37// => Maximum call stack size exceeded
38
39/**********************************************/
40/*** (K) Kestral ~> K := 𝝺ab.a ***/
41
42constant_5 = K(5)
43constant_5(I) == 5
44constant_5(M) == 5
45constant_5(1) == 5
46constant_5(_) == 5
47
48/**********************************************/
49/*** (KI) Kite ~> KI := 𝝺ab.b ***/
50
51KI(1)(0) == K(I)(1)(0)
52/* Kite can be derived from Kestral of identity, or KI;
53 it can also be derived from CK */
54KI == F
55KI(M)(KI) == F
56
57/**********************************************/
58/*** (C) Cardinal ~> C := 𝝺fab.fba ***/
59
60divide = a => b => a / b
61C(divide)(9)(1) == 1 / 9
62C(K)(2)(3) == 3
63
64// C takes a function, 2 arguments, and reverses or "flips" them.
65// CK takes 2 things, returns the 2nd, which sounds familiar...
66// CK and KI are equivalent!
67C(K)(I)(M) == KI(I)(M)
68C(K)(I)(M) == M
69C(K)(I)(M) == I
70
71// CK is built into Haskell as:
72// flip const 1 8 == 8
73
74/*** Booleans ***/
75
76not = p => p(F)(T)
77// - : not ~> 𝝺p.pFT
78
79not(T) == F
80not(F) == T
81not(K) == KI
82not(KI) == K
83
84// NOT is how we achieve negation.
85// Here we're using "booleans" to select 1st value if p is true, otherwise 2nd
86// NOT, then, "flips" that formula around. We've already seen flip:
87
88C(T)(1)(2) == 2 // select 2nd, instead of 1st, on T
89C(F)(1)(2) == 1 // select 1st, instead of 2nd, on F
90
91// The difference is that C generates a new fn, instead of just returning T / F
92// So basically we've recreated KI and K, respectively.
93// C(T) & KI, C(F) & K have _extensional_, not intensional equality.
94
95and = p => q => p(q)(p)
96// - : and ~> 𝝺pq.pqp
97
98// AND is also known as conjunction.
99// if p is F, short-circuit & select itself (p)
100// if p is T, q determines whether the entire statement is T or F, so defer to q
101and(T)(T) == T
102and(F)(T) == F
103and(T)(F) == F
104and(F)(F) == F
105
106or = p => q => p(p)(q)
107// - : or ~> 𝝺pq.ppq
108
109// OR is also known as disjunction, or M* (see the beta reduction below)
110// if p is T, short-circuit; we only need 1 T for OR, so p self-selects.
111// if p is F, defer to q; q determines whether the expression is T or F
112or(T)(T) == T
113or(T)(F) == T
114or(F)(T) == T
115or(F)(F) == F
116
117// let's do a beta reduction substituting x and y for p and q:
118
119// (𝝺pq.ppq)xy
120// (𝝺pq.ppq)xy = xxy
121// xy = xxy
122// x = xx
123// Mf = ff
124
125// This is known as the Mockingbird-Once-Removed, or M*, because we have Mxy = Mxxy instead of just Mx = Mxx
126
127M(T)(T) == T
128M(T)(F) == F
129M(F)(F) == T
130M(F)(F) == F
131
132// boolean equality?
133beq = p => q => p(q)(not(q))
134// - : beq ~> 𝝺pq.p(qTF)(qFT), or:
135// - : beq ~> 𝝺pq.pq(NOT q)
136
137beq(T)(T) == T
138beq(F)(T) == F
139beq(T)(F) == F
140beq(F)(F) == T
141
142/*** NOTES: ***
143
144 * Q: What's a combinator?
145
146 * A: A combinator is a higher-order function that uses only function
147 * application and earlier defined combinators to define a result
148 * from its arguments (Wikipedia: Combinatory Logic)
149
150 * ...or: "Functions with no free variables"
151
152 ***/