Среди 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-подобного синтаксиса и на использование генераторов для упрощения синтаксиса комбинаторов.
UPDATE само-собой парсинг JSON уже давно решенная задача и конечно готовая и протестированная функция на C будет работать лучше. Статья использует эту задачу как пример для объяснения функционального подхода. Так же не пропагандируется использование именно такого кода в продакшене, каждый может почерпнуть себе какие-то идеи, которые могут упростить код и жизнь.
Полный код находится на github.
Функциональный стиль
Как программист справляется с огромной сложностью программ? Он берет простые блоки и строит из них более сложные, из которых строятся еще более сложные блоки и в конце-концов программа. По крайней мере так было после появляния первых языков с подпрограммами.
В основе процедурного стиля лежит описание процедур, которые вызывают другие процедуры вместе меняющие какие-то общие данные. Объекто-ориентированный стиль добавляет возможность описывать структуры данных, составленные из других структур данных. Функциональный же стиль использует композицию (соединение) функций.
Чем же отличается композиция функций от композиции процедур и объектов? Основа функционального подхода — чистота функций, это значит, что результат работы функций зависит только от входных параметров. Если функции чисты, то гораздо проще предсказать результат их композиции и даже создать готовые функции для преобразования других функций.
Именно функции принимающие и/или возвращающие в качестве результата другие функции называются функциями высшего порядка и представляют тему этой статьи.
Какую задачу будем решать?
Для примера возьмем задачу, которую не очень просто решить целиком и посмотрим как функциональный подход поможет нам эту задачу упростить.
Для примера попробуем сделать парсер формата 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, а демонстрация того, как написание маленьких простых (и функционально чистых) функций, а так же простых способов их комбинирования позволяет строить сложные функции простым способом.
А в простом и понятном коде и ошибок меньше. Не бойтесь функционального подхода.
