Re-posted from: https://white.ucc.asn.au/2018/10/03/Dispatch,-Traits-and-Metaprogramming-Over-Reflection.html
This is a blog post about about dispatch.
Mostly, single dispatch, though it trivially generalises to multiple dispatch,
because julia is a multiple dispatch language.
This post starts simple, and becomes complex.
- Beginning with, introductory julia skills: dispatch
- continue to intermidate julia skills: traits
- and finishing up with advanced techniques: metaprogramming over reflection
The last of which is kinda evil.
I think dispatch is very intutitive as a concept.
In C you learn that a function’s signature,
is composed of it’s name, and the types of the arguments and the return type.
So it would make sense that you could define a different function, depending on the types.
(but you can’t).
In a dynamic language you are supposed not worrying too much about the type of your values.
I feel that the emphisis should be on on not worrying too much: you need to worry just the right amount.
Duck-typing is great.
But reasoning about types is very easy.
It is the kind of reasoning we do all the time.
Dispatch is about striking the balance between exploiting knowledge of a type,
and being general.
I can write general code that doesn’t worry about the types,
and then add extra methods based on the types of the arguments for special cases.
Part 1: Displaying a Percentage
I would like to display a value as a percentage.
So that is pretty easy, if I have some portion, (e.g 0.5
),
I can convert it to a percentage by multipling it by 100
(e.g. 100 × 0.5 = 50
),
then I print it and append a %
sign.
Input:
Output:
That gives me a general rule that works for most types.
Input:
Output:
I’m not exactly happy with how that Rational
displayed,
it is correct, but I would rather it was displayed not as a fraction.
So we can fix it by adding a new method for Rational
s.
Our current method has no type constraints.
We will create one that has a constraint that the argument must be a Rational
.
More specific methods, i.e. ones with tighter type constraints are called over ones with looser constraints.
Input:
Output:
Input:
Output:
That worked great.
What if I am given a String as input,
that is already a percentage?
Input:
Output:
MethodError: no method matching *(::Int64, ::String)
Closest candidates are:
*(::Any, ::Any, !Matched::Any, !Matched::Any...) at operators.jl:502
*(!Matched::Missing, ::AbstractString) at missing.jl:139
*(::T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}, !Matched::T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}) where T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8} at int.jl:54
...
Stacktrace:
[1] display_percent(::String) at ./In[1]:1
[2] top-level scope at In[5]:1
We get an error, because there is no method to do 100 times a String
;
and multiplying the string by 100 isn’t what we want to do anyway.
So we can define a special method for how to display a string as a percent.
It is going to check the string is in the correct format,
and if so display it.
Input:
Output:
Input:
Output:
Great, fixed it.
Where this really comes in handy is working with things you as the programmer don’t know the type of, when you are writing the code.
For example if you have a hetrogenous list of elements to process.
Input:
Output:
Real world example of this sort of code is in solving for indexing rules in TensorFlow.jl.
So dispatch is useful, it lets you write different rules for how to handle different types.
Dispatch goes very nicely in a dynamically typed language.
Since (type-unstable) functions can return different types, depending on inputs,
and some types (like our String
and our Rational
) might want to be handled differently,
we need a good way of dealing with those cases.
It is also nicely extensible.
Lets say we created a singleton type to represent a half.
Input:
Output:
Input:
Output:
So it was simple to just add a new method for it.
Users can add support for new types,
completely separate from the original definition.
Constrast it to:
Input:
Output:
Input:
Output:
MethodError: no method matching *(::Int64, ::Half)
Closest candidates are:
*(::Any, ::Any, !Matched::Any, !Matched::Any...) at operators.jl:502
*(::T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}, !Matched::T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}) where T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8} at int.jl:54
*(::Union{Int16, Int32, Int64, Int8}, !Matched::BigInt) at gmp.jl:463
...
Stacktrace:
[1] display_percent_bad(::Half) at ./In[11]:9
[2] top-level scope at In[12]:3
You can see, that since it doesn’t include support for Half
when it was declared,
it doesn’t work,
and you can’t do much to make it work.
This kinda code is common in a fair bit of python code.
Part 2: AsList
, (including using traits)
The kind of code which uses if
conditionals,
is quite common in practice.
In Python TensorFlow has a helper function, _AsList
:
def _AsList(x):
return x if isinstance(x, (list, tuple)) else [x]
It’s purpose is to convert scalar values,
into lists with one item.
So it checks if the input is a list
or a tuple
,
and if it is, then it makes no change,
if not then it wraps it in a list
.
Problem with this is,
what if my input is a type it didn’t expect.
But which actually
duck-types as a list
, as fair as the functionality required is concerned.
e.g. perhaps a dequeue
.
Then the code will break.
My dequeue
will be mangled into a list
containing a deque
,
which won’t index or iterate correctly.
And there is nothing I can do about it, except make a PR to TensorFlow.
(or perhaps as a hack, monkey-patch it).
Example 2.1 direct
The basic way would be to write methods for each.
Like before.
Input:
Output:
The Union
is just a way of saying the argument needs ot match either of these types.
Input:
Output:
What we are saying is that scalar values do one thing,
and nonscalar values do another.
We can add more rules to aslist_direct
.
Though we can’t add more types to the Union
so we would have to declare them separately,
which would involve repreated code.
e.g.
Input:
Output:
Repeating code is bad.
Further what if we want the notion of Scalarness elsewhere in our code?
One way to handle this and avoid repeating code, would be to use abstract types.
If all our scalar things were a subtype of AbstractScalar
,
and all out nonscalar things were not,
then we could just write:
aslist(x::AbstractScalar) = [x]
aslist(x) = x
But the types we are concerned with already have super-types (and you can only have one, not multiple inheritance here),
and are already declared.
Abstract supertypes are bit of a gun with only one bullet;
and that bullet needs to be fired when they are declared.
Instread we can use Traits.
There are packages for traits in julia,
but you don’t really need them.
We are just going to use Holy Traits (named for Tim Holy, who came up with the idea).
Example 2.2 Traits
A trait in julia is basically just a pure function of a type, which returns a typed value that is used for dispatch.
They are used to implement a bunch of rules for handling things related to indexing, broadcasting, iterators etc.
Traits are uesful because they let you make declarative statements about a type.
Declarative code is easy to write and read.
Also, note that they are fast.
Since they are pure functions of their input type,
and Julia compiles (and optimises) specialised versions of every function for each combination of input types,
they are compiled away to just being direct static dispatches to the targeted methods.
The trait functions themselves are not actually evaluated at runtime.
Explaining this is going to take a little bit,
but I think traits are an important concept as you move from basic use of julia to something more advanced.
They are are really expressive.
So I think they are worth understanding.
Types are values and so have a type
Before we start it is important to understand, is that types are first class in julia.
They are values and they thus have a type.
Input:
Output:
Input:
Output:
So the type of a type (such as String
) is DataType
.
A special thing for types though,
is they also act as if they are instances of the special type called Type
.
This is a parametric type,
and it basically has a rule that T <: Type{T}
.
Every type T
is considered as if it were a subtype of Type
with the parameter T
.
It can be used for value-type dispatch.
(Which I will not be going into here, much more,
but see my StackOverflow post on it)
Input:
Output:
Mostly, we will want to use triangular dispatch rules.
That is the form Type{<:AbstractString}
,
also written Type{T} where T<:AbstractString
,
which allows use to place type constraints on the type parameters.
Trait Types
To actually create the trait
we will need to define types for the trait.
This is what the trait function will return.
These should be concrete types.
They don’t need any fields – and indeed generally trait types shouldn’t have any fields if possible (it is better to give them type parameters.)
Though they could have super-types,
and is often good to give them a super-type to make them similar.
Input:
Trait Functions
We are now going to create the trait functions.
These should functions only of the type,
not of the value, so that they can be optimised away at compile time.
Input:
Output:
Nice, declarative code.
Users can add the scalarness type to their types
similarly.
Input:
Output:
Notice below that it is fully inferable and type-stable.
This will result it being optimised away at compile time during specialisation.
Input:
Output:
This is what makes it fast.
Dispatching on Traits
The whole reason we defined these is so we can use them for dispatch.
We will thus create three functions.
- One for
aslist
of scalar types, - one for
aslist
of nonscalar types, - and one to re-dispatch on the trait value.
We will begin with the last since it is the first that will be called.
Input:
Output:
Notice how the first is evaluating the trait function(on the type).
The return type of this is used for the dispatch to one of the other two.
Input:
Output:
Notice that the Set
was treated as a scalar, and wrapped in to an array.
Adding a new type is easy.
Input:
Output:
Part 3: Traits, falling back to hasmethod
A more advanced stratergy is would be to fall back to hasmethod
Input:
Input:
Output:
Now this makes may thing things work without having to define the scalarness trait,
though you would be surprised how many things have iterate
defined.
Input:
Output:
All number
types have the iterate function defined on them.
So we probably want to overwrite that.
Input:
Output:
Input:
Output:
Also, notice that it is now no longer a nice clean static dispatch.
Because it depends on the global state of the method table.
Which will mean that it has to resolve the trait at run-time.
So it will be slower.
Input:
Output:
Though types that we have defined an explict rule for will still be fast.
However, types that we have an more specific trait method for will still be fast,
since they will not hit the type-unstable fallback.
Input:
Output:
On a theoretical level, hasmethod
could be made type-stable and inferable;
which would allow for the static dispatch that we see for the explict cases.
This might be a thing in future versions of Julia.
It requires triggering recompilations of code depending on the lists of methods when they change.
There is some discussion of that here..
Part 4: Hard-core, reflecting upon methods
To avoid the dynamic dispatch that needs to be done for hasmethod
,
we could declare all the scalarness
of all types we know to have iterate
methods.
This can be done could use reflection and metaprogramming,
which will generate a set of trait methods,
based on the current state of the of method table.
Be warned this gets intense.
Notice the methods that exist for iterate: (I’ll just show the first five).
Input:
Output:
We can extract their parameter types.
Input:
Output:
Input:
Output:
Note that that this is not a Tuple value, that is a Tuple type.
First type-param is the function, and the rest are the arguments.
We are actually going to write dispatch based rules to create out trait functions.
Input:
Output:
Input:
Output:
Input:
Output:
Now we can go through and filter based on if try_get_single_argtype
returned nothing,
Input:
Output:
Notice however some of the types we found are from other modules – modules that are loaded but not in
a quick hack that lets use exclude those is to check if occursin(".", string(T))
.
Input:
Output:
Once we have out types we need to generate the code.
The following is a pretty hacky way to do so, abusing strings.
But does give a nice example of dispatch again.
Input:
Output:
Input:
Output:
Input:
Output:
Input:
Output:
Looks like good code that we could evaluate.
I know it doesn’t capture all cases,
but it is more than enough for demonstration.
Input:
Output:
So, this worked for most of them.
It would be possible to go back and tweak out metaprogramming to catch the last few.
Input:
Output:
Input:
Output:
Input:
Output:
So we have done this,
and generated a ton of methods.
And we avoid doing a dynamic dispatch on hasmethod
,
except as a fallback,
for types that were not loaded when our metaprogramming run.
A function could be exposed to rerun this.
The whole thing of metaprograming over reflection is kinda evil though.
But it is perhaps interesting to see how it can be done.