Pattern matching with macros

    Julia does not support a programming technique that has proven itself in the Haskell, Prolog, Erlang, Scala, Mathematica languages ​​as pattern matching . But it allows you to write macros that fix this fatal flaw. It looks something like this:
    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
    

    Source code is available on github .
    A similar one (but much more developed and ready for use) can be taken here , but it is too large to disassemble it as an example in an article.

    As in Scala, for every alternative that needs to be recognized, a type is created (in this case, as it should be in functional programming, it is immutable, but this code will work with types as well). If desired, they can be inherited from one abstract.

    Macro code for Julia is presentedas an Abstract Syntax Tree (AST). In this tree, the leaves will be simple language constants (numbers, strings) and symbols (of type Symbol), and the nodes will be of type Expr with fields head and args. To create an object of type Expr or Symbol syntax sugar is available :: v is just a symbol, and : (1 + 2) stands for Expr (: call,: +, 1, 2) (Expr places the first argument of the constructor in head, the rest in an array args). When constructing expressions, you can "quote" the subexpression created by the program :: ($ (a) + 1) - expression, the addition of the subexpression from the variable a to unity. Quotation (quotation) was invented in the Lisp language and proved to be in demand in many languages ​​that support metaprogramming.

    The 'case' macro receives the parsed expression as the first argument, and the rest - sample-> reaction pairs. Let's see how these expressions look in the 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
    


    Consider the code that processes such expressions.
     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
    

    The casev function takes arguments: v is the symbol associated with the expression being analyzed (and not the expression itself, so as not to calculate it several times), e1 is the sample-> reaction, and np is what to do if the sample is not recognized (a programming- like technique in the sequels ).
    First, it is checked that this expression is of the form '->' and its arguments are stored in the variables 'p' (sample) and 'c' (the code that processes it).
    A pattern similar to a call is parsed into a character type and argument expression. The type symbol must be converted to the type itself (types in Julia are “first order quantities”) in order to understand what you can do with it. You can calculate a character with the eval function. (She calculates the expression in the context of the current module, so I haven’t succeeded in isolating the macro and auxiliary functions into a separate module.)
    Next, we call the spat function on each pair of the type field name corresponding to this sub-field.
      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))
    

    This is a multimethod that is dispersed as a sub-sample. For the Symbol and Any types (all constants fall under it), code is generated and a note about what to do with it later. For a complex sub-sample (of type Expr), a closure is created, which recursively creates a recognizer of the sub-sample, leaving the reaction free (closure argument 'm') - processing of the current sample will be transferred there.
    Now you can create sample processing
    :(if(isa($v,$t)) ; $(pcomp(c,np,es)) else $np end)

    'isa' checks that the value being analyzed is of type 't' (the symbol of which we got from the sample), 'pcomp' compiles the pieces of the code recognizing the sample into a single expression, 'np' is a “continuation” that recognizes the rest of the samples if this is not will be recognized. This approach leads to the fact that the "continue" code will be duplicated during the processing of each possible recognition failure. As long as this macro is used by humans, it is permissible luxury. If robots start writing code on Julia with pattern matching, you will need to make it into a local function and pass its symbol.
     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

    The function receives an array of pieces recognizing individual parts of the sample. If this array is empty, at this point in the generated program the pattern is already recognized and you need to call the reaction code (from the argument 'c').
    If there was a symbol in the sample at this point, you need to create a 'let' block with the variable with this name to be initialized and put the further processing code there.
    If there was a constant, create the corresponding 'if' (the alternative to 'else' contains the “continue” code if it fails).
    And if a short circuit comes, we call it, passing the code for recognizing the remainder of the sample - it will figure out what to do with it.

    Now it’s clear how to process several alternative samples and implement the macro itself:
     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
    

    Code that it hits
    can not read
    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)
    

    Also popular now: