В этой статье мы рассмотрим, насколько ли хорошо эти диалекты пригодны для функционального программирования. Анализ мы будем проводить с точки зрения наличия в компиляторах этих языков одной важной для функционального программирования оптимизации – устранения хвостовых вызовов (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)
Приведённый выше пример сильно надуман, но это было сделано исключительно для простоты демонстрации проблемы. На самом деле, хвостовые вызовы в функциональном программировании встречаются чрезвычайно часто (значительно чаще, чем в императивных программах). Например, некоторые конечные автоматы очень удобно реализовывать через взаимно рекурсивные хвостовые функции. Скажем, программу, определяющую является ли список последовательностью чередующихся двух других списков, можно красиво реализовать через конечный автомат:
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
Ещё один пример – свёртка списка функций в одну функцию:
composeAll :: [Int -> Int] -> (Int -> Int)
composeAll [] = id
composeAll (x:xs) = composeAll xs . x
Далее мы рассмотрим, насколько хорошо поддерживают 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
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 ]);
};
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
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, и во всех трёх случаях код отрабатывал без ошибок, какие бы большие числа/списка я не подсовывал.
Комментариев нет:
Отправить комментарий