The Artima Developer Community
Sponsored Link

Weblogs Forum
In Defense of Pattern Matching

35 replies on 3 pages. Most recent reply: Dec 7, 2012 5: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 | » ]
Andy Dent

Posts: 165
Nickname: andydent
Registered: Nov, 2005

Re: In Defense of Pattern Matching Posted: Jul 1, 2006 10:19 PM
Reply to this message Reply
Advertisement
>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 2, 2006 1:43 AM
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 4: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 5: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 7: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 6: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 7: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 7: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 7: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 8: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 8: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 8: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 11: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.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: pattern-matching is a bit low-level Posted: Jul 3, 2006 5:43 PM
Reply to this message Reply
I think Scala is an excelent language and that it will influence future languages greatly. Having said that I agree with Pasko Robert who said he prefered Multiple Dispatch to patterns. The patterns example is coded below using my Pattern Enforcing Compiler (PEC):

http://pec.dev.java.net/nonav/compile/index.html

that implements the Multiple Dispatch pattern on top of standard Java.
public interface TermMD extends pec.compile.multipledispatch.MultipleDispatch {  // The methods in this interface are Multiply Dispatched
    Term binarySimplify( Term toTheLeft, Term toTheRight );
    Term unarySimplify( Term toTheRight );
}
public interface Term extends TermMD {  // The method in this interface is Singly Dispatched
    Term simplify();
}
public abstract class TerminalTerm implements Term {
    public final Term binarySimplify( Term toTheLeft, Term toTheRight ) { throw new AssertionError(); } // Method body replaced by PEC - with a multiple dispatch call
    public static final Term binarySimplify( final Term kind, final Term toTheLeft, final Term toTheRight ) { return kind; } // Default simplifier for unary terms - do nothing
    public final Term unarySimplify( Term toTheRight ) { throw new AssertionError(); } // Method body replaced by PEC - with a multiple dispatch call
    public static final Term unarySimplify( final Term kind, final Term toTheRight ) {  return kind; } // Default simplifier for binary terms - do nothing
    public Term simplify() { return this; } // Nothing to simplify for a terminal!
}
public abstract class UnaryTerm extends TerminalTerm {
    protected final Term toTheRight;
    protected UnaryTerm( final Term toTheRight ) { this.toTheRight = toTheRight.simplify(); }
    public Term simplify() { return unarySimplify( toTheRight ); }
}
public abstract class BinaryTerm extends UnaryTerm {
    protected final Term toTheLeft;
    protected BinaryTerm( final Term toTheLeft, final Term toTheRight ) {
        super( toTheRight );
        this.toTheLeft = toTheLeft.simplify();
    }
    public Term simplify() { return binarySimplify( toTheLeft, toTheRight ); }
}
public final class Zero extends TerminalTerm {}
public final class NaN extends TerminalTerm {}
public final class Var extends TerminalTerm {}
public final class Mult extends BinaryTerm {
    public Mult( final Term toTheLeft, final Term toTheRight ) { super( toTheLeft, toTheRight ); }
    public static final Term binarySimplify( final Mult m, final Zero z, final Term t ) { return z; } // 0 * x = 0
    public static final Term binarySimplify( final Mult m, final Term t, final Zero z ) { return z; } // x * 0 = 0
    public static final Term binarySimplify( final Mult m, final Zero z, final Zero z2 ) { return z; } // 0 * 0 = 0, needed to resolve conflict
    public static final Term binarySimplify( final Mult m, final NaN n, final Term t ) { return n; } // NaN * x = NaN
    public static final Term binarySimplify( final Mult m, final Term t, final NaN n ) { return n; } // x * NaN = NaN
    public static final Term binarySimplify( final Mult m, final NaN n, final NaN n2 ) { return n; } // NaN * NaN = NaN, needed to resolve conflict
    public static final Term binarySimplify( final Mult m, final NaN n, final Zero z ) { return n; } // NaN * 0 = NaN, needed to resolve conflict
    public static final Term binarySimplify( final Mult m, final Zero z, final NaN n ) { return n; } // 0 * NaN = NaN, needed to resolve conflict
}

The example is slightly expanded to show how conflicts are handelled. In particular 0 * 0, 0 * NaN, NaN * 0, and NaN * NaN. The multiple dispatch methods, the static mathods called binarySimplify and unarySimplify in the code can be in any class and can be seperately compiled. EG the power example:
public final class Power extends BinaryTerm {
    public Power( final Term toTheLeft, final Term toTheRight ) { super( toTheLeft, toTheRight ); }
    public static final Term binarySimplify( final Mult m, final Power pL, final Power pR ) { // x**z * y**z = (x * y)**z
        if ( pL.toTheRight == pR.toTheRight ) return (new Power( new Mult( pL.toTheLeft, pR.toTheLeft ), pL.toTheRight )).simplify();
        return m;
    }
}

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: pattern-matching is a bit low-level Posted: Jul 5, 2006 10:14 AM
Reply to this message Reply
> > 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.

I think I'm not making myself clear. This is probably a terrible idea but what if case classes could have mixin-methods? What I mean is instead of a separate Simplifier class, each case class would implment the simplification terms that applied to it (obviously some of the terms appy to mutliple types of term and that's a serious issue, I think). Then when the simplification method is called, all the term classes' simplification methods would be called (order? I don't know)

This would provide the same functionality but keep things very OO (as I am familiar with it.) Hopefully this explains my thoughts better but I haven't got a really complete solution to describe.

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-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us