Pattern matching с помощью макросов
Язык Julia не поддерживает такую технику программирования, хорошо зарекомендовавшую себя в языках Haskell, Prolog, Erlang, Scala, Mathematica, как pattern matching. Но разрешает писать макросы, которые позволяют исправить этот фатальный недостаток. Выглядит это примерно так: julia> immutable X a end
julia> immutable Y a; b end
julia> @case (Y (X (9),2), Y (4,3)→ 55, Y (X (k),2)→1+k) 10 Исходный код доступен на github.Похожую (но гораздо более развитую и готовую для использования) можно взять здесь, но она слишком большая, что бы разбирать ее как пример в статье.Как в Scala, на каждый альтернативный вариант, который надо распознать, создается тип (в данном случае как положено в функциональном программировании, неизменяемый, но этот код будет работать и с типами). При желании, их можно унаследовать от одного абстрактного.Код на Julia, с которым работают макросы, представлен в виде Абстрактного Синтаксического Дерева (AST). В этом дереве листьями будут простые константы языка (числа, строки) и символы (имеющие тип Symbol), а узлы будут иметь тип Expr с полями head и args. Для создания объекта типа Expr или Symbol доступен синтаксический сахар: : v — это просто символ, а :(1+2) обозначает Expr (: call, :+, 1, 2) (Expr первый аргумент конструктора помещает в head, остальные в массив args). При конструировании выражений можно «цитировать» созадаваемое программой подвыражение: :($(a) + 1) — выражение, сложения подвыражения из переменной a с единицей. Цитирование (quotation) было изобретено в языке Lisp и оказалось восстребованным во многих языках, поддерживающих метапрограммирование.
Макрос 'case' первым аргументом получает анализируемое выражение, а остальные — пары образец→реакция. Посмотрим, как такие выражение выглядят в AST.
julia>:(Y (X (k),2)→1+k).head :→
julia>:(Y (X (k),2)→1+k).args 2-element Array{Any,1}: :(Y (X (k),2)) quote # none, line 1: 1 + k end Рассмотрим код, который обрабатывает такие выражения
casev (v, np, e1) = let … Здесь описана вспомогательная функция spat if (e1.head == :(→)) (p, c) = e1.args if (p.head == :(call)) t = eval (p.args[1]) es = map (spat, t.names, p.args[2: end]) :(if (isa ($v,$t)) ; $(pcomp (c, np, es)) else $np end) end end end Функция casev принимает аргументы: v — символ связанный с анализируемым выраженим (а не само выражение, что бы не вычислять его несколько раз), e1 — образец→реакция, а np — что делать, если образец не будет распознан (прием, напоминающий программирование в продолжениях).Сначала проверяется, что это выражение вида '→' и его аргументы сохраняются в переменных 'p' (образец) и 'c' (обрабатывающий его код).Образец, похожий на вызов (call), разбирается на символ типа и выражения аргументов. Символ типа нужно конвертировать в сам тип (типы в Julia — «величины первого порядка»), что бы понять, что с ним можно делать. Вычислить символ можно функцией eval. (Она вычисляет выражение в контексте текущего модуля, по этому выделить макрос и вспомогательные функции в отдельный модуль у меня пока не получилось.)Далее мы вызываем функцию 'spat' на каждую пару имя поля типа, соответствующий этому полю подобразец. spat (n: Symbol, p: Symbol) = (:(=), :($p = $v.$n)) spat (n: Symbol, p: Expr) = (:(m), let s = gensym () ; (m) → :(let $s = $v.$n $(casev (s, np,:($p→$m))) end) end) spat (n: Symbol, p: Any) = (:(==), :($p == $v.$n)) Это мультиметод, который диспечеризуется по типу подобразца. Для типов Symbol и Any (под это попадают все константы) генерируется код и пометка, что с ним потом делать. Для сложного подобразца (типа Expr) создается замыкание, которое рекурсивно создает распознаватель подобразца, оставляя реакцию свободной (аргумент замыкания 'm') — туда будет переданно продолжение обработки текущего образца.Теперь можно создать обработку образца :(if (isa ($v,$t)) ; $(pcomp (c, np, es)) else $np end) 'isa' проверяет, что анализируемая величена имеет тип 't' (символ которого мы получили из образца), 'pcomp' компилирует кусочки раскознающего образец кода в единое выражение, 'np' — «продолжение», которое распознает остальные образцы, если данный не будет распознан. Такой подход приводит к тому, что код «продолжения» будет продублирован при обработке каждой возможной неудачи распознавания. Пока этот макрос использует человек, это позволительная роскошь. Если код на Julia с pattern matching начнут писать роботы, надо будет оформить его в локальную функцию и передавать ее символ. pcomp (c, np, p) = if (length (p) == 0) c else (r, d) = p[1] n1 = pcomp (c, np, p[2: end]) if (r == :(=)) :(let $d; $n1; end) elseif (r == :(==)) :(if $(d) ; $n1 else $np end) elseif (r == :(m)) d (n1) end end Функция получает массив кусочков, распознающих отдельные части образца. Если этот массив пуст, в этом месте генерируемой программы образец уже распознан и надо вызвать код реакции (из аргумента 'c').Если в данном месте в образце был символ, надо оформить блок 'let' с инциализацией переменной с этим именем и поместить туда код дальнейшей обработки.Если там была константа, создаем соответствующий 'if' (в альтернативе 'else' находится код «продолжения» при неудаче).А если пришло замыкание, вызывем его, передав код распознавания остатка образца — оно само разберется, что с ним делать.Теперь понятно, как обработать несколько альтернативных образцов и реализовать сам макрос:
casen (v, el) = if (length (el) == 0) :() else casev (v, casen (v, el[2: end]), el[1]) end
macro case (v, e1…) if (isa (v, Symbol)) casen (v, e1) else let s = getsym () :(let $(s) = $(v) ; $(casen (s, e1)) end end end Код, который он пораждает можно не читать julia> macroexpand (:(@case (Y (X (9),2), Y (4,3)→ 55, Y (X (k),2)→1+k))) :(let #246###11039 = Y (X (9),2) # line 48: if isa (#246###11039, Y) # line 32: if 4 == #246###11039.a # line 11: if 3 == #246###11039.b # line 11: begin # none, line 1: 55 end else # line 11: if isa (#246###11039, Y) # line 32: let # line 21: #244###11040 = #246###11039.a # line 22: if isa (#244###11040, X) # line 32: let #245#k = #244###11040.a # line 9: begin # ADT.jl, line 22: if 2 == #246###11039.b # line 11: begin # none, line 1: 1 + #245#k end else # line 11: () end end end else # line 32: () end end else # line 32: () end end else # line 11: if isa (#246###11039, Y) # line 32: let # line 21: #244###11040 = #246###11039.a # line 22: if isa (#244###11040, X) # line 32: let #245#k = #244###11040.a # line 9: begin # ADT.jl, line 22: if 2 == #246###11039.b # line 11: begin # none, line 1: 1 + #245#k end else # line 11: () end end end else # line 32: () end end else # line 32: () end end else # line 32: if isa (#246###11039, Y) # line 32: let # line 21: #244###11040 = #246###11039.a # line 22: if isa (#244###11040, X) # line 32: let #245#k = #244###11040.a # line 9: begin # ADT.jl, line 22: if 2 == #246###11039.b # line 11: begin # none, line 1: 1 + #245#k end else # line 11: () end end end else # line 32: () end end else # line 32: () end end end)
