Для работы этой страницы вам нужно включить JavaScript. You need to enable JavaScript to run this app.
WebpurpleWebpurple
  • #translation
  • #javascript
  • #es6
  • #fp
July 19, 2018 12:00 AM
⌚ 7 минут

Оптимизация хвостовых вызовов в ECMAScript 6

Перевод статьи Tail call optimization in ECMAScript 6

Оптимизация хвостовых вызовов - одна из новых возможностей, которая появилась в спецификация ECMAScript 6. Теперь мы можем вызывать определенные функций без увеличения стека вызовов. В данной статье объясняется, как это работает и какую выгоду приносит.

1. Что такое оптимизация хвостовых вызовов

Чтобы понять, что такое оптимизация хвостовых вызовов (TCO - tail call optimization), мы рассмотрим фрагмент кода, представленный ниже. Сначала я объясню как этот код выполняется без TCO, а затем с TCO.

function id(x) {
    return x; // (A)
}
function f(a) {
    let b = a + 1;
    return id(b); // (B)
}
console.log(f(2)); // (C)

1.1 Нормальное выполнение

Предположим, что есть JavaScript движок, который управляет вызовами функций, сохраняя локальные переменные и адреса возврата в стеке. Как такой движок будет выполнять код?

Шаг 1. Первоначально в стек попадают только глобальные переменные id и f.

Global stack frame

Блок записей стека, который кодирует состояние (локальные переменные, включая параметры) текущей области, называется стековым кадром.

Шаг 2. В строке С вызывается функция f(). Сначала в стеке сохраняется место возврата. Затем сохраняются параметр функции f() и ее локальная переменная, и после этого выполнение переходит к телу функции. Теперь стек выглядит следующим образом:

Stack frame of f()

Теперь в стеке 2 кадра: один для глобальной области (снизу), и один для функции f() (сверху). Стековый кадр функции f() включает в себя адрес возврата, строку С.

Шаг 3. Функция id() вызывается в строке B. Снова создается стековый кадр, содержащий адрес возврата и параметр функции id.

Stack frame of id()

Шаг 4. В строке A возвращается результат x. Стековый кадр функции id удаляется, и выполнение переходит к адресу возврата, строке B. (Существует несколько способов возврата значения. Есть два частых решения - оставить результат в стеке или передать его в регистр. В данной статье я игнорирую эту часть исполнения.)

Сейчас стек выглядит так:

pic4

Шаг 5. В строке B значение, возвращаемое функцией id, передается в вызывающую функцию f. Снова удаляется верхний стековый кадр и выполнение переходит к адресу возврата, строка С.

pic5

Шаг 6. Строка C получает значение 3 и выводит его в консоль.

1.2 Оптимизация хвостовых вызовов

function id(x) {
    return x; // (A)
}
function f(a) {
    let b = a + 1;
    return id(b); // (B)
}
console.log(f(2)); // (C)

Если взглянуть на предыдущий раздел, то можно увидеть, что одни шаг лишний - это шаг 5. Все, что происходит в строке B - это передача значения, возвращаемого id(), в строку C. В идеале функция id() может сделать это сама, и промежуточный этап можно опустить.

Мы можем добиться такого поведения по-другому реализовав вызов функции в строке B. Перед вызовом стек выглядит следующим образом:

pic6

Если рассматривать вызов, то можно заметить, что это последнее действие в f(). Как только id() будет выполнена, единственным оставшимся действием, выполняемым f(), будет передача результата id() в функцию, вызывающую f(). Поэтому переменные f больше не нужны, и ее стековый кадр может быть удален перед следующим вызовом. Адрес возврата, передающийся в id(), это адрес возврата f, строка C. Во время выполнения id() стек выглядит следующим образом:

pic7

Тогда id() возвращает значение 3. Можно сказать, что функция id возвращает значение за функцию f, потому что id передает значение в функцию вызывающую f, строка C.

Итак, сделаем вывод. Вызов функции в строке B является хвостовым вызовом. Такой вызов может быть выполнен с нулевым ростом стека. Чтобы узнать, является ли вызов функции хвостовым, мы должны проверить, находится ли эта функция в хвостовой позиции (т.е. является ли последним действием функции). Как это делается рассмотрено в следующем разделе.

2. Как проверить, находится ли вызов функции в хвостовой позиции

В предыдущем разделе было выяснено, что хвостовые вызовы - это вызовы функций, которые могут выполняться более эффективно. Но что считается хвостовым вызовом?

Во-первых, способ, которым вы вызываете функцию, не имеет значения. Следующие вызовы могут быть оптимизированы, если они появятся в хвостовой позиции:

  • Функциональный вызов: func(···)
  • Вызов метода объекта: obj.method(···)
  • Прямой вызов через call(): func.call(···)
  • Прямой вызов через apply(): func.apply(···)

2.1 Хвостовые вызовы в выражениях

Стрелочные функции могут содержать выражения в качестве тела. По этой причине для оптимизации хвостовых вызовов мы должны выяснить, находятся ли вызовы функций в хвостовых позициях внутри выражений. Только следующие выражения могут содержать хвостовые вызовы:

  • Условный оператор (? :)
  • Логический оператор ИЛИ (||)
  • Логический оператор И (&&)
  • Оператор запятая (,)

Давайте рассмотрим примеры каждого из них.

Условный оператор (? :)

const a = x => x ? f() : g();

Обе функции f() и g() находятся в хвостовой позиции.

Логический оператор ИЛИ (||)

const a = () => f() || g();

f() не находится в хвостовом позиции, в отличие от g(). Чтобы понять, почему, взгляните на следующий код, который эквивалентен предыдущему коду:

const a = () => {
    let fResult = f(); // not a tail call
    if (fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};

Результат логического оператора ИЛИ зависит от результата f(), поэтому этот вызов функции не находится в хвостовой позиции (функция, вызывающая f(), делает что-то с ней, кроме возврата). Однако g() находится в хвостовой позиции.

Логический оператор И

const a = () => f() && g();

f() не находится в хвостовой позиции, в отличие от g(). Чтобы понять, почему, взгляните на следующий код, который эквивалентен предыдущему коду:

const a = () => {
    let fResult = f(); // not a tail call
    if (!fResult) {
        return fResult;
    } else {
        return g(); // tail call
    }
};

Результат логического оператора И зависит от результата f(), поэтому этот вызов функции не находится в хвостовой позиции (функция, вызывающая f(), делает что-то с ней, кроме возврата). Однако g() находится в хвостовой позиции.

Оператор запятая (,)

const a = () => (f() , g());

f() не находится в хвостовой позиции, в отличии от g(). Чтобы понять, почему, взгляните на следующий код, который эквивалентен предыдущему коду:

const a = () => {
    f();
    return g();
}

2.2 Хвостовые вызовы в инструкциях

Для инструкций применяются следующие правила.

Только эти составные инструкции могут содержать хвостовые вызовы:

  • Блоки (ограничены {}, с инструкцией метки или без нее)
  • if: либо в ветвях “then” или “else”.
  • do-while, while, for: в теле цикла.
  • switch: в блоке выбора.
  • try-catch: только в блоке catch. В контексте блока try содержится блок catch и поэтому он не может быть оптимизирован.
  • try-finally, try-catch-finally: только в блоке finally, который находится в контексте для других блоков, поэтому они не могут быть оптимизированы.

Из всех одиночных инструкций только "return" может содержать хвостовой вызов. Все остальные инструкции имеют контекст, который нельзя оптимизировать. Следующая инструкция содержит хвостовой вызов, если "expr" содержит его.

return «expr»;

2.3 Оптимизация хвостовых вызовов может производиться только в строгом режиме

В нестрогом режиме (non-strict mode) большинство движков имеет следующие два свойства, которые позволяют проверять стек вызовов:

  • func.arguments: содержит аргументы последнего вызова функции func.
  • func.caller: ссылается на функцию, которая последняя вызывала func.

При оптимизации хвостовых вызовов эти свойства не работают, поскольку информация, на которую они полагаются, может быть удалена. Поэтому строгий режим запрещает эти свойства (как описано в спецификации) и оптимизация хвостовых вызовов работает только в строгом режиме.

2.4 Подводный камень: вызов единственной функции никогда не находится в хвостовой позиции

Вызов функции bar() в следующем коде не находится в хвостовой позиции:

function foo() {
    bar(); // this is not a tail call in JS
}

Причина в том, что последнее действие функции foo() не является вызовом функции bar(), оно (неявно) возвращает undefined. Другими словами, foo() ведет себя так:

function foo() {
    bar();
    return undefined;
}

Функции, вызывающие foo() всегда ожидают возврат undefined. Если bar() должен был вернуть результат за foo() из-за оптимизации хвостового вызова, это могло бы изменить поведение foo.

Поэтому, если мы хотим, чтобы bar() был хвостовым вызовом, необходимо изменить foo() следующим образом:

function foo() {
    return bar(); // tail call
}

3. Хвостовая рекурсия

Функция является "хвостовой рекурсией", если основные рекурсивные вызовы, которые она делает, находятся в хвостовых позициях.

Например, следующая функция не является хвостовой рекурсией, поскольку основной рекурсивный вызов в строке A не находится в хвостовой позиции:

function factorial(x) {
    if (x <= 0) {
        return 1;
    } else {
        return x * factorial(x-1); // (A)
    }
}

Функция factorial() может быть реализована через вспомогательную функцию facRec(). В данном случае основной рекурсивный вызов в строке A находится в хвостовой позиции:

function factorial(n) {
    return facRec(n,1);
}
function facRec(x, acc) {
    if (x <= 1) {
        return acc;
    } else {
        return facRec(x-1, x*acc); // (A)
    }
}

То есть некоторые функции, не являющиеся хвостовыми рекурсиями, могут быть в них преобразованы.

3.1 Циклы через хвостовую рекурсию

Оптимизация хвостовых вызовов позволяет реализовать циклы через рекурсию, не увеличивая стек. Ниже приведены два примера:

forEach()

function forEach(arr, callback, start = 0) {
    if (0 <= start && start < arr.length) {
        callback(arr[start], start, arr);
        return forEach(arr, callback, start+1); // tail call
    }
}
forEach(['a', 'b'], (elem, i) => console.log(`${i}. ${elem}`));

// Output:
// 0. a
// 1. b

findIndex()

function findIndex(arr, predicate, start = 0) {
    if (0 <= start && start < arr.length) {
        if (predicate(arr[start])) {
            return start;
        }
        return findIndex(arr, predicate, start+1); // tail call
    }
}
findIndex(['a', 'b'], x => x === 'b'); // 1