🚀 go-pugleaf

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.

Now we can get into how functional programming doesn't "use" any
time or space at all, so I suppose we could always "cover" one of
these data structures by potentially large sets of trees. 
I don't believe this is a very good way to express such things, and
the implementation (deep down we are interested in implementation)
can often take orders of complexity more time and space.

Besides, any notation I've seen for recursive data types 
(cf. Hoare's "Recursive Data Types") has notational baggage for
dealing with and setting the variants that is equivalent to using
pointers and "new" and "dispose".

> Wirth has gone part of the way in adding a new data type in Modula2 to represent
> procedures.  The low-level module SYSTEM also has a type to represent words.
> But what about Types?  Why isn't there a data type - Type - in the language?
> With this addition, one could construct variable types (and solve the problem 
> that Pascal and Modula2 have had with representing variable array types) and
> functions that return types (i.e. user-defined type constructors).  This is
> POLYMORPHISM.  
> This, too, would favor direct recursion in favor of indirect recursion with
> pointers.
> 
> This latter point brings up a side issue: would polymorphism in Modula2 
> resolve the need for such things as Formal Types (or conformant array parameters
> in Pascal)?

Polymorphism is a current research topic.  It is too bad that Wirth
has chosen to ignore this very important issue in programming
language design, but it is far from a trivial change (as implied 
above) to bolt it into the language.

Whether or not polymorphism eliminates formal parameter specifications
depends of the flavour of polymorphism we are talking about.  In ML
this is true to some extent.  In the language I am involved in
designing and implementing (ForceTwo) formal parameter specifications
continue to be very important.  There is a paper "Polymorphism in
the compiled programming language ForceOne" in the 1987 Hawaii
Conference on Systems Sciences, or you can ask me for a more recent
tech. report.
-- 
Gordon V. Cormack     CS Dept, University of Waterloo, Canada N2L 3G1
                      gvcormack@waterloo  { .CSNET or .CDN or .EDU }
                      gvcormack@water         { UUCP or BITNET }

	I still don't understand how you would reference a recursive
data element that was far down in the structure. How would you parametrize
the reference to, say, the 10th data field of a recursively defined type?
Would you have to type in 10 "." operators, with the field names
between them? And how would you handle variable depth references?

Alan M. Carroll		amc@woodshop.cs.uiuc.edu	carroll@s.cs.uiuc.edu
...{ihnp4,convex}!uiucdcs!woodshop!amc
Quote of the day :
	"Touch my soul, catch the very light
	 Hide the moment, from my eager eyes"

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.

In article <11100002@snail> carroll@snail.CS.UIUC.EDU writes:
>
>	I still don't understand how you would reference a recursive
>data element that was far down in the structure. How would you parametrize
>the reference to, say, the 10th data field of a recursively defined type?
>Would you have to type in 10 "." operators, with the field names
>between them? And how would you handle variable depth references?

If Modula-2 had data type recursion, then roughly like this:
List would be defined by:
	
                  List = RECORD CASE Null:Boolean OF
				   TRUE:              |
				   FALSE: Data:Atom;
					  Next:List
                                END
                         END;

<ACCESING THE TENTH ELEMENT OF THE LIST L:List>

ReadHead is declared to be of type List:

		    ReadHead := L;
		    FOR I := 1 TO 9 DO
			 ReadHead := ReadHead.Next
                    END;
		    RETURN ReadHead.Data;

I first dealt with tree structures using snobol-4, which uses recursively
defined types.  I was very disappointed when I learned about how one does
these things in Pascal.  By the time modula came along, I was over the
shock.  One reason for wanting recursively defined types is that their
semantics is much cleaner than pointer semantics.  I approve of the idea.

Fred Sullivan
Department of Mathematical Sciences
State University of New York at Binghamton
Binghamton, New York  13903
Email: sullivan@marge.math.binghamton.edu