Functional-style pattern matching

[Little Walker]

Hi there,

I've been looking around to see if there's been any discussion of
introducing functional programming-style pattern matching for method/
function dispatch. Could someone point me to any such discussions?

I've seen that perl6 is taking on a lot of ideas from the functional
world (lazy evaluation for instance). With multi-method dispatch on
the agenda pattern matching seems inevitable but I haven't been able
to find information about this or any related discussions.

This is a contrived example of what I'm referring to:

sub traverse([Leaf $a]) {
# do something
}

sub traverse([Tree $left, Tree $right]) {
traverse($left);
traverse($right);
}

my $t = Tree(...);
traverse($t);

---

Many thanks!

[Matthew Walton]

I think the closest things we've got to pattern matching come from a
combination of multiple dispatch, where clauses and signature
unpacking. I don't know much about the latter, but a where clause can
discriminate multiple dispatch variants based on parameter values
rather than just the type, so you can say:

multi doSomething(@a where { .elems == 0 }) {
# empty arrays only
}

multi doSomething(@a where { .elems >= 3 && .[2] == 4 }) {
# arrays with a third element numerically equal to 4
}

multi doSomething(@a) {
# anything else
}

Which is pretty powerful, really.

> This is a contrived example of what I'm referring to:
>
> sub traverse([Leaf $a]) {
>  # do something
> }
>
> sub traverse([Tree $left, Tree $right]) {
>  traverse($left);
>  traverse($right);
> }
>
> my $t = Tree(...);
> traverse($t);

You could do most of this with multidispatch and where clauses. It
doesn't quite work because of the unpacking which pattern matching
does, and also because Perl 6 data structures don't get built in the
same way that Haskell ones do, and you've used a Haskell-like syntax
for Leaf and Tree and so forth.

Now, while it might be nice to say let me write a signature which
accepts a Tree object which has a left and right subtree, and binds
them to $left and $right respectively, arguably a where clause can
check that the subtrees exist, and your tree class should have good
accessors for the subtrees which make unpacking them a little
pointless. This is where Perl 6 is not the same as functional
languages, since it's got an imperative OO element as well.

multi traverse(Tree $t where { all(.left, .right).defined }) { ... }

Perhaps.

[Larry Wall]

On Mon, Mar 08, 2010 at 12:45:44PM -0800, Little Walker wrote:
: Hi there,

:
: I've been looking around to see if there's been any discussion of
: introducing functional programming-style pattern matching for method/
: function dispatch. Could someone point me to any such discussions?

Why settle for discussion when you can have specs? See the
Parameters and Arguments section of:

http://perlcabal.org/syn/S06.html

: I've seen that perl6 is taking on a lot of ideas from the functional

: world (lazy evaluation for instance). With multi-method dispatch on
: the agenda pattern matching seems inevitable but I haven't been able
: to find information about this or any related discussions.
:
: This is a contrived example of what I'm referring to:
:
: sub traverse([Leaf $a]) {
: # do something
: }
:
: sub traverse([Tree $left, Tree $right]) {
: traverse($left);
: traverse($right);
: }
:
: my $t = Tree(...);
: traverse($t);

That's almost exactly the example from:

http://perlcabal.org/syn/S06.html#Unpacking_tree_node_parameters

In fact, a grep of the specs for any of 'Tree', 'traverse', or
even 'left.*right' would have found it.

If any of you wants a greppable version of the specs, use svn to checkout

http://svn.pugscode.org/pugs

and then look in docs/Perl6/Spec.

Larry

[Timothy S. Nelson]

On Tue, 9 Mar 2010, Daniel Ruoso wrote:

> Em Seg, 2010-03-08 às 12:45 -0800, Little Walker escreveu:
>> I've been looking around to see if there's been any discussion of
>> introducing functional programming-style pattern matching for method/
>> function dispatch. Could someone point me to any such discussions?
>

> a Tree matching language is on discussion for about three years already
> (I remember discussing this during YAPC::EU 2007). We have considered
> several things including XPath/XSLT but haven't come to any viable
> conclusion.

I'm planning to write a Tree module, but I'm waiting for Rakudo to
stabilise a bit (ie. to catch up after the -ng branch). I have some code
written already, but it relies on features that aren't implemented yet, and I
haven't gotten around to coding workarounds.

:)

---------------------------------------------------------------------
| Name: Tim Nelson | Because the Creator is, |
| E-mail: way...@wayland.id.au | I am |
---------------------------------------------------------------------

----BEGIN GEEK CODE BLOCK----
Version 3.12
GCS d+++ s+: a- C++$ U+++$ P+++$ L+++ E- W+ N+ w--- V-
PE(+) Y+>++ PGP->+++ R(+) !tv b++ DI++++ D G+ e++>++++ h! y-
-----END GEEK CODE BLOCK-----

[Moritz Lenz]

Hi,

Little Walker wrote:
> I've been looking around to see if there's been any discussion of
> introducing functional programming-style pattern matching for method/
> function dispatch. Could someone point me to any such discussions?

It's done multi dispatch in Perl 6, and you can find an introduction in
a book chapter which we're writing these days:

http://github.com/perl6/book/blob/master/src/multi-dispatch.pod

> I've seen that perl6 is taking on a lot of ideas from the functional
> world (lazy evaluation for instance). With multi-method dispatch on
> the agenda pattern matching seems inevitable but I haven't been able
> to find information about this or any related discussions.
>
> This is a contrived example of what I'm referring to:
>
> sub traverse([Leaf $a]) {
> # do something
> }
>
> sub traverse([Tree $left, Tree $right]) {
> traverse($left);
> traverse($right);
> }
>
> my $t = Tree(...);
> traverse($t);

You got it almost right. The simples approach is to use "normal" matching:

multi traverse(Leaf $a) {
# do something
}

multi traverse(Tree $t) {
traverse($t.left);
traverse($t.right);
}

The latter uses a bit of additional code for unpacking the $t parameter;
you can do that in a signature too (which is not yet covered in the book
chapter; you can find some documentation here:
<http://perlcabal.org/syn/S06.html#Unpacking_tree_node_parameters>)

multi traverse (Tree $t ( $left, $right) ) {
traverse($left);
traverse($right);
}

Since you don't actually access $t anywhere, there's no reason to give
it a name, so you can write this actually as

multi traverse (Tree $ ( $left, $right) ) {
traverse($left);
traverse($right);
}

Hope that helps,
Moritz
--
Moritz Lenz
http://perlgeek.de/ | http://perl-6.de/ | http://sudokugarden.de/

[Little Walker]

> That's almost exactly the example from:
>
>    http://perlcabal.org/syn/S06.html#Unpacking_tree_node_parameters

1. I feel incredibly embarrassed to have missed this
2. This is awesome!

[Little Walker]

> Which is pretty powerful, really.

Absolutely - I think you're referring to the 'type subset' stuff which
is great.

> This is where Perl 6 is not the same as functional
> languages, since it's got an imperative OO element as well.

True, there can be friction between the functional style and OO, but
look at how Scala manages it with case classes. When you look at the
implementation, really it boils down to syntactic sugar but then so do
many of the cool new features in Perl 6!

I bring this up because when thinking of what will be possible with
lazy evaluation, junctions, named parameter shorthand, closures, etc.,
etc., somehow pattern matching screams out at me. It can be concise,
expressive and unambiguous, and very complementary to Perl 6's
existing feature set. I know a lot of work went into bringing
functional and OO together to make Scala happen, so certainly there
may be impracticalities in just 'adding pattern matching'.

Scala case classes: http://www.scala-lang.org/node/107 or
http://programming-scala.labs.oreilly.com/ch06.html#CaseClasses

[Mark J. Reed]

Does the unpacking participate in dispatch? If a Hash comes in as $t
with no 'left' key, will it fail to match?

--
Mark J. Reed <mark...@gmail.com>

[Carl Mäsak]

Mark (>):

> Does the unpacking participate in dispatch?  If a Hash comes in as $t
> with no 'left' key, will it fail to match?

Yes.

$ perl6 -e 'sub foo(%h($left)) { say $left }; foo({ left => "OH HAI" })'
OH HAI

$ perl6 -e 'sub foo(%h($left)) {}; foo({ no => "left key" })'
Not enough positional parameters passed; got 0 but expected 1
[...]

The error message is perhaps slightly LTA, but at least Rakudo
(correctly) fails to match.

// Carl

[Mark J. Reed]

Oh, wow. I was just asking about the spec; didn't know this stuff
already worked. Rakudos to the team! :)

--
Mark J. Reed <mark...@gmail.com>

[Moritz Lenz]

Mark J. Reed wrote:
> Oh, wow. I was just asking about the spec; didn't know this stuff
> already worked. Rakudos to the team! :)

Actually there's quite much that works in Rakudo, even if some corner
cases are missing or error messages might benefit from more verbosity.

Especially in the area of grammars, multi dispatch and object system
there's a whole there are really surprising things you can do.

Cheers,
Moritz