Функции высших порядков и монады для PHP`шников

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

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

Кроме собственно функционального подхода можно обратить внимание на использование классов для создания DSL-подобного синтаксиса и на использование генераторов для упрощения синтаксиса комбинаторов.

Функциональный стиль

Как программист справляется с огромной сложностью программ? Он берет простые блоки и строит из них более сложные, из которых строятся еще более сложные блоки и в конце-концов программа. По крайней мере так было после появляния первых языков с подпрограммами.

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

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

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

Какую задачу будем решать?

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

Для примера попробуем сделать парсер формата JSON, который из строки JSON получит соответствующий PHP объект: число, строку, список или ассоциированный список (со всеми возможными вложенными значениями конечно).

Что такое парсер?

Начнем с самых простых элементов: мы пишем парсер, что же это такое? Парсер это функция, которая берет строку и в случае успеха возвращает пару значений: результат разбора и остаток строки (если разбираемое значение занимало не всю строку) или пустой набор, если разобрать строку не удалось:

Parser: string => [x,string] | []

Например если у нас есть функция-парсер number то мы могли бы написать такие тесты:

assert(number('123;') === [123,';']);
assert(number('none') === []);

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

class Parser {
    const FAILED = [];
    private $parse; 
    function __construct(callable $parse) {
        $this->parse = $parse;
    }
    function __invoke(string $s): array {
        return ($this->parse)($s);
    }
}

Но будем помнить, что Parser это не более чем функция string => array.

Для удобства так же введем функцию parser, которую будем использовать вместо вызова конструктора new Parser для краткости:

function parser($f, $scope = null) { 
    return new Parser($f->bindTo($scope)); 
}

Простейшие парсеры

Итак, мы разобрались что такое парсеры, но ни одного так и не написали, давайте это исправим. Вот пример парсера, который всегда возвращает 1, независимо от исходной строки:

$alwaysOne = parser(function($s) {
    return [1, $s];
});
assert($alwaysOne('123') === [1, '123']);

Полезность этой функции не очевидна, давайте сделаем ее более общей и объявим функцию, которая позволит создавать подобный парсер для любого значения:

function just($x): Parser {
    return parser(function($s) use ($x) {
        return [ $x, $s ];
    });
}

Пока все просто, но все еще не очень полезно, ведь мы хотим парсить строку, а не возвращать всегда одно и то же. Давайте сделаем парсер, который возвращает первые несколько символов входной строки:

function take(int $n): Parser {
    return parser(function($s) use ($n) {
        return strlen($s) < $n ? Parser::FAILED : [ substr($s, 0, $n), substr($s, $n) ];
    });
}

test(take(2), 'abc', ['ab','c']);
test(take(4), 'abc', Parser::FAILED);

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

function none(): Parser {
    return parser(function($s) {
        return Parser::FAILED;
    });
}

Он нам еще пригодится.

Вот и все парсеры, которые нам нужны. Этого достаточно, чтобы разобрать JSON. Не верите? Осталось придумать способ собирать эти кирпичики в более сложные блоки.

Собираем кирпичики вместе

Поскольку мы решили заняться функциональным программированием, то для комбинирования функций парсеров в более сложные парсеры логично использовать функции!

Например если у нас есть парсеры first и second и мы хотим применить к строке любой из них мы можем определить комбинатор парсеров -- функцию, создающую новый парсер на основе существующих:

function oneOf(Parser $first, Parser $second): Parser {
    return parser(function($s) use ($first,$second) {
        $result = $first($s);
        if ($result === Parser::FAILED) {
            $result = $second($s);
        }
        return $result;
    });
}
test(oneOf(none(),just(1)), '123', [1,'123']);

Но, как уже упоминалось выше, такой синтаксис может быстро стать нечитаемым (например oneOf($a,oneOf($b,oneOf($c,$d)))), поэтому мы перепишем эту (и все следующие) функции как методы класса Parser:

function orElse(Parser $alternative): Parser {
    return parser(function($s) use ($alternative) {
        $result = $this($s);
        if ($result === Parser::FAILED) {
            $result = $alternative($s);
        }
        return $result;
    }, $this); // <- вот зачем в функции parser был bindTo: чтобы использовать $this в функции
}
test(none()->orElse(just(1)), '123', [1,'123']);

Так уже лучше, можно писать $a->orElse($b)->orElse($c)->orElse($d) вместо того, что было выше.

И еще одна, не такая простая, но зато гораздо более мощная функция:

function flatMap(callable $f): Parser {
    return parser(function($s) use ($f) {
        $result = $this($s);
        if ($result != Parser::FAILED) {
            list ($x, $rest) = $result;
            $next = $f($x);
            $result = $next($rest);
        }
        return $result;
    }, $this);
}

Давайте разберемся с ней подробнее. Она принимает функцию f: x => Parser, которая принимает результат парсинга нашего существующего парсера и возвращает на его основе новый парсер, который продолжает разбор строки с того места, где остановился наш предыдущий парсер.

Например:

test(take(1), '1234', ['1','234']);
test(take(2), '234',  ['23', '4']);
test(
    take(1)->flatMap(function($x) { # x -- результат парсинга take(1)
        return take(2)->flatMap(function($y) use ($x) { # y -- результат парсинга take(2) 
            return just("$x~$y"); # -- финальный результат
        });
    }),
    '1234',
    ['1~23','4']
);

Таким образом мы скомбинировали take(1), take(2) и just("$x~$y") и получили довольно сложный парсер, который сначала парсит один символ, за ним еще два и возвращает их в виде $x~$y.

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

Эта функция позволит нам описать несколько других полезных комбинаторов:

function onlyIf(callable $predicate): Parser {
    return $this->flatMap(function($x) use ($predicate) {
        return $predicate($x) ? just($x) : none();
    });
}

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

function literal(string $value): Parser {
    return take(strlen($value))->onlyIf(function($actual) use ($value) {
        return $actual === $value;
    });
}
test(literal('test'), 'test1', ['test','1']);
test(literal('test'), 'some1', []);

DO нотация

Мы уже описали простейшие парсеры take, just и none, способы их комбинации (orElse,flatMap,onlyIf) и даже описали с их помощью парсер литералов literal.

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

В связи с этим подсмотрим как решают эту проблему другие языки. Так в языках Haskell и Scala есть весьма удобный синтаксис для работы с подобными вещами (они даже имеют свое название -- монады), называется он (в Haskell) DO-нотация.

Что по-сути делает flatMap? Он позволяет описать что делать с результатом парсинга не совершая собственно парсинга. Т.е. процедура как-бы приостанавливается до момента получения промежуточного результата. Для реализации подобного эффекта можно использовать новый для PHP синтаксис -- генераторы.

Генераторы

Давайте сделаем небольшое отступление и рассмотрим что такое генераторы.

В PHP 5.5.0 и выше появилась возможность описать функцию:

function generator() {
    yield 1;
    yield 2;
    yield 3;
}
foreach (generator() as $i) print $i; # -> 123