在Javascript中使用Lambda演算(使用教堂数字)进行递归的问题 [英] Problem with recursion using lambda calculus (using church numerals) in Javascript

问题描述

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

我创建了一些教堂数字，并且我一直在尝试创建一个递归函数来计算斐波那契数列，但绝对不能正常工作！

我尝试将函数包装在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)
    ...

解决方案

每个人都同意Church编码可以进行深层调用堆栈，但是fib(3)足够小，显然应该有可能不会引起堆栈溢出.

问题出在您的IF上.每次都评估True和False分支.因此，在您的fib程序中，fib 始终会重复出现.

一个简单的解决方法是将任一端的评估延迟到评估条件为止，然后才评估相应的True或False分支.即，

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顺序)评估策略-意味着必须先评估函数的参数，然后才能将其传递给函数

这意味着，要评估IF(pred)(thenA)(elseB)，必须先先评估pred，thenA和elseB，然后再评估IF.而且由于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布尔值–

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).我们将选择正常订单策略 按名称致电  –

按名称调用是一种评估策略，其中在调用函数之前不评估函数的参数，而是将其直接替换为函数主体(使用

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

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

解决方案

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

这篇关于在Javascript中使用Lambda演算(使用教堂数字)进行递归的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！