From: mmcg@cs.monash.edu.au (Mike  Mc Gaughey)
Subject: Re: Distributed lpmud
Organization: Computer Science, Monash University, Australia
Date: Thu, 17 Dec 1992 06:15:19 GMT

oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes:

>2) It really really hate the idea of useing the C pre-processor to
>define constants like RANGE_CHECK. I also hate the idea of use inherits
>to do it (at least, in the way you seem to imply). I get the idea the
>right way to do this sort of stuff is to add the concept of generators
>to the language. (This is something I got from Mike. Hope I understand
>this right).

Oh.  Err.  Um, no, generators would have come up (if at all) in a
different context - I was probably talking about streams (`generator'
is borrowed from ZF-expression syntax, and is, basically, part of a
spiffy way to generate sets or lists :) In these terms, `nil' is the
list's unit value, "X such that <blah>" is the generator for a stream
of X's, and the "such that <blah>" is a filter (ZF-expressions
originated in set theory).  Anyway, all of this is interesting, but
irrelevant... if you want a cite, look at "Continuations implement
Generators and Streams", lloyd allison.  I only have a preprint here;
it was in compjour about june or july '88.

I believe I said "if you see a <blah>, you generate an expression
of type (bleagh|block|blam)" or something - different concept.

>The idea is the '1' is a generator for an integer. As are all the digit
>strings. And "xyzzy" is a generator for a string. And so on. So things
>like RANGE_CHECK should be a generator for the exception labels. This is
>all fine so far. My problems comes in things like this.

The definition was:

type tree(x) = nil
	     + node x tree(x) tree(x)

type list(x) = nil
	     + cons x list(x)

type exception = RANGE_CHECK + DIV_BY_0 + ...

type Int = 1 + 2 + 3 + 4 + ... :)

We can say "the function cons, applied to 2 arguments, of type A and list(A),
generates a value of type list(A)".  You can determine the type of the cons
from the type of its first argument.  But the function "nil" isn't so simple :)

>But you also have the generator 'nil' which is a generator for the empty
>binary tree. SO what happens when you do..
>	a = nil.

Looks like a standard case of either type coercion or function
overloading to me - take your pick (`nil' is a family of 0-ary
functions with different types, so these interpretations are
intrinsically related anyway).  The context for the coercion of `nil'
is the "=" function and the possible types of `a' and `nil'.
Presumably, the type of `a', declared or computed earlier, fixes the
type of `nil' - if not, the type of the expression is the disjunction
of all the compatible types, and you have to rely on the context of the
"=" expression to disambiguate them.

Your `exception' should just be a defined (union) type - i.e.
a specialised type.  None too difficult, considering all your
objects are types anyway :)

>haveing written that, a soluton springs to mind. If you simply define
>the intersection of the List type and Tree type to be the 'nil' token,
>then every thing is fine. So the type of 'nil' is (list | Tree).

Uhh, yes.  There are typechecking difficulties; you have to insist that
the type of each instance of the value `nil' can be resolved within the
context of the function or object it appears in (or, effectively, you
end up having to tag all your values and select appropriate `methods'
at runtime - assuming that you are worried about eliminating tags!).

See Cardelli & Wegner, "On understanding types, data abstraction, and
polymorphism", Comp Surv, 17, 4, Dec 1985.  It gives good coverage of
all this stuff, as well as the idea of treating inheritance (and
multiple inheritance!) as parameterised polymorphism; beware that the
type system she describes (with existential types) is undecidable.

Mike.
--
Mike McGaughey			AARNET:	mmcg@bruce.cs.monash.edu.au

"Head stompin', ass kickin', finger licking nastiness"