[gclist] Reference counting on the fingers of one thumb.

[Roy Ward]

>At 9:31 AM +0200 1/14/97, John Carter wrote:
>
>>From: James McCartney <james@clyde.as.utexas.edu>
>>>Its been done.
>>>There is a graph reduction functional language called Rewrite
>>>that was written for the Mac that has only use once objects.
>>Sigh! I don't have a Mac, but I will indeed have a look at it. Thanks
>>for note, do you have any reference? ftp address?
>
><ftp://mirror.apple.com//mirrors/Info-Mac.Archive/dev/rewrite-027.hqx>
>
Or any other info-mac site. Unfortunately, my web site (which usually has
a copy) is currently down. And yes, it's freeware.

As the author of ReWrite, I'll throw in some comments (sorry for the delay,
I haven't been checking my e-mail):

ReWrite does in fact have only one use objects, and does a LOT of copying
(although the compiler does try to minimise this). For example, the rule:

f[a] -> {FOO[a],BAR[a]};

will make a deep copy of a to pass to FOO, but will will pass the original
to BAR, as it is at that point f no longer needs it. This avoids unecessary
copying a lot of the time. However, this is not without cost, as the
following function to append the length of a list onto the front of a list
indicates:

foo[p:lis] -> {length[p],.p};

Here p will be copied, the copy will be passed to the length function,
and the length function will destroy it (the compiler ensures that all
arguments are either destroyed or passed on to another function).

What is really needed is semantics to say:
    "this is someone else's object, do not alter or destroy",
sort of the opposite of Clean's 'Unique' tags, so as to avoid extra
copies and destroys.

In the meantime, it is possible to program to avoid the worst of this
by having functions return some of their arguments to avoid having to
destroy them, for example length_ext[x] returning the list as well as
the length, but this is more work for the programmer (although the
penalty for failure here is a slow program rather than a buggy program).

The upshot of all this is that yes, it is possible to do reference
counting on the fingers of one thumb, but it is hardly 'free' - it
can involve an awful lot of extra copying. And I wrote it before
finding out anything about linear logic or Henry Baker's work (nothing
as much fun as re-inventing the wheel:-). ReWrite does work well enough
that I did write the compiler in ReWrite itself.

One project on my 'to do' list is to write a variant of ReWrite that is
fully garbage collected, and compare the performance of various versions.
When (if?) I do this, I will definitely post the results here.

A point that is probably too late to do any good: Downloading ReWrite
will not be of any help to anyone without access to a Macintosh, as
I have not included the source code (0.2.x source code is too much of
a mess to share with anyone, 0.3 will be cleaner), ReWrite is written in
ReWrite, so you would need a ReWrite compiler to compile it anyway, and
all the documentation is in a Mac only format (eDoc).

There was a thread here a while back on tail recursion in C++. The lack
of this is the main thing preventing me from writing a ReWrite -> C++
compiler. (Without tail recursion, the stack gets huge).

Henry Baker wrote:
>There is available online an excellent functional language for the
>Macintosh with what they call 'unique' types (the same as 'linear'
>types).  This language is called Clean, and I think that it may
>be downloadable for free.  See ftp.cs.kun.nl/pub/Clean/

Clean is also available for some non-Macintosh platforms (I'm not sure
which, it's on the web page). It is very nice, and operates completely
differently to ReWrite (although they both use a rule-based syntax).

If anyone wants to know more about ReWrite, or has any comments to make,
please e-mail me. If there is  an interest, I'll see what I can do about
getting the docs converted into a non Mac-only format (my resources are
very limited). There is also a (short) section about ReWrite in the
'Programming Paradigms' column of the Feb 1996 issue of Dr. Dobb's Journal.

Meanwhile, on with the next version of ReWrite ...

Roy Ward
roy@earthlight.co.nz

P.S. I'm also interested in any on-line material on linear logic - I don't
have much access to printed material.