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
我希望函数 return 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)
...
Javascript 的筹码量有限。当您不断递归地调用函数时，堆栈会不断增加，直到达到极限并随着堆栈溢出而爆炸（用 Javascript 中的 "RangeError" 表示）。因为 lambda 演算涉及到调用其他函数内部的函数来执行基本上每个你想做的操作，所以这个堆栈限制很快就会被填满。
由于这个原因，Javascript 可能不是试验 lambda 演算的最佳媒介。相反，我建议使用专为 lambda 演算设计的工具 (there are several)。
每个人都会同意 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 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 接受一个表达式和 returns 一个 JavaScript 布尔值 –
toBool(a(ISZERO, church(0))) // => true
toBool(a(ISZERO, church(1))) // => false
稍后我们希望编写 toInt，它接受一个表达式和 returns 一个 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))
<del>const ONE = NEXT(ZERO)</del> // same as church(1)
<del>const TWO = NEXT(ONE)</del> // same as church(2)
<del>const THREE = NEXT(TWO)</del> // 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
我一直在研究 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
我希望函数 return 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)
...
Javascript 的筹码量有限。当您不断递归地调用函数时，堆栈会不断增加，直到达到极限并随着堆栈溢出而爆炸（用 Javascript 中的 "RangeError" 表示）。因为 lambda 演算涉及到调用其他函数内部的函数来执行基本上每个你想做的操作，所以这个堆栈限制很快就会被填满。
由于这个原因，Javascript 可能不是试验 lambda 演算的最佳媒介。相反，我建议使用专为 lambda 演算设计的工具 (there are several)。
每个人都会同意 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 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 接受一个表达式和 returns 一个 JavaScript 布尔值 –
toBool(a(ISZERO, church(0))) // => true
toBool(a(ISZERO, church(1))) // => false
稍后我们希望编写 toInt，它接受一个表达式和 returns 一个 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))
<del>const ONE = NEXT(ZERO)</del> // same as church(1)
<del>const TWO = NEXT(ONE)</del> // same as church(2)
<del>const THREE = NEXT(TWO)</del> // 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