Javascript 无条件递归

Question

我正在尝试 'implement' Church's encoding of lambda calculus 在 Javascript 中，但在我编写阶乘函数时开始遇到问题：

const factorial = n => (iszero(n))(ONE)(multiply(n)(factorial(predecessor(n))));

iszero(n) 充当条件，returns 一个函数，如果 n 为零则执行它的第一个参数，否则执行第二个参数。

对任何值调用此函数都会导致堆栈溢出。

我试图简化它以找出原因：

//const ifelse = condition => a => b => condition ? a : b;
//const factorial = n => ifelse(n == 0)(1)(n * factorial(n - 1));
const ifelse = function(condition, a, b) {
    if (condition) {
        return a;
    } else {
        return b;
    }
}
const factorial = function(number) {
    return ifelse(number == 0, 1, number * factorial(number - 1));
}

在这里调用阶乘也会导致溢出，尽管如果我们减少 factorial 中的 ifelse 函数，它会生成一个不会抛出的完美函数阶乘函数：

//const factorial = n => (n == 0) ? (1) : (n * factorial(n - 1));
const factorial = function(number) {
    if (number == 0) {
        return 1;
    } else {
        return number * factorial(number - 1);
    }
}

但是我试图在阶乘中只使用函数，所以三元条件运算符是不可接受的（参见注释箭头符号）。

为什么我的 factorial 函数在对任何值调用时会导致堆栈溢出，是否可以在仅使用函数（无条件）的情况下避免这种情况？

编辑：第一段代码的定义：

const TRUE = x => y => x;
const FALSE = x => y => y;

const ZERO = f => x => x;
const ONE = f => x => f(x);

const pair = a => b => f => f(a)(b);

const first = p => p(TRUE);
const second = p => p(FALSE);

const iszero = n => n(x => FALSE)(TRUE);

const successor = n => f => x => f(n(f)(x));
const multiply = n1 => n2 => f => x => n1(n2(f))(x);
const predecessor = n => second(n(p => pair(successor(first(p)))(first(p)))(pair(ZERO)(ZERO)));

Answer 1

您正在遇到堆栈溢出，因为 JavaScript 不是惰性求值语言。例如：

ifelse(false)(console.log("YES"))(console.log("NO"))
// => YES
//    NO

两个参数都被评估。防止这种情况发生的方法是将它们保留为函数，直到您需要它们。

ifelse(false)(() => console.log("YES"))(() => console.log("NO"))()
// => NO

因此在您的第二个 factorial 定义中，无论如何都会执行 factorial(n - 1)； ifelse 只是为了让你 select 将两个值中的哪一个 return。显然，factorial(0) 然后会调用 factorial(-1)，这将一直持续到 -infinity，受内存限制。

不对它们进行评估：

factorial = n => ifelse(n == 0)(() => 1)(() => n * factorial(n - 1)())
factorial(1)()
# => 1
factorial(5)()
// => 120

鉴于您没有定义，我无法告诉您第一组有什么问题，但原因可能是相同的。

编辑：看过定义后...让我先添加一个我自己的定义：

const display = n => n(x => x + 1)(0)

(n(x => x + 1)(0) 是一个将教堂数字转换为普通数字的便捷技巧，因此我们可以看到发生了什么。仅用于调试工具，因此它不应违反您正在做的事情的纯洁性。 )

我们的检查员在手... predecessor 不正确。参见：

display(successor(predecessor(ONE)))
// => TypeError: f(...) is not a function
//        at f (repl:1:33)
//        at x (repl:1:36)

试试这个（直接来自您的维基百科link）：

const predecessor = n => f => x => n(g => h => h(g(f)))(u => x)(u => u)

有了这个，你会得到正确的结果：

display(successor(predecessor(ONE)))
// => 1

现在，转向阶乘。应用与上面相同的技巧（将 if 和 else 分支包装到闭包中以防止它们过早评估）：

const factorial = n => (iszero(n))(() => ONE)(() => multiply(n)(factorial(predecessor(n))()));

const FIVE = successor(successor(successor(successor(ONE))));
display(factorial(FIVE)())
// => 120

Answer 2

问题是函数参数在函数本身运行之前被完全求值。所以，例如，当

(n * factorial(n - 1))

是一个参数列表，那里的代码必须在继续调用由

返回的函数之前解析为一个值

n => ifelse(n == 0)(1)

它不会在评估之前首先检查您的 ifelse 条件 - 它无论如何都会尝试评估它。因此，导致堆栈溢出，因为它试图不断计算出 n 的 else 结果，然后是 n - 1，然后是 n - 2，... n - 10 , n - 11, 等等。

将 b 作为函数传递，这样您就可以调用它并将 else 计算为仅当条件最终为false:

const ifelse = condition => a => b => condition ? a : b();
const factorial = n => ifelse(n == 0)(1)(() => n * factorial(n - 1));
//                                       ^^^^^
console.log(factorial(5));

Javascript 无条件递归

Javascript recursion without conditional

javascript

recursion

lambda-calculus

arrow-functions