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