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

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

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

$jNumber = _do(function() {
    $number  = yield literal('-')->orElse( literal('+') )->orElse( just('') );
    $number .= yield takeOf('[0-9]')->onlyIf( notEmpty() );
    if ( yield literal('.')->orElse( just(false) ) ) {
        $number .= '.'. yield takeOf('[0-9]');
    }
    return +$number;
});

Кроме собственно функционального подхода можно обратить внимание на использование классов для создания 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

Что более интересно для нас, данные можно не только получать из генератора, но и передавать в него через yield, и даже с 7 версии получить результат генератора через getReturn:

function suspendable() {
    $first = yield "first";
    $second = yield "second";
    return $first.$second;
}
$gen = suspendable();
while ($gen->valid()) {
    $current = $gen->current();
    print $current.',';
    $gen->send($current.'!');
}
print $gen->getReturn();
# -> first,second,first!second!

Это можно использовать, чтобы спрятать вызовы flatMap от программиста.

flatMap используя комбинаторы

function _do(Closure $gen, $scope = null) {
    $step = function ($body) use (&$step) {
        if (! $body->valid()) {
            $result = $body->getReturn();
            return is_null($result) ? none() : just($result);
        } else {
            return $body->current()->flatMap(
                function($x) use (&$step, $body) {
                    $body->send($x);
                    return $step($body);
                });
        }
    };
    $gen = $gen->bindTo($scope);
    return parser(function($text) use ($step,$gen) {
        return $step($gen())($text);
    });
}

Эта функция берет каждый yield в генераторе (который содержит парсер, результат которого мы хотим получить) и комбинирует его с оставшимся фрагментом кода (в виде рекурсивной функции step) через flatMap.

То же самое без рекурсии и функции flatMap можно было бы записать так:

function _do(Closure $gen, $scope = null) {
    $gen = $gen->bindTo($scope); # ради использования $this в функции
    return parser(function($text) use ($gen) {
        $body = gen();
        while ($body->valid()) {
            $next = $body->current();
            $result = $next($text);
            if ($result === Parser::FAILED) {
                return Parser::FAILED;
            }
            list($x,$text) = $result;
            $body->send($x);
        }
        return $body->getReturn();
    });
}

Но первая запись более интересна тем, что она не привязана особо к парсерам, от них там только функции flatMap, just и none (да и то, можно было бы переписать just чтобы обрабатывать null особым образом и обойтись без none).

Объекты, которые можно комбинировать с помощью двух методов flatMap и just называют монады (это немного упрощенное определение) и этот же код можно использовать, чтобы писать комбинаторы для промисов (Promise), опциональных значений (Maybe,Option) и многих других.

Но ради чего же мы писали эту не самую простую функцию? Для того, чтобы дальнейшее использование flatMap было гораздо легче. Сравним один и тот же код с чистым flatMap:

test(
    take(1)->flatMap(function($x) {
        return take(2)->flatMap(function($y) use ($x) {
            return just("$x~$y");
        });
    }),
    '1234',
    ['1~23','4']
);

и тот же самый код, но написанный через _do:

test(
    _do(function() {
        $x = yield take(1);
        $y = yield take(2);
        return "$x~$y";
    }),
    '1234',
    ['1~23','4']
);

Результирующий парсер делает то же самое тем же способом, но читать и писать такой код гораздо проще!

Строим более сложные парсеры и комбинаторы

Теперь, используя эту нотацию мы можем написать еще несколько полезных парсеров:

function takeWhile(callable $predicate): Parser {
    return _do(function() use ($predicate) {
        $c = yield take(1)->onlyIf($predicate)->orElse(just(''));
        if ($c !== '') {
            $rest = yield takeWhile($predicate);
            return $c.$rest;
        } else {
            return '';
        }
    });
}
function takeOf(string $pattern): Parser {
    return takeWhile(function($c) use ($pattern) {
        return preg_match("/^$pattern$/", $c);
    });
}
test(takeOf('[0-9]'), '123abc', ['123','abc'   ]);
test(takeOf('[a-z]'), '123abc', [   '','123abc']);

И полезные методы класса Parser для повторяющихся элементов:

function repeated(): Parser {
    $atLeastOne = _do(function() {
        $first = yield $this;
        $rest = yield $this->repeated();
        return array_merge([$first],$rest);
    },$this);
    return $atLeastOne->orElse(just([]));
}
function separatedBy(Parser $separator): Parser {
    $self = $this;
    $atLeastOne = _do(function() use ($separator) {
        $first = yield $this;
        $rest = yield $this->prefixedWith($separator)->repeated();
        return array_merge([$first], $rest);
    },$this);
    return $atLeastOne->orElse(just([]));
}

JSON

Каждый из написанных нами парсеров и комбинаторов в отдельности просты (ну может кроме flatMap и _do, но их всего два и они очень универсальны), но используя их теперь нам не составит труда написать парсер JSON.

jNumber = ('-'|'+'|'') [0-9]+ (.[0-9]+)?

$jNumber = _do(function() {
    $number  = yield literal('-')->orElse(literal('+'))->orElse(just(''));
    $number .= yield takeOf('[0-9]');
    if (yield literal('.')->orElse(just(false))) {
        $number .= '.'. yield takeOf('[0-9]');
    }
    if ($number !== '')
        return +$number;
});

Код вполне самодокументирующийся, читать и искать в нем ошибки довольно просто.

jBool = true | false

$jBool = literal('true')->orElse(literal('false'))->flatMap(function($value) {
    return just($value === 'true');
});

jString = '"' [^"]* '"'

$jString = _do(function() {
    yield literal('"');
    $value = yield takeOf('[^"]');
    yield literal('"');
    return $value;
});

jList = '[' (jValue (, jValue)*)? ']'

$jList = _do(function() use (&$jValue) {
    yield literal('[');
    $items = yield $jValue->separatedBy(literal(','));
    yield literal(']');
    return $items;
});

jObject = '{' (pair (, pair)*)? '}'

$jObject = _do(function() use (&$jValue) {
    yield literal('{');

    $result = [];
    $pair = _do(function() use (&$jValue,&$result) {
        $key = yield takeOf('\w');
        yield literal(':');
        $value = yield $jValue;
        $result[$key] = $value;
        return true;
    });
    yield $pair->separatedBy(literal(','));
    yield literal('}');

    return $result;
});

jValue = jNull | jBool | jNumber | jString | jList | jObject

$jValue = $jNull->orElse($jBool)->orElse($jNumber)->orElse($jString)->orElse($jList)->orElse($jObject);

Вот и готов парсер JSON jValue! Причем выглядит не так уж непонятно, как казалось вначале. Есть некоторые замечания к производительности, но они решаются заменой способа разделения строки (например вместо string => [x, string] можно использовать [string,index] => [x,string,index] и избежать многократного разбиения строки). Причем для изменения такого рода достаточно переписать just, take и flatMap, весь остальной код, построенный на их основе останется без изменений!

Заключение

Моей целью было конечно не написание очередного парсера JSON, а демонстрация того, как написание маленьких простых (и функционально чистых) функций, а так же простых способов их комбинирования позволяет строить сложные функции простым способом.

А в простом и понятном коде и ошибок меньше.

Не бойтесь функционального подода :)

Автор: atamur

Источник