Path: utzoo!utgpu!water!watmath!clyde!rutgers!husc6!bbn!uwmcsd1!csd4.milw.wisc.edu!markh
From: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Newsgroups: comp.lang.modula2
Subject: Recursively defined data types.
Summary: Some answers.
Keywords: Side issue: Polymorphism vs. Formal Types
Message-ID: <4593@uwmcsd1.UUCP>
Date: 15 Feb 88 04:59:41 GMT
Sender: daemon@uwmcsd1.UUCP
Reply-To: markh@csd4.milw.wisc.edu (Mark William Hopkins)
Organization: University of Wisconsin-Milwaukee
Lines: 63

In an earlier posting, I asked why Modula2 does not allow direct recursion
on data types as exemplified by the following definition:

	     List  =  RECORD CASE Null:BOOLEAN OF
				  TRUE:          |
				  FALSE: Head: Atomic-Type;
					 Tail: List
                             END
                      END;

Most of the answers I got were of the form:

          Because the compiler does not know how to "size" this type.

The obvious answer to this is to represent the recursive field (Tail) internally
by a pointer -- a language and its implementation are two independent issues.

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 seems more or less like a matter of choice, since they essentally do the same
thing.  I had other things in mind, though,  that tend to sway the issue in 
favor of using recursion.

A good programming language, from what I can infer from Wirth's writings should
support modularity and should be powerful while maintaining uniformity. 

UNIFORMITY would require that as many distinct concepts as possible be unified 
and implemented in a uniform way.  For example, the following sets might be 
unified in a uniform programming language:

     BRANCHING:                        RECURSION:
     Variant Records (Type sums),      Dynamic Types,
     Branching statements (If, Case)   Loops and recursive procedues,
                                       Recursive functions

     PARALLELISM:                      DEFINITIONS:
     Records  (Type products),         Type declarations,
     Parallel execution,               Procedure declarations,
     Parallel evaluation               Assignment statements

Uniformity would demand direct recursion on data types in place of pointers.

One thing that MODULARITY would require is that the difference between 
user-defined and predefined constructs be made invisible to the language.  This
would give the designer wide latitude in implementing (and ***extending***) the
language and would allow for bootstrapping.

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)?