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:
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.
Consider the code that processes such expressions.
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.
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
'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.
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:
Code that it hits
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)