Functional programming in JavaScript (10)

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)

In the next blog entry, we continue the Church encoding of various language elements into JavaScript. We already did booleans, numbers, IF and recursion.

This time we'll do lists.

Lists can be implemented using pairs, a list of (1,2,3,4) is just (1, (2, (3, 4))), nested pairs. Other complex objects can be built on top of this idea.

If you need PAIR/FIRST/SECOND, just go back to the previous blog entry.

// NIL is a pair where the first element is TRUE (a flag for "I am empty")
const NIL    = PAIR(TRUE)(TRUE); 
const IS_NIL = l => FIRST(l); // Returns TRUE if it's NIL, FALSE if it's a real PAIR

// Re-defining PAIR for numbers to ensure FIRST(l) is always FALSE
const LIST_NODE = x => y => PAIR(FALSE)(PAIR(x)(y));
const HEAD = l => FIRST(SECOND(l));
const TAIL = l => SECOND(SECOND(l));

And that's it! We can define a list and an example operation on a list:

// Building the list: [1, 2, 3]
const list1 = LIST_NODE(ONE)(NIL);
const list2 = LIST_NODE(TWO)(list1);
const list3 = LIST_NODE(THREE)(list2); // This is [3, 2, 1]

// --- sum function 
const SUMLIST = Y(self => list => 
  IF (IS_NIL(list))
    (() => ZERO) 
    (() => ADD(HEAD(list))(self(TAIL(list)))));

console.log( toInt(SUMLIST(list3)) );

We could also have an auxiliary toArray function, similar to previous toInt and toBool:

const toArray = (list, elementConverter = (x => x)) => {
  const result = [];
  let current = list;

  // While IS_NIL is FALSE (using toInt to bridge the Church Boolean to JS)
  while (toInt(IS_NIL(current)) === 0) {
    // 1. Get the data from the current node
    const churchValue = HEAD(current);
    
    // 2. Convert and push to our JS array
    result.push(elementConverter(churchValue));
    
    // 3. Move to the next node
    current = TAIL(current);
  }
  
  return result;
};

console.log( toArray( list3, toInt ) ); // [3,2,1]

How about MAP or other list operations that just transform list to another list?

Well, using all the tools we have, it's easy:

const MAP = Y(self => f => list =>
  IF (IS_NIL(list))
    (() => NIL)
    (() => LIST_NODE(f(HEAD(list)))(self(f)(TAIL(list)))));

// Example: Double every number in the list
const DOUBLE = n => ADD(n)(n);
const doubledList = MAP(DOUBLE)(list3); // [6, 4, 2]

console.log("First item doubled:", toInt(HEAD(doubledList))); // 6
console.log("Total:", toInt(SUMLIST(doubledList)));           // 12

And that's it. You can continue from here on your own. Define other operators, write more high level functions. Experiment.

Just to give you some more ideas:

const LEQ = m => n => IS_ZERO(SUB(m)(n));  // no negative numbers, subtracting from ZERO stays at ZERO!
const GT = m => n => NOT(LEQ(m)(n));
const LT = m => n => NOT(LEQ(n)(m));

console.log( toBool( LEQ(TWO)(FOUR)) ); // true
console.log( toBool( LEQ(FOUR)(TWO)) ); // false
console.log( toBool( LEQ(TWO)(TWO)) );  // true
console.log( toBool( LT(TWO)(FOUR)));   // true
console.log( toBool( LT(FOUR)(TWO)));   // false
console.log( toBool( LT(FOUR)(TWO)) );  // false

A complete code of all examples of Church encoding:

const TRUE  = a => b => a;
const FALSE = a => b => b;

const AND = p => q => p(q)(p);
const OR  = p => q => p(p)(q);
const NOT = p => p(FALSE)(TRUE);

const toBool = f => f(true)(false);

console.log( toBool( TRUE ) );
console.log( toBool( FALSE ) );

console.log( toBool( AND(TRUE)(TRUE) ) );
console.log( toBool( AND(FALSE)(TRUE) ) );
console.log( toBool( AND(TRUE)(FALSE) ) );
console.log( toBool( AND(FALSE)(FALSE) ) );

console.log( toBool( OR(TRUE)(TRUE) ) );
console.log( toBool( OR(FALSE)(TRUE) ) );
console.log( toBool( OR(TRUE)(FALSE) ) );
console.log( toBool( OR(FALSE)(FALSE) ) );

console.log( toBool( NOT(TRUE) ) );
console.log( toBool( NOT(FALSE) ) );

const ZERO  = f => x => x;
const ONE   = f => x => f(x);
const TWO   = f => x => f(f(x));
const THREE = f => x => f(f(f(x)));

const toInt = n => n(i => i + 1)(0);

console.log( toInt( ZERO ) );
console.log( toInt( ONE ) );
console.log( toInt( TWO ) );
console.log( toInt( THREE ) );

const SUCC  = n => f => x => f(n(f)(x));

const FOUR = SUCC(THREE);
console.log( toInt( FOUR ) );

const ADD   = m => n => f => x => m(f)(n(f)(x));
const MUL   = m => n => f => m(n(f));

console.log( toInt( ADD(TWO)(THREE) ) );
console.log( toInt( MUL(TWO)(THREE) ) );

//const POW = m => n => n(m);
const POW = m => n => f => n(m)(f);

console.log( toInt( POW(TWO)(FOUR) ) );

// --- lists
const PAIR   = x => y => f => f(x)(y);
const FIRST  = p => p(TRUE);
const SECOND = p => p(FALSE);

// A helper that takes a pair (n, n+1) and returns (n+1, n+2)
const PHI = p => PAIR(SECOND(p))(SUCC(SECOND(p)));

// PRED starts at (0, 0), applies PHI 'n' times, then takes the FIRST element
const PRED = n => FIRST(n(PHI)(PAIR(ZERO)(ZERO)));

// SUBTRACT(m)(n) is just applying PRED to m, n times.
const SUB = m => n => n(PRED)(m);

console.log( toInt( PRED(FOUR) ) );
console.log( toInt( SUB(FOUR)(TWO) ) );
console.log( toInt( SUB(TWO)(FOUR) ) );

// --- if
const IF = p => a => b => p(a)(b)();

// --- recursion
const Y = f => (x => x(x))(x => f(y => x(x)(y)));

const IS_ZERO = n => n(x => FALSE)(TRUE);

const EQUALS = m => n => 
  AND (IS_ZERO(SUB(m)(n))) 
      (IS_ZERO(SUB(n)(m)));

// --- THE FAC FUNCTION ---
const FAC = Y(self => n =>
  IF (EQUALS(n)(ONE))               // if n == 1
    (() => ONE)                     //    return 1
    (() => MUL(n)(self(PRED(n))))); //    else return n * fac(n-1)

console.log( toInt( FAC(FOUR) ) );

// NIL is a pair where the first element is TRUE (a flag for "I am empty")
const NIL    = PAIR(TRUE)(TRUE); 
const IS_NIL = l => FIRST(l); // Returns TRUE if it's NIL, FALSE if it's a real PAIR

// Re-defining PAIR for numbers to ensure FIRST(l) is always FALSE
const LIST_NODE = x => y => PAIR(FALSE)(PAIR(x)(y));
const HEAD = l => FIRST(SECOND(l));
const TAIL = l => SECOND(SECOND(l));

// Building the list: [1, 2, 3]
const list1 = LIST_NODE(ONE)(NIL);
const list2 = LIST_NODE(TWO)(list1);
const list3 = LIST_NODE(THREE)(list2); // This is [3, 2, 1]

// --- sum list
const SUMLIST = Y(self => list => 
  IF (IS_NIL(list))
    (() => ZERO) 
    (() => ADD(HEAD(list))(self(TAIL(list)))));

console.log( toInt(SUMLIST(list3)) );

const toArray = (list, elementConverter = (x => x)) => {
  const result = [];
  let current = list;

  // While IS_NIL is FALSE (using toInt to bridge the Church Boolean to JS)
  while (toInt(IS_NIL(current)) === 0) {
    // 1. Get the data from the current node
    const churchValue = HEAD(current);
    
    // 2. Convert and push to our JS array
    result.push(elementConverter(churchValue));
    
    // 3. Move to the next node
    current = TAIL(current);
  }
  
  return result;
};

console.log( toArray( list3, toInt ) ); // [3,2,1]

// --- map
const MAP = Y(self => f => list =>
  IF (IS_NIL(list))
    (() => NIL)
    (() => LIST_NODE(f(HEAD(list)))(self(f)(TAIL(list)))));

// Example: Double every number in the list
const DOUBLE = n => ADD(n)(n);
const doubledList = MAP(DOUBLE)(list3); // [6, 4, 2]

console.log("First item doubled:", toInt(HEAD(doubledList))); // 6
console.log("Total:", toInt(SUMLIST(doubledList))); // 6

const LEQ = m => n => IS_ZERO(SUB(m)(n));  // no negative numbers, subtracting from ZERO stays at ZERO!
const GT = m => n => NOT(LEQ(m)(n));
const LT = m => n => NOT(LEQ(n)(m));

console.log( toBool( LEQ(TWO)(FOUR)) ); // true
console.log( toBool( LEQ(FOUR)(TWO)) ); // false
console.log( toBool( LEQ(TWO)(TWO)) );  // true
console.log( toBool( LT(TWO)(FOUR)));   // true
console.log( toBool( LT(FOUR)(TWO)));   // false
console.log( toBool( LT(FOUR)(TWO)) );  // false

Happy coding!

Functional programming in JavaScript (9)

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)

We continue our Church encoding of numbers. In the last post we've defined ADD/MUL/POW.

How do we define SUB?

To have SUB, we have to have PRED, the predecessor function. How do we get this?

Turns out, this is tricky. SUCC was about applying a function. How do you un-apply a function?

The solution found by Stephen Klenee in 30s involves pairs and so called sliding window.

Start with a pair of (0,0). Then apply function (a,b) => (b, b+1) to it n times. Then take first element of the pair.

Got it? Let's try for 3. (0,0) -> (0,1) -> (1,2) -> (2,3). First element of the result pair is 2.

To have this in our encoding system, we define some helper functions and then, the PRED. With PRED, we can have SUB:

// --- pairs
const PAIR   = x => y => f => f(x)(y);
const FIRST  = p => p(TRUE);
const SECOND = p => p(FALSE);

// A helper that takes a pair (a,b) and returns (b, b+1)
const PHI = p => PAIR(SECOND(p))(SUCC(SECOND(p)));

// PRED starts at (0, 0), applies PHI 'n' times, then takes the FIRST element
const PRED = n => FIRST(n(PHI)(PAIR(ZERO)(ZERO)));

// SUBTRACT(m)(n) is just applying PRED to m, n times.
const SUB = m => n => n(PRED)(m);

console.log( toInt( PRED(FOUR) ) );
console.log( toInt( SUB(FOUR)(TWO) ) );

We are finally ready to have IF and recursion (using the Y discussed eariler). Note that IF forces an extra computation of its result with (). This is because of the eager evaluation of JavaScript that will force us to define both IF branches as functions (that have to be evaluated). We also define the IS_ZERO predicate and EQUALS (using IS_ZERO and SUB):

// --- IF, with additional ()
const IF = p => a => b => p(a)(b)();

// --- Y (recursion)
const Y = f => (x => x(x))(x => f(y => x(x)(y)));

const IS_ZERO = n => n(x => FALSE)(TRUE);

const EQUALS = m => n => 
  AND (IS_ZERO(SUB(m)(n))) 
      (IS_ZERO(SUB(n)(m)));

And here comes the big moment. We can now use all building blocks together to actually implement a high level recursive function:

// --- factorial!
const FAC = Y(self => n =>
  IF (EQUALS(n)(ONE))               // if n == 1
    (() => ONE)                     //    return 1
    (() => MUL(n)(self(PRED(n))))); //    else return n * fac(n-1)

console.log( toInt( FAC(FOUR) ) );

Wow, that was a long journey! We started from simple blocks, TRUE/FALSE, we added boolean operators, numbers, arithmetic, recursion and voila, we have built a system that's capable of expressing non-trivial computation of factorials!

If you just thought "it kind of looks like LISP" then you're on the right track. Conceptually, these two, Church encoding and LISP are similar. Technically, they differ much as LISP goes forward in optimizing how things are represented. For example, to represent 1000 in our encoding, we nest function application 1000 times. LISP supports numbers as values and performs arithmetics directly.

While at mathematical level, both are very close, you could say that LISP is a Church encoding optimized to make it a practical programming language.

Next time we'll discuss lists.

Functional programming in JavaScript (8)

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)

We continue the previous post on Church encoding. Please make sure you follow by quickly reading the basics.

So let's encode natural numbers. The idea here is to apply a function n-times to encode a natural number n. An auxiliray function to visualise numbers is exacly like "apply i => i+1 to 0 n times". Note how unusual this encoding is - numbers are not just "values", they are "processes". THREE is not just 3, it's a function applied 3 times.

const ZERO  = f => x => x;
const ONE   = f => x => f(x);
const TWO   = f => x => f(f(x));
const THREE = f => x => f(f(f(x)));

const toInt = n => n(i => i + 1)(0);

console.log( toInt( ZERO ) );
console.log( toInt( ONE ) );
console.log( toInt( TWO ) );
console.log( toInt( THREE ) );

ZERO, ONE, TWO, THREE, great but how do we continue? How to define a SUCC function that just computes n+1 from given n? That should be easy: "apply a function n times and just once again":

const SUCC  = n => f => x => f(n(f)(x));

const FOUR = SUCC(THREE);
console.log( toInt( FOUR ) );

Since this could be tricky here, how the SUCC actually work, let's try to symbolically perform some example computations. Everytime you feel unsafe later on, you can verify presented definitions in a similar way.

Let's check what's SUCC(ZERO).

SUCC is n => f => x => f(n(f)(x))

Here, n looks like a function since it's used in a term n(f). And indeed, since ZERO is f => x => x, we have:

SUCC(ZERO) = (n => f => x => f(n(f)(x))(f => x => x)

There seem to be a variable name collision and to avoid it, we rename variables in f => x => x to a => b => b (or anything else not containing n, f and x)

SUCC(ZERO) = (n => f => x => f(n(f)(x))(a => b => b) = (we substitute a => b => b for n) = ...

          ... = f => x => f( (a => b => b)(f)(x) ) = f => x => f( (b => b)(x) ) = f => x => f(x) = ONE

How do we define ADD and MUL? Well, ADD is "apply function n times and then m times". MUL is "apply n times (apply m times)".

const ADD   = m => n => f => x => m(f)(n(f)(x));
const MUL   = m => n => f => m(n(f));

console.log( toInt( ADD(TWO)(THREE) ) );
console.log( toInt( MUL(TWO)(THREE) ) );

That's impressive! POW is even simpler, we just apply m to n:

const POW = m => n => n(m);

console.log( toInt( POW(TWO)(FOUR) ) );

and if this one bothers you as too similar to MUL, you can rewrite it to make it explicit:

const POW = m => n => f => n(m)(f);

console.log( toInt( POW(TWO)(FOUR) ) );

Slow down and carefully consult the difference between MUL and POW.

Ready to continue? In the next post we'll define SUB and write our first complex function.

Functional programming in JavaScript (7)

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)

One of the most beautiful examples of functional approach, that opens eyes and helps to understand basics, is the Church encoding. It's basically a way to encode operations and data types as functions; Church encoding encodes things in lambda calculus but here we are going to work with JavaScript.

Why is this even interesting? Encoding functions (operations) as functions sounds obvious. But encoding data types - booleans, numbers, lists (arrays/objects) as functions - basically means that we can build a world of computations that only contains functions, nothng else! It's not efficient, you wouldn't use it for real-world applications but it's really simple and has a really powerfull property: it's Turing complete which means that:

• you can store data (it has paris/lists)
• it does arithmetic (add/sub)
• it can make decisions (it has Booleans/IF)
• it can loop (or recurse infinitely) (it has the Y combinator)

Following the Church encoding in JavaScript is straightforward, at least at first. There are some technical difficulties later on, when IF is implemented. Before we begin, let's discuss this.

The IF will be a function of three arguments, IF(Condition)(ResultA)(ResultB). In some functional languages (like Haskell), function arguments are evaluated lazily, only if needed. When Haskell sees function arguments and some of them are not used in function definition, Haskell doesn't even try to evaluate them.

JavaScript instead computes arguments eagerly, all arguments are evaluated before the function is executed. If there's a recursion (possibly with another IF), JavaScript does a work that's not required, risking an infinite recursion.

Because of that, the Church encoding of some elements will differ in JavaScript comparing to how you'd encode things in Haskell.

Anyway, let's get started from basic building blocks.

const TRUE  = a => b => a;
const FALSE = a => b => b;

const AND = p => q => p(q)(p);
const OR  = p => q => p(p)(q);
const NOT = p => p(FALSE)(TRUE);

If you are new to this, that could be quite surprising, seeing even true and false encoded as functions. More, they are defined in a specific way, always taking one argument and possibly returning another function of one argument.

Is there a way to map TRUE and FALSE to plain JavaScript booleans, so that we can test and see how things work here? Well, just define a simple helper:

const toBool = f => f(true)(false);

and you can write few tests:

console.log( toBool( TRUE ) );
console.log( toBool( FALSE ) );

console.log( toBool( AND(TRUE)(TRUE) ) );
console.log( toBool( AND(FALSE)(TRUE) ) );
console.log( toBool( AND(TRUE)(FALSE) ) );
console.log( toBool( AND(FALSE)(FALSE) ) );

console.log( toBool( OR(TRUE)(TRUE) ) );
console.log( toBool( OR(FALSE)(TRUE) ) );
console.log( toBool( OR(TRUE)(FALSE) ) );
console.log( toBool( OR(FALSE)(FALSE) ) );

console.log( toBool( NOT(TRUE) ) );
console.log( toBool( NOT(FALSE) ) );

If you need some intuition: TRUE is a function of two arguments that just discards the second (try to think about TRUE as (a,b) => a) and FALSE is a function that takes two arguments and discards the first ((a,b) => b). Let's try to rewrite few of above examples then:

AND(TRUE)(TRUE) = T(T)(T) (because of how AND is defined) = T (because T discards second argument)

AND(TRUE)(FALSE) = T(F)(T) (because of how AND is defined) = F (because T discards second argument)

AND(FALSE)(TRUE) = F(T)(F) (because of how AND is defined) = F (because F discards first argument)

AND(FALSE)(FALSE) = F(F)(F) (because of how AND is defined) = F (because F discards first argument)

You can follow and rewrite OR and NOT, make sure you follow before moving forward. We'll continue in next post.