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)