AST — Absolutely Superior Treatment

Я часто говорю, что если язык лишен встроенных средств работы с AST — абстрактным синтаксическим деревом — то этот язык спроектирован не очень умными людьми. Идолопоклонники могут с пеной у рта доказывать, что AST никому не нужно, или что хорошего API к AST — достаточно, или что прикрученное сбоку AST-представление закрывает потребности…

Это все детский лепет, и ниже я собираюсь рассказать, почему. Оба самых «популярных» (читай: хайповых) языка программирования современности — Rust и Go — не обошлись без этой родовой травмы (если вы считаете, что экспорт AST при помощи костыля rustc_ast::ast — решает эту проблему, вы просто не понимаете, что такое AST и зачем он нужен).

Когда разговор заходит про макросы — люди умные и образованные сразу вспоминают LISP, терпилы — препроцессор C/C++, а все остальные — довольствуются фразами популяризаторов наподобие «не используйте макросы, они увеличивают когнитивную нагрузку. Кстати, откуда вообще взялось в нашей профессии поверие, будто увеличение когнитивной нагрузки — это плохо? Как оно уживается с тем, что подавляющее большинство разработчиков считает наше ремесло — сложным, а вдобавок — чуть ли не творчеством, или, простихосподи, искусством? Ладно.

Так вот, макросы. В LISP’ах они такие естественные и простые — просто потому, что являются такой же стандартной частью языка, как арифметическое сложение. Это бесплатно, потому что LISP — сам себе AST. Любое выражение — просто кусок синтаксического дерева.

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

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

Как AST может помочь там, где экспортируемые конструкции языка бессильны

В одном из предыдущих текстов я писал про то, что иногда eval — наш друг. Если речь про более-менее простое отложенное вычисление — можно хранить его строкой и, когда придет время, вычислять по месту. Но таскать туда-сюда строки по коду — идея так себе. А просто код таскать не получится, потому что компилятор постарается его выполнить, как только сможет. В ФП для этой цели принято использовать функции высшего порядка, но их применимость — у́же, поскольку в большинстве языков анонимные функции являются по совместительству кложами, то есть захватчиками контекста — а значит, не совсем пригодны для холодной десериализации.

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

setMatcher(   %{      {:ok, _} => true,      _ -> false   } )

Компилятор такой код не пропустит, потому что попытается по месту вычислить аргумент, встретит там _ в качестве ключа в мапе и расстроится.

ОК, давайте так тогда:

setMatcher(fn input ->   case input do     {:ok, _} -> true,     _ -> false   end end)

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

Что же делать? — Использовать AST. Компилятор не попытается ничего сделать с вашим AST, потому что оно — по определению — статические данные, а значит — на этапе компиляции проблем не будет. Зато потом, когда потребуется, можно будет превратить это AST в исполняемый код и запихнуть в матч. AST представление позволяет нам таскать туда-сюда куски кода и разворачивать их по месту в самый последний момент. Оставаясь при этом в пределах компайл-тайма (можно и в рантайм протащить, но сейчас не об этом).

Живой пример: stream comprehension

В одном из проектов нам потребовалось разбирать строку в стандартном формате крона и запускать внутренние задачи соответственно. Если попробовать определить тип результата нужного нам преобразования, это будет что-то вроде string → stream(timestamp()).

События, описываемые строкой из крона — это бесконечный стрим, начинающийся «скоро» и не заканчивающийся никогда. Можно, конечно, пойти по пути наименьшего сопротивления, и сказать, что, мол, через 10 лет сдохнет либо ишак, либо эмир, либо батарейка в чмосе, но мы тут обсуждаем правильные решения.

Поскольку крон нам аффиннирует временную ось, логично было бы создать стрим «каждая следующая минута» — а потом фильтровать его сообразно циферкам и звездочкам в исходной строке. Для фильтрации входного списка у нас из коробки есть comprehensions. Но оно не умеет работать с бесконечными стримами. Аналога для стримов в языке нет (и пока я его имплементировал, я понял, почему).

В общем, я решил причинить сообществу добро и реализовать comprehensions для стримов.

Библиотека LazyFor

Я опущу первые три акта этого хоррор-балета (отрицание, гнев и торг) и перейду сразу к последней, четвертой: к решению проблемы. Для нетерпеливых: https://hexdocs.pm/lazy_for.

Сначала я написал рабочую имплементацию на функциях модуля Stream из корки. Это был монстр, который позволил мне узнать, что в линтере credo существует захардкоженный верхний лимит на кофигурацию разрешенного количества цикломатических вложений. Код выглядел примерно так:

    Stream.transform([dt.year, dt.year + 1], :ok, fn year, :ok ->       {Stream.transform(1..dt.calendar.months_in_year(year), :ok, fn          month, :ok when year <= dty and month < dtm ->            {[], :ok}           month, :ok ->            unless ct.month.eval.(month: month) do              {[], :ok}            else              {Stream.transform(1..dt.calendar.days_in_month(year, month), :ok, fn                 day, :ok when year <= dty and month <= dtm and day < dtd ->                   {[], :ok}                  day, :ok ->                   unless dom_or_dow.(day, dt.calendar.day_of_week(year, month, day)) do                     {[], :ok}                   else                     {Stream.transform(0..23, :ok, fn                        hour, :ok                        when year <= dty and month <= dtm and day <= dtd and hour < dth ->                          {[], :ok}                           → и еще три отступа вправо, а там                            {[result], :ok}

Показать такой код коллегам я не могу, но он был мне нужен не для того. Мне нужны были тесты, когда мои comprehensions будут готовы. Я хотел разрешить в результате что-то такое:

stream dt <- every_minute(now()),        cron.valid?(dt.year), …, cron.valid?(dt.minute),        take: 5,        do: dt

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

И тут меня ждала первая ловушка: единственный доступный мне инструмент — Stream.transform/3 мне нужно было вызвать рекурсивно неопределенное количество раз (потому что оно определяется количеством фильтров и биндингов внутри второй строки в примере выше).

Рекурсивный вызов единственный вариант еще и потому, что comprehension может быть вложенным (for i <- 1..3, j <- 1..3, i != j, k <- 1..3, i != k, do: [i, j, k]). Тут еще и новые биндинги, которые доступны только после объявления, и в собственно результирующем вычислении. А где-то впереди финальным монстром с домокловым мечом наперевес — маячил reduce, который я тоже хотел бы поддержать.

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

Я попробовал пойти стандартным путём, через quote/2, но быстро сломался на рекурсии. Тогда я перекурил, выпил несколько чашек кофе, и посмотрел на то, как выглядит нужный мне вызов в AST.

iex|🌢|1  quote do ...|🌢|1    Stream.transform(initial, acc, fn value, acc -> ...|🌢|1      Stream.transform(initial, acc, fn value, acc -> ...|🌢|1      end) ...|🌢|1    end) ...|🌢|1  end  {{:., [], [{:__aliases__, [alias: false], [:Stream]}, :transform]}, [],  [    {:initial, [], Elixir},    {:acc, [], Elixir},    {:fn, [],     [       {:->, [],        [          [{:value, [], Elixir}, {:acc, [], Elixir}],          {{:., [], [{:__aliases__, [alias: false], [:Stream]}, :transform]}, [],           [             {:initial, [], Elixir},             {:acc, [], Elixir},             {:fn, [],              [{:->, [], [[{:value, [], Elixir}, {:acc, [], Elixir}], nil]}]}           ]}        ]}     ]}  ]}

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

  defmacrop __s__(any \\ {:_, [], nil}),     do: quote(do: {:., [], [{:__aliases__, [alias: false], [:Stream]}, unquote(any)]})

И приступил к построению голого AST. Грубо говоря (да и без грубостей тоже, в общем-то), я просто прохожу по синтаксическому дереву того, что в качестве аргументов получил мой пока несушествующий макрос stream/2, и преобразую их в вызовы функций модуля Stream.

  # simple comprehension, outer, guards   defp clause(          {:<-, _meta, [{:when, _inner_meta, [var, conditions]}, source]},          {__s__(), _, _} = inner,          acc        ),        do: do_stransf_clause(source, acc, do_fn_body(inner, var, conditions))    # simple comprehension, inner, guards   defp clause({:<-, _meta, [{:when, _inner_meta, [var, conditions]}, source]}, inner, acc),     do: do_stransf_clause(source, acc, do_fn_body([inner], var, conditions))    # simple comprehension, outer, no guards   defp clause({:<-, _meta, [var, source]}, {__s__(), _, _} = inner, acc),     do: do_stransf_clause(source, acc, do_fn_body(inner, var))    # simple comprehension, inner, no guards   defp clause({:<-, _meta, [var, source]}, inner, acc),     do: do_stransf_clause(source, acc, do_fn_body([inner], var))    # expression   defp clause({:=, meta, [var, expression]}, inner, acc),     do: clause({:<-, meta, [var, [expression]]}, inner, acc)    # и так далее

Опции точно так же превращаются в соответствующие вызовы:

  defp do_apply_opts({reducer, ast}, opts, caller) do     ast =       if opts[:uniq],         do: {{:., [], [{:__aliases__, [alias: false], [:Stream]}, :uniq]}, [], [ast]},         else: ast      into = opts[:into]      ast =       if into,         do: {{:., [], [{:__aliases__, [alias: false], [:Stream]}, :into]}, [], [ast, into]},         else: ast      ast =       case opts[:take] do         :all ->           {{:., [], [{:__aliases__, [alias: false], [:Enum]}, :to_list]}, [], [ast]}          i when is_integer(i) ->           {{:., [], [{:__aliases__, [alias: false], [:Enum]}, :take]}, [], [ast, i]}          _ ->           ast       end      …      ast   end

В этот момент я понял, что цель в принципе достижима. Осталось понять, что делать с несколькими параметрами в вызове stream/2 (оригинальный жадный for/2 — это специальная форма, которая парсится до всего остального, поэтому там много запятых — не помеха, но у меня это должен быть валидный эликсир, поэтому увы и ах, запятые разделяют аргументы, а тут не джаваскрипт, количество аргументов входит в сигнатуру). Я решил это недокументированным конфигурируемым параметром @clauses, по умолчанию равным 42. Если кому-то потребуется больше — он разберется в исходниках. То есть, я сгенерировал 42 функции (stream/2, stream/3, …, stream/42).

Еще немного моей крови выпила опция reduce, но как я её реализовал — выходит за рамки этого текста, поэтому кому интересно — вот код.

В результате я получил абсолютно работоспособную ленивую реализацию для comprehension, при помощи которой в результате переписал свой кроннер. Без продуманного в языке AST это было бы невозможно. А полученный опыт, в результате, привел к тому, что я часто при написании гораздо более тривиальных макросов — просто оперирую синтаксическим деревом, без хождения кругами через quote/2. Чего и вам желаю.

Удачного лазания по синтаксическим деревьям!