Не все тестовые задания удостаиваются внимания на Хабре. Почему — примерно, понятно. Однако бывают исключения. Так, некоторое время тому назад одно, в общем-то, ничем не примечательное тестовое задание на Хабре породило аж целых две статьи про него.

Первая из них — "История одного фееричного провала тестового задания на C#" — была написана в жанре пространной жалобы соискателя на невежливый ответ (дословно: "отвратительно, халтурно") нанимателя на решение тестового задания, которое автору дали при попытке устройства на работу. В принципе, у меня эта статья особого интереса не вызвала: там было вполне рабочее решение — но без всякого блеска и с явными следами торопливости (похоже, именно они не понравились нанимателю) — не слишком интересной задачи — сделать класс, разбирающий строку расписания в cron-подобном формате и реализующий методы поиска в этом расписании.

Однако через некоторое время на Хабре появилась вторая посвященная этому тестовому заданию статья. Его решение в той статье было с монадами и goto, и оно произвело на меня сильное впечатление. Первая мысль после прочтения у меня была "Круто!" (или, как выразился автор первого же комментария "Шикарно"). В частности, одна из примечательных особенностей решения — использование для разбора строки не своего "велосипеда", а хорошей сторонней библиотеки.

Тем не менее, на второй взгляд все оказалось не так хорошо, на как на первый. Та часть решения, которая представляет собой программу-разборщик строки расписания, могла быть существенно улучшена, с сокращением объема и улучшением понятности, если для этого полнее использовать методы той же самой библиотеки для построения разборщиков (ну, и не забывать, что мы пишем на языке C#). Если вам интересно, как, почему и что может быть сделано — добро пожаловать под кат.

Введение

Для начала, думаю, что тут требуется немного пояснений для тех, кто не читал или уже не помнит обсуждаемую статью. Если вкратце, то решение там устроено следующим образом. Первая его часть создает объект-разборщик (parser), который потом, в конструкторе класса расписания, преобразует строку расписания во внутреннее его представление. При этом автор не стал изобретать свой велосипед — разборщик он создает путем комбинирования объектов — классов из специально предназначенной для такого использования сторонней библиотеки Pidgin. Именно этой части решения будет посвящена эта моя статья.

Вторая часть решения — это реализация набора методов класса расписания для поисков ближайших разрешенных расписанием моментов времени. Она тоже примечательна — представляет собой высокооптимизированный код, сделанный с использованием метапрограммирования (часто встречающегося в C++, а теперь доступного и в C#), работающий с внутренним представлением. Но этой части решения я в данной статье касаться не буду.

О программе построения разборщика и используемой библиотеке

Код программы построения разборщика у автора второй статьи получился, как я, к сожалению для себя выяснил, не очень простым и не слишком наглядным. Лично я поймал себя на том, что, хотя в целом мне понятно, что именно делает эта программа, но когда я пытался разобраться, что именно происходит в данном конкретном месте, смысл происходящего ускользал. Это было похоже на то, как будто я читаю текст на не слишком хорошо знакомом языке. Конкретно те методы, код которых вызвал затруднения, написаны с использованием языка запросов LINQ. Нельзя сказать, что язык этот широко распространен среди программистов на C# — автор недавней статьи на Habr вон, вообще отнес его к бесполезным (на первый взгляд) фичам C# — но мне язык этот вполне знаком, а как человеку, много работавшему с SQL — даже несколько привычен. Затруднение вызвало другое обстоятельство — странный контекст его использования. Обычно язык запросов LINQ (как и его отдаленный аналог SQL) применяется для работы с набором однородных значений, для представления которых в C# используется интерфейс IEnumerable и его наследники (или их типизированные обобщенные модификации). Но в рассматриваемой программе работа на языке запросов LINQ идет не с IEnumerable, а с объектами из библиотеки Pidgin, которые IEnumerable не реализуют.

Пояснения автора в тексте статьи понять, как именно реализовано его решение, помогают не слишком: автор постоянно что-то говорит на тему что он делает, не особо поясняя, как он это делает. И, к тому же, он поясняет свое решение так, будто оно написано на языке функционального программирования, вроде Haskell — тогда как решение написано на C#.

Немного о самой библиотеке (она называется Pidgin). Библиотека дает возможность создать программу-разборщик AKA парсер (parser) путем комбинирования определенных в библиотеке объектов — элементарных парсеров (символов, строк, чисел), с преобразование их при необходмости в значения другого типа, а также — ранее созданных парсеров-комбинаций. Основой программы разборки являются объекты обобщенного класса c двумя параметрами-типами Parser<TToken,T> (далее парсером я буду называть объект именно этого типа), где TToken — тип элемента входной последовательности (в нашем случае — char), а T — тип возвращаемого результата. Для этого класса определены многочисленные методы, преобразующие тип значения, создающие новые парсеры путем комбинирования с другими парсерами с возможностью преобразования результатов всех комбинируемых парсеров в нужный тип. Кроме того, как уже сказано, библиотека содержит базовые элементарные парсеры — для отдельных символов, строк и т.д., в виде методов дополнительных статических классов. А вот интерфейс IEnumerable, который ожидаешь при работе с LINQ, класс парсера не реализует.

В конце концов, путем комбинирования базовых и промежуточных комбинированных парсеров получается полный парсер, пригодный для разбора строки нужного формата и преобразования ее в экземпляр выходного типа. Затем для разбора строки для созданного полного парсера вызывается один из определенных для него методов: Parse или ParseOrThrow, который и выполняет работу по разбору переданной в него строки.

Фактически, библиотека, может, и опирается на функциональную парадигму, в рамках которой автор поясняет свое решение в статье, но эта функциональная парадигма нигде особо из нее не торчит. И для понимания того, как работать с библиотекой, знать никаких там монад не требуется — разве что, чтобы понять объяснения автора статьи. И вообще, ФП — не единственная парадигма, которую можно привлечь для описания этой библиотеки. Можно, например, посмотреть на эту библиотеку со стороны старого доброго ООП (кстати, для C# парадигмы куда более органичной), и сказать, что библиотека Pidgin реализует "паттерн проектирования Компоновщик" (Composite). Но пользоваться этой библиотекой можно вообще без каких-либо знаний как о монадах и вообще об ФП, так и о паттернах проектирования ООП.

Спрямляем путь

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

  from V1 in O1
  from V2 in O2
  select EXPRESSION(V1,V2)

однозначно преобразуется в запись на обычном C# (в формат вызова методов) как

 O1.SelectMany(_=>O2, (V1,V2)=>EXPRESSION(V1,V2))

Лямбда-функция вида V1=>O2 вместо просто O2 в первом параметре появилась тут за счет того, что на месте объекта O2 в запросе LINQ может стоять выражение, зависящее от V1. Но в нашем случае это не так, поэтому параметр V1 просто игнорируется (заменяется символом подчеркивания).

Чтобы увидеть, как выглядит преобразование для рассматриваемого решения, возьмем для примера get-метод свойства ParserHelper.IntervalParser, как самый простой, содержащий эта конструкцию:

        public static Parser<char, (int begin, int? end)> IntervalParser { get; } =
            from begin in NumberParser
            from end in Char('-').Then(NumberParser).Optional()
                .Map(MapMaybeStruct)
            select (begin, end);

Переписываем конструкцию на языке запросов LINQ в форму с вызовом методов буквально:

        public static Parser<char, (int begin, int? end)> IntervalParser { get; } =
            NumberParser.SelectMany(_ => Char('-').Then(NumberParser).Optional().Map(MapMaybeStruct), (begin, end) => (begin, end));

И пробуем скомпилировать — компилируется. А подсказка в Visual Studio IDE подсказывает, почему: использованный здесь метод SelectMany — это метод класса Parser<,>. То есть, оказывается, магия языка запросов LINQ работает просто потому, что у класса Parser<,> оказался среди используемых для комбинирования парсеров методов в наличии метод SelectMany с подходящей сигнатурой.

Переписываем таким же образом остальные методы: там предложений from больше, из них получаются более длинные и менее наглядные цепочки вызовов SelectMany, но в целом — никаких сюрпризов. Итак, загадка языка запросов LINQ разгадана. Но вот программа от этого проще не стала, скорее — наоборот. Этот промежуточный результат можно увидеть здесь.

Чтобы упростить далее, смотрим, какие ещё методы для комбинации парсеров приготовила нам библиотека Pidgin. Во-первых, находим в ней вариант метода Then (у него много вариантов, и один из них, простейший, автор оригинального решения даже использовал), напоминающий по форме SelectMany, но принимающий в качестве первого параметра не делегат с ненужным нам входным параметром, возвращающий нужное нам значение, а само это значение. Заменяем для начала вызовы SelectMany на этот Then (этот промежуточный результат — здесь ). Решение по сравнению с предыдущим вариантом стало прямее и короче, но совсем чуть-чуть. Нужно улучшать код дальше.

Однако, прежде чем идти дальше по пути спрямления решения с избавлением от цепочек вызовов Then, сделаем несколько мелких улучшений. Во-первых, если мы посмотри на код решения, то увидим, что результат разбора парсера Asterisk нигде далее не используется, так что можно не тратить силы на его преобразование, а оставить то, что возвращает парсер Char (т.е. символ, char):

        public static Parser<char, char> Asterisk { get; } = Char('*');

Об остальном — о согласовании типов параметров там, где Asterisk используется — позаботится механизм выведения типов компилятора (но вот тип самого свойства Asterisk надо подправить вручную: он там вручную же и задан).

Далее, в библиотеке есть замечательный встроенный парсер для преобразования строки в число — UnsignedInt, так что велосипед под названием NumberParser, с его преобразованием методами C# строки цифр в число, не нужен. Но так как имя свойства NumericParser уже написано и много где задействовано, просто заменяем реализацию тела метода get этого свойства на UnsignedInt(10) (10 — это система счисления):

        public static Parser<char, int> NumberParser { get; } = UnsignedInt(10);

Еще одно мелкое усовершенствование — это замена конструкции Optional().Map(MapMaybe/MapMayBeStruct) парсером необязательного элемента для той же подстроки, возвращающим при разборе null в случае отсутствия этого элемента (т.е, тип вовращаемого значения заменяется на его допускающий null: T->T?). Для реализации этого парсера был создан метод расширения Nullable<TToken,T>, расширяющий средствами C# библиотеку Pidgin. Этот метод принимает парсер типа Parser<TToken,T> в качестве своего единственного параметра с квалификатором this (что позволяет использовать его с нотацией вызова обычного экземплярного метода — через точку) и возвращает парсер Parser<TToken,T?>, который при разборе необязательного элемента возвращает null при его отсутствии, примерно так:

        public static Parser<TToken, T?> Nullable<TToken, T>(this Parser<TToken, T> parser) where T : struct  //or class
            => parser.Map<T?>(t => t).Or(Parser<TToken>.Return(default(T?)));

Далее, заменим механизм проверки допустимости значений, возвращаемых парсерами, реализованный автором статьи через самописный (и довольно неуклюжий) метод Validate и ещё несколько других методов, на использование предназначенного для этого штатного метода Assert в классе парсера. Автор рассматриваемого решения пишет, и тут я с ним согласен, что "валидация — это всегда боль и печаль", однако метод Assert в данном случае позволяет эту боль и печаль уменьшить: он, будучи методом самого класса Parser<,>, просто вызывается ("через точку"), на свой выход при нормальной работе он передает тот парсер, для которого он вызван, а в процессе своей работы он проверяет предикат, заданный его первым параметром и выбрасывает исключение, если предикат возвращает false. Это сильно удобнее, чем код с функцией Validate, которая комбинирует через SelectMany исходный парсер с парсером Fail (который выбрасывает точно такое же исключение с сообщением об ошибке (и уж тем более — более ранний вариант кода из статьи, где то же самое комбинирование не спрятано в отдельный метод).

Используя Assert, прежде всего, производим замену в методе ParserHelper.IntervalsSequenceParser, где проверяется, что список интервалов, получающийся в результате разбора различных компонентов даты/времени, не содержит других интервалов, если в нем есть звездочка (т.е. что уже и так допустимы все значения компонента, и все другие элементы списка, очевидно, излишни). Через Assert эта проверка встраивается в парсер IntervalsSequenceParser совершенно прямолинейно, и это позволяет выкинуть из класса ParserHelper совершенно лишний при такой проверке метод GetWildcardsCheck.

Следующий набор проверок, используемых в решении, проверяет, что границы ни одного из интервалов в списке не выходят за границы допустимых для компонента значений. Мест, где такая проверка производится, много, код, который производит ее и формирует подходящее сообщение об ошибке для вызова метода Assert, нетривиален, так что для такой проверки был создан специальный метод расширения ParserHelper.AssertBounds. В оригинальном решении совместно с Validate используется метод GetBoundsCheck, принимающий три параметра — название компонента (для сообщения) и границы допустимых значений, и метод AssertBounds также принимает (помимо обязательного для метода расширения первого параметра с квалификатором this) эти же три параметра. Но он получился значительно короче.

Тем не менее, этот метод позволяет избавиться в классе ParserHelper как от GetBoundsCheck, так и, наконец, от всего Validate (ибо он больше уже нигде не вызывается) — уменьшив тем самым боль и печаль. Промежуточный вариант, получившийся после всех этих мелких улучшений — здесь

Теперь наступила пора сократить, наконец, длинные и некрасивые цепочки вызовов Then, которые присутствуют в методах DateParser, TimeParser и FullFormatParser. Сейчас, к примеру, метод DateParser выглядит так:

        public static Parser<char, ScheduleDate> DateParser { get; } =
            IntervalsSequenceParser.AssertBounds("Year", Constant.MinYear, Constant.MaxYear).Then(
                Char('.').Then(
                    IntervalsSequenceParser.AssertBounds("Month", Constant.MinMonth, Constant.MaxMonth).Then(
                        Char('.').Then(
                            IntervalsSequenceParser. AssertBounds("Day", Constant.MinDay, Constant.MaxDay),
                            (_, days) => days
                        ),
                        (months, days) => (days: days, months: months)
                    ),
                    (_, md) => md
                 ),
                (years, md) => new ScheduleDate(years, md.months, md.days)
            );

Не слишком красиво и понятно, правда? Поэтому, для начала, выкинем из цепочки вызовов парсеров, объединенных черех Then, вызовы парсера Char(), результаты которых все равно игнорируются, и которые нужны только, чтобы проверить наличие символа-разделителя между списками значений компонентов расписания (года, месяца и дня для DateParser). Вместо дополнительного вызова SelectMany/Then воспользуемся для такой проверки методом Before, присутствующим в классе Parser<,>. Этот метод комбинирует свой параметр-парсер (Char() в данном случае) с исходным парсером, для которого метод Before вызывается. Получившийся комбинированный парсер после проверки того, что входная строка успешно разбирается последовательно обоими парсерами, возвращает результат работы исходного парсера, а результат парсера — параметра Before игнорирует. С помощью Before количество парсеров в цепочке вызовов Then резко сокращается, в частности, для DateParser — с пяти до трех:

        public static Parser<char, ScheduleDate> DateParser { get; } =
            IntervalsSequenceParser.AssertBounds("Year", Constant.MinYear, Constant.MaxYear).Before(Char('.')).Then(
                IntervalsSequenceParser.AssertBounds("Month", Constant.MinMonth, Constant.MaxMonth).Before(Char('.')).Then(
                    IntervalsSequenceParser. AssertBounds("Day", Constant.MinDay, Constant.MaxDay),
                    (months, days) => (days: days, months: months)
                ),
                (years, md) => new ScheduleDate(years, md.months, md.days)
            );

Аналогичную операцию проводим и для парсеров TimeParser и FullFormatParser.

Но и это — ещё не все, что можно сделать с помощью методов комбинирования парсеров из библиотеки Pidgin. В ней есть очень удобный парсер, создаваемый вариантом метода Map, который позволяет объединить сразу несколько (до 8) парсеров (второй и далее параметры) так, что результаты их последовательного выполнения объединяются в результат выполнения парсера, возвращаемого Map, с помощью делегата (первый параметр Map), принимающего нужное количество параметров нужного типа — результатов работы объединяемых парсеров. В результате получается такая вот аккуратная и понятная конструкция для DateParser:

        public static Parser<char, ScheduleDate> DateParser { get; } =
            Map((years, months, days) => new ScheduleDate(years, months, days),
                IntervalsSequenceParser.AssertBounds("Year", Constant.MinYear, Constant.MaxYear).Before(Char('.')),
                IntervalsSequenceParser.AssertBounds("Month", Constant.MinMonth, Constant.MaxMonth).Before(Char('.')),
                IntervalsSequenceParser. AssertBounds("Day", Constant.MinDay, Constant.MaxDay)
            );

Производим аналогичные преобразования с TimeParser и FullFormatParser и все: мы получили на четверть более короткий (88 строк вместо 119) и, полагаю, что для большинства — более понятный код, не использующий магию языка запросов LINQ. И все это — благодаря более полному использованию возможностей библиотеки Pidgin. Посмотреть окончательный результат можно по ссылке .

Является ли это решение идеальным? Не совсем. Ошибки в дате или дне недели хотя и помешают расписанию пройти разбор, но адекватного сообщения о них не будет: они будут отнесены к ошибкам разбора формата времени. Дело в том, что в FullFormatParser пришлось, на случай отсутствия в расписании даты и/или дня недели использовать метод Try.

Метод Try перехватывает и поглощает ошибки, после чего возвращает текущую позицию разбора на то место, откуда он был вызван — но он всеяден: он поглотит не только ошибки формата даты или дня недели, но и ошибки проверки соблюдения границ значений или наличия избыточных элементов в списке значений вместе с '*'. Чтобы сделать сообщения об этих ошибках более информативными, следовало бы разбить расписание на отдельные сегменты для даты, дня недели и времени по пробелам-разделителям и разобрать каждый сегмент отдельно. При просмотре списка методов в библиотеке Pidgin что-то подходящее для этого вроде бы проглядывает. Но я с этим не разбирался, т.к. я ограничился только тем, что переписал в более компактном виде решение предыдущего автора.

И да, при использовании этой библиотеки можно совершенно не знать, что такое монада, и прочие подобные подробности из теории ФП. Или — что такое полиморфизм и позднее связывание из теории ООП. Для использования библиотеки Pidgin достаточно только понять, как пользоваться этой конкретной библиотекой, понять ее идиомы, изучить список ее классов и методов (т.е. ООП чуть-чуть знать-таки надо). А есть ли в библиотеке там внутри монады, используется ли позднее связывание, или ещё там что-то такое же теоретическое — это знать не требуется. И даже слов таких знать не нужно — просто берем библиотеку и работаем.

Выводы

Из описанного случая можно извлечь две морали.

Первая — об использовании сторонних библиотек: это палка о двух концах. С одной стороны, библиотеки позволяют не изобретать велосипед, а использовать уже написанный и проверенный код. Но с другой стороны, прежде чем использовать библиотеку, с ней надо ознакомиться и понять, что и как можно делать с ее помощью, и как это сделать оптимально. И если библиотека достаточно богатая и не особо хорошо документированная, это может потребовать заметного времени. Как в нашем случае: для Pidgin документирован только минимум — классы и сигнатуры методов с коротким их описанием, а сведения, как концептуально устроена библиотека и как с ней работать, в документации отсутствуют. А методов — хороших и разных — в этой библиотеке немало. И не факт, что время на изучение библиотеки получится компенсировать, если библиотеку использовать лишь для однократного решения простой задачи, типа рассматриваемой. И все это — не говоря о побочных эффектах из-за появления в коде зависимости от чужой библиотеки.

И так как полноценное освоение достаточно богатой библиотеки требует времени, то на нем хочется сэкономить. Вот автор рассматриваемого решения и сэкономил (по его словам, он потратил на изучение библиотеки всего 4 часа): нашел минимальный набор вызовов библиотеки, позволивший ему решить задачу, и приколотил их костылями в виде "функциональщины" из C#. Почему костылями — это, я надеюсь, после сокращения на четверть объема кода от первоначального, очевидно, а почему реализацию парадигмы ФП (парадигмы действительно мощной и эффективной) конкретно в C# я называю не слишком благозвучно и уважительно — функциональщина — об этом как раз будет вторая мораль.

Однако мои слова ни в коем случае не следует рассматривать как претензию к автору: сам характер задачи (напоминаю, исходно это было тестовое задание, т.е. то, что по определению делается на один раз) определяет, что от решения не следует требовать того, что требуется от полноценной, предназначенной для долговременного использования программы. Так что на усилиях по разработке такого решения вполне оправданно сэкономить. Но вот назвать получившееся "совершенным кодом" (на что намекает публикация статьи в одноименном хабе) — это, по моему мнению, погрешить против истины.

Теперь — мораль номер два: о функциональном программировании на C#. Конечно, C# не совсем уж непригоден для использования парадигмы функционального программирования. В нем, по крайней мере, есть необходимый для этого минимум: функции в нем являются полноценными объектами языка, такими же, как и объекты данных. Для этого в C# используются делегаты: типы для переменных, которые содержат ссылку на код функции.

Но это — все, что в C# есть для функционального программирования.

В отличие от языков, предназначенных для программирования в функциональной парадигме, сам язык C# не предоставляет никакой помощи для использования этой парадигмы. Во-первых, в самом C# нет операций над функциями (композиции и других операций комбинирования, каррирования и пр.). И всякое комбинирование или частичное применение функций надо писать вручную, через соответствующие делегаты. Во-вторых, в C# нет средств контроля побочных эффектов функций на уровне языка и системы типов (в том числе — средств выделения "чистых", без побочных эффектов функций): вы можете комбинировать что угодно с чем угодно, и компилятор при этом никак не ограничивает вашу свободу творить (и свободу ошибаться — тоже). А потому комбинировать парсеры из библиотеки Pidgin можно не за счет их монадичности, как пишет автор, а потому что просто в C# можно комбинировать все: компилятор ничего на эту тему не проверяет, для него все делегаты — на одно лицо, ему достаточно, чтобы типы параметров и возвращаемых значений делегатов (никак не зависящие от наличия побочных эффектов) были совместимы.

Вот по этим-то двум причинам я называю введенные в C# элементы функционального программирования "функциональщиной". И, программируя на C#, предпочитаю вообще забыть, что есть такое "функциональное программирование", во избежание разочарований от несбывшихся надежд — ибо помощи от компилятора C# в получении свойственных функциональной парадигме преимуществ все равно не дождешься: делегаты использовать приходится исключительно на свой страх и риск. А для функционального программирования, по моему скромному мнению, есть более подходящие другие языки.

Заключение

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

P.S. На КДПВ — пример спрямления пути в реале. Но в реале все сложнее — там на спрямление потребовалось лет двадцать.