Cryptic Recursion
Original:
((function(f){return f(f);})(
(function(make_factorial){
return function(n){
return (n===0) ? 1 : n * make_factorial(make_factorial)(n-1);
};
})))(5);
After abstraction:
const op = (x,y) => x*y; //similar to op in accumulate(op, init, xs)
function gen(n){
return t => op(n,t); //op constructor
}
(f=>f(f))(func =>
n => n === 0
? 1 //base case
: gen(n) //do something at this layer
(func(func)(n - 1))) //wishful thinking
//previous two lines are like op(n, accumulate(the_rest))
(5);
In the program above, gen(n)
is used to generate an operator function using function op
. An operator function is a function that receives the second operand and outputs the result of op(n, _the_second_operand)
.
I believe the most cryptic part is why func(func)(n-1)
is written that way. Why does func
appear twice and why not func(func(n-1))
? First, func
should be a function thet receives and outputs a function, because it is a parameter of function f => f(f)
. Then, we consider why func
is used twice:
Let g(x)
be the equivalent of our target function, which means g(x)
is equal to the factorial of x.
Let f(x)
be the function defined by func => …
, which means f(x)
= the result of the expression where we replace all func on the LHS of =>
with the value of x.
In the program below, x * something part is dealt with by gen(n), so I’ll simply write x * something there for easier reading.
g(n) = f(f)(n)
= f(n => n * g(n — 1))
= f(n => n * f(f)(n — 1))
g(n-1)
is replaced with f(f)(n-1)
because we know that g(n) = f(f)(n)
and we can replace all n with x-1.
Okie Dokie, QED.
Other words
I guess func(f)(n)
means t => n * f(t-1)
in this case, so func(func)(n)
is actually doing the recursive step. By substitution, we obtain func(func)(n) = t => n * func(t-1)
, which displays the “call itself” property of a recursive process.
Confusion
In Source, expression const f = (t => t === 0 ? 1 : f(t-1));
is legal. It is strangely similar to the substituttion of func(func)(n)
. However, Prof. Henz explicitly warned that const a = a + 1;
is illegal even if we have const a
defined in an outer context (cause if it is in the same context, const a
would be redefined, if it is not in the outer context, a on the RHS would be undefined). I am afraid that the behavior of func(func)(n)
is similar to the “illegal” behavior of such a const assignment.