Xref: utzoo comp.lang.misc:7180 comp.object:2970
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!decwrl!deccrl!bloom-beacon!eru!kth.se!sunic!mcsun!ukc!warwick!nott-cs!piaggio!anw
From: anw@maths.nott.ac.uk (Dr A. N. Walker)
Newsgroups: comp.lang.misc,comp.object
Subject: Re: CHALLENGE: heterogeneous collections
Message-ID: <1991Mar29.180957.8348@maths.nott.ac.uk>
Date: 29 Mar 91 18:09:57 GMT
References: <1991Mar22.210725.29448@neon.Stanford.EDU> <1991Mar25.220525.11087@leland.Stanford.EDU>
Reply-To: anw@maths.nott.ac.uk (Dr A. N. Walker)
Organization: Maths Dept., Nott'm Univ., UK.
Lines: 87

In article <1991Mar25.220525.11087@leland.Stanford.EDU>
hoelzle@leland.Stanford.EDU (urs hoelzle) writes:

>	type T = "some type"
>	type SubT = "subtype of T"

	And here's where I start having difficulties.  I wanted to reply
to Urs's challenge using Algol 68 with the modal extensions (described by
Charles Lindsey in Algol Bulletin #37, July 1974).  But Algol doesn't
have subtypes;  you instead always build modes "upwards".  Well, perhaps
that's a problem with Algol;  but Urs's challenge is based on a particular
OO model, and it would help me to know whether I'm *really* missing out
on something if he [or some other kind reader] could re-state the challenge
in a more neutral way, eg as a real-world problem.

>				       someProc just iterates through the
>    list and sends 'foo'

	OO again!

>							      But as soon as
>    Lists are mutable (e.g. define insert(newElem: T)), the type system
>    won't let you do it because List[SubT] is *not* a subtype of List[T].

	Why not?  Because your particular OO language has this restriction?
Or is there [or do you think there is!] something deeper that makes this a
generic problem with static typing.

	I had other problems with Urs's challenge.  He wanted to construct
a list of "A" called "listA" and a list of "B" called "listB", and then to
concatenate them into a "listC".  But you can't concatenate lists of
different types -- that's a *strong* typing, not a *static* typing
restriction.  I can construct a "listC" from *copies* of the elements of
"listA" and "listB":

	mode list = (mode x) struct (x element, ref list (x) next);

	proc concatenate = (mode x, y, ref list (x) lx, ref list (y) ly)
				     ref list (union (x, y)):
		if lx isnt nil then list (union (x, y)) :=
			 (element of lx, concatenate (x, y, next of lx, ly))
		  elif ly isnt nil then concatenate (y, x, ly, lx)
		  else nil
		fi;

	ref list (a) lista := ...;
	ref list (b) listb := ...;
	ref list (union (a, b)) listc := concatenate (a, b, lista, listb);

[untested! -- no doubt someone will tell me if I've got the reference levels
wrong somewhere].  Is this what Urs wanted?  Or have I constructed something
quite other?

	Again, Urs wanted me to "send foo" to "listC" and to "display" the
elements.  The problem here is that, in Algol, any given identifier has a
statically determined meaning, so a procedure cannot [unless I've missed
something] decide at run-time which of several identically identified
procedures is really meant.  The following *is* possible:

	proc apply = (mode x, ref list (x) lx, op (ref x) void p) void:
	   ( lx isnt nil | p element of lx; apply (x, next of lx, p) );

	op jointdisplay = (union (a, b) this) void:
	   case this in
	       (a thisa): display thisa,
	       (b thisb): display thisb
	   esac;

	apply (union (a, b), listc, jointdisplay)

	comment
	  where "display" is an operator, and "a" and "b" are assumed to be
	  sufficiently different modes;  otherwise, they might as well all
	  be procedures with names like "displaya" and "displayb"
	comment

but this may not be sufficiently generic for everyone's tastes.  I'll
think about the "foo" problem, but again I suspect there is no completely
generic solution in Algol, and there must be different "fooa", "foob"
"objects".  This is, of course, where inheritance is nice;  but you do
then run into problems with multiple inheritance that have not, as far
as I know, been solved in an aesthetically satisfying [ie, better than
"this is what my compiler does about it"] way.

-- 
Andy Walker, Maths Dept., Nott'm Univ., UK.
anw@maths.nott.ac.uk