Lambda Calculus in Javascript: Two Lectures by Gabriel Lebec (glebec); notes by jcottrell

index.js

// Lambda Calculus - Fundamentals of Lambda Calculus & Functional Programming
// Part 1
// https://www.youtube.com/watch?v=3VQ382QG-y4

const inspect = Symbol.for('nodejs.util.inspect.custom')

// Idiot or Identity or Haskell's id
const I = a => a

// Mockingbird (Haskell cannot implement)
const M = f => f(f)

// Kestrel or Haskell's const
const K = a => b => a

// Kite or K I or Haskell's const id
const KI = K(I)

// Cardinal or Haskell's flip
const C = f => a => b => f(b)(a)

// Lambda calculus True
const T = K
T[inspect] = () => 'T / K'

// Lambda calculus False
const F = KI
F[inspect] = () => 'F / KI'

// not boolean or C / flip
const not = p => p(F)(T)

// and boolean or p => q => p(q)(F)
const and = p => q => p(q)(p)

// or boolean or p => q => p(T)(q) or p => q => p(p)(q)
const or = p => q => M(p)(q)

// equality for booleans or xnor gate or p => q => p(q(T)(F))(q(F)(T))
const beq = p => q => p(q)(not(q))

// Lambda Calculus - Fundamentals of Lambda Calculus & Functional Programming
// Part 2
// https://www.youtube.com/watch?v=pAnLQ9jwN-E

// Lambda calculus 1
const zero = F
const once = f => a => f(a)
const twice = f => a => f(f(a))
const thrice = f => a => f(f(f(a)))

// const succ = n => f => a => f(n(f)(a))
const jsnum = n => n(x => x + 1)(0)
const n0 = zero
const n1 = once
const n2 = twice
const n3 = thrice

// Bluebird or compose or Haskell's (.)
const B = f => g => a => f(g(a))
const compose = B

// successor to determine the next Church numeral
const succ = n => f_ => B(f_)(n(f_))

// const twice = succ(once)
// const twice = f_ => B(f_)(once(f_))
// const twice = f_ => B(f_)(a => f_(a))
// const twice = f_ => f_(a => f_(a))
// jsnum = n => n(x => x + 1)(0)
// jsnum = twice => twice(x => x + 1)(0)
// jsnum = twice => (x => x + 1)(a => (x => x + 1)(a))(0)
// jsnum = twice => (x => x + 1)((x => x + 1)(0))
// jsnum = twice => (x => x + 1)((1))
// jsnum = twice => (x => x + 1)(1)
// jsnum = twice => (1 + 1)

const n4 = succ(thrice)
const n5 = succ(n4)

const add = n => k => n(succ)(k)
const mult = B
// Thrush or C I or Haskell's flip id
const pow = n => k => k(n)

// isZero - where n is n0 then K(F) doesn't run and instead
//  a function waiting to receive an argument and return it
//  is returned (F = ignored K(F) => T => T);
//  Any other Church numeral runs K(F) which returns a function
//  that is waiting for a second argument that it will promptly
//  ignore and just return the F
const isZero = n => n(K(F))(T)

//
// Data structures
//

// Vireo (bird) or a pair or B C T or in Haskell flip . flip id
const V = a => b => f => f(a)(b)
const pair = V
//  Getting the first and second of a pair, in Haskell Fst and Snd
const first = p => p(K) // Kestral
const second = p => p(KI) // Kite

// Deriving subtraction
const phi = p => V(second(p))(succ(second(p)))
const pred = n => first(n(phi)(pair(n0)(n0)))

/*
    B C K I
==============
KI = K I = C K
B1 = B B B
Th = C I
V  = B C Th = B C (C I)

 */

module.exports = {
  I, M, K, KI, C, T, F, not, and, or, beq,
  succ,
  jsnum,
  zero, once, twice, thrice,
  n0, n1, n2, n3, n4, n5,
  B, compose,
  add, mult, pow,
  isZero,
  V, pair, first, second,
  phi, pred
}