Search code examples
javascriptfunctional-programminglambda-calculus

Problem with recursion using lambda calculus (using church numerals) in Javascript

I have been playing around with with lambda calculus in javascript (node).

I created some Church numerals, and I've been trying to create a recursive function that calculates the fibonacci sequence, but it's definitely not working!

I have tried wrapping the function in a Y combinator, and a Z combinator, but neither (or my application for them) worked.

What I think might be happening is that javascript is just applying the recursive function and then each time it does that, the recursive function is created again, and again etc. 

const TRUE = a => b => a;
const FALSE = a => b => b;
const ISZERO = n => n(x=>FALSE)(TRUE);
const LEQ = m => n => ISZERO (SUB(m)(n));
const EQ = m => n => AND(LEQ(m)(n), LEQ(n)(m));
const IF = p => a => b => p(a)(b);
const ZERO = f => x => x;
const NEXT = n => f => x => f(n(f)(x));
const PLUS = m => n => f => x => m(f)(n(f)(x));
const PRE = n => f => x => n(g=> h=> h(g(f)))(u=>x)(u=>u);
const toInt = c => c((x) => x + 1)(0);
const SUB = m => n => n(PRE)(m);

const ONE=NEXT(ZERO);
const TWO=NEXT(ONE);
const THREE=NEXT(TWO);

console.log(toInt(THREE));                  // returns 3
console.log(toInt(PLUS(THREE)(TWO)));       // returns 5
console.log(toInt(PRE(PLUS(THREE)(TWO))));  // returns 4

// Define my Fibonacci function
const fib = x => IF(LEQ(x)(ONE))(ONE)(PLUS(fib(PRE(PRE(x))))(fib(PRE(x))));

console.log(toInt(fib(THREE))); // Doesn't work

I expect the function to return the Fibonacci number for 3, but instead, I get the call stack: 

> fib(THREE)
Thrown:
RangeError: Maximum call stack size exceeded
    at NEXT.f (repl:1:19)
    at x (repl:1:46)
    at x (repl:1:31)
    at x (repl:1:46)
    at x (repl:1:46)
    ...
Solution

  • Everyone will agree that Church encoding makes deep call stacks but fib(3) is small enough it should obviously be possible without causing a stack overflow.

    The issue is with your IF. It evaluates both the True and False branches every time. So in your fib program, fib always recurs.

    A simple fix is to delay evaluation of either side until the conditional is evaluated, only then evaluate the corresponding True or False branch. Ie,

    IF(cond)(t => trueExpression)(f => falseExpression)

    In the implementation of IF, you will call the resulting branch with no argument. Notice the trailing ...() –

    const IF = p => a => b => p(a)(b)();

    Verify the results in your own browser below –

    const TRUE = a => b => a;
const FALSE = a => b => b;
const ISZERO = n => n(x=>FALSE)(TRUE);
const LEQ = m => n => ISZERO (SUB(m)(n));
const EQ = m => n => AND(LEQ(m)(n), LEQ(n)(m));
const IF = p => a => b => p(a)(b)();
const ZERO = f => x => x;
const NEXT = n => f => x => f(n(f)(x));
const PLUS = m => n => f => x => m(f)(n(f)(x));
const PRE = n => f => x => n(g=> h=> h(g(f)))(u=>x)(u=>u);
const toInt = c => c((x) => x + 1)(0);
const SUB = m => n => n(PRE)(m);

const ONE=NEXT(ZERO);
const TWO=NEXT(ONE);
const THREE=NEXT(TWO);
const FOUR=NEXT(THREE);

// Define my Fibonacci function
const fib = x => IF(LEQ(x)(ONE))(_ => ONE)(_ => PLUS(fib(PRE(PRE(x))))(fib(PRE(x))));

console.log(toInt(fib(ZERO))); // 1
console.log(toInt(fib(ONE))); // 1
console.log(toInt(fib(TWO))); // 2
console.log(toInt(fib(THREE))); // 3
console.log(toInt(fib(FOUR))); // 5

    But this isn't entirely interesting. Above, we're using JavaScript's functions to encode lambdas, so this locks us into using JavaScript's strict (applicative order) evaluation strategy - meaning a function's arguments must be evaluated before they're passed to the function

    That means, to evaluate IF(pred)(thenA)(elseB), before we attempt to evaluate IF, we must first evaluate pred, thenA, and elseB. And because fib recurs in the elseB section of the code, fib is eagerly-evaluated regardless of the exit condition, pred - thus the stack overflow.

    But lambda calculus has no specific evaluation strategy. Using JavaScript's primitives to directly encode your programs ties you to JavaScript's inherent evaluation strategy. A more interesting solution lies in implementing your own evaluator where you decide what type of strategy is used. This enables us to use Church's definitions verbatim.

    This is work I've already done, but I'm organizing it here as a long-format answer. After this exercise, you should have a good idea how to write an evaluator that uses any strategy of your choosing.

    First we start with three expression constructors, to match the three possible expression types available in the lambda calculus –

    const Variable = name =>
  ({ type: 'variable', name })

const Lambda = (parameter, body) =>
  ({ type: 'lambda', parameter, body })

const Apply = (procedure, argument) =>
  ({ type: 'application', procedure, argument})

    Next we assign some aliases to make it a bit more convenient to construct our expressions –

    const v = Variable
const l = Lambda
const a = (e, ...exprs) => exprs.reduce(Apply, e)

    Now let's see how we define terms using our constructors –

    // before
const TRUE = a => b => a
// after
const TRUE = l('a', l('b', v('a')))

// before
const FALSE = a => b => b
// after
const FALSE = l('a', l('b', v('b')))

// before
const ISZERO = n => n(x=>FALSE)(TRUE)
// after
const ISZERO = l('n', a(v('n'), l('x', FALSE), TRUE))

    Let's look at what we're going to build: toBool takes an expression and returns a JavaScript boolean –

    toBool(a(ISZERO, church(0))) // => true
toBool(a(ISZERO, church(1))) // => false

    And later we'll expect to write toInt, which takes an expression and returns a JavaScript number –

    toInt(a(NEXT, church(7))) // => 8

    Notice using church(n) rather than pre-defining ONE, TWO, THREE - this makes it easy to construct any church numeral on demand –

    const NEXT =
  l('n', l('f', l('x', a(v('f'), a(v('n'), v('f'), v('x'))))))

const ZERO = l('f', l('x', v('x')))

const church = n => n === 0 ? ZERO : a(NEXT, church(n-1))

const ONE = NEXT(ZERO) // same as church(1)
const TWO = NEXT(ONE)  // same as church(2)
const THREE = NEXT(TWO) // same as church(3)

toInt(a(NEXT, church(9))) // => 10
toBool(a(EQ, church(5), a(NEXT, church(4)))) // => true

    Now we just need a generic evaluator that evaluates an expression (Variable, Lambda, or Apply) for a given environment. We'll choose the normal-order strategy, call by name –

    Call by name is an evaluation strategy where the arguments to a function are not evaluated before the function is called—rather, they are substituted directly into the function body (using capture-avoiding substitution) and then left to be evaluated whenever they appear in the function. If an argument is not used in the function body, the argument is never evaluated; if it is used several times, it is re-evaluated each time it appears.

    const evaluate = (env, expr) => {
  switch (expr.type) {
    case 'variable':
      return env[expr.name]() // force evaluation
    case 'lambda':
      return x =>
        evaluate 
          ( { ...env, [expr.parameter]: x }
          , expr.body
          )
    case 'application':
      return evaluate
        (env, expr.procedure) // eval the func
        (_ => evaluate (env, expr.argument)) // delay the argument
    default:
      throw Error(`unsupported expression: ${expr}`)
  }
}

    Now we can implement toBool and toInt. Notice the similarity of toInt compared to the code in your question - it's slightly different here because the evaluation strategy is different –

    // before
const toInt = c => c((x) => x + 1)(0);

// after
const toInt = expr =>
  evaluate ({}, expr) (_ => x => x () + 1) (_ => 0)

// a new evaluator type
const toBool = expr =>
  evaluate ({}, expr) (_ => true) (_ => false)

    And now to implement FIB. Notice this implementation allows to use IF without having to artificially delay either branch –

    // before
const fib = x =>
  IF(LEQ(x)(ONE))
    (_ => x)
    (_ => PLUS(fib(PRE(PRE(x))))
              (fib(PRE(x))))

// after
const FIB =
  l('r', l('x', a(
    IF,
      a(LEQ, v('x'), church(1)),
      v('x'),
      a(
        PLUS,
        a(v('r'), a(PRE, v('x'))), 
        a(v('r'), a(PRE, a(PRE, v('x'))))
      )
  )))

    Note the extra l('r', ...) around the entire expression. When applying this function using the Y-combinator, the r variable becomes the recursion mechanism itself –

    // Y combinator
// λf.(λx.f(x x))(λx.f(x x))
const Y = l('f', a(
  l('x', a(v('f'), a(v('x'), v('x')))),
  l('x', a(v('f'), a(v('x'), v('x'))))
))

toInt(a(Y, FIB, church(10))) // => 55

    Expand the snippet below to check the evaluator against a rigorous set of tests –

    // expression constructors
const Variable = name =>
  ({ type: 'variable', name })

const Lambda = (parameter, body) =>
  ({ type: 'lambda', parameter, body })

const Apply = (procedure, argument) =>
  ({ type: 'application', procedure, argument})

const v = Variable
const l = Lambda
const a = (...exprs) => exprs.reduce(Apply)

// evaluator
const evaluate = (env, expr) => {
  switch (expr.type) {
    case 'variable':
      return env[expr.name]()
    case 'lambda':
      return x =>
        evaluate
          ( { ...env, [expr.parameter]: x }
          , expr.body
          )
    case 'application':
      return evaluate (env, expr.procedure) (_ => evaluate (env, expr.argument))
    default:
      throw Error(`unsupported expression: ${expr}`)
  }
}

const toInt = expr =>
  evaluate ({}, expr) (_ => x => x () + 1) (_ => 0)

const toBool = expr =>
  evaluate ({}, expr) (_ => true) (_ => false)

// -----------------------------------------------------
// church encoding
const TRUE = l('a', l('b', v('a')))
const FALSE = l('a', l('b', v('b')))
const ISZERO = l('n', a(v('n'), l('x', FALSE), TRUE))

const NEXT =
  l('n', l('f', l('x', a(v('f'), a(v('n'), v('f'), v('x'))))))

const PRE =
  l('n', l('f', l('x', a(
    v('n'),
    l('g',l('h', a(v('h'), a(v('g'), v('f'))))),
    l('u', v('x')),
    l('u', v('u'))
  ))))

const ZERO = l('f', l('x', v('x')))
const PLUS = l('m', l('n', a(v('m'), NEXT, v('n'))))
const MINUS = l('m', l('n', a(v('n'), PRE, v('m'))))
const EXP = l('m', l('n', a(v('n'), v('m'))))
const MULT = l('m', l('n', l('f', a(v('m'), a(v('n'), v('f'))))))

const church = n => n === 0 ? ZERO : a(NEXT, church(n-1))

const IF = l('p', l('a', l('b', a(v('p'), v('a'), v('b')))))
const AND = l('p', l('q', a(v('p'), v('q'), v('p'))))
const OR = l('p', l('q', a(v('p'), v('p'), v('q'))))
const NOT = l('p', a(v('p'), FALSE, TRUE))
const LEQ = l('m', l('n', a(ISZERO, a(MINUS, v('m'), v('n')))))
const EQ = l('m', l('n', a(AND, a(LEQ, v('m'), v('n')), a(LEQ, v('n'), v('m')))))

const CONS = l('x', l('y', l('p', a(v('p'), v('x'), v('y')))))
const CAR = l('p',a(v('p'),l('x',l('y',v('x')))))
const CDR = l('p',a(v('p'),l('x',l('y',v('y')))))

const Y = l('g', a(
  l('x', a(v('g'), a(v('x'), v('x')))),
  l('x', a(v('g'), a(v('x'), v('x'))))
))

const FACT = l('r', l('n', a(
  a(ISZERO, v('n')),
  church(1),
  a(MULT, v('n'), a(v('r'), a(PRE, v('n'))))
)))

const FIB =
  l('r', l('x', a(
    IF,
      a(LEQ, v('x'), church(1)),
      v('x'),
      a(
        PLUS,
        a(v('r'), a(PRE, v('x'))), 
        a(v('r'), a(PRE, a(PRE, v('x'))))
      )
  )))

// tests
const assert = (label, actual, expected) =>
  actual === expected
    ? console.log(label, "=>", actual)
    : console.error(label, "=>", actual, `; expected: ${expected}`)

const assertTrue = (label, actual) =>
  assert (label, actual, true)

const assertFalse = (label, actual) =>
  assert (label, actual, false)

assert
  ( "IDENTITY #9"
  , toInt(a(l('x', v('x')), church(9)))
  , 9
  )

assert
  ( "NEXT #7"
  , toInt(a(NEXT, church(7)))
  , 8
  )

assertTrue
  ( "ISZERO #0"
  , toBool(a(ISZERO, church(0)))
  )

assertFalse
  ( "ISZERO #1"
  , toBool(a(ISZERO, church(1)))
  )

assertFalse
  ( "NOT TRUE"
  , toBool(a(NOT, TRUE))
  )

assertTrue
  ( "NOT FALSE"
  , toBool(a(NOT, FALSE))
  )

assertTrue
  ( "AND TRUE TRUE"
  , toBool(a(AND, TRUE, TRUE))
  )

assertFalse
  ( "AND TRUE FALSE"
  , toBool(a(AND, TRUE, FALSE))
  )

assertFalse
  ( "AND FALSE TRUE"
  , toBool(a(AND, FALSE, TRUE))
  )

assertFalse
  ( "AND FALSE FALSE"
  , toBool(a(AND, FALSE, FALSE))
  )

assertTrue
  ( "OR TRUE TRUE"
  , toBool(a(OR, TRUE, TRUE))
  )

assertTrue
  ( "OR TRUE FALSE"
  , toBool(a(OR, TRUE, FALSE))
  )

assertTrue
  ( "OR FALSE TRUE"
  , toBool(a(OR, FALSE, TRUE))
  )

assertFalse
  ( "OR FALSE FALSE"
  , toBool(a(OR, FALSE, FALSE))
  )

assert
  ( "IF TRUE #4 #5"
  , toInt(a(IF, TRUE, church(4), church(5)))
  , 4
  )

assert
  ( "IF TRUE #4 #5"
  , toInt(a(IF, FALSE, church(4), church(5)))
  , 5
  )

assert
  ( "IF (EQ #3 #3) #4 #5"
  , toInt(a(IF, a(EQ, church(3), church(3)), church(4), church(5)))
  , 4
  )

assertTrue
  ( "LEQ #2 #4"
  , toBool(a(LEQ, church(2), church(4)))
  )

assertTrue
  ( "LEQ #4 #4"
  , toBool(a(LEQ, church(4), church(4)))
  )

assertFalse
  ( "LEQ #5 #4"
  , toBool(a(LEQ, church(5), church(4)))
  )

assertFalse
  ( "EQ #3 #4"
  , toBool(a(EQ, church(3), church(4)))
  )

assertTrue
  ( "EQ #4 #4"
  , toBool(a(EQ, church(4), church(4)))
  )

assertFalse
  ( "EQ #4 #5"
  , toBool(a(EQ, church(4), church(5)))
  )

assert
  ( "PLUS #4 #3"
  , toInt(a(PLUS, church(4), church(3)))
  , 7
  )

assert
  ( "MINUS #9 #4"
  , toInt(a(MINUS, church(9), church(4)))
  , 5
  )

assert
  ( "MULT #3 #5"
  , toInt(a(MULT, church(3), church(5)))
  , 15
  )

assert
  ( "EXP #2 #5"
  , toInt(a(EXP, church(2), church(5)))
  , 32
  )

assert
  ( "CAR (CONS #1 #2)"
  , toInt(a(CAR, a(CONS, church(1), church(2))))
  , 1
  )

assert
  ( "CDR (CONS #1 #2)"
  , toInt(a(CDR, a(CONS, church(1), church(2))))
  , 2
  )

assert
  ( "Y FACT #5"
  , toInt(a(Y, FACT, church(5)))
  , 120
  )

assert
  ( "Y FIB #10"
  , toInt(a(Y, FIB, church(10)))
  , 55
  )

    Output

    IDENTITY #9 => 9
NEXT #7 => 8
ISZERO #0 => true
ISZERO #1 => false
NOT TRUE => false
NOT FALSE => true
AND TRUE TRUE => true
AND TRUE FALSE => false
AND FALSE TRUE => false
AND FALSE FALSE => false
OR TRUE TRUE => true
OR TRUE FALSE => true
OR FALSE TRUE => true
OR FALSE FALSE => false
IF TRUE #4 #5 => 4
IF TRUE #4 #5 => 5
IF (EQ #3 #3) #4 #5 => 4
LEQ #2 #4 => true
LEQ #4 #4 => true
LEQ #5 #4 => false
EQ #3 #4 => false
EQ #4 #4 => true
EQ #4 #5 => false
PLUS #4 #3 => 7
MINUS #9 #4 => 5
MULT #3 #5 => 15
EXP #2 #5 => 32
CAR (CONS #1 #2) => 1
CDR (CONS #1 #2) => 2
Y FACT #5 => 120
Y FIB #10 => 55