Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!yale!cmcl2!lanl!lambda!jlg
From: jlg@lambda.UUCP (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Anyone want to design a language?
Message-ID: <14249@lambda.UUCP>
Date: 23 Feb 90 20:54:37 GMT
References: <11911@nigel.udel.EDU>
Distribution: usa
Lines: 35

From article <11911@nigel.udel.EDU>, by new@udel.edu (Darren New):
> In article <14245@lambda.UUCP> jlg@lambda.UUCP (Jim Giles) writes:
>>I)   Recursive data types.
>>        As an example, consider a possible declaration of a binary tree
>>        data type (all examples are in a Fortran/C-ish syntax - that is,
>>              y = btree{3,x,btree{4,null,null}}
> 
> Ok.  Now how do I write the declaration of a function that returns 
> a pointer to the first sub-tree with the value four at its root
> without winding up with an aliased value?  AND how do I do this
> without using recursion?          -- Darren

Well, since ther aren't any pointers, a function which returns a pointer
is not a problem - it's impossible.  And, who said anything about not
using recursion?  I didn't.  I think recursion is a grand idea!

Actually, you didn't read my entire post.  I pointed out that recursive
data structures probably _SHOULD_ allow aliasing.  It was the only one
of the set of data structures I gave which did.  However, there are
implementations of recursive data structures which _DON'T_ allow
aliasing. (Many functional programming languages don't allow aliasing -
they most certainly _DO_ have recursion in both data and function
structures.  If you think about it, aliasing isn't an issue in functional
programming since assignment isn't allowed.)

The advantage of using recursive data structures instead of pointers is
mostly notational (no 'dereferencing' operator, no confusion between
pointers and the objects they point to, etc.).  This makes programs
easier to read and maintain.  Also, it helps the compiler to determine
that the _only_ thing a 'b_tree' (for example) can be aliased to is
another 'b_tree'.  There isn't even the possibility of a pointer 'cast'
accidentally (or deliberately) aliasing a 'b_tree' to a char string or
something.  This improves the compilers ability to optimize the code.

J. Giles