Method dispatch using pattern matching v0.0

[Toivo Henningsson]

Over the past week, I've written some code to implement method dispatch using pattern matching in Julia: method signatures are patterns instead of argument lists (this is meant to be a generalization). Just as with native multiple dispatch, the method with the most specific signature is invoked, and a warning printed if there can be ambiguity.

Examples:
    # f(x) returns x, except for f(2) = 42:
    @pattern f(2) = 42
    @pattern f(x) =  x

    # g(a) returns x*y if x is a
    # 2-element Vector {x,y}; otherwise nothing:
    @pattern g({x,y}) = x*y
    @pattern g(x) = 2

    # eq(x,y) returns true iff x and y are equal:
    @pattern eq(x,x) = true
    @pattern eq(x,y) = false

There's already a fair bit of functionality (for a v0.0), though its not that thoroughly tested or fast (it does generate pattern <-> value matching code from each pattern, though). For more details, see the project github page:

https://github.com/toivoh/julia-pattern-dispatch

I'm writing this mail to announce the project, and because I'd like to know:
* Are people interested to use this kind of functionality?
* If so, what is required of the project before you would start using it?
* Any thoughts on proper syntax and semantics for pattern dispatch?
* What functionality do people want?
* What do you _not_ want the dispatch code to do?
* How important is speed as compared to expressiveness?
* Anything else?
Any feedback welcome!

Background/motivation:
I really love Julia's multiple dispatch, and the very axiomatic coding style that it often allows. In fact, I've become so addicted to it that I've started to shun if statements and to feel uneasy about long imperative method bodies.
This has brought me to try to create types for everything that I want to be able to dispatch on, but that's probably a bit of misuse of the type system. Also, you sometimes need more than type dispatch, as I've found out trying to implement some graph rewriting.
I think that an optional mechanism for pattern dispatch could help separate the decision of what types to use from what things you want to dispatch on. This kind of functionality also allows to dispatch on things that were not coded with a multitude of types, such as to dispatch on head types in ASTs.

[Jeff Bezanson]

Very cool. You're right that the best of all worlds is to define
patterns for basically anything you can imagine, then group the
patterns into types, and within that generate efficient matching code
to resolve the more dynamic patterns (e.g. specific numeric values).
Of course in theory the whole compiler could work that way and you
wouldn't need a "two level" system, but it's probably useful to have a
clear notion of what the compiler can figure out (types) and what it
can't (everything else). You can also look at it from the
specialization perspective. Obviously there are very few functions
we'd want specialized for every integer (though they do exist), so we
can use types to define what is specialized on by default.

[Tim Hoffmann]

Great. I am sure I would use it. 

Is there a way to put conditions in pattern like

@pattern f(0) = 42

@pattern f(x) = x //if x>0

@pattern f(x) = -x //if x<0

or more general a bool valued function that needs to evaluate to true on the match in order for the rule to apply? That would be powerful and nice to have, I think.

A common programming pattern in MATHEMATICA is something like this

f[0] = 1;

f[n_] := f[n] = n*f[n-1];

Putting the question aside wether one should do something like this, is it possible with your pattern approach?

Tim

[Toivo Henningsson]

On Monday, May 21, 2012 6:18:43 PM UTC+2, Tim Hoffmann wrote:

Great. I am sure I would use it. 

Glad to hear it!
 

Is there a way to put conditions in pattern like

@pattern f(0) = 42

@pattern f(x) = x //if x>0

@pattern f(x) = -x //if x<0

or more general a bool valued function that needs to evaluate to true on the match in order for the rule to apply? That would be powerful and nice to have, I think.

A common programming pattern in MATHEMATICA is something like this

f[0] = 1;

f[n_] := f[n] = n*f[n-1];

Putting the question aside wether one should do something like this, is it possible with your pattern approach?

 
Yes, I've been thinking about the same thing. (Any thoughts on a nice syntax for it?)
The most natural case to implement in the current setup would be to have independent assertions for each pattern value, which must all hold true for a match.
My current thinking has been to extend type qualifications like x::Int to domain qualifications, where a domain basically represents a set of possible values. Then your example might look like

@pattern f(0) = 42

@pattern f(x::when(x>0)) = x //if x>0

@pattern f(x::when(x<0)) = -x //if x<0

Arbitrary boolean conditions would of course be fine when deciding whether a single pattern matches.

With multiple methods for the same pattern function, I want to know if one signature is more specific than another. For that,  need to intersect domains. I guess the challenge is to express the domains {x;x > 0} and {x; x < 0} so that the intersection can be computed to be empty. Otherwise you might need to define @pattern f(x::when(x > 0 && x < 0)) to suppress the ambiguity warning.

[Toivo Henningsson]

On Sunday, May 20, 2012 11:26:27 PM UTC+2, Jeff Bezanson wrote:

Very cool. You're right that the best of all worlds is to define
patterns for basically anything you can imagine, then group the
patterns into types, and within that generate efficient matching code
to resolve the more dynamic patterns (e.g. specific numeric values).

I think it would be pretty straightforward to let multiple dispatch do the first filtering. Given an argument list (a pattern that is a tuple of type qualified variables), I can intersect it with the available patterns and create code for the dispatch that remains. (Pattern intersection is already there to find the most specific pattern.) I could take one such argument list from each pattern. (Would have to think about what happens if they cause ambiguity, but then there must be ambiguity in the patterns too, I think)

With nested patterns like (x, {y::Int, z::Float}), (x, {y::Real, z::Float}), it might also be an idea to recurse on the node {y, z} to generate a separate function that parses it with aid of multiple dispatch. Not sure if that's an optimization.
 

Of course in theory the whole compiler could work that way and you
wouldn't need a "two level" system, but it's probably useful to have a
clear notion of what the compiler can figure out (types) and what it
can't (everything else). You can also look at it from the
specialization perspective. Obviously there are very few functions
we'd want specialized for every integer (though they do exist), so we
can use types to define what is specialized on by default.

Yes, I agree that there's many functions where you would not want to let people override behavior for a single argument value etc. With the current setup, the first definition of a function decides whether its a regular/pattern function.

Pattern matching also involves a bit more magic, so I think it's a good thing to make it a conscious decision to use it. Keeping multiple dispatch as the default also gives the user a better insight into the workings of Julia, which will probably be helpful to make efficient use of pattern dispatch as well.

One question about speed: I'm currently letting

    @pattern f(x)=x

do

    const f = closure_for_pattern_dispatch_of_f

This is to make sure a regular method definition cannot override the pattern signatures. Do you think this is a good way to protect the pattern function?
 

[Viral Shah]

This would be really interesting if it is practical to be included in the language. It would then make it real easy to pick different algorithms for different problem sizes. Currently, we have inline code for multiplying 2x2 matrices, but it has to be thrown into a conditional, and adding more cases just gets ugly. If constraints could be supported, one could even have different algorithms for different types of inputs. And to dream - this would also open the door for a more general ATLAS style tuning of different codes on different architectures.

-viral

[Jeffrey Sarnoff]

So very good; and about halfway to Julia ∵ Julia(Julia).

[Jeffrey Sarnoff]

Here is colon-free a syntax suggestion for specifying conditions in patterns
             f( x | (x == 0) ) = 42
             f( x | (x >= 0) ) =  x
             f( x | (x <   0) ) = -x

On Sunday, May 20, 2012 8:48:26 PM UTC, Toivo Henningsson wrote:

[Toivo Henningsson]

On Thursday, May 24, 2012 4:28:07 PM UTC+2, Jeffrey Sarnoff wrote:

Here is colon-free a syntax suggestion for specifying conditions in patterns
             f( x | (x == 0) ) = 42
             f( x | (x >= 0) ) =  x
             f( x | (x <   0) ) = -x

Yes, I've thought about that one too. It reads pretty nice, but seeing as comprehensions have recently been changed from [x | x=1:5]  to [x for x=1 to 5], it would seem like a step backward. I might prefer something like

             f(x where x == 0) = 42
             f(x where x >   0) =  x
             f(x where x <   0) = -x

or

             f(x; where x == 0) = 42
             f(x; where x >   0) =  x
             f(x; where x <   0) = -x

But those are not valid ASTs right now, so I'll see what I can cook up that is. One possibility would be

             f(x ~where[x == 0]) = 42
             f(x ~where[x >   0]) =  x
             f(x ~where[x <   0]) = -x

I also want to be able to write something like

             f(x ~odd)      = 42
             f(x where>0) =  x

as shorthand for

             f(x where isodd(x)) = 42
             f(x where x > 0    ) =  x

respectively. Avoiding to duplicate the name of x sometimes aids readability/writability/maintainability.

[Toivo Henningsson]

On Thursday, May 24, 2012 6:37:19 AM UTC+2, Viral Shah wrote:

This would be really interesting if it is practical to be included in the language.

That would be really cool, once it's in shape for it.
I'm not sure what is required of code that goes into the language itself; haven't been able to find any contributor's guidelines.

I have tried to structure the code to have a minimal and extensible core for pattern matching. I guess that would help keep it smaller and more manageable.
I also suppose pattern dispatch could be loaded rather late, after the core functionality.
 

It would then make it real easy to pick different algorithms for different problem sizes. Currently, we have inline code for multiplying 2x2 matrices, but it has to be thrown into a conditional, and adding more cases just gets ugly.

I guess what pattern dispatch would contribute is to uncouple method declararations for different problem sizes etc, just as multiple dispatch uncouples method declarations for different type signatures.

It might also be possible to generate reasonably efficient dispatch code to find the right method for given arguments, with a little DP to create a reasonably low decision tree; at least in the absence of ambiguity warnings. This requires to intersect guard conditions from different methods, but that should be straightforward for e g inequality constraints on individual matrix dimensions.
 

If constraints could be supported, one could even have different algorithms for different types of inputs.

 
By type, I suppose you mean something finer than typeof(x)?

And to dream - this would also open the door for a more general ATLAS style tuning of different codes on different architectures.

I'm not really sure what this implies. Load different pattern methods/with different guard conditions depending what can be inferred about system characteristics?
 

[Jeffrey Sarnoff]

(typing out loud)
The next examples use 'when' rather than 'where';  There may be two conceptually distinguished, operationally distinct, mutually re-enforcing neighborhoods you are touching: one situated, one of duration/transition.

ok, how about

              f( when x == 0 ) = 42
              f( when x >   0 ) =  x
              f( when x <   0 ) = -x

     zero a is special case, it might have its own conditional tokens

             f( ~eql0 ) = 42                  f( ~eql(42) ) = Inf
             f( ~gtn0 ) =   x                  f(  ~gtn(42) ) = x
             f( ~ltn0 )   = -x                  f( ~ltn(-42) ) = -x
                                                     f( ~ ) = NaN              
                                                     f( ~ ) := f( otherwise )
   

what of partially external conditions in patterns (guards)?
f( where !hot(temp(motherboard))  when x > 1e7 ) = f( bignum(x) )

[Jeff Bezanson]

The type system is precisely that object model which the compiler knows everything about. If julia knew what x>0 meant, it would suddenly be a rather different language. If julia continues not to know what this means, then the functionality is not really part of the language, regardless of where or how it is implemented.
One might also wish to avoid having both declarative and imperative syntax for everything.
Not to discourage all this of course; scheme has its various case-lambdas and whatnot.

[John Cowan]

On Thu, May 24, 2012 at 11:34 AM, Jeffrey Sarnoff
<jeffrey...@gmail.com> wrote:
> (typing out loud)

> The next examples use 'when' rather than 'where';  There may be two
> conceptually distinguished, operationally distinct, mutually re-enforcing
> neighborhoods you are touching: one situated, one of duration/transition.
>
> ok, how about
>
>               f( when x == 0 ) = 42
>               f( when x >   0 ) =  x
>               f( when x <   0 ) = -x

I like this best so far, but I also like "f = 42 if x == 0", which is
Pure style.

--
GMail doesn't have rotating .sigs, but you can see mine at
http://www.ccil.org/~cowan/signatures

[Toivo Henningsson]

On Thursday, May 24, 2012 6:38:25 PM UTC+2, Jeff Bezanson wrote:

The type system is precisely that object model which the compiler knows everything about. If julia knew what x>0 meant, it would suddenly be a rather different language.

Yes, I've been thinking about this too. I guess it might actually be too much even to assume that you know what x>0 means when x::Int; someone might have overloaded it.

A more modest way to go about it would be something like

    @pattern f(x ~equalto(2))       = 42
    @pattern f(x ~greaterthan(2)) = x
    @pattern f(x ~lessthan(2))      = x

Here, equalto(), greaterthan(), and lessthan() would create Domain objects (at the point of definition). These would be provided by the user (me). x ~dom would basically be short for (@assert has(dom,x); x) -- a generalization of type assert to other kinds of domains. Since I write these domain types to deal with subsets of the real line, I can also code them to know how to intersect with each other.

Still, julia does know what && and || means, (and could know what ! means if it were restricted to the basic Bool -> Bool form). So I could still do some basic mangling of general boolean conditions, like seeing that

    @pattern f(x where isodd(x), y) = x
    @pattern f(x, y where iseven(y)) = y

requires exactly

@pattern f(x where isodd(x), y where iseven(y)) = ...

to resolve the ambiguity.
 

If julia continues not to know what this means, then the functionality is not really part of the language, regardless of where or how it is implemented.

Of course. I took it that Viral meant to make it a part of the standard library.

One might also wish to avoid having both declarative and imperative syntax for everything.
Not to discourage all this of course; scheme has its various case-lambdas and whatnot.

I'm not quite sure what you mean by this, are you referring to guard conditions vs conditionals in a function body?
All that the pattern dispatch stuff really amounts to is syntactic sugar, (but potentially very useful sugar, I think!) maybe you can say the the decoupling of pattern methods goes a little beyond that.
 

[John Cowan]

On Thu, May 24, 2012 at 3:14 PM, Toivo Henningsson <toiv...@gmail.com> wrote:

> All that the pattern dispatch stuff really amounts to is syntactic sugar,
> (but potentially very useful sugar, I think!) maybe you can say the the
> decoupling of pattern methods goes a little beyond that.

I think that pattern dispatch (which is really dispatching on types
whose position in the type lattice is not known until run time) is
only really useful if you can define the cases in separate places and
have Julia merge them into single LLVM functions. That's what Pure
does.

Since the compiler can't figure out the "proper" order of matches for
arbitrary predicates, you end up having to lay down an arbitrary rule
like "first written, first processed", which is what Pure uses, though
I often wish for "first written, *last* processed" at the REPL, which
would allow me to add special cases after writing down the general
case.

I would be slow to provide pattern methods until the advantages and
limitations are fully hashed out.

[Stefan Karpinski]

I would be most interested in providing methods for specific *values* rather than general conditionals, which is what Mathematica allows. We already allow this for types, by writing `sizeof(::Type{Foo}) = 42` which is, of course, less nice than dispatching on a value. The obvious thing you'd want to write is `sizeof(Foo) = 42` — but that would mean that Foo is a parameter name with type Any, so some other syntax would be necessary.

Dispatching on values could be compiled into efficient LLVM code without relying on ordering. However, it seems like it doesn't buy you that much — it's really not that hard to just write checks in the appropriate method body. It's mainly just an elegant way to write recursion base cases, which is nice.

[John Cowan]

On Thu, May 24, 2012 at 3:41 PM, Stefan Karpinski <ste...@karpinski.org> wrote:

> I would be most interested in providing methods for specific *values* rather
> than general conditionals, which is what Mathematica allows. We already
> allow this for types, by writing `sizeof(::Type{Foo}) = 42` which is, of
> course, less nice than dispatching on a value.

That could be achieved within the current framework by loosening
Type{} to accept a value that is not a type. Then to handle 42 as a
special case you'd just write a method whose argument type is
Type{42}. This is what CLOS calls EQL types, and they can be very
useful, especially with nominal data, where you can just add a new
method rather than rewriting a conditional in an existing method when
you add a new nominal value.

BTW, the name Type{} is inconsistent with the convention of writing
*Kind for the types of types. You should either change it to Kind{},
or (better IMHO) change CompositeKind to CompositeType. After all, if
the type of all integers is called Integer, the type of all composite
types should be called CompositeType, I think.

[Patrick O'Leary]

On Thursday, May 24, 2012 2:50:55 PM UTC-5, John Cowan wrote:

BTW, the name Type{} is inconsistent with the convention of writing
*Kind for the types of types.  You should either change it to Kind{},
or (better IMHO) change CompositeKind to CompositeType.  After all, if
the type of all integers is called Integer, the type of all composite
types should be called CompositeType, I think.

Type{T} is not the type of T, it is the instance of the type Type parameterized by T. So Type{T} is a type just like Array{T} is a type, rather than a kind.

[Jeff Bezanson]

Yes, it is a kind but I didn't want to be too pedantic.

[Jeff Bezanson]

Actually it is hard to say since julia doesnt strictly separate types and kinds the way a "real" type system would. The type of a value is also a value, so the type of a type is also a value, a type, and a kind.

[Stefan Karpinski]

I'd just throw out there that the fact that a type, conceptualized as a set of objects, can't be an element of itself in ZFC indicates to me that ZFC is an inappropriate basis for theories of types (rather than the traditional conclusion that a type cannot be its own type).

[John Cowan]

[Consolidated reply]

On Thu, May 24, 2012 at 4:06 PM, Patrick O'Leary
<patrick...@gmail.com> wrote:

> Type{T} is not the type of T, it is the instance of the type Type
> parameterized by T.

Fair enough. But I still think singleton types should be generalized
to all objects, precisely because it neatly allows the special
handling of specific values using the existing type machinery.

> So Type{T} is a type just like Array{T} is a type,
> rather than a kind.

Parameterized or not, Type is a type of types, which is how "kind" is
defined elsewhere in the language. That only counts if the decision
is to keep the *Kind names, which I am against anyway.

On Thu, May 24, 2012 at 4:27 PM, Jeff Bezanson <jeff.b...@gmail.com> wrote:

> Actually it is hard to say since julia doesnt strictly separate types and
> kinds the way a "real" type system would. The type of a value is also a
> value, so the type of a type is also a value, a type, and a kind.

Right, which is why I propose the *Kind names be changed to *Type.
There is no real distinction between types of types and kinds of types
in a dynamic typing system.

On Thu, May 24, 2012 at 4:33 PM, Stefan Karpinski <ste...@karpinski.org> wrote:

> I'd just throw out there that the fact that a type, conceptualized as a set
> of objects, can't be an element of itself in ZFC indicates to me that ZFC is
> an inappropriate basis for theories of types (rather than the traditional
> conclusion that a type cannot be its own type).

In Smalltalk, there is a loop in the iterated instance->class
function. 5 isa SmallInteger which isa SmallInteger class (the
metaclass of SmallInteger) which isa Metaclass which isa Metaclass
class which isa Metaclass which ...

("You are not expected to understand this." --sjc || dmr)

This happens because all metaclasses (which in Smalltalk carry the
class variables and methods, so there is one metaclass for every
class) are instances of Metaclass, including the metaclass of
Metaclass itself.

[Patrick O'Leary]

On Thursday, May 24, 2012 4:50:02 PM UTC-5, John Cowan wrote:

[Consolidated reply]

On Thu, May 24, 2012 at 4:06 PM, Patrick O'Leary
<patrick...@gmail.com> wrote:

> Type{T} is not the type of T, it is the instance of the type Type
> parameterized by T.

Fair enough.  But I still think singleton types should be generalized
to all objects, precisely because it neatly allows the special
handling of specific values using the existing type machinery.

> So Type{T} is a type just like Array{T} is a type,
> rather than a kind.

Parameterized or not, Type is a type of types, which is how "kind" is
defined elsewhere in the language.   That only counts if the decision
is to keep the *Kind names, which I am against anyway.

I suppose that for any Type{T}, T inhabits Type{T}, so it does work as a kind. It does work as the second argument of isa() if the first argument is a type, which makes it a kind. In retrospect, I'm quite wrong here, as isa(T, Type) for any T is true, which didn't register despite having used the multiple dispatch equivalent. Yielded. That said, I believe it's the kind *, which I'm used to reading as "type," so Type seems like a perfectly cromulent name. (Cue counterexample...)

[Toivo Henningsson]

On Thursday, May 24, 2012 9:29:48 PM UTC+2, John Cowan wrote:

> All that the pattern dispatch stuff really amounts to is syntactic sugar,
> (but potentially very useful sugar, I think!) maybe you can say the the
> decoupling of pattern methods goes a little beyond that.

I think that pattern dispatch (which is really dispatching on types
whose position in the type lattice is not known until run time)

I don't see how this differs between julia's multiple dispatch and my pattern dispatch; I've rather thought of the difference as between
restricting signatures to be tuples of type qualified (unrepeated) variables,
vs allowing signatures that are composed of atoms, variables (qualified by type or other domains), and composite types recursively built from these.
 

is only really useful if you can define the cases in separate places and
have Julia merge them into single LLVM functions.  That's what Pure
does.

I think that should definitely be doable. Not sure whether it's the best way to leverage julia's type inference though; you probably want a function call upon entry to the method body to specialize on the actual argument types.
The part with defining cases in separate places I'm all for. (That works already)

 

Since the compiler can't figure out the "proper" order of matches for
arbitrary predicates, you end up having to lay down an arbitrary rule
like "first written, first processed", which is what Pure uses, though
I often wish for "first written, *last* processed" at the REPL, which
would allow me to add special cases after writing down the general
case.

But with some discipline on the part of the user, it can figure out the proper order!
I've chosen to take julia's lead from multiple dispatch: dispatch to the method with the most specific signature that matches the arguments.

    signature1 <= signature2  <==>  any value that matches signature1 matches signature2 also

Dispatch on signature_i such that

    signature_i matches the argument
    no signature_j <= signature_i matches the argument

This  is only unambiguous if the signatures form a semilattice, but otherwise I can give an informative warning message when a method that introduces an ambiguity is declared, including the signature that will break the ambiguity.
From my experience with julia so far, explicitly avoiding ambiguity in this way works very well, so I think it is well worth the cost of a few additional method declarations (or rethinking your design).
It does put some restrictions on the kind of guard conditions that you can use however, since the system must intersect them to determine the <= relation on signatures.

When you gather all method declarations at the same place, it might be ok to list them in order of priority. But if you want to declare a pattern function that others should be able to overload, I think it will quickly break down, since changing the order of loading modules/packages would change the dispatch rule.

I also think that having a semilattice of signatures can be quite helpful for efficient dispatch: I could exploit this structure to often create a much shorter decision sequence than linear search through the patterns.

I would be slow to provide pattern methods until the advantages and
limitations are fully hashed out.

 That's one of the reasons I initiated this discussion; glad that so many want to participate!

[Toivo Henningsson]

On Thursday, May 24, 2012 5:34:41 PM UTC+2, Jeffrey Sarnoff wrote:

(typing out loud)
The next examples use 'when' rather than 'where';  There may be two conceptually distinguished, operationally distinct, mutually re-enforcing neighborhoods you are touching: one situated, one of duration/transition.

ok, how about

              f( when x == 0 ) = 42
              f( when x >   0 ) =  x
              f( when x <   0 ) = -x

There has to be something that tells that x is the name of the argument. To me, in f(when x > 0), x>0 is just a boolean expression.
On the other hand,

              f( x when x>0 ) = x

marks it clearly enough, and I would consider

              f( x when>0 ) = x

as a shorthand for this.

On the other hand, as Jeff pointed out, it might be unsafe to assume something like !((x > 0)&&(x < 0)), since > and < can be overloaded.
An unambiguous way to write it would be

    f(x when  (x<=0) &&  (0<=x) ) = 42 # x == 0
    f(x when !(x<=0) &&  (0<=x) ) =  x # x >  0
    f(x when  (x<=0) && !(0<=x) ) = -x # x <  0

In the case that !(x<=0) && !(0<=x), f(x) would give an undefined method error.
It should be possible to shorten these predicates to look something like x==0, x>0 and x < 0.
 

     zero a is special case, it might have its own conditional tokens

             f( ~eql0 ) = 42                  f( ~eql(42) ) = Inf
             f( ~gtn0 ) =   x                  f(  ~gtn(42) ) = x
             f( ~ltn0 )   = -x                  f( ~ltn(-42) ) = -x
                                                     f( ~ ) = NaN              
                                                     f( ~ ) := f( otherwise )
   

what of partially external conditions in patterns (guards)?

 

    f( where !hot(temp(motherboard))  when x > 1e7 ) = f( bignum(x) )

 
In principle, external values would be pretty straightforward to implement as additional, implicit, function parameters. Whether it's advisable to do so is more than I know; it does introduce a degree of impurity into the method definitions that use it.

There's also a question of syntax, of course. In the current/planned syntax, motherboard would be taken as a pattern variable, and the evaluation of !hot(temp(...)) would be done once, at the point of function declaration. A possibility would be to write it as

    f(x where currentvalue(!hot(temp(motherboard)))  when x > 1e7 ) = f( bignum(x) )
 
I did have syntax similar to currentvalue before I introduced dispatch on most specific pattern.

[Jeffrey Sarnoff]

Any suggestion that really would introduce impurity is withdrawn.

Instead of  f( x when>0 ) for f( x when x>0 ),
bring back the tilde, let it tie the argument to the condition,
carrying 'x when x' as 'x~x' and identifying the function arg:

        f( x~x>0 )

--

[david tweed]

I note that all the examples given have just one conditioned argument. My understanding is that one of the intricate (although not that complex) things in, eg, a Haskell compiler, is factoring out implicit common elements of guards so they aren't evaluated more than once.

Eg, in

data Tree a=Lf | Nd a

f Lf Lf=0
f (Nd _) Lf=1
f Lf (Nd _)=2
f (Nd _) (Nd _)=3

there's only one test against the first argument being Lf, one for snd being Lf and then the dispatching uses those values. (Actually, its a bit more complicated due to laziness, but ignore that). So in researching any possible design for Julia I'd definitely consider multi-argument matching in figuring the issues to solve.

[Toivo Henningsson]

On Saturday, May 26, 2012 8:51:15 PM UTC+2, david tweed wrote:

I note that all the examples given have just one conditioned argument. My understanding is that one of the intricate (although not that complex) things in, eg, a Haskell compiler, is factoring out implicit common elements of guards so they aren't evaluated more than once.

Eg, in

data Tree a=Lf | Nd a

f Lf Lf=0
f (Nd _) Lf=1
f Lf (Nd _)=2
f (Nd _) (Nd _)=3

there's only one test against the first argument being Lf, one for snd being Lf and then the dispatching uses those values. (Actually, its a bit more complicated due to laziness, but ignore that). So in researching any possible design for Julia I'd definitely consider multi-argument matching in figuring the issues to solve. 

Thanks. I haven't got quite that far with the code generation yet :) but I'll definitely consider it when the time comes.

 

[tor]

This looks very nice. Just one thought. Would it be possible to make it multi-line, so that one could write something like

@patterns (

f (n where n == 0) = 1

,

f(n where n>0 ) = n + f(n-1)

,

g (x) = 2x+1

,

h (x) = 3x-2

)

That is, pass a tuple or list of assignment expressions to the macro? (I haven't written any macros yet, so I'm uncertain how they work).

[Patrick O'Leary]

Macros take one or more expressions as an argument. Prevailing style for multiple statements is to use the statement grouping begin...end:

@patterns begin

    f (n where n == 0) = 1

    f(n where n>0 ) = n + f(n-1)

    ...
end

[Tor Gausen]

That is very beautiful!

[Michael Fox]

And then, after all of that discussion and development -- for no conceivable reason -- the idea died. Never to be seen or heard from again. The end.

On Monday, July 9, 2012 6:31:47 AM UTC-7, tor wrote:

That is very beautiful!

[Toivo Henningsson]

It is not dead. There is PatternDispatch.jl, the successor to julia-pattern-dispatch. And there is also Match.jl, with a different take on pattern matching. I haven't had much time to devote to this since I started my new job in January, but I've recently started toying with some new ideas for improved pattern dispatch. We'll see if it turns into something. Search the julia-dev archives for PatternDispatch to turn up some more discussions. (perhaps there are a few more than those)

 / Toivo

[Abram Demski]

Hi all,

Checking up on this. I've been getting into Julia and would personally love for pattern dispatch to be standard. I'm a fan of Pure and would be very happy to see more of that style enabled here.

Reading through the thread, I understood that there were some obstacles (I also see in a couple of other threads). I'd like to ask the naive question: what's stopping Julia from using Pure's approach?

Best,

Abram

[Toivo Henningsson]

Can you describe a little bit what is Pure's approach?

[Kevin Squire]

Can you describe a little bit what is Pure's approach?

I think that explains why Julia is not using Pure's approach. :-)

Pure's a little bit obscure, but my understanding (from a brief exploration a while ago) is that it is based mostly on pattern matching + term rewriting.  I found it quite elegant, but was discouraged (at the time) from using it for anything serious because it wasn't very fast. 

Abram, is that what you meant by "Pure's approach", or did you meant something more specific?

Macro's give the rewriting part of that ability now, but the pattern matching part is generally still lagging.

In a slightly different direction, there has been discussion of attempting to match and simplify complex mathematical expressions, which would seem to be in Pure's domain, but I can't find the pointer right now.

Cheers,

   Kevin

[Abram Demski]

Kevin, Toivo,

In Pure, functions are defined by what amounts to multi-dispatch via patterns, allowing an algebraic term-rewriting style. I recall that this is implemented via some form of optimized decision tree.

Ah, found a reference:

http://purelang.bitbucket.org/quickref/pure-quickref.pdf

There is a note about the evaluation algorithm on the final two pages, which cites this paper:

http://pure-lang.googlecode.com/svn/docs/rtapaper.pdf

John Cowan made this comment about Pure's technique earlier in the thread:

I think that pattern dispatch (which is really dispatching on types 

whose position in the type lattice is not known until run time) is 

only really useful if you can define the cases in separate places and 
have Julia merge them into single LLVM functions.  That's what Pure 
does. 

Since the compiler can't figure out the "proper" order of matches for 
arbitrary predicates, you end up having to lay down an arbitrary rule 
like "first written, first processed", which is what Pure uses, though 
I often wish for "first written, *last* processed" at the REPL, which 
would allow me to add special cases after writing down the general 
case. 

Another thing which Pure does, which probably fits less well with Julia (as it stands), is to simply halt evaluation when no re-writes apply, so for example if you enter "x" and the variable hasn't been assigned a value, you just get "x" back. Similarly, f(1,2) => f(1,2) if f hasn't been given a definition which applies to those arguments. This makes "undefined" cases useful: they are actually constructors. I like this, but I'm guessing it wouldn't play well with Julia's way of doing things.

My understanding is that Pure is fairly slow mainly because it doesn't do any type inference and never intends to. The pattern-matching itself is fairly fast.

[Lucas Garron]

This is also one of my favorite features of Mathematica.

Expression-based/pattern-matching programming can give you a lot of that "it just works" flexibility when you're exploring a problem.

(Mathematica also has well-defined typesetting, so it's really easy to define yourself some nice syntactic sugar, but that's less relevant for Julia.)

Unfortunately, Mathematica isn't free (Wolfram Language doesn't really give you the same power), and I don't know of a great online writeup about this topic.

»Lucas Garron