Блог

Я читаю SICP в 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))
 

Это объясняет, что:

Это сделало бы функцию не просто неэффективной, но и фактически не завершающейся! Проблема в том, что объявление константы появляется вне условного выражения, что означает, что оно выполняется даже при выполнении базового варианта exp === 0 .

Я просто не могу понять, когда exp === 0, он завершается на 1, но почему выполняется half_exp?

Вы выполняете рекурсивный вызов в первой строке, которая выполняется независимо ни от чего. Это означает, что функция не завершается, то есть является бесконечным циклом.

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

Рекурсивные вызовы всегда должны выполняться в паре с какой-либо проверкой, чтобы убедиться, что есть точка выхода.

Часть, которую вы неправильно поняли, заключается в том, как и когда инициализируются переменные, а не в том, как работает троичный. Троичный будет работать так, как вы думали, если интерпретатор достиг его.

Вы поместили 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.

Лексическая привязка: инициализатор идентификатора привязки

1. Пусть bindingId будет строковым значением BindingIdentifier .
2. Пусть lhs будет ResolveBinding(bindingId).
3. Если IsAnonymousFunctionDefinition(инициализатор) имеет значение true, то

   a. Пусть значением будет NamedEvaluation инициализатора с аргументом bindingId .

4. Ещё,

   a. Пусть rhs будет результатом вычисления инициализатора *.
   b. Пусть значение будет ? Получить значение (rhs).

5. Возвращает InitializeReferencedBinding(lhs, значение).

_{*: Выделение мое.}

Итак, как вы можете видеть, интерпретатор не будет ждать использования переменной.

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

 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