В последнее время развелось много различных диалектов Haskell: PureScript, Frege, GHCJS, Elm, Haste и т.д.
В этой статье мы рассмотрим, насколько ли хорошо эти диалекты пригодны для функционального программирования. Анализ мы будем проводить с точки зрения наличия в компиляторах этих языков одной важной для функционального программирования оптимизации – устранения хвостовых вызовов (tail call elimination, далее TCE).
Мотивация
TCE – это оптимизация компилятора, которая позволяет избежать "раздувания" стека, когда функции вызывают друг друга и эти вызовы являются хвостовыми. Типичный пример таких хвостовых вызов – это взаимная рекурсия:
isOdd x = if (x == 0) then False else isEven (x - 1)
isEven x = if (x == 0) then True else isOdd (x - 1)
Как видно из кода программы, функция isOdd вызывает функцию isEven в хвостовой позиции, а значит стек-фрейм функции isOdd уже больше не понадобится и он может быть переиспользован для функции isEven. GHC такой код успешно оптимизирует, и функция isOdd может быть вызвана со сколько угодно большим числом.
Приведённый выше пример сильно надуман, но это было сделано исключительно для простоты демонстрации проблемы. На самом деле, хвостовые вызовы в функциональном программировании встречаются чрезвычайно часто (значительно чаще, чем в императивных программах). Например, некоторые конечные автоматы очень удобно реализовывать через взаимно рекурсивные хвостовые функции. Скажем, программу, определяющую является ли список последовательностью чередующихся двух других списков, можно красиво реализовать через конечный автомат:
match :: Eq a => [a] -> [a] -> [a] -> Bool
match list list1 list2 = match1 list where
match1 [] = True
match1 list | list1 `isPrefixOf` list = match2 $ drop (length list1) list
match1 _ = False
match2 [] = True
match2 list | list2 `isPrefixOf` list = match1 $ drop (length list2) list
match2 _ = False
Например, если вызвать match с аргументами [1,1,2,1,1,2] [1,1] [2], то он вернёт True.
Ещё один пример – свёртка списка функций в одну функцию:
composeAll :: [Int -> Int] -> (Int -> Int)
composeAll [] = id
composeAll (x:xs) = composeAll xs . x
Этот пример сворачивает список функций [f1, f2, ... , fn] в одну функцию fn ∘ ... ∘ f2 ∘ f1, т.е. каждая функция вызывает следующую функцию в хвостовой позиции. Для того чтобы конечная функция не упала с переполнением стека на большом списке, компилятор должен поддерживать TCE.
Далее мы рассмотрим, насколько хорошо поддерживают TCE различные диалекты Хаскелля.
PureScript
PureScript – это строгий диалект Хаскелля, транслирующий в JavaScript. Установку PureScript я выполнил по
этой инструкции и реализовал вышеописанные примеры.
Пример с isOdd и isEven выглядит следующим образом:
import Prelude
import Data.List
import Control.Monad.Eff.Console
isOdd n = if n == 0 then false else isEven $ n - 1
isEven n = if n == 0 then true else isOdd $ n - 1
main = isOdd 1000000 # show # log
Функции isOdd и isEven транслировались вот в такой JS-код:
var isOdd = function (n) {
var _0 = n === 0;
if (_0) {
return false;
};
if (!_0) {
return isEven(n - 1);
};
throw new Error("Failed pattern match: " + [ _0.constructor.name ]);
};
var isEven = function (n) {
var _1 = n === 0;
if (_1) {
return true;
};
if (!_1) {
return isOdd(n - 1);
};
throw new Error("Failed pattern match: " + [ _1.constructor.name ]);
};
Как видно, никакой TCE здесь не пахнет. Запуск этой программы через Node.js (который не поддерживает TCE) падает с ошибкой переполнения стека:
var isEven = function (n) {
^
RangeError: Maximum call stack size exceeded
at isEven (D:\temp\purescript\output\Main\index.js:16:23)
at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
at isEven (D:\temp\purescript\output\Main\index.js:22:16)
at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
at isEven (D:\temp\purescript\output\Main\index.js:22:16)
at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
at isEven (D:\temp\purescript\output\Main\index.js:22:16)
at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
at isEven (D:\temp\purescript\output\Main\index.js:22:16)
at isOdd (D:\temp\purescript\output\Main\index.js:12:16)
* ERROR: Subcommand terminated with error code 1
Второй пример я реализовывать не стал, но зато реализовал третий:
composeAll :: List (Int -> Int) -> (Int -> Int)
composeAll Nil = id
composeAll (Cons x xs) = composeAll xs <<< x
fs :: List (Int -> Int)
fs = replicate 100000 (+1)
main = 100 # composeAll fs # show # log
По идее, этот код должен прибавить единицу к числу 100000 раз, но он валится с ошибкой переполнения стека.
Frege
С
Хаскеллем под JVM всё обстоит почти так же плохо, как и с PureScript. JVM, как и Node.js, не поддерживают TCE, а значит TCE ложится на плечи транслятора в Java. Но Frege выполнил эту задачу лишь частично. Из трех примеров без StackOverflowError выполнился только первый. Второй и третий упали приблизительно с такой ошибкой:
java.lang.StackOverflowError
at frege.runtime.Fun1$1.eval(Fun1.java:63)
at frege.runtime.Delayed.call(Delayed.java:198)
at frege.runtime.Delayed.forced(Delayed.java:257)
at frege.prelude.PreludeMonad$?$_bullet?eb83462e.eval(PreludeMonad.java:4921)
at frege.prelude.PreludeMonad$?$_bullet?eb83462e.eval(PreludeMonad.java:4915)
at frege.runtime.Fun2$1.eval(Fun2.java:58)
at frege.runtime.Fun1$1.eval(Fun1.java:63)
at frege.runtime.Delayed.call(Delayed.java:198)
at frege.runtime.Delayed.forced(Delayed.java:257)
at frege.prelude.PreludeMonad$?$_bullet?eb83462e.eval(PreludeMonad.java:4921)
at frege.prelude.PreludeMonad$?$_bullet?eb83462e.eval(PreludeMonad.java:4915)
at frege.runtime.Fun2$1.eval(Fun2.java:58)
at frege.runtime.Fun1$1.eval(Fun1.java:63)
at frege.runtime.Delayed.call(Delayed.java:198)
...
Elm и Haste
Elm и
Haste – ещё два диалекта Haskell, транслирующиеся в JS (первый строгий, второй ленивый). Elm упал с переполнением стека на примере с isOdd и isEven. Haste упал на втором примере со списком из 500 тыс. значений.
GHCJS
Последняя надежда осталась на
GHCJS – транслятор Haskell в JS. Особенность это транслятора заключается в том, что он полностью совместим с Хаскеллем, в отличие от всех вышеперечисленных диалектов. Также он поддерживает практически все стандартные модули Haskell. Из минусов этого компилятора – большой размер сгенерированных js-файлов, в которых невозможно разобраться, и медленный старт, а также сложность установки GHCJS (я так и не смог установить GHCJS под Windows, пришлось тестировать на Linux).
Все три примера успешно скомпилировались через GHCJS "как есть". Сгенерированный код я запускал через Node.js, и во всех трёх случаях код отрабатывал без ошибок, какие бы большие числа/списка я не подсовывал.
Итог
Как видно, писать функциональные программы на диалектах Хаскелля нужно с осторожностью, так как в любой момент есть риск напороться на переполнение стека. С первого взгляда, это может показаться незначительной проблемой, но на самом деле это не так. Когда ваша программа станет достаточно большой, таких мест в ней может оказаться достаточно много. И не удивляйтесь потом, почему ваша программа работает на GHC, но не работает на вашем диалекте Хаскелля, падая на больших входных данных.
