One of the things which has been puzzling me is how to
pattern match abstract data types. This puzzle reawakened
by considering RAList.
An RAList, like a list, supports functions:
empty ()
cons (elt, list)
and it supports
isempty (list)
head (list) when not isempty
tail (list)
and also uncons = head,tail.
Now the secret of list pattern matching is that
empty () => 0, ()
cons (elt,list) => 1, (elt,list)
in other words, the constructors
Empty = 0
Cons = 1,
and the terms constructed are just tuples:
constructor, argument
so a pattern match says:
if run time constructor tag
= 0, then empty() was called, argument is ()
= 1, then cons was called, so argument is (elt, list)
and given the argument is at a known offset just after the tag,
we can just cast it, and we have got the function's argument out.
Clearly, nested patterns are handled by successive application
of the above mechanism.
So carefully note that the constructor tag is basically the selector
for a particular projection function to extract the arguments from
the expresion tuple (i.e. its the second projection, which depends
on the result of applying the first projection).
For a tuple (rather than a variant), the projections are statically known.
However, Felix doesn't implement it quite like this.
Instead it has two functions: a match comparator, and a match handler.
The match handler is user code but includes the match extractor,
the bit that, once you know the type, applies the projection chains
needed to set the match variables used by the match handler.
Now, my critical observation is this: we can rewrite this to
if isempty(arg) then () else
if not isempty(arg) then var elt,list = uncons (arg)
Let's be more precise: suppose for some ABSTRACT data type T,
we have constructor FUNCTIONS
C0 : A0 -> T
C1: A1 -> T
,,,
and we have corresponding match checker functions
IS0 : T -> bool
IS1 : T -> bool
...
and we have also corresponding extractors
X0 : T -> A0
X1: T -> A1
...
then we can do a "general" decode of the abstract data type like:
if IS0 a then H0 (X0 a)
elif IS1 a then H1 (X1 a)
...
where H0, H1, .. is the user handler code in the match branch,
which is a function accepting a tuple of the type of the argument
of the constructor C0, C1, etc.
So the critical thing is we must list for the abstract data type these NAMED
triples:
N0: C0, IS0, X0
N1: C1, IS1, X1
The types must be as above: C0: A0 -> T, X0: T -> A0 (precondition IS0 T),
however there's more: clearly:
a = X0 (C0 a)
In other words, X0 has to "undo" the effect of applying C0 to get back
the argument to C0. So any old functions, even of the right types,
aren't good enough. I have a gut feeling this is a categorical adjunction.
Why the names? Obviously so we can now write:
match expr with
| N0 (?a0) => ...
| N1 (?a1) => ...
...
The match checker applied is ISi for name i, and the extractor Xi is used if the
checker succeeds. Both the checker and extractors are ordinary functions
so composition, that is, nested patterns, will work with the existing
algorithm.
In fact for pattern matching, we do not require the C0 component,
however it could be useful as follows: define
N0 (a) by C0 (a)
In other words, make Ni a synonym for the function Ci so it looks like a
other union types: we have a constructor name Ni which can be
pattern matched.
Note arbitrary abstract types might not admit this representation.
Note that if you have an object with accessor functions, one could always
provide the extractor (and checker for the precondition), and the name,
but no constructor function. Conversely, one could provide a constructor
with no checker or extractor. For example we might provide
match 1.0 + 2.0 i with
| Imag ?y => // imaginary part
..
Here there's no constructor because we don't know the real part:
the extractor loses it (assuming the checker was universally true,
rather than checking for a pure imaginary!)
On the other hand this looks cool:
match z with
| Polar (?angle, ?length) => ...
The constructors don't have to be disjoint, nor the destructors.
SO: I think I have found a good way to generalise pattern matching.
--
john skaller
[email protected]
http://felix-lang.org
------------------------------------------------------------------------------
Want excitement?
Manually upgrade your production database.
When you want reliability, choose Perforce
Perforce version control. Predictably reliable.
http://pubads.g.doubleclick.net/gampad/clk?id=157508191&iu=/4140/ostg.clktrk
_______________________________________________
Felix-language mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
