www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - A plea for pattern matching

reply KlausO <kobi goppertsweiler.de> writes:
be honest, have you ever written code like this in any of your D projects ?

//-------------------------------------------------
auto refer = cast(ExpectedClass)node;
if (null !is refer)
{
// do something
...
}
//-------------------------------------------------

Recently I implemented a small declarative domain specific language in D.
I got to the semantic passes and had to deal with AST traversal.
My first thought was to use the visitor pattern. But my AST
class hierarchy was still in flux and maintaining a visitor framework
while your node classes changes is a pain.

So I employed the above cast at some points in my semantic passes, but 
every time
I look at this code it has the smell of a dirty hack.
I do not know where this feeling comes from exactly, but maybe it is the 
knowledge
that this kind of code is some kind of poor man's pattern matching.

Other languages like ML and Haskell support algebraic data types which
directly address problems where you need recursive data structures. And
with pattern matching they support a save and elegant way to traverse them.
(Even Oberon had a simple form of pattern matching with so called
message records and a with statement with type guards.)

Other languages like PLT Scheme come with a library which implements pattern
matching.

In the OO world there are some efforts to achieve the same. Either 
implemented as
preprocessors or as language extensions. Some examples are:

C++
 - Memphis preprocessor  (see [1]).

Java
  - JMatch (see [2])

But IMHO the most well thought out approach of pattern matching in an OO 
environment
is implemented in the Scala language. There is a paper [3] and a 
dissertation [4]
by Burak Emir [5] which describes the use cases and the solution in detail.

If you look at the source of compilers implemented in languages that 
supports pattern matching you will notice that their code is extremely 
compact. Most of this compactness
is IMO reached through pattern matching expressions within the different 
compiler
passes. The compiler expands these expressions internally to decision 
trees and then
to nested checks with the attached actions.
Safety is achieved at compile time through static analysis and/or at runtime
through exceptions  similar to the SwitchError exception in D.


"Active Patterns" extension [6].

Will we see this feature in D one day in the (hopefully near) future ?
Thank you for your comments

KlausO


[1] http://memphis.compilertools.net/
[2] http://www.cs.cornell.edu/Projects/jmatch/
[3] http://lamp.epfl.ch/%7Eemir/written/patmattrans.pdf
[4] http://library.epfl.ch/theses/?nr=3899
[5] http://burak.emir.googlepages.com/
[6] http://research.microsoft.com/apps/pubs/default.aspx?id=70422
Dec 25 2008
next sibling parent KlausO <kobi goppertsweiler.de> writes:
KlausO schrieb:


 "Active Patterns" extension [6].


Sorry, this is not correct, they worked at the same time on this and
may have influenced each other, see
http://blogs.msdn.com/dsyme/archive/2006/08/16/ActivePatterns.aspx


KlausO
Dec 25 2008
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
KlausO, I like limited forms of pattern matching, I have asked for them in D in
the past; they also fit with the growing functional nature of D2.
But I've seen the pattern matching you can see for example in Scala adds lot of
complexity to the compiler (and some to the language too), and D2 is already a
quite complex language. So I am not sure it's a good thing to add it to D2.

Bye,
bearophile
Dec 25 2008
parent KlausO <kobi goppertsweiler.de> writes:
bearophile wrote:

 KlausO, I like limited forms of pattern matching, I have asked for them in D
in the past; they also fit with the growing functional nature of D2.
 But I've seen the pattern matching you can see for example in Scala adds lot
of complexity to the compiler (and some to the language too), and D2 is already
a quite complex language. So I am not sure it's a good thing to add it to D2.

 Bye,
 bearophile
   


Maybe you are right, but the part that deals with pattern matching
in the Scala compiler is quite small compared to the rest of the compiler.

Funny: Advanced Scala concepts like extractor objects with it's
fixed named apply/unapply methods looks a bit like D's operator overloading.
And case classes seems to be syntactic sugar which makes the programmers
live easier by implicitly declaring an extractor object and some
overloaded functions (equals, hashCode, toString) to identify the class 
type.
IMHO most of this is already contained as meta data in D's type descriptors.
Greets,


KlausO
Dec 26 2008