Please take a look at other posts about functional programming in JavaScript:
- Part 1 - what Functional Programming is about
- Part 2 - Functional Pipelines
- Part 3 - the Y Combinator
- Part 4 - Monads
- Part 5 - Trampoline
- Part 6 - Lenses
- Part 7 - Church encoding (booleans)
- Part 8 - Church encoding (arithmetics)
- Part 9 - Church encoding (if, recursion)
- Part 10 - Church encoding (lists)
- Part 11 - Church encoding (strings, objects)
Having lists in our toolbox, we can move forward to strings and objects.
What's a string? A list of characters. We could use two auxiliary functions:
// convert JS string to Church list of characters
const toChurchString = (str) => {
return str.split('').reverse().reduce((acc, char) => {
// Convert char to its code, then to a Church Numeral
const code = char.charCodeAt(0);
const churchNum = (f => x => {
let res = x;
for(let i=0; i<code; i++) res = f(res);
return res;
});
return LIST_NODE(churchNum)(acc);
}, NIL);
};
// convert Church list back to JS string
const fromChurchString = (cStr) => {
let result = "";
let current = cStr;
while(toInt(IS_NIL(current)) === 0) {
const charCode = toInt(HEAD(current));
result += String.fromCharCode(charCode);
current = TAIL(current);
}
return result;
};
String operations are then now just list operations, e.g.:
const APPEND = Y(self => list1 => list2 =>
IF (IS_NIL(list1))
(() => list2)
(() => LIST_NODE(HEAD(list1))(self(TAIL(list1))(list2))));
const str1 = toChurchString("Hello ");
const str2 = toChurchString("world");
const combined = APPEND(str1)(str2);
console.log(fromChurchString(combined)); // "Hello world"
Checking if two string are equal is just checking if two lists are equal. The algorithm would be as follows:
- if both lists are empty - equal
- if one empty, the other not empty - not equal
- if both not empty - compare heads and call recursively for tail comparison
const LIST_EQ = Y(self => l1 => l2 =>
IF (IS_NIL(l1))
// If l1 is empty, they are equal only if l2 is also empty
(() => IS_NIL(l2))
// If l1 is not empty...
(() => IF (IS_NIL(l2))
// ...but l2 is empty, they are not equal
(() => FALSE)
// Both are non-empty: Compare heads and recurse on tails
(() => AND
(EQUALS(HEAD(l1))(HEAD(l2))) // Heads must match
(self(TAIL(l1))(TAIL(l2))) // Tails must match
)
));
console.log( toBool(LIST_EQ(toChurchString('foo'))(toChurchString('foo')) ) ); // true
console.log( toBool(LIST_EQ(toChurchString('foo'))(toChurchString('bar')) ) ); // false
How to have objects?
First approach would be to have a list of pairs, label (field name) and value. We could even have numbers as labels (to simplify the example).
Assuming 1 is NAME and 2 is AGE, a list:
PAIR(PAIR(AGE)(25))(PAIR(PAIR(NAME)(72))(NIL))
would conceptually represent and object { "age" : "25", "name" : "72" }.
Getting a value from the object is just then yet another way of traversing the list:
const NAME = ONE;
const AGE = TWO;
const CITY = THREE;
// A helper to make creating entries easier: (Key, Value)
const ENTRY = k => v => PAIR(k)(v);
// Create the "Object": { AGE: 3, NAME: 1 }
const user = LIST_NODE(ENTRY(AGE)(THREE))
(LIST_NODE(ENTRY(NAME)(ONE))
(NIL));
Querying the object is just yet another version of list traversal:
const GET = Y(self => key => list =>
IF (IS_NIL(list))
(() => FALSE) // Base case: not found
(() =>
// We "extract" the head and pass it into a function
// that acts as our scope for 'entry'
(entry =>
IF (EQUALS(key)(FIRST(entry)))
(() => SECOND(entry)) // Found it!
(() => self(key)(TAIL(list))) // Keep looking
)(HEAD(list)) // This is where 'entry' is bound
)
);
// Querying the object
const ageResult = GET(AGE)(user);
const nameResult = GET(NAME)(user);
console.log("User Age:", toInt(ageResult)); // 3
console.log("User Name ID:", toInt(nameResult)); // 1
In second approach, an object could just be a function that gets a key and returns a value. Adding new keys would just mean wrapping existing function inside the new function:
// A "Church Object" is a function that takes a key 'k'
const EMPTY_OBJ = k => FALSE;
// To add a property, we wrap the old object in a new function
const SET = obj => key => value =>
requestedKey =>
IF (EQUALS(requestedKey)(key))
(() => value)
(() => obj(requestedKey));
const user_2 = SET(SET(EMPTY_OBJ)(NAME)(ONE))(AGE)(THREE);
// To "get" a value, you just call the object with the key!
const name2 = user_2(NAME);
const age2 = user_2(AGE);
console.log("Pure Functional Object - Name:", toInt(name2)); // 1
console.log("Pure Functional Object - Age:", toInt(age2)); // 3
This feels like the ultimate, functional approach to objects. No lists, no loops to search, just nested chain of closures, each new SET just creates a closure that "remembers" the key/value and an original object inside!
If a new object could also "peek" in an existing object for a value, so that a new object possibly points to another one, its prototype, we could have a functional approach to prototypal inheritance. It's just a step ahead of what we did here!
How to have methods that can possibly access the this parameter? Well, we can put functions in objects (as fields) and when we call the function, we call the functtion passing the owning object to the function!
// another label (field name)
const DOGAGE = FOUR;
// a const
const SEVEN = SUCC(SUCC(SUCC(FOUR)));
// A Method that calculates 'Age in Dog Years'
// It expects 'self' so it can look up 'AGE'
// like: (this) => this.age * 7
const get_dog_age_f = self => MUL(self(AGE))(SEVEN);
const user_3 = SET(SET(EMPTY_OBJ)(DOGAGE)(get_dog_age_f))(AGE)(THREE);
// send "message" (key) to the object which expects to call the function passing the object to
// the function
const SEND = obj => key => obj(key)(obj);
// --- Execution ---
// we "SEND" the DOGAGE message (field name) to the object
// this calls the function, passing the object as "self" to it!
const result = SEND(user_3)(DOGAGE);
console.log("Dog Years:", toInt(result)); // 21 (3 * 7)
Note that with one extra argument, we could call a method from an object, passing another possibly unrelated object as this! Does it sound familiar?
One of the last features of the encoding we could cover would be the let binding and while loop.
Let's start with LET. In languages where memory can be given a label, you can store arbitrary intermediate results in variables:
let x = 3; let y = foo(); ...
What such assignment is really about?
Take a look: let x = 3; do something with x - it actually means that you have to "do something with x given x is 3"!
In other words:
let x = VALUE; do something with x;
is in fact:
(x => do something with x)(VALUE)
!
We can then define LET as:
// LET = value => body => body(value) const LET = v => f => f(v);
and use it:
// x = 4
// y = 7
// return x + y
console.log(
toInt(
LET(FOUR)(x =>
LET(SEVEN)(y =>
ADD(x)(y)
)
) ) );
Now, consider what a while loop is about - it's just a recursive function over a state! Is has:
- a condition - it recursively loops until the condition is falsified
- a transformer - it transforms the state to a new state
- an initial state
A straight implementation would be then:
const WHILE = Y(self => condition => transform => state =>
IF (condition(state))
// if true: execute the transformation and recursively call in new state
(() => self(condition)(transform)(transform(state)))
// if false: return state
(() => state)
);
This allows us to have:
const condition = n => NOT(IS_ZERO(n)); const transform = n => PRED(n); const initial = FIVE; const result = WHILE(condition)(transform)(initial); console.log( toInt( result ) );
This works but it's quite disappointing. It's great that while returns a value but the value is always bound to falsified condition, in this example case, WHILE returns 0 no matter what it "does" internally.
How to make it usable? Well, with an idea:
- initial state is a pair: (index, accumulator)
- condition works in the index, possibly just checks if it's equal to ZERO
- transform transforms the pair (index, accumulator) to a new pair (index', accumulator')
This way, the SECOND element of the returned pair is the accumulator - the actual "result" of the loop!
Let's try it on an example. Let's write a WHILE loop that sums values from 5 to 0:
const condition = pair => NOT(IS_ZERO(FIRST(pair))); // index != 0
const transform =
pair =>
LET(FIRST(pair))(i =>
LET(SECOND(pair))(a =>
PAIR(PRED(i))(ADD(i)(a))));
const initial = PAIR(FIVE)(ZERO);
const result = WHILE(condition)(transform)(initial);
console.log( toInt( SECOND(result) ) ); // 15
We can now refactor it to a single function:
const SUM_0TON = n =>
SECOND( // return accumulator from (index, accumulator)
WHILE
(pair => NOT(IS_ZERO(FIRST(pair)))) // while index != 0
(pair => // take (index, accumulator)
LET(FIRST(pair))(i => // i = index
LET(SECOND(pair))(a => // a = accumulator
PAIR(PRED(i))(ADD(i)(a)))) // return (i-1, a+i)
)
(PAIR(n)(ZERO)) // initial state: (index, accumulator) = (n,0)
);
console.log( toInt( SUM_0TON(FIVE) ) ); // 15
Why bother looping over pairs every time? Let's have FOR that separates looping over index from transforming the accumulator!
const FOR = init_i => step => init_acc => body =>
SECOND(
WHILE
(pair => NOT(IS_ZERO(FIRST(pair))))
(pair =>
LET(FIRST(pair))(index =>
LET(SECOND(pair))(acc =>
PAIR(step(index))(body(acc)(index))
)
)
)
(PAIR(init_i)(init_acc))
);
// start with n, loop to 0 with PRED
// accumulate i+acc on every step
const SUM_0TON_2 = n => FOR(n)(PRED)(ZERO)(acc => i => ADD(acc)(i));
console.log( toInt( SUM_0TON_2(FIVE) ) );
If it bothers you that the FOR condition always expects that loop index is ZERO, let's abstract that too:
const FOR2 = init_i => end_i => step => init_acc => body =>
SECOND(
WHILE
(pair => NOT(EQUALS(end_i)(FIRST(pair))))
(pair =>
LET(FIRST(pair))(index =>
LET(SECOND(pair))(acc =>
PAIR(step(index))(body(acc)(index))
)
)
)
(PAIR(init_i)(init_acc))
);
// from n to ZERO desc
const SUM_0TON_3 = n => FOR2(n)(ZERO)(PRED)(ZERO)(acc => i => ADD(acc)(i));
console.log( toInt( SUM_0TON_3(FIVE) ) );
// from 0 to n+1 (not including n+1)
const SUM_0TON_4 = n => FOR2(ZERO)(SUCC(n))(SUCC)(ZERO)(acc => i => ADD(acc)(i));
console.log( toInt( SUM_0TON_4(FIVE) ) );
which can be further refactored to
const FOR3 = init_i => cond => step => init_acc => body =>
SECOND(
WHILE
(pair => cond(FIRST(pair)))
(pair =>
LET(FIRST(pair))(index =>
LET(SECOND(pair))(acc =>
PAIR(step(index))(body(acc)(index))
)
)
)
(PAIR(init_i)(init_acc))
);
// acc = 0
// for i=0; i<n; i++
// acc = acc + i
const SUM_0TON_5 = n => FOR3(ZERO)(i => LEQ(i)(n))(SUCC)(ZERO)(acc => i => ADD(acc)(i));
console.log( toInt( SUM_0TON_5(FIVE) ) );
With booleans, numbers, strings, objects, if, variables and loops, we are free to code whatever we want!
A short summary of what we've covered:
| Concept | Standard programming | Church encoding |
|---|---|---|
| Booleans | true, false | x=>y=>x, x=>y=>y |
| Numbers | 3 | f => x => f(f(f(x))) |
| Branching | if (p) { a } else { b } | p(a)(b) |
| Variables | let x = 3; doWork(x); | LET(3)(x => doWork(x)) |
| Loops | initial; while (condition) { transform }; | WHILE(condition)(transform)(initial) |
| Loops | for (initial; condition; loop transform ) { accumulator transform } | FOR(intial)(loop transform)(condition)(accumulator transform) |
| Lists/Arrays | [1, 2] | PAIR(1)(PAIR(2)(NIL)) (almost :), it was in fact slightly more complicated to make it work in JS) |
| Objects | obj.prop | obj(KEY) |
| Methods | obj.doWork() | SEND(obj)(DO_WORK) |
You can continue on your own from here:
- create more complicated methods that possibly have more arguments
- make your field names not numbers but strings
- add the EXTEND function that takes an existing object and creates a new one with the given set as prototype
- find out how negative numbers or floating point numbers can be encoded
Happy coding!
