Lambda Calculus in JavaScript

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 ***/