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 | » ]
Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

In Defense of Pattern Matching (View in Weblogs)
Posted: Jun 29, 2006 5:48 PM
Reply to this message Reply
Summary
Pattern matching is much maligned by object-oriented programmers. I wonder why?
Advertisement

As I wrote before, Scala aims to unify object-oriented and functional programming. When people talk about functional programming, they usually mean one of two different things: In the exclusive sense, functional means no side-effects. In the inclusive sense it means a programming style which composes functions in interesting ways. When I talk about functional programming, I usually mean it in the inclusive sense.

A number of language constructs are called functional because they are used a lot in functional languages or because they first appeared in a functional language. Three such features are:

  • functions as first-class values
  • parameterized types
  • pattern matching

When I talk to many advocates of object-oriented programming, they 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. Parameterized types are also very common, with variations such as C++ templates, or the generics of Eiffel, Java 1.5 or C# 2.0. But when I propose pattern matching, I get violent outbursts of rejection. The arguments against are usually a permutation of:

  1. Pattern matching is unnecessary, just use the visitor design pattern.
  2. Pattern matching is not extensible.
  3. Pattern matching breaks encapsulation .

I disagree, obviously.

``Pattern matching is unnecessary'' - Sure, one can use the visitor pattern to get something similar. But visitors require a lot of code scaffolding. Also, they don't allow nested patterns. To pick an example (complete code), let's say I want to simplify arithmetic expressions. Expressions are given by the following Scala class hierarchy:

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

There is a base class Term with four subclasses: Num for numbers, Var for variables, Mul for multiplication operations, and Add for addition operations. So the term (2 * x) would be represented as new Mul(new Num(2), new Var(x)).

Note that each of the four subclasses has a case modifier. This means we can pattern match on it, and also that we get an implicit factory method with the same name as the case class. With the factory methods, we can abbreviate the term above to Mul(Num(2), Var(x)).

Now let's say we want to implement some simplification rules on such terms. Two useful simplifications apply the equalities:

0 * x  =  0
1 * x  =  x

With pattern matching they can be expressed straightforwardly:

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

How much harder is this with a visitor? I invite you to try it out!

``Pattern matching is not extensible'' - This assumes that pattern matching can only be done on so-called algebraic datatypes which have a fixed number of cases. This is indeed the common approach in functional languages (an exception are polymorphic variants in OCaml). In Scala, however, any class can be labeled a case class. It would be perfectly possible to define other case classes that inherit from Term in different compilation units.

``Pattern matching breaks encapsulation'' - I think this is a misunderstanding in that people assume that pattern matching can inspect the internal fields of an object. But in Scala, pattern matching simply reverses the construction process. That is, you can find out through pattern matching what is the case class of the selector value and what are its constructor parameters. Any internal fields remain hidden. Also, if you don't want your clients to see the way an object was constructed, don't mark its class as a case class.

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.


Kay Schluehr

Posts: 302
Nickname: schluehk
Registered: Jan, 2005

Re: In Defense of Pattern Matching Posted: Jun 30, 2006 2:29 AM
Reply to this message Reply
I did not follow the discussions about pros and contras of FP style pattern matching in the OO community very closely.

I guess the crucial point about the discomfort with pattern matching is the same as with imperative conditionals and switches which match against exact values instead of organizing classes in extensible hierarchies and binding methods dynamically to instances. From this point of view FP still seems to be just a more consise way to replace classical imperative conditions in a declarative manner.

A funny idea I came along for pragmatic reasons and which I applied in a couple of projects ( starting with C++ and C# but providing also a short reference implementation in Python ) is that of chainlets [1]. Chainlets let me deconstruct the semantics of an imperative switch-statement, such that it works in an OO fashion. In case of chainlets there is no nominal class hierarchy but instances of the Chainlet class are organized to mimic class-hierarchies. Different to class hierarchies operators can be applied to combine chainlets for creating new ones. In a sense chainlets are "pure pattern". They exist for no other purpose than pattern matching but pattern matching in an OO fashion. The code that uses them looks suspiciously like good old imperative code - but it isn't.

http://www.fiber-space.de/EasyExtend/doc/gallery/gallery.html#3.1_Chainlets

Alexandre Tachard

Posts: 3
Nickname: alextp
Registered: Nov, 2005

Re: In Defense of Pattern Matching Posted: Jun 30, 2006 7:22 AM
Reply to this message Reply
The main problem with pattern matching in not-very-functional languages is "what are you matching against". In an OO language, say, you could match against an object's constructor, but the constructor may not uniquely specify an object.
In this Scala example, what would happen if the Term class is mutable? Or, rather, how would you specify what happens without forcing immutability/referencial transparency for type contructors/some other not-very-much-oo feature?
Well, at least this is the main reason I can come up with.

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: In Defense of Pattern Matching Posted: Jun 30, 2006 8:57 AM
Reply to this message Reply
> In this Scala example, what would happen if the Term class
> is mutable? Or, rather, how would you specify what happens
> without forcing immutability/referencial transparency for
> type contructors/some other not-very-much-oo feature?
> Well, at least this is the main reason I can come up with.

The Term class might have (mutable or immutable) fields besides the constructor parameters, but these are not matched.

It is also possible that the constructor parameters themselves are mutable. In the example
I gave, this could be expressed as follows:

case class Add(var l: Term, var r: Term)

The var modifier make l and r mutable. In that case, pattern matching
will retrieve the current values of l and r, not the initial ones.

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: In Defense of Pattern Matching Posted: Jun 30, 2006 9:08 AM
Reply to this message Reply
> I guess the crucial point about the discomfort with
> pattern matching is the same as with imperative
> conditionals and switches which match against exact values
> instead of organizing classes in extensible hierarchies
> and binding methods dynamically to instances.

That's a good point. OOP emphasizes the structuring model that all methods operating on some data are grouped in one class with the data. This makes it easy to extend the system with new data variants. FP ephasizes the structuring model where data and the functions operating on them are kept separate. This makes it easy to extend the system with new operations. Part of the difficulty in system design is to choose which solution is more appropriate. For arithmetic simplification, the functional pattern matching solution seems more appropriate because

- the syntax of terms changes rarely whereas new simplification rules might be added all the time

- the simplification rules themselves involve more than one object, so we cannot rely on dynamic (single-)dispatch alone to select them.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: In Defense of Pattern Matching Posted: Jun 30, 2006 9:15 AM
Reply to this message Reply
Martin-

I hate to hijack this thread but do have any control over the nablle scala forum? It's the only one I could find and I was unable to subscribe to it. I have some questions about some apparent inconsistencies between the documentation and the actual behavior but I don't think it's appropriate to further side-track your thread here.

thanks and I do apologize.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: In Defense of Pattern Matching Posted: Jun 30, 2006 9:44 AM
Reply to this message Reply
One of the things I have trouble with when you talk about 'pattern matching' is that I immediately think of regular expressions when I see that term. I've also written a arithmetic expression simplifier using regular expressions in Java and I have a bit of cognitive dissonance when I read these examples.

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: In Defense of Pattern Matching Posted: Jun 30, 2006 9:49 AM
Reply to this message Reply
The official mailing-list is scala@listes.epfl.ch. To find out how to subscribe:

http://listes.epfl.ch/cgi-bin/doc_en?liste=scala

Hope this helps

-- Martin

Harrison Ainsworth

Posts: 57
Nickname: hxa7241
Registered: Apr, 2005

pattern-matching is a bit low-level Posted: Jun 30, 2006 10:26 AM
Reply to this message Reply
The weakness of pattern-matching is that it is comparatively low-level.

In the basic-non-OO part of OCaml there seem to be three principal elements: functions, data structures, and pattern matching. In OO they are simplified and united, and form a single higher level element.

Having the mechanisms available separately enables them to be used more powerfully. But I think it is better to have a simpler, more restricted, but higher level -- larger -- building block.

However, something that *incorporates* more pattern-matching in OO -- like Scala appears to do -- is an appealing possibility.

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: pattern-matching is a bit low-level Posted: Jun 30, 2006 1:26 PM
Reply to this message Reply
I think that if people grumble about pattern matching, it's probably because of the 'open/closed principle'

If you add a new case class, aren't you pretty much obliged to hunt down all of the case clauses across your program and decide where you need to need to handle the new one? It's pretty much the reason why we favor polymorphism over switches in OO, to avoid that problem.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: pattern-matching is a bit low-level Posted: Jun 30, 2006 2:01 PM
Reply to this message Reply
> I think that if people grumble about pattern matching,
> it's probably because of the 'open/closed principle'
>
> If you add a new case class, aren't you pretty much
> obliged to hunt down all of the case clauses across your
> program and decide where you need to need to handle the
> new one? It's pretty much the reason why we favor
> polymorphism over switches in OO, to avoid that problem.

I was thinking this same thing and that if the language could support the case statements (not the classes) as Objects (and allow them to be mixed-in somehow) then you'd really have something.

Harrison Ainsworth

Posts: 57
Nickname: hxa7241
Registered: Apr, 2005

Re: pattern-matching is a bit low-level Posted: Jun 30, 2006 6:48 PM
Reply to this message Reply
> If you add a new case class, aren't you pretty much obliged to hunt down all of the case clauses across your program

Any such duplication could be factored into a single function. The weakness is that it is a 'smaller' concept. You would be, in effect, building a virtual dispatch mechanism manually. But a ready-made one attached to a larger conceptual structure is available with OO.

There would be greater scope for variations of course. Multi-dispatch for example. But they would be better as part of a larger pattern or structure.

Martin Odersky

Posts: 84
Nickname: modersky
Registered: Sep, 2003

Re: pattern-matching is a bit low-level Posted: Jun 30, 2006 7:01 PM
Reply to this message Reply
> > I think that if people grumble about pattern matching,
> > it's probably because of the 'open/closed principle'
> >
> > If you add a new case class, aren't you pretty much
> > obliged to hunt down all of the case clauses across
> your
> > program and decide where you need to need to handle the
> > new one? It's pretty much the reason why we favor
> > polymorphism over switches in OO, to avoid that
> problem.
>
> I was thinking this same thing and that if the language
> could support the case statements (not the classes) as
> Objects (and allow them to be mixed-in somehow) then you'd
> really have something.

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.

I guess my point is that extensibility and open/closed principle are not in conflict with pattern matching, as long as you do it the object-oriented way, that is, pattern match over a class hierarchy instead of a fixed set of alternatives.

-- Martin

Pasko Robert

Posts: 5
Nickname: pkr
Registered: Mar, 2005

Re: pattern-matching is a bit low-level Posted: Jul 1, 2006 10:35 AM
Reply to this message Reply
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 9: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!

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