A plea for pattern matching

KlausO kobi at goppertsweiler.de
Thu Dec 25 12:54:52 PST 2008


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.

The Scala implementation has already influenced the F# team to create the
"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



More information about the Digitalmars-d mailing list