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

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

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

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

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

Полный код находится на github.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом мы скомбинировали take(1) , take(2) и just("$x

$y") и получили довольно сложный парсер, который сначала парсит один символ, за ним еще два и возвращает их в виде $x

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

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

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

DO нотация

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

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

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

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

Давайте сделаем небольшое отступление и рассмотрим что такое генераторы. В PHP 5.5.0 и выше появилась возможность описать функцию:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

А в простом и понятном коде и ошибок меньше. Не бойтесь функционального подхода.