Toivo Henningsson

This package is an attempt to provide method dispatch based on pattern matching for Julia. Bug reports and feature suggestions are welcome at https://github.com/toivoh/PatternDispatch.jl/issues.

In Julia, install the `PatternDispatch`

package:

```
Pkg.add("PatternDispatch")
```

Pattern methods are defined using the `@pattern`

macro. The method with the most specific pattern that matches the given arguments is invoked,
with matching values assigned to the corresponding variables.
The pattern method that is invoked is guaranted to be no less specific than
any other pattern method that matches.
Beyond that, no guarantees are made whatsoever about which method is invoked,
i.e. in the face of ambiguity, any of the most specific methods may be picked
at any given invocation.

Method signatures in pattern methods may contain variable names and/or
type assertions, just like regular method signatures.
(Varargs, e.g. `f(x,ys...)`

are not implemented yet.)
A number of additional constructs are also allowed.
Signatures can contain a mixture of variables and literals, e.g.

```
using PatternDispatch
@pattern f(x) = x
@pattern f(2) = 42
println([f(x) for x=1:4])
```

prints

```
[1, 42, 3, 4]
```

Using `show_dispatch(f)`

to inspect the generated dispatch code gives

```
const f = (args...)->dispatch(args...)
# ---- Pattern methods: ----
# f(x,)
function match1(x) # test_examples.jl, line 6:
x
end
# f(2,)
function match2() # test_examples.jl, line 7:
42
end
# ---- Dispatch methods: ----
function dispatch(x_1::Any)
match1(x_1)
end
function dispatch(x_1::Int64)
if is(x_1, 2)
match2()
else
match1(x_1)
end
end
```

A type tuple is allowed as a second argument to `show_dispatch`

to restrict
the set of dispatch methods printed,
e.g. `show_dispatch(f, (Int,))`

prints only the second method, since the first
one can never be triggered with an argument of type `Int`

.

Signatures can also contain patterns of tuples and vectors:

```
@pattern f2((x,y::Int)) = x*y
@pattern f2([x,y::Int]) = x/y
@pattern f2(x) = nothing
==> f2((2,5)) = 10
f2((4,3)) = 12
f2([4,3]) = 1.3333333333333333
f2((4,'a')) = f2([4,'a']) = f2(1) = f2("hello") = f2((1,)) = f2((1,2,3)) = nothing
```

A vector pattern will match any `Vector`

. To restrict to a given
element type, use e.g.

```
@pattern f([x,y]::Vector{Int}) = ...
```

The pattern `p~q`

matches a value if and only if
it matches both patterns `p`

and `q`

.
This can be used e.g. to get at the actual vector that matched a vector pattern:

```
@pattern f3(v~[x::Int, y::Int]) = [v,x*y]
==> f3([3,2]) = [[3, 2], 6]
f3(Any[3,2]) = [Any[3, 2], 6]
f3([3,2.0]) = nothing
```

Symbols in signatures are replaced by pattern variables by default
(symbols in the position of function names and at the right hand side of `::`

are not). To use the *value* of a variabe at the point of method definition,
it can be interpolated into the method signature:

```
@pattern f4($nothing) = 1
@pattern f4(x) = 2
==> f4(nothing) = 1
f4(1) = f4(:x) = f4("hello") = 2
```

A warning is printed if a new definition makes dispatch ambiguous:

```
@pattern ambiguous((x,y),z) = 2
@pattern ambiguous(x,(1,z)) = 3
```

prints

```
Warning: New @pattern method ambiguous(x_A, (1, z_A))
is ambiguous with ambiguous((x_B, y_B), z_B).
Make sure ambiguous(x_A~(x_B, y_B), z_B~(1, z_A)) is defined first.
```

- Pattern signatures can contain
- variables, literals, and type annotations
- unifications and tuples of patterns

- Dispatch on most specific pattern
- Generates dispatch code to find the most specific match for given arguments,
in the form of nested
`if`

statements - Leverages Julia's multiple dispatch to perform the initial steps of dispatch
- Warning when addition of a pattern method causes dispatch ambiguity
- Function to print generated dispatch code for a pattern function

- Provide a powerful and intuitive dispatch mechanism based on pattern matching
- Support a superset of Julia's multiple dispatch
- Generate fast matching code for a given collection of pattern method signatures
- Allow Julia's optimizations such as type inference to work with pattern dispatch

- Patterns for arrays and dicts
- varargs, e.g.
`(x,ys...)`

,`[x,ys...]`

etc. - Support for non-tree patterns, where the same variable occurs in several positions
- User definable pattern matching on user defined types
- Greater expressiveness: more kinds of patterns...

- Not yet terribly tested
- No support for type parameters a la f{T}(...)

Semantics:

- Pattern matching is conceptually performed on the arguments
tuple of a function call, e.g.
`(1,2,3)`

in the call`f(1,2,3)`

. - Equality of values is defined in terms of
`is`

, e.g.`@pattern f(3) = 5`

matches on`f(x)`

only if`is(x,3)`

.

Background:

- To be able to match a single pattern against a value,
the pattern has to provide
- a
*predicate*to check whether a given value matches, - a set of
*pattern variable*symbols, - a
*mapping*of input values to pattern variable values, valid for matching patterns.

- a
- To do most-specific pattern dispatch, patterns must also support
- a
*partial order*`p >= q`

, read as "p is less specific or equal to q", or "x matches q ==> x matches p, for any value x" - an
*intersection*operation`p & q`

; the pattern`p & q`

will match those values that match both`p`

and`q`

.

- a

Implementation aspects:

- Patterns are represented by
the operations needed to evaluate the matching predicate
and the mapping, in the form of a
DAG.
- Each
*node*is either- an
*operation*, such as to evaluate`isa(x,Int)`

or`x[3]`

, where`x`

is the result value of another node, or - a
*source*, such as a literal value or the pattern's input value.

- an
- Two nodes are equal iff they represent the same (sub-)DAG.

- Each
- A pattern is composed of
- a set of
*guard predicates*(boolean-valued nodes), such that the pattern matches iff all predicates evaluate to true, - a set of
*bindings*from symbols to nodes, to produce the mapping.

- a set of
- Two patterns are equal iff their guard sets are equal.
- Pattern intersection
`p & q`

forms the union of the guards sets of`p`

and`q`

. The result is simplified, e.g.`x::Number & ::Int`

reduces to`x::Int`

. `p >= q`

is evaluated as`(p & q) == q`

.

12/12/2012

about 2 months ago

156 commits