Doing it better 1999-05-27 a
###

This is why writing up ideas is a good thing. Another reason, anyway.

I have a problem with pattern matching. I'm not allowing matching with
constants, or with side conditions, or anything fancy, just a simple
typecase statement. However, I still have problems.


Types are generated by this grammar:

T ::= Integer | String | Float
    | T*T
    | T+T
    | ch x.T

There are other cases I am omitting, and Strings and Floats probably won't
feature in the first iteration if ever, but this is the grammar I am using
for this illustration.

T*T constructs a product type. For example, Integer*String variables hold
both an integer and a string at the same time.

T+T constructs a sum type. For example integer+string variables hold an
integer or a string but not both.

ch x.T constructs a channel type. You can send a value of type T down a
value of type ch x.T. Inside T, x stands for ch x.T, which allows
recursive types.


These can all be illustrated together by the example:

        ch x.()+(Integer*ch y.x)

which represents the sending end of a stream of integers. It is a channel
down which you can either send nothing (the empty product, or unit, as in
ML) to indicate the end of the stream, or both an integer and a channel,
down which can be sent a channel for the rest of the stream.


The problem is that my sum is not tagged, unlike ML. For example,
Integer+Integer is the same type as Integer, whereas in ML you'd have to
invent two different constructors to distinguish the two cases.


Let's declare type IS to be Integer+String, and FS to be Float+String.
Let's further declare a variable j of type IS+FS, and use it as the pivot
of a case statement:

case j of
when Integer i...
when Float f...
when String s...
endcase

This is fine, but different to what ML would have done. The following is
also fine:

case j of
when Integer i...
when Float+String fs...
endcase

although you wouldn't be able to do very much with fs apart from use it in
another case statement. This is not allowed:

case j of
when Integer+String...
when Float+String...
endcase

because there are two cases which could be taken when j is a String. I
could introduce a disambiguation rule, but I think that is too
complicated, so ambiguous alternatives are not allowed.

For sums and products of primitive types, there is no problem with this
scheme (although the representation of the data is going to be fun!)
because the sum of two types can always be broken into non-overlapping
cases.


Two channel types always overlap. For example, ch x.Integer and ch
y.String both contain ch z.Integer+String. This suggests our case
statement should have three when clauses, one for x-z, one for y-z and one
for z. However, I have no way of representing x-z and y-z, and indeed
cutting one type out of another is not a computationally nice thing to do.
It's a bit like negation in regular expressions.

Should I:

1) Tag all of my sum types. This effectively means I can no longer use sum
types for inheritance, and so I have to substantially complicate the
language to do inheritance. I want inheritance.

2) Tag all my channel types. Same problem as 1) I think, just delayed by
one message. Needs some thought.

3) Invent disambiguation rules. This precludes the nice trick of
representing a channel as a branch table with one entry for each of the
non-overlapping cases. A similar trick would have to be found for
efficiency, as doing sub-type analysis at runtime sounds hairy and slow.

4) ?

I favour 4) at the moment, i.e. ask if you have any ideas. Do you?


It's a dangerously interesting problem, because of the counter-intuitive
'channel which carries a supertype is a subtype' feature, and because it
looks like it must be solvable. Beware!

Alistair