y_combinator.js

/*
Y Combinator: From Factorial to Fixed-point Combinator
Modern JS Implementation
https://picasso250.github.io/2015/03/31/reinvent-y.html
https://gist.github.com/igstan/388351
*/

/* STEP 1: Basic recursive factorial */
const fact1 = n => n < 2 ? 1 : n * fact1(n - 1);

/* STEP 2: Transform to take function as parameter */
// In lambda calculus, everything is nameless
// So we pass function as parameter
const fact2 = (f, n) => n < 2 ? 1 : n * f(n - 1);
// But this doesn't work because
// if we call fact2(fact2, 5)
// f(n-1) becomes fact2(4)

/* STEP 3: Make f call itself */
const fact3 = (f, n) => n < 2 ? 1 : n * f(f, n - 1);
// Usage: fact3(fact3, 5)

/* STEP 4: First step of currying - wrap in outer function */
const fact4 = f => {
	return (n) => n < 2 ? 1 : n * f(f, n - 1);
}

/* STEP 5: Curry the inner call */
const fact5 = f => {
	return (n) => n < 2 ? 1 : n * (f(f))(n - 1);
}

/* STEP 6: Remove unnecessary brackets and block */
const fact6 = f => n => n < 2 ? 1 : n * f(f)(n - 1);
// Usage: fact6(fact6)(5)

/* STEP 7: Inline fact6(fact6) into one expression */
const fact7 = (f => n => n < 2 ? 1 : n * f(f)(n - 1))
	(f => n => n < 2 ? 1 : n * f(f)(n - 1));
// Usage: fact7(5)

/* STEP 8: Extract duplication */
const dupe = f => f(f);
const fact8 = dupe(f => n => n < 2 ? 1 : n * f(f)(n - 1));

/* STEP 9: Remove double call using helper */
const fact9_bad = dupe(f => {
	// BAD: f(f) will go infinite recursion in eager evaluation
	const g = f(f);
	return n => n < 2 ? 1 : n * g(n - 1);
});
const fact9 = dupe(f => {
	// This trick is eta-expansion or thunking
	const g = n => f(f)(n);
	return n => n < 2 ? 1 : n * g(n - 1);
});

/* STEP 10: Abstract pattern into extractor */
const ext10 = h => dupe(f => {
	const g = n => f(f)(n);
	return h(g);
});
const fact10 = ext10(k => n => n < 2 ? 1 : n * k(n - 1));

/* STEP 11: Inline g function */
const ext11 = h => dupe(f =>
	h(n => f(f)(n))
);
const fact11 = ext11(k => n => n < 2 ? 1 : n * k(n - 1));

/* STEP 12: Inline dupe, final Y combinator */
const Y = h => (f => f(f))(f => h(n => f(f)(n)));

/* TEST */
// k refers to the recursive function itself
const factorial = Y(k =>
	n => n < 2 ? 1 : n * k(n - 1)
);
const fibonacci = Y(k =>
	n => n <= 1 ? n : k(n - 1) + k(n - 2)
);
const sum = Y(k =>
	n => n <= 0 ? 0 : n + k(n - 1)
);
console.log(factorial(5)); // 120
console.log(fibonacci(5)); // 5
console.log(sum(5)); // 15

Let's break down eta-expansion and thunking in functional programming, highlighting their differences and use cases.

Eta-Expansion (η-expansion)

• What it is: Eta-expansion converts a function value into a function expression. It's the process of explicitly representing a function application that could be implicitly inferred. In essence, you're adding a lambda abstraction (an anonymous function) where it wasn't explicitly written before.

• Example (Haskell):

  f :: a -> b
  f = someFunction  -- This is equivalent to...
  f x = someFunction x -- ...this after eta-expansion

• Why it's useful:

  • Type inference: Sometimes the compiler needs a more explicit form to infer types correctly.
  • Point-free style: While eta-expansion seems to add verbosity, it can sometimes enable a more concise point-free style by allowing you to compose functions without explicitly naming their arguments.
  • Partial application clarity: It can make partial application more explicit, although partial application is often clear without it.

Thunking

• What it is: Thunk is a strategy to delay the evaluation of an expression. It wraps an expression in a function that takes no arguments (often called a "nullary" function). The expression is only evaluated when this function is called.

• Example (Haskell):

  expensiveComputation :: Int
  expensiveComputation = someLengthyCalculation
  
  thunk :: IO ()
  thunk = print (expensiveComputation) -- expensiveComputation is evaluated immediately
  
  delayedThunk :: IO ()
  delayedThunk = do
      let t = return expensiveComputation -- expensiveComputation is NOT evaluated yet
      print (<- t) -- expensiveComputation is evaluated here

• Why it's useful:

  • Deferring side effects: In the example above, thunk performs the expensive calculation immediately. delayedThunk delays the calculation until inside the print call. This control over when side effects (like printing or file I/O) occur is crucial for managing program behavior.
  • Optimizations: Thunks can prevent unnecessary computations if the wrapped expression is never needed. This is especially relevant in lazy languages like Haskell.
  • Passing computations: Thunks allow you to pass computations around as values without immediately executing them. This is powerful for building complex control flow and algorithms.
  • Simulating call-by-name: In call-by-value languages, arguments are evaluated before being passed to a function. Thunks can simulate call-by-name by passing unevaluated computations as arguments, which are then evaluated inside the function only when needed.

Key Differences

Feature	Eta-expansion	Thunking
Purpose	Make function application explicit; facilitate type inference and point-free style	Delay evaluation of an expression
Argument(s)	Can take arguments (like any function)	Typically takes no arguments (nullary function)
Evaluation	Doesn't inherently delay evaluation	Delays evaluation until the thunk is called
Side effects	Doesn't directly manage side effects	Primarily used to control side effects

In Summary

Eta-expansion is about making function application explicit, while thunking is about delaying evaluation. They serve distinct purposes and are not directly related, although they can sometimes be used together in more complex scenarios. Thunking is a much more significant concept in terms of program behavior and optimization, especially in lazy languages or when dealing with side effects.