Crockford's Javascript Applicative Order Y Combinator syntax construct explanation?

Question

Wanted to understand what syntax construct do / Find appropriate documentation covering the subject.

Was reading Crockford's The Little JavaScripter at https://www.crockford.com/little.html

I took a liberty to reformat code a little to point out the place where I get confused.

Note: It is too easy to wrongly format this piece of code, parser insertions can get in the way of execution and render factorial not valid function (perhaps that deserves whole new question)

function Y(le) {
    // just one return
    return (
        // ok, so far it returns a function
        function (f) { return f(f); }
        // here it starts to be syntaxically puzzling
        // what does following part, after already returning 
        // the function do?
        // construct looks like 'return ( f1(x) (f2 (x)) )'... 
        // looks very lispy
        (function (f) { 
            return le(function (x) { 
                return f(f)(x); 
            } ); 
        } )
    );
}

var factorial = Y(function (fac) {
    return function (n) {
        return (
            n <= 2
            ? n
            : n * fac(n - 1)
        );
    };
});

var number120 = factorial(5);
document.write(number120);

I am aware of so called IIFE syntax construct https://developer.mozilla.org/en-US/docs/Glossary/IIFE but construct used here is not really following IIFE (as far as I understand IIFE). This is kind of upside down construct and looks like it is some other kind of function construct recently introduced to JavaScript, but I cannot find the part of the documentation that covers this use. Is there a term covering this construct like there is IIFE (so I can search by the term).

Links to documentation are welcome.

Answer 1

My confusion was created by not understanding that:

var x = (function (a) {return a})(1);
var y = (function (a) {return a} (2));
var z = function (a) {return a} (3);

are all IIFE variants of the same kind. At least all 3 are recognized and executed in the same fashion (in the modern browser). MDN needs to clarify this.

MDN explain IIFE is in the form x

Crockford's example uses variant y.

Answer 2

Instead of reverse engineering Crockford's Y, perhaps it's better to understand Y beginning with its purpose first. It's when we start with an intention and work our way forward to a solution that we can begin to understand how Y works.

"I want to write a recursive formula... without using recursion"

This was a problem facing mathematicians and logicians long before people had widespread access to computers. And this is the problem the Y combinator solves, but how does it do it? Let's first start with a recursive "formula" we want to write -

const fact = n =>
  n <= 2
    ? n
    : n * fact (n - 1) // <-- recursive!

Above fact is defined in terms of itself. We can remove this self-reference by using an extra parameter to control recursion, recur -

const fact =          n =>
const fact = recur => n =>
  n <= 2
    ? n
    : n * fact (n - 1)
    : n * ...  (n - 1)

But what should recur be? And how do we fill in ...? Meet U. U simply applies a function to itself -

const U = f =>
  f (f)                     // <-- apply f to itself

const fact = recur => n =>
  n <= 2
    ? n
    : n * U (recur) (n - 1) // <-- apply recur to itself

console.log (U (fact) (5))  // <-- apply fact to itself
// 120

Above we call U (fact) (5) to compute the result. It's important to observe that we could've applied U when we defined fact = ... -

const U = f =>
  f (f)

const fact = U (recur => n => // <-- apply U directly on lambda
  n <= 2
    ? n
    : n * U (recur) (n - 1))

console.log (fact (5)) // <-- call fact normally
// 120

Using U, we now have a generic way to write recursive expressions -

U (recur => ...      U (recur) ...)

---

"I don't like that I have to remember to use U (recur) (...). Can I just call recur (...) instead?"

U is an extremely simple mechanism, but indeed it is a little cumbersome because we have to remember to "reflect" recur back onto itself each time we recur. And this is where the Y combinator differs from the U. Y says,

• Give me function f, that's asking for a recursion mechanism
• I'll give you a recursion mechanism, x => ..., and when you call it, I will handle passing x to some U (recur) (...)

const Y = f =>
  f (x => ...) // <-- instead of f (f)...

Just like we saw with fact above, we can write a recursive expression using U -

U (recur => ...      U (recur) ...)

So Y of some function f, will create a recursion mechanism, U (recur => ...) and it will call f with a function, x => ..., that when applied, will recur with x using U (recur) (x) -

const Y = f =>
  //            f (x =>    ...    (x))
  //            =======           ====
  //               |               |
  //               v               v
  // U (recur => ...    U (recur) ...)

     U (recur => f (x => U (recur) (x)))

Let's see Y in action below -

const U = f =>
  f (f)

const Y = f =>
  U (recur => f (x => U (recur) (x)))

const fact = Y (recur => n =>
  n <= 2
    ? n
    : n * recur (n - 1)) // <-- call "recur" normally

console.log (fact (5)) // <-- call "fact" normally
// 120

---

tomato, tomahto

Crockford calls the Y-combinator "...one of the most strange and wonderful artifacts of Computer Science", but I think that's because he doesn't understand it and continues to copy/paste the same Y examples you see around the internet. There's nothing strange about it unless you write it in such a way that obfuscates all meaning -

// replace IIFE with U
function Y(le) {
  return (
    function (f) { return f(f); }
    U
    (function (f) { 
      return le(function (x) { 
        return f(f)(x);
        return U(f)(x) 
      }); 
    })
  )
}

// remove unnecessary outer (...)
function Y(le) {
  return U(function (f) { 
    return le(function (x) { 
      return U(f)(x)
    })
  })
}

// simplified arrow expression
const Y = le =>
  U (f => le (x => U (f) (x))

// alpha rename "f" to "recur"
const Y = le =>
  U (recur => le (x => U (recur) (x))

// alpha rename "le" to "f"
const Y = f =>
  U (recur => f (x => U (recur) (x))

Which matches our version of Y above -

const Y = f =>
  U (recur => f (x => U (recur) (x)))

---

without U

We can expand U such that Y has a standalone definition -

// starting with 
const Y = f =>
  U (recur => f (x => U (recur) (x)))

// expand inner U
const Y = f =>
  U (recur => f (x => recur (recur) (x)))

// expand outer U
const Y = f =>
  (recur => f (x => recur (recur) (x)))
  (recur => f (x => recur (recur) (x)))

We're back to an IIFE, but this time our definition more closely matches Haskell Curry's original definition -

const Y = f =>
  (recur => f (x => recur (recur) (x)))
  (recur => f (x => recur (recur) (x)))

const fact = Y (recur => n =>
  n <= 2
    ? n
    : n * recur (n - 1))

console.log (fact (5))
// 120

---

expanding our Y intuition

Like almost all other Y tutorials out there, Crockford demonstrates using Y on a function with a single argument. There's a lot of potential lurking just beyond these preliminary understandings of Y. I'll show you simple functions that take 2 or even 3 arguments -

const Y = f =>
  (recur => f (x => recur (recur) (x)))
  (recur => f (x => recur (recur) (x)))

const range1 = Y (recur => m => n =>
  m > n
    ? []
    : [ m, ...recur (m + 1) (n) ])

const range2 = Y (recur => r => m => n => 
  m > n
    ? r
    : recur ([ ...r, m ]) (m + 1) (n)) ([])

const fib = Y (recur => a => b => n =>
  n === 0
    ? a
    : recur (b) (a + b) (n - 1)) (0) (1)

console.log (range1 (5) (10))
// [ 5, 6, 7, 8, 9, 10 ]

console.log (range2 (5) (10))
// [ 5, 6, 7, 8, 9, 10 ]

console.log (fib (10))
// 55

There's really no limit to the complexity of program that Y can express -

const Y = f =>
  (recur => f (x => recur (recur) (x)))
  (recur => f (x => recur (recur) (x)))

const reduce = Y (recur => i => f => state => a =>
  i >= a.length
    ? state
    : recur (i + 1) (f) (f (state, a[i])) (a)) (0)

const filter = f =>
  reduce ((r, x) => f (x) ? [ ...r, x ] : r) ([])

const odds =
  filter (n => n & 1)

console.log (odds ([ 0, 1, 2, 3, 4, 5, 6 ]))
// [ 1, 3, 5 ]

Answer 3

This is an IIFE. It might he more clear if we format it as:

  return (function (f) { return f(f); })(
    function (f) { 
        return le(function (x) { 
            return f(f)(x); 
        }
    }
 });