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)
    
    • +10
    • 4,9k
    • 2
    Поделиться публикацией

    Комментарии 2

      +3
      Порождаемый код поразительно совпадает с тем что делает такая же библиотечка для Common Lisp.
      github.com/m2ym/optima

      И у макросистем много общего, если не считать типы.
        0
        Lisp на Julia сильно повлиял.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое