Functional programming in JavaScript (11)

Please take a look at other posts about functional programming in JavaScript:

1. Part 1 - what Functional Programming is about
2. Part 2 - Functional Pipelines
3. Part 3 - the Y Combinator
4. Part 4 - Monads
5. Part 5 - Trampoline
6. Part 6 - Lenses
7. Part 7 - Church encoding (booleans)
8. Part 8 - Church encoding (arithmetics)
9. Part 9 - Church encoding (if, recursion)
10. Part 10 - Church encoding (lists)
11. 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:

1. if both lists are empty - equal
2. if one empty, the other not empty - not equal
3. 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. 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)
      )
    ) ) );

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))
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:

1. create more complicated methods that possibly have more arguments
2. make your field names not numbers but strings
3. add the EXTEND function that takes an existing object and creates a new one with the given set as prototype
4. find out how negative numbers or floating point numbers can be encoded

Happy coding!