javascript - 在 Javascript 中使用 lambda 演算(使用教堂数字)的递归问题

Question

我一直在玩 javascript(节点)中的 lambda 演算。

我创建了一些 Church 数字，并且一直在尝试创建一个计算斐波那契数列的递归函数，但它绝对行不通!

我曾尝试将函数包装在 Y 组合器和 Z 组合器中，但它们(或我的应用程序)都不起作用。

我认为可能发生的是javascript只是应用递归函数，然后每次这样做，递归函数都会再次创建，等等。

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

我希望该函数返回 3 的斐波那契数，但相反，我得到了调用堆栈:

> 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)
    ...

Answer 1

每个人都会同意 Church 编码会产生深度调用堆栈，但是 fib(3)足够小它显然应该是可能的而不会导致堆栈溢出。

问题在于您的 IF .它每次都评估 True 和 False 分支。所以在你的fib程序，fib总是重复。

一个简单的解决方法是延迟评估任一侧，直到评估条件，然后才评估相应的 True 或 False 分支。 IE，

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

在执行 IF ，您将调用不带参数的结果分支。注意尾随 ...() –

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

在您自己的浏览器中验证以下结果 -

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

但这并不完全有趣。上面，我们使用 JavaScript 的函数来编码 lambda，所以这将我们锁定在使用 JavaScript 的严格 ( applicative order) 评估策略 - 这意味着函数的参数必须在传递给函数之前进行评估

这意味着，要评估 IF(pred)(thenA)(elseB) , 在我们尝试评估 IF 之前，我们必须首先评估 pred , thenA , 和 elseB .因为 fib在 elseB 中重复出现代码部分， fib无论退出条件如何，都会进行热切评估， pred - 因此堆栈溢出。

但是 lambda 演算没有具体的评估策略。使用 JavaScript 的原语直接编码您的程序将您与 JavaScript 固有的评估策略联系在一起。一个更有趣的解决方案在于实现您自己的评估器，您可以在其中决定使用哪种类型的策略。这使我们能够逐字使用 Church 的定义。

这是我已经完成的工作，但我在这里将其组织为长格式答案。在这个练习之后，你应该知道如何编写一个使用你选择的任何策略的评估器。

首先，我们从三个表达式构造函数开始，以匹配 lambda 演算中可用的三种可能的表达式类型——

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 = (e, ...exprs) => exprs.reduce(Apply, e)

现在让我们看看我们如何使用我们的构造函数来定义术语——

// 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))

让我们看看我们要构建什么: toBool接受一个表达式并返回一个 JavaScript bool 值——

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

稍后我们将期望写入 toInt ，它接受一个表达式并返回一个 JavaScript 数字——

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

注意使用 church(n)而不是预先定义 ONE , TWO , THREE - 这使得按需构建任何教堂数字变得容易 -

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

现在我们只需要一个通用的评估器来评估给定环境的表达式( Variable 、 Lambda 或 Apply )。我们将选择正常顺序策略 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}`)
  }
}

现在我们可以实现 toBool和 toInt .注意 toInt 的相似性与您问题中的代码相比 - 这里略有不同，因为评估策略不同 -

// 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)

现在实现 FIB .注意这个实现允许使用 IF无需人为地延迟任何一个分支——

// 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'))))
      )
  )))

注意额外的 l('r', ...)围绕整个表达式。当使用 Y 组合器应用此函数时， r变量成为递归机制本身——

// 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

展开下面的代码片段，根据一组严格的测试检查评估者——

// 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
  )

输出

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