Ternary conditions to find expmod?

I am reading SICP in JS about a non-terminating example of ternary conditions:

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

It explains that:

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.

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

Answer

The part you’ve misunderstood is how and when the variables are initialized, and not how the ternary works. The ternary would work as you thought, if the interpreter had reached it.

---

You’ve put the half_exp variable in a conditional expression and expected it to not evaluate its initializer until it is used.

However, that’s not how it works.

All variable initialization statements (both var, let and const) evaluate their initializer immediately when the control reaches the statement, without checking whether the variable is used later; and store the value of the initializer to the variable.

You can see it by running the following snippet:

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

You can also confirm this by looking at the ECMAScript Specification.

LexicalBinding : BindingIdentifier Initializer

1. Let bindingId be StringValue of BindingIdentifier.

2. Let lhs be ResolveBinding(bindingId).

3. If IsAnonymousFunctionDefinition(Initializer) is true, then

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

4. Else,

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

5. Return InitializeReferencedBinding(lhs, value).

_{*: Emphasis mine.}

So, as you can see, the interpreter won’t wait for the variable to be used.

This means that in your code:

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

…you have infinite recursion.

---

To get around the issue, we have to move that call into a conditional part. In your code, that’s easy, as instead of writing a multiplication with itself, we can raise the value to its second power, eliminating one of the references:

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

In other cases, where there’s no such straightforward way, we could’ve refactored the code otherwise, for example, using 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