🚀 go-pugleaf

I think you are missing the point. The definition below is in fact an infinitely
sized data object.

>		    List = RECORD
>			      Key: ... ;
>			      Data: ... ;
>			      Next: List
>                           END;
>
>he goes on to say that this would not be a valid definition because "it does not
>terminate" and seems to argue from there that direct recursion should not be 
>represented in the language.

There is a difference between data recursion and program recursion. I am not
sure which one you are referring to.
>
>     My comment is that of course you would not represent a list like that, 
>because you have to account for the possible null value of the pointer.  The
>proper abbreviation is a VARIANT record with a null variant for the empty list:
>
>		    List = RECORD CASE Null:BOOLEAN OF
>				 TRUE:                |
>				 FALSE:  Key: ... ;
>					 Data: ... ;
>					 Next: List
>                           END;
>
>This definition does terminate.
>(...)
	When? The compiler can't know when it terminates at compile time. And
accessing elements far down the chain is going to be a major amount of typing.
In fact, I would like to see how you would, say, sum up all the data elements.
You'd have to explicitly code the level of depth in the structure when you
referenced it. How would you allocate it? For a normal variant record,
there is an exact number of variant tags. In this case there is an arbritrary
and unknown number. The reason for pointers is to allow, in a reasonable way,
what you seem to want to do.

Alan M. Carroll		amc@woodshop.cs.uiuc.edu	carroll@s.cs.uiuc.edu
...{ihnp4,convex}!uiucdcs!woodshop!amc
Quote of the day :
	"I've consulted all the sages I could find in Yellow Pages,
	 but there aren't many of them" - AP & EW

>>		    List = RECORD CASE Null:BOOLEAN OF
>>				 TRUE:                |
>>				 FALSE:  Key: ... ;
>>					 Data: ... ;
>>					 Next: List
>>                           END;
>>

While the above type would indeed be infinite in the sense that
some of its ''possible'' values would be infinite, some of its
values would also be finite.  The problem is that the size of a 
value of such a type would not in general be determinable at 
compile time.  This implies automatic allocation of dynamic
storage, and that would break Modula-2 ... which has no garbage
collection.  A more sensible implementation would use hidden pointers
(hence the sizes would be determinable at compile time), but that
would still require garbage collection.  

BTW-1: It is not at all hard to distinguish at compile time between 
infinite types that are useful and those that are non-useful; i.e. 
those for which all values are infinite.

BTW-2: There ARE languages that allow infinite types; e.g. ML.

BTW-3: There ARE languages in which infinite types are represented 
without pointers; e.g. Courier and ANS 1.  Of course, these are not 
programming languages but languages for defining application level
communication protocols.  

-- Steve