Pattern matching with macros

The Julia language does not support such a programming technique that is well-proven in Haskell, Prolog, Erlang, Scala, and Mathematica, as pattern matching . But allows you to write macros that allow you to fix this fatal flaw. It looks 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 .
Similar (but much more developed and ready for use) can be taken here , but it is too big to sort it out as an example in the article.

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

The code for Julia, with which the macros work, is presented in the form of an Abstract Syntactic Tree (AST). In this tree, the leaves will be simple language constants (numbers, strings) and symbols (having the type Symbol), and nodes will have type Expr with the head and args fields. To create an object of type Expr or Symbol, syntactic sugar is available :: v is just a symbol, and : (1 + 2) indicates Expr (: call,: +, 1, 2) (Expr, the first argument of the constructor puts in the head, the rest in the array args). When constructing expressions, you can “quote” the subexpression created by the program :: ($ (a) + 1) is an expression, adding subexpressions from the variable a with unit. The quotation was invented in Lisp and found to be in demand in many languages ​​that support metaprogramming.

The macro 'case' receives the analyzed expression as the first argument, and the rest, the sample-> reaction pairs. Let's see how such expressions look in 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 technique that resembles programming in continuations ).
First it is checked that this expression is of the form '->' and its arguments are stored in the variables 'p' (sample) and 'c' (the processing code).
A sample that looks like a call is broken down into a symbol for the type and expression of the arguments. The type symbol needs to be converted into the type itself (the types in Julia are “first order values”) in order to understand what can be done with it. The symbol can be calculated using the eval function. (It calculates the expression in the context of the current module, so I did not manage to select the macro and auxiliary functions into a separate module.)
Next, we call the function 'spat' for each pair of the name of the type field corresponding to this field subsample.

  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, which is dispersed by the type of sample. For the Symbol and Any types (all constants fall under this) a code is generated and a mark, what to do with it later. For a complex subsample (of type Expr), a closure is created that the recognizer of the subsample creates recursively, leaving the response free (closure argument 'm') - the 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' verifies that the value being analyzed is of type 't' (the character of which we received from the sample), 'pcomp' compiles the pieces of the unrecognizing sample code into a single expression, 'np' is a “continuation” that other samples recognize if it 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. While this macro is used by man, this is a permissible luxury. If the code on Julia with pattern matching starts writing robots, it will be necessary to arrange 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 that recognize individual parts of the sample. If this array is empty, the sample is already recognized in this place of the generated program and the response code must be called (from the 'c' argument).
If there was a symbol in this place in the sample, it is necessary to arrange the block 'let' with the initialization of the variable with this name and place the code for further processing there.
If there was a constant, create the appropriate 'if' (in the alternative 'else', the “continue” code is found on failure).
And if a closure arrives, we call it, passing the pattern recognition code of the sample residue - 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