Path: utzoo!utgpu!water!watmath!clyde!rutgers!ucla-cs!cit-vax!elroy!ames!coherent!aimt!uunet!mcvax!ukc!eagle!icdoc!cam-cl!scc
From: scc@cl.cam.ac.uk (Stephen Crawley)
Newsgroups: comp.lang.modula2
Subject: Re: Recursion & Types
Message-ID: <1135@jenny.cl.cam.ac.uk>
Date: 16 Feb 88 02:40:36 GMT
References: <4536@uwmcsd1.UUCP> <11100001@snail>
Reply-To: scc@cl.cam.ac.uk (Stephen Crawley)
Organization: U of Cambridge Comp Lab, UK
Lines: 30
Posted: Tue Feb 16 02:40:36 1988

>>		    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