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 ]
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
Advertisement
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.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: pattern-matching is a bit low-level Posted: Jul 5, 2006 3:57 PM
Reply to this message Reply
@James Watson,

With the multiple dispatch demonstrated in the post above yours you can do what you want. The simplifier methods can be in any class and in any order. The methods can be added to at any time whilst the program is running by loading a class that contains more methods, i.e. referencing a new class, a class from another machine, etc.

damien morton

Posts: 15
Nickname: dmost
Registered: Jan, 2004

Re: In Defense of Pattern Matching Posted: Jul 6, 2006 6:59 AM
Reply to this message Reply
Very interesting stuff.

Ive been working on something similar myself, trying to leverage C# 3.0 features.

Unfortunately, it isnt possible to convert anonymous methods with statement blocks into expression trees, so the following sample wouldnt work with C# 3.0 as it stands.

Its a bit ugly, but heres a sample of how it might look:

Matcher match = new Matcher(
(int a, int b, int c) => Case(Foo(Bar(Baz(a,b,c),4,_))) >>
()=>{
Foo foo = new Foo();
for (int i = a; i < b; i += c)
foo.Add(new Bar(i));
return foo;
}),
(int a) => Case(Foo(Bar(Baz(a,_,_),_,7)))) >> ()=>Foo(a),
(Baz x) => Case(Foo(Bar(x),_,_))) >> ()=>x
);

Mauricio Noda

Posts: 1
Nickname: noda
Registered: Jul, 2006

Re: In Defense of Pattern Matching Posted: Jul 7, 2006 12:48 AM
Reply to this message Reply
<pre class="literal-block">
class Term
case class Num(n: int) extends Term
case class Var(name: String) extends Term
case class Mul(l: Term, r: Term) extends Term
case class Add(l: Term, r: Term) extends Term

def simplify(term: Term) = term match {
case Mul(Num(0), x) => Num(0)
case Mul(Num(1), x) => x
case _ => term
}
</pre>

Extensibility analysis:
If you add another subclass of Term, most patterns associated with Term will need another case and will break.
Poor extensibility.

Encapsulation analysis:
If class Num n field changes, it will affect constructor parameters and the simplify pattern will break.
If class Mul l field changes, it will affect constructor parameters and the simplify pattern will break.
If class Mul r field changes it will affect constructor parameters and the simplify pattern will break.
All other patterns associated with Term using Term subclasses constructors will break too.
If class Term changes everything will break. (an OO issue, not a pattern matching issue)
Poor encapsulation.


Alternative pure OO aproach using polymorphism and true delegation:
<pre class="literal-block">
public class Term {
Term simplify() {return this;}
Term simplifyMul(Mul mul) {return mul;}}

class Num extends Term {int n; Num(int n) {this.n = n;}
Term simplifyMul(Mul mul) {
if (n == 0) {return new Num(0);}
else if (n == 1) {return mul.getR();}
else {return mul;}}}

class Var extends Term {String name; Var(String name) {this.name = name;}}

class Mul extends Term {Term l; Term r; Mul(Term l, Term r) {this.l = l; this.r = r;}
Term getR() {return r;}
Term simplify() {return l.simplifyMul(this);}}

class Add extends Term {Term l; Term r; Add(Term l, Term r) {this.l = l; this.r = r;}}
</pre>

Extensibility analysis:
If you add another subclass of Term, coupling will be done through method overriding and won't break other classes.
Better extensibility.

Encapsulation analysis:
If class Mul r field changes it will break class Num, but thats it.
If class Term changes everything will break.
Encapsulation is not perfect here neither, but is a lot better than the pattern matching example.


The OO example was written in Java and so it has a lot more lines of code than the Scala example, but it is a Java issue, not an OO issue.

And NO, the Visitor pattern is not needed in this case, as it is not needed in most cases. Basic OO is enough most of the time.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: In Defense of Pattern Matching Posted: Jul 7, 2006 1:20 AM
Reply to this message Reply
@Mauricio Noda

> And NO, the Visitor pattern is not needed in this case, as
> it is not needed in most cases. Basic OO is enough most of
> the time.

But you have coded a visitor, if I rewrite:
Term simplify() { return l.simplifyMul( this ); }

As
Term simplify() { return l.accept( this ); }

You can see the visitor pattern, an accept with a this argument. The Term accepts a Mul visitor in the example.

But I agree with you that the Visitor formulation is quite good. Personally I prefer multiple dispatch to both, see my previous post.

Mark Grand

Posts: 1
Nickname: mgrand
Registered: Aug, 2009

Pattern matching is lower level than it needs to be Posted: Aug 1, 2009 11:17 AM
Reply to this message Reply
Scala pattern matching is based on static sequences of pattern constants. There is no good way to reuse sequences of patterns or to compute patterns.

In a dynamic & extensible system, it would be good to be able to drive navigation through a composable collection of computed patterns.

Oliver Plow

Posts: 3
Nickname: oliplow
Registered: Dec, 2012

Re: In Defense of Pattern Matching Posted: Dec 7, 2012 5:27 AM
Reply to this message Reply
> Pattern matching is much maligned by object-oriented
> programmers. I wonder why?

The reason is that some explanation is missing when pattern matching makes sense and when not. It seems like case classes make most sense when you have a finite number of possible cases defined in a simple hierarchy, much like an enumeration. The sample you make fits very well into this category. But when reading your article you get the impression that case classes are considered universal without limitations and the respective OO approach is not only redundant but also inferior.

If I develop a very sophisticated BTree, because I want to implement a database, I have no worries that the OO solution will give me the extensibility I need. I'm not sure here about case classes. I think somethink like this is what many OO programmers think when they read articles that say something like case classes are best. Some explanation is required what case classes are considered good for, pros and cons.

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