Re: Implementation Language Choice

Gabriel Dos Reis wrote:


> Joachim Durchholz <joachim.durchholz@web.de> writes:
>
>> [...] it's beyond me why [pattern matching] never made it into
>> mainstream imperative languages; it's exceedingly useful.
>
> Probably because people have been using the more general Visitor
> Pattern?


It's just the other way round: pattern matching is more general than
Visitor.


Visitor is for iterating through collections of polymorphic data.
Pattern matching is for inspecting and acting upon a single instance
of some polymorphic data. Actually it's the reverse of OO-style
polymorphism: in OO, the set of operations is fixed and the set of
types is extensible; pattern matching assumes a fixed set of types and
an extensible set of operations.


Here's how pattern matching works:


1. You define a union of record types. Something like
            Tree = Leaf value: int | Node left: Tree; right: Tree
which translates to a record with a "selector" field that distinguishes
the "int" case from the "left: Tree; right: Tree" case, and a memory
area that either contains the int or the two Tree fields. (I tried to
write this in C, but the syntax got so riddled with irrelevant detail
that I decided to stick with the prose description.)


2. Whenever your code does something with a Tree data object, it does
pattern matching, like this:
      case t of
          Leaf i: ... // Do something with i.
          Node l, r: ... // Do something with l and r.
      end
The "i" above gets bound to the "int" field in the Tree (Leaf variant)
record.
The "l" and "r" above get bound to the "left" and "right" fields in the
Tree (Node variant) record.


The nice thing about pattern matching is that it does in one fell swoop
what you want anyway: detect which case is at hand, and access the
fields in it in some handy local variables because you don't want to
write t->value, t->left, t->right all over the place.
Even nicer is the following: accessing t->value in the "l, r" branch
would be perfectly valid C, and require a run-time check in Pascal; with
pattern matching, "i" is out of scope in the "l, r" branch and vice
versa, so any accidental misuse will be caught at compile time.


Regards,
Jo
--
Currently looking for a new job.

Return to the comp.compilers page.
Search the comp.compilers archives again.