The relation between pattern matching and multiple dispatch

Internals & Design
1

Since not everybody is familiar with pattern matching here is an example of that feature:

factorial(0) = 1
factorial(n) = n * factorial(n -1)

It looks like a more powerful multiple dispatch right? That leads me to question what is the relation between PM and MD?

At first glance they look very similar. For example I could describe PM as MD on literals and also the other way around: MD as a PM on types.

Therefore it looks like that one is just natural extension of the other…

But how does this statement hold in practice? Can PM be implemented in terms of MD with little tweaking? Will it be efficient?

2 Likes
2

See [Value types](http://docs.julialang.org/en/latest/manual/types.html#\).

1 Like
3

For pattern matching, see GitHub - kmsquire/Match.jl: Advanced Pattern Matching for Julia

1 Like
4

You misunderstand me. I am not asking for julia implementation of pattern matching. I am asking about the relation between multiple dispatch and pattern matching…

1 Like
5

Dispatch works on types, pattern matching on values. At least from your examples given.
So the latter can be implemented with value types as linked above, at the expense of possibly creating one specialized function for each value that can be stored in the corresponding value type. Here, for an integer, that might be 2 to the power of 64 functions. Whether you consider this efficient is up to you.

1 Like
6

No. For example, how would you express f(n even), i.e. have a pattern for when n is even?

7

Your question is very vague and it is hard to see what it has to do with Julia.

3 Likes
8

Can PM be implemented in terms of MD with little tweaking?

Well, I’m not sure what “in terms of” means here, but see GitHub - toivoh/PatternDispatch.jl: Method dispatch based on pattern matching for Julia for an implementation. Note that it hasn’t been updated in a year, so it might have problems running on Julia v0.6 (and maybe even v0.5).

Cheers,
Kevin

9

They are indeed similar and someone (Oscar) has proposed something similar before.

The main issue though is on the “little tweaking” part. You can certainly implement something to do that in dispatch but it requires much more than “little tweaking” to make it fast.

In general, we implement features in local scope (i.e. not global scope) that can be optimized using the knowledge that the compiler can know. In general this is the type and not the value so the most important optimization we do in julia is to statically decide the method to call based on type info (and this includes inlining). For pattern matching, you need to use the value in additional to the type. In additional to express it in the method table, which is not possible now since they can only hold types, in order to have any hope of running this fast, you have to be able to identify the patterns that matters and compute an (reasonably) optimized conditional statement that do the matching at runtime.

I’m not saying it’s impossible. It almost certainly is but is absolutely not “little”. Given that such features can be implemented quite easily already we are unlikely going to add it to be part of dispatch unless someone can donate a nice implementation that can be easily optimized and run fast.

7 Likes
10

Also note that the pattern matching this way is almost certainly not going to be as expressive as conditions since that’ll make the dispatch undecidable and it’ll make every other dispatch slow, something we absolutely don’t want.

1 Like
11

@dpsanders Would you consider the following an example to use pattern matching in terms of (multiple) dispatch for your mentioned evenness pattern?

fn(::Val{true},  n) = "even $n"
fn(::Val{false}, n) = "odd $n"
fn(n) = fn(Val{n%2==0}(), n)

Or am I mixing things up here?

12

It is using dispatch for pattern matching and it’s highly recommanded against and very slow.

3 Likes