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.

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 } = console23I = a => a4M = f => f(f)5K = a => b => a6KI = a => b => b7C = f => a => b => f(b)(a)89I.inspect = () => "I := 𝝺a.a"10M.inspect = () => "M := 𝝺f.ff"11K.inspect = () => "K := 𝝺ab.a"12KI.inspect = () => "KI := 𝝺ab.b"13C.inspect = () => "C := 𝝺fab.fba"1415T = K16F = KI17T.inspect = () => "T / K"18F.inspect = () => "F / KI"19_ = () => "noop"2021/**********************************************/22/*** (I) Idiot ~> I := 𝝺a.a ***/2324I(I) == I25I(M) == M2627/**********************************************/28/*** (M) Mockingbird ~> M := 𝝺f.ff ***/2930M(I) == I31// 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 exceeded3839/**********************************************/40/*** (K) Kestral ~> K := 𝝺ab.a ***/4142constant_5 = K(5)43constant_5(I) == 544constant_5(M) == 545constant_5(1) == 546constant_5(_) == 54748/**********************************************/49/*** (KI) Kite ~> KI := 𝝺ab.b ***/5051KI(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 == F55KI(M)(KI) == F5657/**********************************************/58/*** (C) Cardinal ~> C := 𝝺fab.fba ***/5960divide = a => b => a / b61C(divide)(9)(1) == 1 / 962C(K)(2)(3) == 36364// 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) == M69C(K)(I)(M) == I7071// CK is built into Haskell as:72// flip const 1 8 == 87374/*** Booleans ***/7576not = p => p(F)(T)77// - : not ~> 𝝺p.pFT7879not(T) == F80not(F) == T81not(K) == KI82not(KI) == K8384// NOT is how we achieve negation.85// Here we're using "booleans" to select 1st value if p is true, otherwise 2nd86// NOT, then, "flips" that formula around. We've already seen flip:8788C(T)(1)(2) == 2 // select 2nd, instead of 1st, on T89C(F)(1)(2) == 1 // select 1st, instead of 2nd, on F9091// The difference is that C generates a new fn, instead of just returning T / F92// So basically we've recreated KI and K, respectively.93// C(T) & KI, C(F) & K have _extensional_, not intensional equality.9495and = p => q => p(q)(p)96// - : and ~> 𝝺pq.pqp9798// 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 q101and(T)(T) == T102and(F)(T) == F103and(T)(F) == F104and(F)(F) == F105106or = p => q => p(p)(q)107// - : or ~> 𝝺pq.ppq108109// 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 F112or(T)(T) == T113or(T)(F) == T114or(F)(T) == T115or(F)(F) == F116117// let's do a beta reduction substituting x and y for p and q:118119// (𝝺pq.ppq)xy120// (𝝺pq.ppq)xy = xxy121// xy = xxy122// x = xx123// Mf = ff124125// This is known as the Mockingbird-Once-Removed, or M*, because we have Mxy = Mxxy instead of just Mx = Mxx126127M(T)(T) == T128M(T)(F) == F129M(F)(F) == T130M(F)(F) == F131132// boolean equality?133beq = p => q => p(q)(not(q))134// - : beq ~> 𝝺pq.p(qTF)(qFT), or:135// - : beq ~> 𝝺pq.pq(NOT q)136137beq(T)(T) == T138beq(F)(T) == F139beq(T)(F) == F140beq(F)(F) == T141142/*** NOTES: ***143144 * Q: What's a combinator?145146 * A: A combinator is a higher-order function that uses only function147 * application and earlier defined combinators to define a result148 * from its arguments (Wikipedia: Combinatory Logic)149150 * ...or: "Functions with no free variables"151152 ***/