Path: utzoo!utgpu!water!watmath!clyde!rutgers!ames!pasteur!agate!ig!uwmcsd1!csd4.milw.wisc.edu!markh
From: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Newsgroups: comp.lang.modula2
Subject: Re: Recursively defined data types.
Summary: Representing cyclic data structures.
Message-ID: <4640@uwmcsd1.UUCP>
Date: 17 Feb 88 03:14:09 GMT
References: <4593@uwmcsd1.UUCP> <5158@watdragon.waterloo.edu>
Sender: daemon@uwmcsd1.UUCP
Reply-To: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Organization: University of Wisconsin-Milwaukee
Lines: 54

In article <5158@watdragon.waterloo.edu> gvcormack@watdragon.waterloo.edu (Gordon V. Cormack) writes:
>In article <4593@uwmcsd1.UUCP>, markh@csd4.milw.wisc.edu (Mark William Hopkins) writes:
>> So why do I even make an issue about it in the first place?  Using pointers and 
>> allowing for direct recursion in a language are fully equivalent.  Direct 
>> recursion would be implemented with pointers anyway.  My question, then, was 
>> why using pointers is favored over direct recursion.
>
>It is not true that they are equivalent.  Recursion can be used only
>to express trees:  it cannot represent DAGS or data structures with
>cycles.

I argue that they are fully equivalent:

Example of how a recursive data type would be used to represent a cyclic 
structure:

type     List = RECORD CASE Null:BOOLEAN OF
			 TRUE:             |
			 FALSE: Data:Atom;
				Next:List
                       END
                END;
...
var      L : List;
...

		Here, L is representing the circular list:

		       L ~~~>   A --> B --> C -* ,  L  =   *---------------*
				^              |           |       A       |
				|              |           *---------------*
				*--------------*           | *-----------* |
<ASSIGNING L ITS VALUE>                                    | |     B     | |
WITH L DO                                                  | *-----------* |
   Null := FALSE;                                          | | *-------* | |
   Data := A;                                              | | |   C   | | |
   WITH Next DO                                            | | *-------* | |
      Null := FALSE;                                       | | |   L   | | |
      Data := B;                                           | | *-------* | |
      WITH Next DO                                         | *-----------* |
         Null := FALSE;                                    *---------------*
         Data := C;
         Next := L       (***** This closes the cycle *****)
      END
   END
END

This is if Modula-2 had data type recursion in it.

I guess I don't see the problem ... except if it be in assigning the last Next
field the value of the very record being accessed.

It is obvious that one would have to use internal pointers to represent the Next
field, but other than that there does not seem to be any major problem here.