"I have a mind like a steel... uh... thingy." Patrick Logan's weblog.

Search This Blog

Saturday, August 11, 2007

On Pattern Matching

An aspect of Erlang that is often mentioned but seldom highlighted, and fairly unrecognized for its contribution is pattern matching. Languages implementors that wish to achieve Erlang-like concurrency in their own language's runtime will also have to come to terms with Erlang's simple message selection mechanism based on pattern matching.

Again this is where an implementation like Termite, based on Lisp (Scheme) can work as well as Erlang. Other languages not so much, but some creative use of syntax and meta-programming in Smalltalk, Python, and Ruby might do the job.

Other languages not so much. Especially those modern curly braced ones, which will likely have pattern matching piled-on in their next set of features, this time to seem more Erlang-like. Either Java or C# will add this first, then the other language implementors will be compelled to meet or exceed the first.

Either way, they've all got a long way to go. I'd bet on several Lisps and on Smalltalk to keep up most easily.


Vladimir Sedach said...

I think that pattern matching of one sort or another is a kind of
fundamental tool for loosely coupled distributed systems. It's a
central feature of Erlang, but interestingly enough not of Hewitt's
original Actors model (where an actor's/process's handling of messages
was described more like a state machine transition). What is really
interesting is that it is also a central feature of
Linda/tuplespaces. Given that C-Linda was a more or less an ok
language, I think that it's unfair to say that "curly braced
languages" are going to have undue trouble with pattern matching.

This does present one mystery that has been tugging at my mind for
some time now: out of the three fundamental paradigms for distributed
systems, which I consider to be Actors, tuplespaces, and
data-parallelism (I don't consider "traditional" (whatever that is
supposed to mean in the context of emerging computer practice and
science) approaches to concurrency like semaphores and locks a
fundamental paradigm, since the only places they can be practically
implemented as fundamental mechanisms is in very small-scale
multiprocessor systems), only data parallelism can get away without
any pattern matching in a practical implementation.

The obvious answer is that data parallelism is a paradigm for tightly
and not loosely coupled distributed systems, and the more abstract way
of stating that is that data parallelism cannot handle non-determinism
very well. Since reading Hillis and Steele's Data Parallel Algorithms,
I'm convinced there is a deeper reason for it, and that reason lies in
the relationship of data parallel and sequential programming.

Back to pattern matching, I should say that it's not all fun and
games. I think pattern-directed invocation in functional languages can
invite abuse, particular when mixed with Erlang-like record
constructs. If you have a bunch of functions that pattern-match on a
record of a specific type, and you later want to extend them to handle
records of another but similar type (think inheritance here), it is
not fun. Likewise, it makes refactoring a pain.

Patrick Logan said...

I guess one thing somewhat working in erlang's favor on evolution of record types is that ultimately they are just tuples. The record syntax is just a convenient syntax.

In practice I don't know what that actually does for you. The difference between theory and practice, in theory is...

Vladimir Sedach said...

...unfortunately confirmed by bitter experience. I didn't have the most pleasant introduction to Erlang (to be specific, I was trying to extend the graphics primitives in Wings 3d to four dimensions; maybe I just bit off more than I could chew at that time).

Blog Archive

About Me

Portland, Oregon, United States
I'm usually writing from my favorite location on the planet, the pacific northwest of the u.s. I write for myself only and unless otherwise specified my posts here should not be taken as representing an official position of my employer. Contact me at my gee mail account, username patrickdlogan.