пятница, 21 августа 2015 г.

Про tail call elimination или почему с диалектами Haskell нужно быть осторожным

В последнее время развелось много различных диалектов 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, но не работает на вашем диалекте Хаскелля, падая на больших входных данных.

воскресенье, 16 августа 2015 г.

Должен ли программист знать математику?

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

Почему вдруг именно сейчас сформировалось моё мнение? Дело в том, что мне недавно исполнилось 27 лет, а в среде программистов 27 лет (плюс-минус два года) – это такой возраст, когда многие достигают некоторого "потолка" в своей карьере. То есть среднестатистический программист к этому возрасту уже прошёл ступени от начинающего разработчика до опытного разработчика (тимлид/сеньор/архитектор). И тут у них возникает вопрос – что делать дальше? Существует два пути: либо продолжить карьерный рост, став менеджером/начальником/директором, или остаться программистом и пытаться расти дальше профессионально.

И вот тут-то начинает решать знание математики. Программисты, которые не знают математику, расти дальше профессионально не могут. Ну просто они достигли той грани, до которой ещё можно было расти исключительно засчёт экстенсивного расширения своих навыков, увеличивая количество баззвордов в своём резюме, но подняться выше которой нельзя без определённых фундаментальных математических знаний. Например, после 5 лет написания веб-сайтов ты вряд ли сможешь написать свою распределённую отказоустойчивую базу данных, если у тебя нету знаний хотя бы основ матанализа, сколько бы баззвордов ты не знал. Таким образом, тебе рано или поздно надоедает клепать однообразные CRUD'ы, а решать более сложные задачи ты не способен, поэтому ты выбираешь путь менеджера.

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

Что касается меня, то я определённо не собираюсь становиться менеджером. Некоторая математическая база у меня есть, которая сильно пригодилась в моей текущей работе. А дальше посмотрим. Математическая база – это, конечно хорошо, но хочется копать вглубь и развиваться в какой-то конкретной области. Возможно, это будет связано с функциональным программированием.