三元条件求expmod？

Question

我正在阅读 SICP in JS 关于三元条件的非终止示例：

function is_even(n) {
    return n % 2 === 0;
}

function expmod(base, exp, m) {
    const half_exp = expmod(base, exp / 2, m);
    return exp === 0 ? 1
           : is_even(exp) ? half_exp * half_exp % m
           : base * expmod(base, exp - 1, m) % m;
}

console.log(expmod(4, 3, 5))

它解释说：

This would make the function not just inefficient, but actually non-terminating! The problem is that the constant declaration appears outside the conditional expression, which means that it is executed even when the base case exp === 0 is met.

我只是不明白它的想法，当 exp === 0 时，它以 1 终止，但是为什么 half_exp 被执行了？

Answer 1

I just cannot get its idea, when exp === 0, it terminate with 1 but why half_exp executed?

否，当 exp 为 0 时，表达式不会以 1 结尾。 exp === 0 ? 1: is_even(exp) 将计算为 1 并且整个表达式将作为下一个三元运算符的条件。由于 1 是一个真实值，因此整个表达式的计算结果将是 half_exp * half_exp % m

//Initial expression
(exp === 0 ? 1
   : is_even(exp)) ? (half_exp * half_exp % m)
   : (base * expmod(base, exp - 1, m) % m);

//Put exp = 1
(1 === 0 ? 1
   : is_even(exp)) ? (half_exp * half_exp % m)
   : (base * expmod(base, exp - 1, m) % m);

//Evaluate the first ternary expression
(1) ? (half_exp * half_exp % m)
   : (base * expmod(base, exp - 1, m) % m);

//The result of first will convert to boolean
Boolean(1) ? (half_exp * half_exp % m)
   : (base * expmod(base, exp - 1, m) % m);

//The result of first expression acts as condition for second ternary operator
true ? (half_exp * half_exp % m)
   : (base * expmod(base, exp - 1, m) % m);

//As condition is true to first expression is returned
(half_exp * half_exp % m)

Answer 2

你在第一行进行了递归调用，无论如何都会执行。这意味着函数是非终止的，也就是无限循环。

function expmod(base, exp, m) {
    const half_exp = expmod(base, exp / 2, m); // <- recursive call
    // code ...
}

递归调用应始终与某种检查配对以确保存在退出点。

Answer 3

您误解的部分是变量初始化的方式和时间，而不是三元组的工作原理。三元将按您的想法工作，如果解释器已达到它。

您已将 half_exp 变量放入条件表达式中，并期望它在使用之前不会计算其初始值设定项。

然而，事实并非如此。

所有变量初始化语句（var、let 和 const）当控制到达语句时，立即计算它们的初始化器，不检查变量是否在以后使用；并将初始化器的值存储到变量中。

您可以通过运行以下代码段查看：

const foo = console.log("I'm executed!") //`foo` is never used, but the code will print "I'm executed!" anyway

您还可以通过查看 ECMAScript Specification.
来确认这一点

LexicalBinding : BindingIdentifier Initializer

Let bindingId be StringValue of BindingIdentifier.

Let lhs be ResolveBinding(bindingId).

If IsAnonymousFunctionDefinition(Initializer) is true, then

a. Let value be NamedEvaluation of Initializer with argument bindingId.

Else,

a. Let rhs be the result of evaluating Initializer *.
b. Let value be ? GetValue(rhs).

Return InitializeReferencedBinding(lhs, value).

_{*: Emphasis mine.}

因此，如您所见，解释器不会等待变量被使用。

这意味着在您的代码中：

// v-------------------------------------------+ function expmod(base, exp, m) { // | const half_exp = expmod(base, exp / 2, m); // ---+ // ^^^^^^--- This will always be called // This line is not even reached! return exp === 0 ? 1 : is_even(exp) ? half_exp * half_exp % m : base * expmod(base, exp - 1, m) % m; }

...你有无限递归。

为了解决这个问题，我们必须将该调用移到条件部分。在您的代码中，这很容易，因为我们可以将值提高到它的二次方，而不是编写与自身的乘法，从而消除其中一个引用：

function is_even(n) { return n % 2 === 0; } function expmod(base, exp, m) { return exp === 0 ? 1 : is_even(exp) ? expmod(base, exp / 2, m) ** 2 % m : base * expmod(base, exp - 1, m) % m; } console.log(expmod(4, 3, 5)) //4

在其他情况下，如果没有这种直接的方法，我们可以通过其他方式重构代码，例如，使用 ifs:

function is_even(n) { return n % 2 === 0; } function expmod(base, exp, m) { if(exp === 0) return 1; if(is_even(exp)){ // We are in a conditional statement, so it's safe to call: const half_exp = expmod(base, exp / 2, m) return half_exp * half_exp % m } return base * expmod(base, exp - 1, m) % m; } console.log(expmod(4, 3, 5)) //4

三元条件求expmod？

Ternary conditions to find expmod?

javascript

sicp