Extractor functions

[nystrom]

This PR implements extractor functions for Rematch.

Patterns can use extractor functions (also known as active patterns). These are just any function that takes a value to match and returns either nothing (indicating match failure) or a tuple that decomposes the value. The tuple is then matched against other patterns.

An extractor function must have a lowercase name to distinguish it from a struct name. [I'd like to relax this requirement, if possible, but we should discuss.]

An extractor function must take one argument--the value to be matched against--and should return either one value (for nullary and unary patterns), or a tuple of values (for 2+-ary patterns). Returning nothing indicates the extractor does not match.

For example to destruct an array into its head and tail:

function Cons(xs)
    if isempty(xs)
        nothing
    else
        ([xs[1], xs[2:end]])
    end
end

@match [1,2,3] begin
    ~Cons(x, xs) => @assert x == 1 && xs == [2,3]
end

The main code changes are in handle_destruct for the T_(subpatterns__) case.

[cscherrer]

This looks really nice @nystrom . Am I understanding right that the semantics are that

@match foo begin
    cons(x, xs) => bar
end

is equivalent to

@match cons(foo) begin
    (x, xs) => bar
end

so it seems the function is converted to its inverse? I haven't used active patterns much, is this a common way to write things?

[nystrom]

Those two cases are equivalent. Yes, the extractor is basically the inverse of the constructor. But you can't just call the inverse function directly on the scrutinee after @match because you need to call different functions in different case arms. For example:

@match foo begin
   cons(x, cons(y, ys)) => foo
   cons(x, xs) => bar
   [] => baz
end

calls cons on foo in both the first and second patterns, but not in the third.

[nystrom]

I was thinking that rather than using uppercase/lowercase to distinguish between structs and extractors, we could just prepend an operator like ~.

@match foo begin
   ~Foo(x,y,z) => ... # call extractor Foo
   Foo(x,y,z) => ... # match struct Foo
end

I'm converting this back to a draft PR.

[amirsh]

@nystrom this is really nice :) looking forward to see it merged :D

[nystrom]

Thanks @rai-nhdaly and @amirsh for the comments/review.

I haven't really been pushing this since we've basically worked around its absence for a while now, and I'm no longer sure I'll even use it since extractors will not work with the type dispatch macros I layered on top of Rematch in the compiler. I'd like to actually back-port the type dispatch code into Rematch but haven't had the time.

Sorry @rai-nhdaly I don't like your syntax proposal :-) It doesn't look much like pattern matching to me anymore. The whole idea is to make the pattern look like the code used to construct the scrutinee of the match, but with free variables for constructor arguments. At least that's what I'm used to in functional languages. I tried to stay as close to the Scala behavior as possible.

I'll merge this when I'm back from vacation.

[amirsh]

@NHDaly sure.

Regarding the syntax, I totally agree with @nystrom . The proposed syntax matches better with the one from Scala and F#.

One minor comment is that the last part of the README file is broken due to a missing ```.

Please let me know once the code is available for review.

[nystrom]

I fixed the missing quote, thanks.

[ghost]

Excellent. Like i said, i don't have much experience with those other systems, so i trust your gut - sorry for the drama. :)

Enjoy the vacation!! :)