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

[Bart Massey]

An important distinction is between the runtime type of a
value, and the static analysis that ensures that runtime
type errors will not occur.  When you use poly, you turn off
the latter.

So with
  typedef struct { poly f; } t;
you can store in the field f anything you want from
the compiler's point of view, including
  t x = {f = <>};
  t y = {f = x};
y is now a value that looks like
  global t y = {f = {f = <>}};
What is the type of this value of y?  It is
  typedef struct { struct {void f;} f; } t_y;
Indeed, y holds the only legal value of this type.
Thus
  t_y z = y;
works as expected: Nickle can't rule out this assignment at
compile time, and it checks out OK at runtime.

Note that t_y is not a recursive type: just a nested
structure type.  You cannot create infinitely nested
(i.e. recursive) values in (new) Nickle, because there is no
way to "tie the knot", so you'd have to type an infinitely
long initializer in.

HTH,

	Bart

In message <E17XQpk-0001CE-00@localhost> you wrote:
> 
> 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.