Path: utzoo!utgpu!water!watmath!clyde!rutgers!ukma!gatech!purdue!i.cc.purdue.edu!j.cc.purdue.edu!pur-ee!uiucdcs!snail!carroll
From: carroll@snail.CS.UIUC.EDU
Newsgroups: comp.lang.modula2
Subject: Re: Recursion & Types
Message-ID: <11100001@snail>
Date: 12 Feb 88 15:19:00 GMT
References: <4536@uwmcsd1.UUCP>
Lines: 44
Nf-ID: #R:uwmcsd1.UUCP:4536:snail:11100001:000:1763
Nf-From: snail.CS.UIUC.EDU!carroll    Feb 12 09:19:00 1988


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