[Nickle]Recursive datatypes (was: Tonight's topics)

[Keith Packard]

Around 13 o'clock on Jul 24, Carl Worth wrote:

 >      typedef x;
 >      typedef struct {
 >         x y;
 >      } x;

> While I could probably live without this, what's the fundamental
> difference between that struct definition and the following:

It's not a matter of "probably" living without recursive structures, the 
fact is you can't actually create a value of that type -- the 
representation of this type is of infinite size.  The current kludge is to 
ensure that the automatic structure value creation code doesn't recurse in 
this case, but that leaves us with a structure containing undefined 
values, that's what we're trying to eliminate.  

The way around this type problem is to use a type which can be represented
with more than one kind of value.

> typedef struct {
>   poly y;
> } x;

Now I can represent values of this type easily: 

	x foo = { y = 7 };
	x bar = { y = (x) { y = (x) { y = <> } } };

To avoid pure polymorphism, you can use a union type instead:

	typedef list;

	typedef union {
		list	next;
		void	end;
	} listref;

	typedef struct {
		listref	ref;
	} list;

	list l = { ref = (listref.next) (list) { ref = (listref.end) <> } };

	union switch (l.ref) { 
	case next: printf ("next\n"); break;
	case end: printf ("end\n"); break; 
	}

	if (l.ref == listend) printf ("yes\n");

	l.ref.next.ref.next = (list) { ref = listend };

ML has a cleaner syntax for unions which makes this look less awkward. The
advantage of unions is you can retain most of the compile-time 
typechecking, and the run-time typechecking is all explicitly labeled in
the code.

-keith