Path: utzoo!mnetor!uunet!mcvax!ukc!eagle!icdoc!dcw
From: dcw@doc.ic.ac.uk (Duncan C White)
Newsgroups: comp.lang.modula2
Subject: Re: Recursively defined data types.
Message-ID: <208@gould.doc.ic.ac.uk>
Date: 25 Feb 88 13:38:42 GMT
References: <2420@csli.STANFORD.EDU>
Reply-To: dcw@doc.ic.ac.uk (Duncan C White)
Organization: Dept. of Computing, Imperial College, London, UK.
Lines: 153
Summary: WARNING: QUITE LONG


I have been following the current discussion about recursive data types
[RDTs from now on] with great interest.

I would like to add my thoughts to the matter.

In article <2420@csli.STANFORD.EDU> kasper@csli.UUCP (Kasper Osterbye) writes:
>Dear Mark,
>
>RDTs are not pointers in disguise. If I am not wrong, they
>will only represent trees - and here is why.
>
>I will assume your definition of a list.
>
>List = RECORD CASE Null:BOOLEAN OF
>         TRUE : |
>         FALSE: Key: ...;
>                Data: ....;
>                Next: List;
>       END
>
>
>now assume that we have variables l1,l2 of type "List", and that l1 is (a,b,c).
>the magic of the concept RDTs is that it is not pointers so
>when I do a 
>
>l2 := l1;
>
>l2 gets assigned a COPY of l1, and if you change anything to l1, it will not
>affect l2.
>

Why not support TWO kinds of assignment :

1).	assign-with-copy:	creates an entirely new copy, as you suggest
			[ie. what you are assuming := does..]
and
2).	assign-reference:	makes a new reference to the same object.
			[roughly what Modula-2 currently does with := ]


Incidentally, this is what SIMULA-67 does.... [applying it to class-instances
of course, rather than direct recursion] :

ie.	:= is (1) and :- is (2).

Personally, I think I prefer adding a new inbuilt polymorphic function
copy( ), to be used as in
	l2 := copy( l1 );
and leaving := unchanged [ meaning (2)]


Kasper continues:
>further more, an assignment of the form:
>
>l1.next.next := l1
>
>will not give you a cycle, but rather the list (a,b,a,b,c). 
>

Is there any problem here?

One question does remain: is it always possible for the compiler to generate
code to copy an RDT?

I think it is, but my mind bottles out at really complex egs, and I don't
have a proof...

>That is at least how I learned RDTs. As to your changed syntax
>for pointers so they pretend they are recursive, I dislike it, it looks
>different, but you will still have to learn the concept of pointers to
>use it.
>The why not use pointers afterall?
>

Well, RDTs are a much higher level concept than pointers.

I would like to suggest a totally new syntax for such RDTs... borrowed from
the experimental functional language HOPE [Burstall & McQueen, Edinburgh]
in which you declare new RDTs as groups of alternative SHAPES, and then
use pattern-matching to determine which shape an element of an RDT is.

For example, in HOPE syntax: [ dollars just to highlight it]

$	data num_tree == niltree ++ node( tree X tree ) ++ tip( num );
$
$	dec rev_tree : num_tree -> num_tree;
$	--- rev_tree( niltree ) <= niltree;
$	--- rev_tree( tip(n) ) <= tip(n);
$	--- rev_tree( node(left,right) ) <=
$		node( rev_tree(right), rev_tree(left) );

In a Modula-like language, then, we might write:

$	TYPE
$		num_tree =
$			SHAPE niltree
$			OR node( left : num_tree ; right : num_tree )
$			OR tip( t : INTEGER ) ;
$
$	FUNCTION rev_tree( atree : num_tree ) : num_tree;
$	BEGIN
$		CASE SHAPEOF( atree ) OF
$		  niltree : RETURN niltree;
$		| tip     : RETURN tip( atree.t );
$		| node    : RETURN node(
$				rev_tree(atree.right),
$				rev_tree(atree.left) );
$		END;
$	END rev_tree;

here, I have introduced a predicate SHAPEOF( x ) to extract the current shape
of a piece of shaped-data - after all, we need an alternative to pattern
matching.

Possible extensions:

1).	HOPE also provides polymorphic data declarations:

eg.

$	data tree( alpha ) == niltree ++ tip( alpha ) ++
$		node( tree(alpha) X tree(alpha) );

alpha "matches" any single type at run-time - but notice that HOPE cannot
declare PROLOG-style "untyped" lists.

So why not add something like this to the language ?
[Perhaps allowing untyped RDTs too? ]

2).	Classes.  Object-orientated programming is a whole new subject,
	but now Prof. Wirth has shot his bolt in announcing OBERON
	[my opinion: it's a bad joke] someone could introduce a nice
	set of class-extensions to Modula.


If anyone has any thoughts on these, I'd welcome discussion of them.


Finally, however, may I say that I think the resultant langauge would be
a lovely language to program in, but it would most definitely NOT be
Modula-2.


>/Kasper

	Duncan.

----------------------------------------------------------------------------
Duncan White,           |       Flying is the art of aiming oneself
Dept. Of Computing,     |       at the ground and missing.
Imperial College,       |               -- Douglas Adams, So Long and Thanks
London SW7, England     |                  for all the fish.