The Artima Developer Community
Sponsored Link

Weblogs Forum
In Defense of Pattern Matching

35 replies on 3 pages. Most recent reply: Dec 7, 2012 2:27 AM by Oliver Plow

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 35 replies on 3 pages [ « | 1 2 3 | » ]
Pasko Robert

Posts: 5
Nickname: pkr
Registered: Mar, 2005

Re: pattern-matching is a bit low-level Posted: Jul 1, 2006 7:35 AM
Reply to this message Reply
Advertisement
I think this is a nice example where FP and OO have have found their own ways of solving equivalent problem: the OO solution is IMO multiple dispatch - since in OO variant types do not have long tradition and people were using subtyping to achieve that effect (and MD is just other way to say what to do with different "variants"/subclasses), while in FP pattern matching came as natural solution.

And the reasons why multiple dispatch did not found its place in modern OO languages are probably mostly practical (e.g. that's what Stroustrup says in Design&Evolution of C++).

Imam Alam

Posts: 3
Nickname: uchchwhash
Registered: Jul, 2006

Re: In Defense of Pattern Matching Posted: Jul 1, 2006 6:40 PM
Reply to this message Reply
well, I guess my personal objection is simple: classes are not merely tuples. in Scala, for example, the tuple view is somewhat forced on the programmer (in Java you have several constructors, that would, in effect, demand several patterns to match against). but I guess a truly scalable language should have tuples to make life simpler.

but overall it's a surprize to me why people would not be able to appreciate the conciseness of (Scala-style) pattern matching with inferred types.
if(object instanceof Person) {
  Person person = (Person)object;
  String name = person.getName();
  int age = person.getAge();
  ...
}

against
case Person(name, age) => ...

:)

I think the best thing about Scala patterns is that it is just a syntactic sugar saving the programmer for doing worthless things. the above examples are equivalent. please correct me if I'm wrong. but I suppose promoting the sugar aspect will help people realize that there is nothing wrong with it: no OO principle whatsoever is being violated.

cheers!

Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: In Defense of Pattern Matching Posted: Jul 1, 2006 7:19 PM
Reply to this message Reply
>Pattern matching is much maligned by object-oriented programmers.

I have been an OO programmer since 1992 and a regular reader of books and articles in the field. Either your point is a strawman or I am missing something because I haven't encountered such maligning. However, my work has been in Object Pascal, C++, Python and REALbasic. I do very little with Java and am certainly not an idiomatic Java developer.

Could you be a bit more specific about which community is maligning pattern matching please and especially if this extends beyond the Java camp, who I suspect you are talking about.

I'd also be intrigued to see a list of OO design books these people have studied beyond the basic Design Patterns.

A quick Google on "pattern matching" functional programming templates c++ turns up some interesting sites.

Kay Schluehr

Posts: 302
Nickname: schluehk
Registered: Jan, 2005

Re: In Defense of Pattern Matching Posted: Jul 1, 2006 10:43 PM
Reply to this message Reply
> but overall it's a surprize to me why people would not be
> able to appreciate the conciseness of (Scala-style)
> pattern matching with inferred types.
>
> if(object instanceof Person) {
>   Person person = (Person)object;
>   String name = person.getName();
>   int age = person.getAge();
>   ...
> }
> 

> against
>
> case Person(name, age) => ...
> 

> :)

Because the code snippet above is considered as an imperative relict and therefore as crap among many OO programmers. The usual recommendation is to refactor it into a method that keeps a parameter of type Person and let the framework dynamically dispatch to the method.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: pattern-matching is a bit low-level Posted: Jul 2, 2006 1:44 PM
Reply to this message Reply
> But you can do that: Simply use standard overriding with
> super calls for the pattern matching functions. In my
> simplification example, let's assume we ant to add a new
> case class
>

> case class Power(l: Term, exp: Term)
>

> Let's say we ant to also add the simplification rule
>

> x**z * y**z = (x*y) ** z
>

> You'd implement this by subclassing the Simplifier class:
>

> class PowerSimplifier extends Simplifier {
> override def apply(term: Term): Term = term match {
> case Mul(Power(x, z1), Power(y, z2)) if z1 == z2 =>
> Power(Mul(x, y), z1)
> case _ =>
> super.apply(term)
> }
> }
>

>
> Furthermore, with factory methods, you could make sure
> that in a system with Power nodes you always used the
> PowerSimplifier to simplify terms. It's not necessary to
> go back to the old simplifier methods and change them.

That's not really what I meant. Suppose I have taken your simplifier class and added operations and simplifications. Then I later purchse a third-party library that also extends from your initial set of classes and simplification rules. Unless I'm missing something, there's no way to mix in the new rules and types without going back and modifying my custom types and libraries.

What I was thinking was more of a system where the cases are actually Objects and can be mixed-in dynamically but with the power of the pattern matching that you already provide. The main problem with this would be that I don't know how you could control the order of evaluation (given you don't know the complete set of rules) and that often (as in the given example) the rules and types are very much coupled together.

I guess I'm not really complaining about the pattern-matching but more wishing for something.

PS. If what i am talking about here is already possible in Scala, I'd love to be enlightened.

Kay Schluehr

Posts: 302
Nickname: schluehk
Registered: Jan, 2005

Re: pattern-matching is a bit low-level Posted: Jul 2, 2006 2:28 PM
Reply to this message Reply
> What I was thinking was more of a system where the cases
> are actually Objects and can be mixed-in dynamically but
> with the power of the pattern matching that you already
> provide. The main problem with this would be that I don't
> know how you could control the order of evaluation (given
> you don't know the complete set of rules) and that often
> (as in the given example) the rules and types are very
> much coupled together.

Chainlets, which I linked in my response to Martin, provide a small aspect of what you were asking for ( there are just 2 operators to combine chainlets to create new ones ). They realize proper OO-ish pattern. The evaluation order doesn't matter here - for the prize of evaluating all conditions in order to find the best match ( at least in case there isn't an exact match ) before applying a dedicated rule. The costs would still increase if chainlets permit more complex expressions. Hence keeping chainlets small and using just few of them in a single statement is recommended.

Imam Alam

Posts: 3
Nickname: uchchwhash
Registered: Jul, 2006

Re: In Defense of Pattern Matching Posted: Jul 2, 2006 4:10 PM
Reply to this message Reply
> Because the code snippet above is considered as an
> imperative relict and therefore as crap among many OO
> programmers. The usual recommendation is to refactor it
> into a method that keeps a parameter of type Person and
> let the framework dynamically dispatch to the method.

I see what you mean. even though I haven't read much OO books, makes sense to me. but I think the issue remains when you don't have the opportunity to modify someone else's code. even though this pattern matching is not pure OO (I'm convinced, the more I think about it), it should be useful in some circumstances.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: In Defense of Pattern Matching Posted: Jul 3, 2006 3:54 AM
Reply to this message Reply
> readily embrace the first two. After all, functions as
> first-class
> values are also found in Smalltalk (where they are called
> blocks),
> Python, or Ruby. The next version of C# is going to have
> them, and I
> would not be surprised if a future version of Java also
> acquired
> them.

Without a desire to nitpick, but doesn't C# in version 2.0 already supports anonymous delegates?

> <p>So, in summary I think pattern matching is extremely
> convenient and is
> a good fit with object-oriented programming. I wonder why
> not more
> mainstream languages have adopted it.</p>

In my opinion object-oriented programming, pattern-matching and if/switch statements are quite similar, if not the same. One can think of object-orientation as a mechanism for pattern-matching on classes: "if the class is a button then paint button else if the class is a text box paint a text box" etc.

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: In Defense of Pattern Matching Posted: Jul 3, 2006 4:12 AM
Reply to this message Reply
Andy Dent wrote:

> >Pattern matching is much maligned by object-oriented
> programmers.
>
> I have been an OO programmer since 1992 and a regular
> reader of books and articles in the field. Either your
> point is a strawman or I am missing something
> because I haven't encountered such maligning.

I am not sure whether maligning is the right word. These were fiendly personal discussions with people from various OO camps (including people programming in Java, Self and Smalltalk). In these discussions I encountered many times the same arguments against pattern matching, which I listed in my blog.

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: pattern-matching is a bit low-level Posted: Jul 3, 2006 4:28 AM
Reply to this message Reply
James Watson wrote:

> What I was thinking was more of a system where the cases
> are actually Objects and can be mixed-in dynamically but
> with the power of the pattern matching that you already
> provide. The main problem with this would be that I don't
> know how you could control the order of evaluation (given
> you don't know the complete set of rules) and that often
> (as in the given example) the rules and types are very
> much coupled together.
>
> I guess I'm not really complaining about the
> pattern-matching but more wishing for something.
>
> PS. If what i am talking about here is already possible in
> Scala, I'd love to be enlightened.

If I understand you correctly, you want to be able to combine independent extensions of data and operations.
You can do this with mixin composition. Let's assume we have a base system of algebraic terms, with a simplifier.

class Simplifier {
def apply(term: Term): Term = term match {
...
}
}

Now, let's say I extend the base system with new case classes and a new simplifier:

class MySimplifier extends Simplifier {
def apply(term: Term): Term = term match {
case ... => ...
case ... => ...
case _ => super.apply(term)
}
}

The new simplifier handles all the cases I care about in my extension. If none of the new cases match, it passes control to super.
As an independent extension, you add other case classes and another simplifier:

class YourSimplifier extends Simplifier {
def apply(term: Term): Term = term match {
case ... => ...
case ... => ...
case _ => super.apply(term)
}
}

Now, if I want to combine my extensions with your extensions, I can combine the two simplifiers as follows:

class CombinedSimplifier
extends MySimplifier with YourSimplifier

This will thread the super calls through all simplifiers. I.e. in

(new CombinedSimplifier).apply(aterm)

first, your simplification rules will be tried; if none of them matches, my extended simplification rules will be tried, and if none of these matches, the base simplification rules will be tried.

This behavior also resembles a lot Kay's chainlets, I think.

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: In Defense of Pattern Matching Posted: Jul 3, 2006 4:32 AM
Reply to this message Reply
> Without a desire to nitpick, but doesn't C# in version 2.0
> already supports anonymous delegates?
>
That's correct. But I thought true closures that also capture local variables are only to appear in C# 3.0.

-- Martin

Russ Freeman

Posts: 7
Nickname: freemanr
Registered: Jul, 2006

Re: In Defense of Pattern Matching Posted: Jul 3, 2006 5:12 AM
Reply to this message Reply
To me, this is a simple case where Scala is offering more flexibility over dispatch.

Whereas Java only offers dispatch varying on a static hierarchy, Scala is doing it with a dynamic hierarchy and thus gives you more flexibity.

If you consider the example terms, these are really just subtypes of Term, yet subtypes that only exist dynamically when there terms are configured with this state.

This is like modelling something that would usually be only an instance of a more general class as an explicit subtype, something I often do during domain analysis before I've chosen the target language e.g.:

class Person {}
class Martin extends Person{}
class Russ extends Person{}

or to be more specific with the example:-

class Term {}
class Num extends Term {}
class Var extends Term {}
class Mul extends Term {}
class Add extends Term {}
class MulByZero extends Term {}
class MulByOne extends Term {}

Kay Schluehr

Posts: 302
Nickname: schluehk
Registered: Jan, 2005

Re: pattern-matching is a bit low-level Posted: Jul 3, 2006 5:33 AM
Reply to this message Reply
I'm not sure if we understand each other correctly. Are case classes derivable? Can a new case class RealNum be created by deriving from Num to represent real numbers ( or floats if you want )? If Num and RealNum where chainlets RealNum would be matched according to the subtype relation whereever a case statement is defined that matches Num. That's what we would expect from typical class based inheritance. But when both Num and RealNum are present evaluation order is important:


case class Num(f:float) : extends Term
case class RealNum(f:float) : extends Num


def simplify(term: Term) = term match {
case Num(x) => Num(0)
case RealNum(x) => Floor(x)
case _ => term
}


If evaluation order actually matters the RealNum case would be shadowed by the Num case. This might either cause a compiler error or an internal reordering that promotes the most special case to the top.

Russ Freeman

Posts: 7
Nickname: freemanr
Registered: Jul, 2006

Re: pattern-matching is a bit low-level Posted: Jul 3, 2006 5:49 AM
Reply to this message Reply
Personally, I don't know until I learn Scala (soon hopefully). I just saw an obvious pattern there, which is that you can apparently specify different behaviour for a "virtual" subtype.

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: pattern-matching is a bit low-level Posted: Jul 3, 2006 8:14 AM
Reply to this message Reply
Kay Schluehr wrote:

> I'm not sure if we understand each other correctly. Are
> case classes derivable?

You can inherit from a case class, for instance like this:

class RealNum(val v: float) extends Num(x.toInt)

In that case, an instance of the subclass matches the superclass pattern. For instance, the following is legal

new RealNum(1.1) match {
case Num(x) => System.out.println(x)
}

and would print 1.

At present, the class that inherits from a case class may not itself be a case class. This restriction was introduced to speed up pattern matching -- because of it, we can translate a `match' statement to a `switch' over tags. We are thinking of dropping that restriction. As long as it is there, one would have to re-formulate your example slightly as follows:

def simplify(term: Term) = term match {
case Num(x) => Num(0)
case x: RealNum => Floor(x.value)
case _ => term
}

The second case above is a "typed pattern". It matches
any selector value whose type conforms to the given type. It's basically the same as a match of an exception in a `catch' clause.

> If evaluation order actually matters the RealNum case
> would be shadowed by the Num case. This might either cause
> a compiler error or an internal reordering that promotes
> the most special case to the top.

In Scala, the ordering does indeed matter.

Flat View: This topic has 35 replies on 3 pages [ « | 1  2  3 | » ]
Topic: Five-minute Multimethods in Python Previous Topic   Next Topic Topic: Service Locator Pattern Revisited, Part 2

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use