Трамплин в JavaScript

Трамплин - функция которая итеративно вызывает возвращенную функцию преобразователь (стиль продолжений). Одного трамплина достаточно чтоб выразить все управление программой, программа тем самым становиться трамплинной или выраженная в трамплинном стиле. Конвертирование программы в трамплинный стиль называется "трамплинирование". Трамплинные функции могут быть использованы программистами для реализации хвостовой оптимизации в стековых языках - Wikipedia

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

Это именно то, что нужно на ответ "определите трамплины" на экзамене, так как демонстрирует что вы тщательно изучили тему. Но если спросят объяснить трамплины, нужен более обучающий подход.

Рассмотрим наш случай использования.

Рекурсия

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

Усложнением задачи может быть, реализация ее в рекурсивном стиле.

Вы написали:

function factorial (n) {
  return n
  ? n * factorial(n - 1)
  : 1
}

Первым ограничением этой реализации будет то, что она вызывает сама себя n-ное количество раз, для получение результата в типичном стековом языке, необходим стек с n-ным уровнем вложенности. И JavaScript является таким языком.

Это создает две проблемы:

1. Нам нужно место для каждого уровня стека. Собственно, это то же, что и если бы мы написали 1 x 1 x 2 x 3 x 4 x ... перед тем как сделать расчеты.
2. Большинство языков программирования имеют ограничение на глубину стека, и он намного меньше нежели необходимое количество памяти необходимое для данных.

Запустив это на NodeJS, я получил:

factorial(10)
  //=> 3628800
factorial(32768)
  //=> RangeError: Maximum call stack size exceeded

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

Хвостовая оптимизация

Давайте представим, что вам сказали, что целевая платформа JavaScript поддерживает хвостовую оптимизацию. Имеется ввиду что когда функция возвращает результат вызова самой себя, язык не делает дополнительный вызов функции, а просто оборачивает тело функции в цикл вместо вас.

Написанный factorial, не может быть оптимизирован, так как не возвращает результат вызова функции, он вызывает функцию и потом делает что-то с результатом. То есть он все еще нуждается в уровнях стека.

Lisp программисты в наши дни переписали бы функцию в "форму хвостовой рекурсии", и это то, что мы собираемся сделать. Все что нам нужно сделать - взять выражение n * factorial(n - 1) и сдвинуть его ниже в функцию которую мы сможем вызвать с параметрами.

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

Если мы используем символ _ для представление своего рода "слота", в выражениях где будем размещать результат каждый раз когда factorial вызывает сам себя, это потребует запомнить n * _, поэтому когда мы получим назад результат мы можем умножит его на n и вернуть обратно. Впервые вызванный он запомнит 10 * _, после второго самовызова он запомнит 9 * _, и так далее для остальных значений:

 1 * _
 2 * _
 3 * _
 4 * _
 5 * _
 6 * _
 7 * _
 8 * _
 9 * _
10 * _

И наконец вызываем factorial(0) который вызывает 1. После получаем верхушку стека, и вычисляем 1 * 1. Результат конечно же 1 и далее вычисляем 2 * 1. Который возвращает 2 и мы вычисляем 3 * 2 и так пока не достигнем 10 * 362880 который вернет 3628800 собственно что мы и выведем.

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

Такой вызов называется "хвостовой позицией" или "хвостовым вызовом". Устранение хвостового вызова значит, что мы не делаем полноценный вызов функции, включая создания уровня в стеке. Мы просто делаем эквивалент "прыжка" (jump).

Если нам не нужно ничего запоминать, мы не создаем дополнительный уровень стека, мы просто переиспользуем текущий. Когда я говорю "мы", я имею ввиду людей которые пишут интерпретаторы. В общем это функционал языка, а не самой программы.

Если бы у нас была реализация хвостовой рекурсии в JavaScript, то нам нужно бы было переписать функцию факториала, для того чтоб она сработала. Это просто сделать с вспомогательный функцией. Для реальных задач мы бы использовали IIFE или другие техники для инкапсуляции и предотвращения создания замыкания на каждый вызов факториала, но так как у нас учебный пример, поэтому:

function factorial (n) {
  var _factorial = function myself (acc, n) {
    return n
    ? myself(acc * n, n - 1)
    : acc
  };

  return _factorial(1, n);
}

Теперь наша функция возвращает значение или результат вызова другой функции, без обработки этого результата.

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

Это дает нам правильный результат, но мы можем увидеть что NodeJS не умеет делать эту магическую "хвостовую оптимизацию".

factorial(10)
  //=> 3628800
factorial(32768)
  //=> RangeError: Maximum call stack size exceeded

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

Десятое правило Гринспена: Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp.

Следствие Стила & Крокфорда к десятому правилу Гринспена: Любая достаточно интересная библиотека к JavaScript содержит неспецифицированную, глючную и медленную реализацию половины языка Haskell.

Трамплины

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

Когда мы вызываем функцию, она возвращает преобразователь который мы вызываем чтоб получить результат. Конечно же, преобразователь может вернуть еще один преобразователь, и так каждый раз когда мы получаем результат, мы проверяем не преобразователь ли он. Если нет, мы получили остаточный результат.

Что такое преобразователь? Я не объяснил еще? Для наших нужд, преобразователь это функция которая не принимает аргументов, и должна быть чистой функцией. К примеру, вот это преобразователь:

function () {
    return 'Hello World';
}

Необычайно простая и полезная реализация трамплина может быть найдена в библиотеке Lemonad. Она работает при условии, что трамплин это функция которая не возвращает функцию. Вот реализация:

L.trampoline = function(fun /*, args */) {
  var result = fun.apply(fun, _.rest(arguments));

  while (_.isFunction(result)) {
    result = result();
  }

  return result;
};

Перепишем ее на стиль allong.es для согласованности с другими статями в этом блоге. В смысле, напишем функцию декоратор:

//npm install allong.es

var variadic = require('allong.es').variadic;

var trampoline = function (fn) {
  return variadic( function (args) {
    var result = fn.apply(this, args);

    while (result instanceof Function) {
      result = result();
    }

    return result;

  });
};

Теперь вот наша реализация factorial которая обернута в хвостовую трамплинную функцию:

function factorial (n) {
  var _factorial = trampoline( function myself (acc, n) {
    return n
    ? function () { return myself(acc * n, n - 1); }
    : acc
  });

  return _factorial(1, n);
}

factorial(10);
  //=> 362800
factorial(32768);
  //=> Infinity

Вуаля, она работает для n = 32768. Теперь решим проблему "бесконечности", которая вызвана лимитами целых чисел в JavaScript. Вот наша законченная работа:

//npm install big-integer

var variadic = require('allong.es').variadic,
    bigInt = require("big-integer");

var trampoline = function (fn) {
  return variadic( function (args) {
    var result = fn.apply(this, args);

    while (result instanceof Function) {
      result = result();
    }

    return result;

  });
};

function factorial (n) {
  var _factorial = trampoline( function myself (acc, n) {
    return n.greater(0)
    ? function () { return myself(acc.times(n), n.minus(1)); }
    : acc
  });

  return _factorial(bigInt.one, bigInt(n));
}

factorial(10).toString()
  //=> '3628800'
factorial(32768)
  //=> GO FOR LUNCH - (можем идти на обед)

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

И реализация не потребовала сильной модификации. Это хорошо, конвертирование в хвостовую форму более назойливое.

Вот что мы сделали:

1. Переписали нашу функцию в хвостовую форму, и;
2. Вместо возвращения результата вызова самого себя мы;
3. Вернули преобразователь, функция которая вызывает себя, и;
4. Вызывает декоратор trampoline, и;
5. Конвертирует в арифметику с большими числами.

Ограничение этой простой реализации есть то, что тесты для функции возвращающей функцию, не будут работать для функции которая возвращает функцию. Если вам надо функцию трамплин которая возвращает функцию, вам надо более утонченный механизм, например как реализация трамплина в bilby.js.

Вот наш factorial реализован в рамках bilby:

var B = require('bilby'),
    cont = B.cont,
    done = B.done,
    trampoline = B.trampoline;

function factorial (n) {
  var _factorial =  function myself (acc, n) {
    return n.greater(0)
    ? cont( function () { return myself(acc.times(n), n.minus(1)); })
    : done( acc )
  };

  return trampoline( _factorial(bigInt.one, bigInt(n)) );
}

factorial(10).toString();
  //=> '3628800'
factorial(32768);
  //=> GO FOR LUNCH - идем обедать

Подход Bilby имеет больше движущихся частей, но они понятные и именование может объяснить предназначение. И как бонус, нет больше ограничения что трамплин не может вернуть функцию.

Заключение

Трамплин это техника для "ручной" реализации хвостовой рекурсии. Имеется ввиду если вы возьмете рекурсивную функцию и перепишете в хвостовую форму, мы уменьшите необходимость в создании уровня стека на каждый вызов.

Это очень удобно в языках на подобие JavaScript, это то что позволяет вам использовать рекурсивный стиль без необходимости заботиться о ограничениях размера стека.

Источник