church-encoding

This is a thought exercise in functional programming to represent most of the javascript primitives using only lambdas (anonymous functions). It's not intended to be used in any production user facing software.

Motivation

I was informally introduced to this idea by watching this talk by John Hughes which is based on his paper. This talk by Philip Walder brilliantly explains this in a more historical context. The SICP book also introduced me to using lambdas and recursive constructs to define operations on lists. There are many more comprehensive implementations in typed functional languages but I wanted to see how far I could go without a formal type system and combinators. Ultimately, on a more philosophical note, this exercise sufficiently proves that:

Mathematics is not invented. It is discovered.

Install

npm install @f0rr0/church-encoding@latest

or if you're using yarn

yarn add @f0rr0/church-encoding@latest

Usage

There are 3 different builds in commonjs, umd and esmodule format, should you have a preference or environment constraints. Normally, modern tools will automatically pick the esmodule build which enables tree-shaking.

  import {
    cons,
    emptyList,
    zero,
    inc,
    map,
    mul,
    decodeInteger,
    decodeList
  } from '@f0rr0/church-encoding';

  const one = inc(zero);
  const two = inc(one);
  const list = cons(zero, cons(one, cons(two, emptyList)));
  
  const listOfNative = map(decodeInteger, list);
  console.log(decodeList(listOfNative)); // [0, 1, 2]
  
  const doubleList = map(i => mul(two, i), list);
  
  const doubleListOfNative = map(decodeInteger, doubleList);
  console.log(decodeList(doubleListOfNative)); // [0, 2, 4]

API

The API is organized into five parts which progressively build on each other. However, since everything is a function, they are not namespaced into separate exports. The function names pretty much sum up what they do.

1. Boolean
2. List
3. Natural Number
4. Integer
5. Decode

Boolean

• T
• F
• IF
• AND
• OR
• NOT

List

• emptyList
• cons
• head
• tail
• isEmpty
• map
• filter
• nth
• length

Natural Number

• zeroNat
• isZeroNat
• incNat
• decNat
• addNat
• subNat
• isEqualNat
• mulNat
• expNat
• isLessThanNat
• isLessThanEqualNat
• isGreaterThanNat
• isGreaterThanEqualNat
• divNat
• modNat

Integer

• pair
• first
• second
• zero
• isZero
• inc
• dec
• normalize
• abs
• negate
• add
• sub
• isEqual
• mul
• exp
• isNegative
• isLessThan
• isLessThanEqual
• isGreaterThan
• isGreaterThanEqual

Decode

• decodeBool
• decodeList
• decodeNat
• decodeInteger

Limitations

I still have to work on implementing rational numbers so that integer division can work. There are no throw or Error statements in the codebase since I strived to only use lambdas. Therefore, you need to be careful to not do mathematically impossible stuff e.g. divide a natural number by zeroNat, or else you'd be presented with a cryptic error.