Среди 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', []);Мы уже описали простейшие парсеры 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 от программиста.
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([]));
}Каждый из написанных нами парсеров и комбинаторов в отдельности просты
(ну может кроме flatMap и _do, но их всего два и они очень универсальны),
но используя их теперь нам не составит труда написать парсер JSON.
$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 = literal('true')->orElse(literal('false'))->flatMap(function($value) {
return just($value === 'true');
});$jString = _do(function() {
yield literal('"');
$value = yield takeOf('[^"]');
yield literal('"');
return $value;
});$jList = _do(function() use (&$jValue) {
yield literal('[');
$items = yield $jValue->separatedBy(literal(','));
yield literal(']');
return $items;
});$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->orElse($jBool)->orElse($jNumber)->orElse($jString)->orElse($jList)->orElse($jObject);Вот и готов парсер JSON jValue! Причем выглядит не так уж непонятно, как казалось вначале.
Есть некоторые замечания к производительности, но они решаются заменой способа разделения строки
(например вместо string => [x, string] можно использовать [string,index] => [x,string,index] и избежать
многократного разбиения строки).
Причем для изменения такого рода достаточно переписать just, take и flatMap, весь
остальной код, построенный на их основе останется без изменений!
Моей целью было конечно не написание очередного парсера JSON, а демонстрация того, как написание маленьких простых (и функционально чистых) функций, а так же простых способов их комбинирования позволяет строить сложные функции простым способом.
А в простом и понятном коде и ошибок меньше.
Не бойтесь функционального подода :)