Path: utzoo!utgpu!water!watmath!watdragon!gvcormack
From: gvcormack@watdragon.waterloo.edu (Gordon V. Cormack)
Newsgroups: comp.lang.modula2
Subject: Re: Recursively defined data types.
Keywords: Side issue: Polymorphism vs. Formal Types
Message-ID: <5158@watdragon.waterloo.edu>
Date: 15 Feb 88 13:05:18 GMT
References: <4593@uwmcsd1.UUCP>
Organization: U of Waterloo, Ontario
Lines: 53

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 }