Трамплины и продолжения
Любопытно, конечно, что наибольшую популярность завоёвывают именно плохие с инженерной точки зрения технологии. Я не могу объяснить этот феномен: казалось бы, согласно эволюционной теории "более лучшие" вещи должны постепенно заменять эквивалентные по функционалу "более худшие", но этого не происходит. И даже не всегда проблема в том, что что-то сложнее, а что-то легче: обычно, в плохо продуманных технологиях сложность как раз выше, просто она "отложенная".
Давайте, например, посмотрим на такие платформы: Common Lisp/Scheme, Haskell или OCaml. А потом на такие: Java или Javascript. В чём разница? Правильно, в одних есть хвостовая рекурсия, в других нет :)
Ладно, на самом деле, большинству программистов наджави эта рекурсия нафиг не сдалась. Полагаю, что многие и не подозревают даже что это такое, и подобное неведение никак не мешает им вполне комфортно существовать на свете. Но оная проблема встаёт достаточно остро для пользователей более вменяемых языков, которые используют джаву или js в качестве бэкенд-платформы. Например, Clojure для jvm или Elm для javascript. Эти языки предполагают функциональную парадигму программирования, и отсутствие TCO при этом причиняет серьёзные неудобства.
Честно говоря, натолкнувшись на переполнение стека в Elm, я был несколько ошарашен. Ничто не предвещает беды, вокруг тепло и уютно: с одной стороны, у тебя почти хаскель, с другой тебе было обещано отсутствие рантайм-исключений (если ты не выходишь за рамки чистого elm). И тут херак, привет из js:
RangeError: Maximum call stack size exceeded
Я поначалу даже растерялся - к такому меня жизнь явно не готовила. Пришлось потратить некоторое количество времени, чтобы разобраться, как в таких случаях следует поступать: ведь никаких специальных технических средств для написания явных циклов руками в ельме нет. Он умеет оптимизировать только самые простые хвостовые вызовы, но любая чуть более сложная рекурсия сразу становится "честной". Поэтому пишу этот материал постфактум в качестве инструкции - мало ли кому ещё поможет.
Итак, давайте рассмотрим следующий синтетический пример:
isEven : Int -> Bool
isEven x =
case abs x of
0 -> True
v -> isOdd <| v - 1
isOdd : Int -> Bool
isOdd x =
case abs x of
0 -> False
v -> isEven <| v - 1
isSumEven : Int -> Int -> Bool
isSumEven a b =
isEven a == isEven b
Я тут попытался смоделировать проблему: у нас есть две взаимно-рекурсивные функции (определяющие, чётное или нечётное число на входе) и одна утилитарная, которая их как-то использует (предсказывает, будет ли сумма двух чисел чётная).
Можно сразу посмотреть в репле, как они (не) работают:
> isEven 2
True : Bool
> isOdd 13
True : Bool
> isSumEven 100 1
False : Bool
> isEven 100000
RangeError: Maximum call stack size exceeded
Как их заставить работать, если платформа не поддерживает TCO? Никак, надо переписывать.
Общепринятая практика использовать в таких случаях технику, которая называется trampolining. Она широко используется, например, в Clojure. Идея там достаточно простая. Мы рефакторим функции, использующие рекурсию таким образом, чтобы:
В Elm, оказывается, есть даже микро-пакетик с трамплинами: elm-lang/trampoline. С его помощью можно переписать вышеприведённые взаимно-рекурсивные функции следующим образом:
import Trampoline exposing (Trampoline, done, jump, evaluate)
isEvenTr : Int -> Trampoline Bool
isEvenTr x =
case abs x of
0 -> done True
v -> jump <| \() -> isOddTr <| v - 1
isOddTr : Int -> Trampoline Bool
isOddTr x =
case abs x of
0 -> done False
v -> jump <| \() -> isEvenTr <| v - 1
В данном случае, всё получается достаточно прямолинейно: когда готов результат, возвращаем его через done, а когда нужно выполнить рекурсивный вызов, оборачиваем его в thunk и возвращаем через jump. Соответственно, в пакете trampoline лежит ещё функция evaluate, которая как раз крутит цикл, вызывая по-очереди все возвращаемые продолжения. Проверяем:
> evaluate <| isEvenTr 2
True : Bool
> evaluate <| isOddTr 13
True : Bool
> evaluate <| isOddTr 100000
False : Bool
Да, в этом варианте всё работает!
Кстати, небольшое отступление. Очевидно, что многим (включая меня) может не понравиться, как выглядит вот этот кусок кода:
jump <| \() -> isOddTr <| v - 1
Лично я его автоматически написал сначала так:
jump <| always <| isOddTr <| v - 1
За что был наказан потерянным часом на отладку. Кто может предположить, в чём кроется засада? :) Для справки: always.
Ладно, возвращаемся к примерам. Как написать трамплин-версию isSumEven? В принципе, можно как-то так:
isSumEvenTr : Int -> Int -> Trampoline Bool
isSumEvenTr a b =
done <| (evaluate <| isEvenTr a) == (evaluate <| isEvenTr b)
Конкретно для этого синтетического примера, наверно, такой вариант особо ничем не плох. Но всё же: можно ли обойтись только одним evaluate? Очевидно, что можно, если получится каким-то образом "попасть внутрь" типа Trampoline a, чтобы достать значение a или, хотя бы, как-то его преобразовать. Но вот незадача: этот тип не является функтором или монадой, никаких соответствующих комбинаторов для него нет, да и вообще это всё страшные слова, и такой мерзости у нас в эльме не водится! Следовательно, единственный вариант - это честно интерпретировать Trampoline a через evaluate. Или нет?
На самом деле, есть способ "состыковать" несколько Trampoline-ов, чтобы выполнить их в одном цикле-эвалюаторе: опять же, CPS. Но для этого нам опять нужно отрефакторить функции, на этот раз в continuation passing style:
isEvenTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isEvenTrK x k =
case abs x of
0 -> k True
v -> jump <| \() -> isOddTrK (v - 1) k
isOddTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isOddTrK x k =
case abs x of
0 -> k False
v -> jump <| \() -> isEvenTrK (v - 1) k
isSumEvenTrK : Int -> Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isSumEvenTrK a b k =
isEvenTrK a <|
\resultA ->
jump <| \() -> isEvenTrK b <|
\resultB ->
k <| resultA == resultB
Главное изменение: функции теперь не возвращают результаты напрямую (логически, они уже ничего не должны возвращать), вместо этого они принимают дополнительные параметр: "продолжение", которому этот результат передаётся. Теперь в isEvenTrK появилась возможность состыковать две "затрамплиненные" функции внутри продолжения, при этом сохранив тип возвращаемого значения Trampoline Bool, который уже скармливается единственному evaluate:
> evaluate <| isSumEvenTrK 100000 1 done
False : Bool
> evaluate <| isSumEvenTrK 100000 100000 done
True : Bool
В принципе, этот трюк может пригодится, например, когда завёрнутым в трамплин типом является тот же Result - и надо уметь в процессе работы запускать разные ветки вычислений в зависимости от того, успешно ли отработал один из рекурсивных вызовов, или нет.
Ну, в целом, как-то так. Далее полагается, чтобы я написал какие-то выводы или подытоги, но какие тут могут быть выводы? Сложно, запутанно. Но это и есть та самая "отложенная сложность", про которую я говорил в начале поста. Был бы в вашем джаваскрипте изначально родной TCO, я бы не писал этот текст, а вместо этого сделал бы что-нибудь полезное.
Давайте, например, посмотрим на такие платформы: Common Lisp/Scheme, Haskell или OCaml. А потом на такие: Java или Javascript. В чём разница? Правильно, в одних есть хвостовая рекурсия, в других нет :)
Ладно, на самом деле, большинству программистов наджави эта рекурсия нафиг не сдалась. Полагаю, что многие и не подозревают даже что это такое, и подобное неведение никак не мешает им вполне комфортно существовать на свете. Но оная проблема встаёт достаточно остро для пользователей более вменяемых языков, которые используют джаву или js в качестве бэкенд-платформы. Например, Clojure для jvm или Elm для javascript. Эти языки предполагают функциональную парадигму программирования, и отсутствие TCO при этом причиняет серьёзные неудобства.
Честно говоря, натолкнувшись на переполнение стека в Elm, я был несколько ошарашен. Ничто не предвещает беды, вокруг тепло и уютно: с одной стороны, у тебя почти хаскель, с другой тебе было обещано отсутствие рантайм-исключений (если ты не выходишь за рамки чистого elm). И тут херак, привет из js:
RangeError: Maximum call stack size exceeded
Я поначалу даже растерялся - к такому меня жизнь явно не готовила. Пришлось потратить некоторое количество времени, чтобы разобраться, как в таких случаях следует поступать: ведь никаких специальных технических средств для написания явных циклов руками в ельме нет. Он умеет оптимизировать только самые простые хвостовые вызовы, но любая чуть более сложная рекурсия сразу становится "честной". Поэтому пишу этот материал постфактум в качестве инструкции - мало ли кому ещё поможет.
Итак, давайте рассмотрим следующий синтетический пример:
isEven : Int -> Bool
isEven x =
case abs x of
0 -> True
v -> isOdd <| v - 1
isOdd : Int -> Bool
isOdd x =
case abs x of
0 -> False
v -> isEven <| v - 1
isSumEven : Int -> Int -> Bool
isSumEven a b =
isEven a == isEven b
Я тут попытался смоделировать проблему: у нас есть две взаимно-рекурсивные функции (определяющие, чётное или нечётное число на входе) и одна утилитарная, которая их как-то использует (предсказывает, будет ли сумма двух чисел чётная).
Можно сразу посмотреть в репле, как они (не) работают:
> isEven 2
True : Bool
> isOdd 13
True : Bool
> isSumEven 100 1
False : Bool
> isEven 100000
RangeError: Maximum call stack size exceeded
Как их заставить работать, если платформа не поддерживает TCO? Никак, надо переписывать.
Общепринятая практика использовать в таких случаях технику, которая называется trampolining. Она широко используется, например, в Clojure. Идея там достаточно простая. Мы рефакторим функции, использующие рекурсию таким образом, чтобы:
- во всех местах, где производится рекурсивный вызов, вместо этого возвращалось наружу продолжение (достаточно просто обычного замыкания: thunk)
- на самом "верхнем" уровне выполняется обычный тупой цикл (trampoline), который последовательно вызывает отрефакторенную функцию до тех пор, пока она возвращает продолжения
В Elm, оказывается, есть даже микро-пакетик с трамплинами: elm-lang/trampoline. С его помощью можно переписать вышеприведённые взаимно-рекурсивные функции следующим образом:
import Trampoline exposing (Trampoline, done, jump, evaluate)
isEvenTr : Int -> Trampoline Bool
isEvenTr x =
case abs x of
0 -> done True
v -> jump <| \() -> isOddTr <| v - 1
isOddTr : Int -> Trampoline Bool
isOddTr x =
case abs x of
0 -> done False
v -> jump <| \() -> isEvenTr <| v - 1
В данном случае, всё получается достаточно прямолинейно: когда готов результат, возвращаем его через done, а когда нужно выполнить рекурсивный вызов, оборачиваем его в thunk и возвращаем через jump. Соответственно, в пакете trampoline лежит ещё функция evaluate, которая как раз крутит цикл, вызывая по-очереди все возвращаемые продолжения. Проверяем:
> evaluate <| isEvenTr 2
True : Bool
> evaluate <| isOddTr 13
True : Bool
> evaluate <| isOddTr 100000
False : Bool
Да, в этом варианте всё работает!
Кстати, небольшое отступление. Очевидно, что многим (включая меня) может не понравиться, как выглядит вот этот кусок кода:
jump <| \() -> isOddTr <| v - 1
Лично я его автоматически написал сначала так:
jump <| always <| isOddTr <| v - 1
За что был наказан потерянным часом на отладку. Кто может предположить, в чём кроется засада? :) Для справки: always.
Ладно, возвращаемся к примерам. Как написать трамплин-версию isSumEven? В принципе, можно как-то так:
isSumEvenTr : Int -> Int -> Trampoline Bool
isSumEvenTr a b =
done <| (evaluate <| isEvenTr a) == (evaluate <| isEvenTr b)
Конкретно для этого синтетического примера, наверно, такой вариант особо ничем не плох. Но всё же: можно ли обойтись только одним evaluate? Очевидно, что можно, если получится каким-то образом "попасть внутрь" типа Trampoline a, чтобы достать значение a или, хотя бы, как-то его преобразовать. Но вот незадача: этот тип не является функтором или монадой, никаких соответствующих комбинаторов для него нет, да и вообще это всё страшные слова, и такой мерзости у нас в эльме не водится! Следовательно, единственный вариант - это честно интерпретировать Trampoline a через evaluate. Или нет?
На самом деле, есть способ "состыковать" несколько Trampoline-ов, чтобы выполнить их в одном цикле-эвалюаторе: опять же, CPS. Но для этого нам опять нужно отрефакторить функции, на этот раз в continuation passing style:
isEvenTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isEvenTrK x k =
case abs x of
0 -> k True
v -> jump <| \() -> isOddTrK (v - 1) k
isOddTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isOddTrK x k =
case abs x of
0 -> k False
v -> jump <| \() -> isEvenTrK (v - 1) k
isSumEvenTrK : Int -> Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isSumEvenTrK a b k =
isEvenTrK a <|
\resultA ->
jump <| \() -> isEvenTrK b <|
\resultB ->
k <| resultA == resultB
Главное изменение: функции теперь не возвращают результаты напрямую (логически, они уже ничего не должны возвращать), вместо этого они принимают дополнительные параметр: "продолжение", которому этот результат передаётся. Теперь в isEvenTrK появилась возможность состыковать две "затрамплиненные" функции внутри продолжения, при этом сохранив тип возвращаемого значения Trampoline Bool, который уже скармливается единственному evaluate:
> evaluate <| isSumEvenTrK 100000 1 done
False : Bool
> evaluate <| isSumEvenTrK 100000 100000 done
True : Bool
В принципе, этот трюк может пригодится, например, когда завёрнутым в трамплин типом является тот же Result - и надо уметь в процессе работы запускать разные ветки вычислений в зависимости от того, успешно ли отработал один из рекурсивных вызовов, или нет.
Ну, в целом, как-то так. Далее полагается, чтобы я написал какие-то выводы или подытоги, но какие тут могут быть выводы? Сложно, запутанно. Но это и есть та самая "отложенная сложность", про которую я говорил в начале поста. Был бы в вашем джаваскрипте изначально родной TCO, я бы не писал этот текст, а вместо этого сделал бы что-нибудь полезное.