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)

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.