Path: utzoo!utgpu!water!watmath!clyde!bellcore!decvax!decwrl!labrea!agate!ig!uwmcsd1!csd4.milw.wisc.edu!markh
From: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Newsgroups: comp.lang.modula2
Subject: Recursion & Types
Summary: Why are recursive type definitions excluded from Modula-2?
Message-ID: <4536@uwmcsd1.UUCP>
Date: 11 Feb 88 03:43:24 GMT
Sender: daemon@uwmcsd1.UUCP
Reply-To: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Organization: University of Wisconsin-Milwaukee
Lines: 46


    In the book "Programming in Modula 2" written by the designer Niklaus Wirth,
the author goes over an example illustrating the use of pointer types.  Consider
the following definition:

		  ListPointer = POINTER TO ListNode;
		  
		  ListNode    = RECORD
				   Key: ... ;
				   Data: ... ;
				   Next: ListPointer
                                END;

The author makes the comment that the following is not a substitute for the
definition above:

		    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.

     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.

     The question then is why is direct recursion excluded from Modula-2?  
The only major use of pointers in the language is to make type definitions that
are indirectly recursive.  Having pointers in the language, though, seems to be
much like having goto statements. The latter can lead to "spaghetti programming"
and the former to "spaghetti data structures".  So the other question is why 
pointers are included in the language when direct recursion may be more 
appropriate?