y-combinator.js

#!/usr/bin/env node

/**
 * Following code samples and notes are from my following of Jim Weirich's
 * presentation "Y Not? Adventures in Functional Programming"
 *
 * http://confreaks.tv/videos/rubyconf2012-y-not-adventures-in-functional-programming
 * https://www.youtube.com/watch?v=FITJMJjASUs
 *
 * Note: presentation was done using Ruby, while my code sample are in
 * JavaScript.
 *
 */

// === THEORIES ================================================================

// -----------------------------------------------------------------------------
//
// // Simple add, multiply functions
// const add1 = n => 1 + n
// const mul3 = n => 3 * n
//
// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------
//
// // Higher order functions
// //
// // Function that either take in or return functions.
//
// const make_adder = x => n => x + n
// const compose = (f, g) => n => f(g(n))
//
// const add1 = make_adder(1)
//
// const mul3add1 = compose(mul3, add1)
//
// -----------------------------------------------------------------------------



// -----------------------------------------------------------------------------
//
// // Functional Refactoring #1
// // Tennent Correspondence Principle
// //
// //  Given expression `x`, surrounded by a lambda which is immediately invoked,
// //  you get `x` back.
// //
// // (() => x)() === x
//
// //    mul3 = n => 3 * n
// const mul3 = n => (() => 3 * n)()
//
// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------
//
// // Functional Refactoring #2
// // Introduce Binding
// //
// // Given a lambda with no arguments, we can add a new argument binding to it
// // without affecting the enclosed expression.
// //
// // (() => x)() === (z => x)(1234) === x
//
// //    mul3 = n => (() => 3 * n)()
// const mul3 = n => (z => 3 * n)(1234)
//
// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------
//
// // Functional Refactoring #3
// // Wrap Function
// //
// // Given a function with single argument, we can wrap it in a lambda with one
// // argument and call the function inside that lambda and pass that argument down
// // to caller.
// //
// // n => n + 1  -->  v => (n => n + 1)(v)
// //
// //    make_adder = x => n => x + n
// const make_adder = x => v => (n => x + n)(v)
//
// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------
//
// // Functional Refactoring #3
// // Inline definition
// //
// // Given a function that is called by it's name, we can take the definition of
// // that function and replace that name with it
// //
// //    add1 = make_adder(1)
// const add1 = (x => v => (n => x + n)(v))(1)
//
// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------

// Summary

//    make_adder = x => n => x + n
// const make_adder = x => v => (n => x + n)(v)


//    add1 = n => 1 + n
//    add1 = make_adder(1)
// const add1 = (x => v => (n => x + n)(v))(1)

//    mul3 = n => 3 * n
//    mul3 = n => (() => 3 * n)()
// const mul3 = n => (z => 3 * n)(1234)

//    compose = (f, g) => n => f(g(n))
//    compose = (f, g) => (() => n => f(g(n)))()
// const compose = (f, g) => (z => n => f(g(n)))(1234)

//    mul3add1 = compose(mul3, add1)
//    mul3add1 = ((f, g) => (z => n => f(g(n)))(1234))(mul3, add1)
//    mul3add1 = ((f, g) => (z => n => f(g(n)))(1234))(mul3, ((x => v => (n => x + n)(v))(1)))
//    mul3add1 = ((f, g) => (z => n => f(g(n)))(1234))((n => (z => 3 * n)(1234)), ((x => v => (n => x + n)(v))(1)))
// const mul3add1 = ((f, g) =>
//   (z => n => f(g(n)))(1234))(
//     (n => (z => 3 * n)(1234)),
//     ((x => v => (n => x + n)(v))(1))
//   )

// -----------------------------------------------------------------------------

// === APPLICATION =============================================================

const error = n => {
  throw new Error('SHOULD NEVER BE CALLED')
}

// -----------------------------------------------------------------------------
//
// // Factorial as a conventional function
// const fact = n => 0 === n ? 1 : n * fact(n - 1)
//
// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------

// Factorial created from a higher order function
// const make_factorial = fact => n => 0 === n ? 1 : n * fact(n - 1)
// const fact = make_factorial(???)  // NOPE!

// const fact_improver = partial => n => 0 === n ? 1 : n * partial(n - 1)

// const f0 = fact_improver(error)
// const f1 = fact_improver(f0)
// const f2 = fact_improver(f1)
//
// const fx = fact_improverfact_improver((fact_improver(error)))
//
// const fx =
// (improver =>
//   improver(improver(error))
// )(
//   partial =>
//     n => 0 === n ? 1 : n * partial(n - 1)
// )
//
// const fx =
// (improver =>
//   improver(improver)
// )(
//   improver =>
//     n => 0 === n ? 1 : n * improver(improver)(n - 1)
// )
//

// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------

const fact_improver =
    partial => n => 0 === n ? 1 : n * partial(n - 1)

// (Applicative Order) Y Combinator
// Also known as Z-combinator or Fixpoint Combinator
const y =
  improver =>
    (gen => gen(gen))(
      gen => improver(v => gen(gen)(v))
    )

  // f =>
  //   (x => x(x))(
  //     x => f(v => x(x)(v))
  //   )

  // improver =>
  //   (
  //     gen => improver(v => gen(gen)(v))
  //   )(
  //     gen => improver(v => gen(gen)(v))
  //   )

  // f =>
  //   (
  //     x => f(v => x(x)(v))
  //   )(
  //     x => f(v => x(x)(v))
  //   )

// Function `y` calculates the fixpoint of an improver function
let fact = y(fact_improver)

// `fact` is the fixpoint of `fact_improver`
fact = fact_improver(fact)

// -----------------------------------------------------------------------------


// -----------------------------------------------------------------------------
console.log(

  // ---------------------------------------------------------------------------
  // mul3(add1(10))
  // mul3add1(10)
  // (((f, g) =>
  // (z => n => f(g(n)))(1234))(
  //   (n => (z => 3 * n)(1234)),
  //   ((x => v => (n => x + n)(v))(1))
  // ))(10)
  // ---------------------------------------------------------------------------


  // ---------------------------------------------------------------------------

  // fact(5)

  // The Problem
  // Out factorial function as a lambda expression still reference itself by
  // name.
  // (n => 0 === n ? 1 : n * fact(n - 1))(5)

  // f2(2)
  // fx(50)

  // ((improver =>
  //   improver(improver)
  // )(
  //   improver =>
  //     n => 0 === n ? 1 : n * improver(improver)(n - 1)
  // ))(5)

  // ((gen =>
  //   gen(gen)
  // )(
  //   gen =>
  //     n => 0 === n ? 1 : n * gen(gen)(n - 1)
  // ))(5)

  //
  // // Apply Tennent Correspondence Principle
  // ((gen =>
  //   gen(gen)
  // )(
  //   gen =>
  //     (() =>
  //       n => 0 === n ? 1 : n * gen(gen)(n - 1)
  //     )()
  // ))(5)
  //

  //
  // // introduce binding (causes stack overflow)
  // ((gen =>
  //   gen(gen)
  // )(
  //   gen =>
  //     (code =>
  //       n => 0 === n ? 1 : n * gen(gen)(n - 1)
  //     )(gen(gen))
  // ))(5)
  //

  //
  // // wrap function
  // ((gen =>
  //   gen(gen)
  // )(
  //   gen =>
  //     (code =>
  //       n => 0 === n ? 1 : n * gen(gen)(n - 1)
  //     )(v => gen(gen)(v))
  // ))(5)
  //

  //
  // // wrap function #2
  // ((gen =>
  //   gen(gen)
  // )(
  //   gen =>
  //     (code =>
  //       n => 0 === n ? 1 : n * (v => gen(gen)(v))(n - 1)
  //     )(v => gen(gen)(v))
  // ))(5)
  //

  //
  // // refactor: replace inner `v => gen(gen)(v)` with `code`
  // ((gen =>
  //   gen(gen)
  // )(
  //   gen =>
  //     (code =>
  //       n => 0 === n ? 1 : n * code(n - 1)
  //     )(v => gen(gen)(v))
  // ))(5)
  //

  //
  // // rename code -> partial
  // // Notice we have our previous improver in the middle there
  // ((gen =>
  //   gen(gen)
  // )(
  //   gen =>
  //     (partial =>
  //       n => 0 === n ? 1 : n * partial(n - 1)
  //     )(v => gen(gen)(v))
  // ))(5)
  //

  //
  // // Apply another Tennent Correspondence Principle to entire expression
  // (() =>
  //   ((gen =>
  //     gen(gen)
  //   )(
  //     gen =>
  //       ((partial) =>
  //         n => 0 === n ? 1 : n * partial(n - 1)
  //       )(v => gen(gen)(v))
  //   ))
  // )()(5)
  //

  //
  // // introduce binding to outer most lambda
  // (code =>
  //   ((gen =>
  //     gen(gen)
  //   )(
  //     gen =>
  //       (partial =>
  //         n => 0 === n ? 1 : n * partial(n - 1)
  //       )(v => gen(gen)(v))
  //   ))
  // )(error)(5)
  //

  //
  // // pass in improver as the as the value of `code`
  // (code =>
  //   ((gen =>
  //     gen(gen)
  //   )(
  //     gen =>
  //       (partial =>
  //         n => 0 === n ? 1 : n * partial(n - 1)
  //       )(v => gen(gen)(v))
  //   ))
  // )(
  //   (partial =>
  //     n => 0 === n ? 1 : n * partial(n - 1)
  //   )
  // )(5)
  //

  //
  // // replace inner improver with `code`
  // (code =>
  //   ((gen =>
  //     gen(gen)
  //   )(
  //     gen =>
  //       code(v => gen(gen)(v))
  //   ))
  // )(
  //   (partial =>
  //     n => 0 === n ? 1 : n * partial(n - 1)
  //   )
  // )(5)
  //

  //
  // // rename code -> improver
  // (improver =>
  //   ((gen =>
  //     gen(gen)
  //   )(
  //     gen =>
  //       improver(v => gen(gen)(v))
  //   ))
  // )(
  //   (partial =>
  //     n => 0 === n ? 1 : n * partial(n - 1)
  //   )
  // )(5)
  //

  //
  // // extract parts out #1
  // (improver =>
  //   ((gen =>
  //     gen(gen)
  //   )(
  //     gen =>
  //       improver(v => gen(gen)(v))
  //   ))
  // )(fact_improver)(5)
  //

  //
  // // extract parts out #2
  // y(fact_improver)(5)
  //

  fact(5)

  // ---------------------------------------------------------------------------

)