Published
Edited
Jan 10, 2020
Insert cell
Insert cell
Y_Combinator = f => (x => f(x(x)))
(x => f(x(x)))
Insert cell
Insert cell
{
var fib_x = (fib_next => fib_next(fib_next))
(fib_next => (n,a,b) => n < 1 ? a : fib_next(fib_next)(n-1,b,a+b));

// Let's try calculating different numbers in the Fibonacci series...
return {
fib0 : fib_x(0,0,1),
fib1 : fib_x(1,0,1),
fib2 : fib_x(2,0,1),
fib5 : fib_x(5,0,1),
fib20 : fib_x(20,0,1),
fib50 : fib_x(50,0,1),
fib100 : fib_x(100,0,1),
fib1474 : fib_x(1476,0,1)
}
}
Insert cell
Insert cell
// The IDENTITY function returns its parameter without modification
IDENTITY = val => val
Insert cell
Insert cell
// Combinator functions representing TRUE and FALSE
TRUE = true_part => false_part => true_part
Insert cell
FALSE = true_part => false_part => false_part
Insert cell
Insert cell
// The universal combinator
U = fn => fn(fn)
Insert cell
// Passing U to itself is a really bad idea because JavaScript will
// promptly disappear down the rabbit hole of infinite recursion!
U(U)
Insert cell
Insert cell
{
// Anytime a function calls itself as the only parameter, replace
// this with a call to the universal combinator. So
// var fib_x = (fib_next => fib_next(fib_next))
// (fib_next => (n,a,b) => n < 1 ? a : fib_next(fib_next)(n-1,b,a+b));
// becomes:
var fib_x = (fib_next => U(fib_next))
(fib_next => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b))
}
Insert cell
Insert cell
{
// Apply TCP to the Fibonacci function and add some indentation so
// var fib_x = (fib_next => U(fib_next))
// (fib_next => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b));
// becomes:
var fib_x = (fib_next => U(fib_next))
(fib_next =>
(() => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b))()
);
// As expected, TCP refactoring has no effect on the end result
return fib_x(5,0,1);
}
Insert cell
Insert cell
{
// First, pass U(fib_next) as a parameter to the wrapped Fibonacci function
var fib_x = (fib_next => U(fib_next))
(fib_next =>
(() => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b))(U(fib_next))
);
}
Insert cell
Insert cell
{
// Second, use fib_next as the parameter name for this value
var fib_x = (fib_next => U(fib_next))
(fib_next =>
(fib_next => (n,a,b) => n < 1 ? a : U(fib_next)(n-1,b,a+b))(U(fib_next))
);
}
Insert cell
Insert cell
{
// Replace occurrences of U(fib_next) with the parameter name fib_next
var fib_x = (fib_next => U(fib_next))
(fib_next =>
(fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b))(U(fib_next))
);
}
Insert cell
Insert cell
{
// Wrap the call to U(fib_next) in a function to delay its invocation
// This function must receive the three parameters used to calculate
// the fibonacci series
var fib_x = (fib_next => U(fib_next))
(fib_next =>
(fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b))
((n,a,b) => U(fib_next)(n,a,b))
);

// Ah, that's better
return fib_x(20,0,1);
}
Insert cell
Insert cell
{
// Make the Fibonacci function a parameter to the recursion function
var fib_x = (rec_fn =>
(fib_next => U(fib_next))
(fib_next => rec_fn((n,a,b) => U(fib_next)(n,a,b)))
)(fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b));

// Check that everything still works as before...
return fib_x(10,0,1);
}
Insert cell
Insert cell
{
// Define a do_fib function that can calculate any number in the Fibonacci series
var do_fib = fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b);

var fib_x = (rec_fn =>
(fib_next => U(fib_next))
(fib_next => rec_fn((n,a,b) => U(fib_next)(n,a,b)))
)(do_fib);

// Again, check that everything still works as before...
return fib_x(10,0,1);
}
Insert cell
Insert cell
{
// Define a do_fib function that can calculate any number in the Fibonacci series
var do_fib = fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b);

var fib_x = (rec_fn =>
(gen_rec => U(gen_rec))
(gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b)))
)(do_fib);

// Have we broken it?
return fib_x(10,0,1);
}
Insert cell
Insert cell
{
// Define a do_fib function that can calculate any number in the Fibonacci series
var do_fib = fib_next => (n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b);

// We now have a definition of the Y-Combinator
var Y = (rec_fn =>
(gen_rec => U(gen_rec))
(gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b)))
)

// Now use the Y-Combinator as the framework within which any
// function can be called recursively
var fib = Y(do_fib);

// Everything still works as before...
return fib(10,0,1);
}
Insert cell
Insert cell
{
// Define a do_fact function that calculates the factorial of a number
var do_fact = fact_next => n => n < 2 ? 1 : n * fact_next(n-1);

// We now have a definition of the Y-Combinator
var Y = (rec_fn =>
(gen_rec => U(gen_rec))
(gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b)))
)

// Use the Y-Combinator to create a factorial function
var fact = Y(do_fact);

// The factorial of 5 should be 120...
return fact(5);
}
Insert cell
Insert cell
Insert cell
{
// The Y-Combinator
var Y = (rec_fn =>
(gen_rec => U(gen_rec))
(gen_rec => rec_fn((n,a,b) => U(gen_rec)(n,a,b)))
)

// Define functions to calculate the Fibonacci series and factorial
// We can also tidy up the useability of the do_fib function so that the user does not need
// to pass 0 and 1 as the sequence start values. Again, this is done by function wrapping
var do_fib = fib_next => n => ((n,a,b) => n < 1 ? a : fib_next(n-1,b,a+b))(n,0,1);
var do_fact = fact_next => n => n < 2 ? 1 : n * fact_next(n-1);

// If we really have derived the Y-Combinator, then the following
// assignments should give exactly the same results.
// Y(f) === f(Y(f));
var fact1 = Y(do_fact); // fact_next => n < 2 ? 1 : n * fact_next(n-1)
var fact2 = do_fact(Y(do_fact)); // fact_next => n < 2 ? 1 : n * fact_next(n-1)

var fib1 = Y(do_fib); // fib_next => (n,a,b) < 1 ? a : fib_next(n-1,b,a+b)
var fib2 = do_fib(Y(do_fib)); // fib_next => (n,a,b) < 1 ? a : fib_next(n-1,b,a+b)
return {
y_combinator_test_1_satisfied : fact1(5) === fact2(5),
y_combinator_test_2_satisfied : fib1(20) === fib2(20)
}
}
Insert cell
Insert cell
{
// Change all meaningful variable names to meaningless ones
// Rename rec_fn to f
var Y = (f =>
(gen_rec => U(gen_rec))
(gen_rec => f((n,a,b) => U(gen_rec)(n,a,b)))
)
}
Insert cell
Insert cell
{
// Change all meaningful variable names to meaningless ones
// Rename gen_rec to x
var Y = (f =>
(x => U(x))
(x => f((n,a,b) => U(x)(n,a,b)))
)
}
Insert cell
Insert cell
{
// Change all meaningful variable names to meaningless ones
// U(x) changes back to x(x)
var Y = (f =>
(x => x(x))
(x => f((n,a,b) => x(x)(n,a,b)))
)
}
Insert cell
Insert cell
{
// Change all meaningful variable names to meaningless ones
// Remove the wrapper function around x(x)
var Y = (f =>
(x => x(x))
(x => f(x(x)))
)
}
Insert cell
Insert cell
{
// Change all meaningful variable names to meaningless ones
// Wrap the first x(x) call in a call to f - which happens in this case to be a no-op.
// Adjust the carriage returns and indentation to make it look pretty (mysterious)
var Y = (f => (x => f(x(x)))
(x => f(x(x))))
}
Insert cell
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more