[stack] problems with high-level purely linear languages

This may be too esoteric to post, but I seem to recall a few people  
being interested, so here it is.

Brief intro: A linear language is one in which all values are always  
singly referenced. Such a language can do away with garbage collection  
and allow mutation of data while remaining purely functional. Linear  
languages also match up nicely with how the real world works, for  
whatever that's worth. For more info, check Henry Baker's research  
archive.

Concatenative languages have this nice property where, due to the lack  
of binding and especially due to the ability of functions to return  
multiple arguments, it becomes possible to have a purely linear  
language without any type system needed to enforce it. When you 'dup'  
a value, the value and everything it references gets copied. This may  
seem grossly inefficient, and sometimes it is, but the fact that you  
get to work with cache-friendly mutable data structures can often make  
up for it. That's the theory anyway.

There's a catch: In order to have a linear values without linear or  
uniqueness types, *every* value needs to be linear. As a quick  
example, imagine a language where every value is linear and operations  
are implemented via mutation *except* for lists which are persistent.  
If you were to take the head of a list of linear values, or simply dup  
the list itself, you'd have two references to a single linear value  
which destroys the whole thing. All of the purely functional niceness  
is out the window.

I've spent some time experimenting with linear interpreters and I've  
come to the conclusion that pervasive linearity is a wholly terrible  
idea for a high level language. It's also a wholly terrible idea for a  
low level language where sharing and mutation are critical for  
performance, so it seems purely linear languages aren't much good for  
general purpose programming. This is probably not surprising to most  
people.

Leaving the performance issues aside, here are three less obvious but  
equally critical issues I ran into when designing a purely linear  
typed language:

1. Things like records and tuples become much more complicated. In  
functional languages, accessing a field of a tuple returns a reference  
to an immutable value. In a linear language, accessing a field of a  
tuple requires that you *deep copy* the value onto the stack. Given  
how unacceptable this is, it becomes necessary to *move* the value to  
the stack so it can be mutated and then placed back into the tuple. To  
support this, the type system needs to have some notion of "nullable"  
types where a record or tuple field can either be null or a value of  
some other type, but never both.

2. Linear languages are only pure if your program is a big chain of  
unary functions. This breaks down however when you do anything more  
interesting. Say you introduce contracts to your language so that you  
can test pre and post conditions for functions. In order for contracts  
to be a sensible addition, they cannot have any impact on a program so  
that a program behaves identically if they're removed. With a non- 
linear functional language, it's easy to save the top N values on the  
stack, perform the test (the type system can ensure the test has no  
side effects), and then restore the original values when the test is  
over. With a linear language, you'd have to *copy* the top N values  
which is grossly inefficient. The only way around copying is to  
introduce "read-only" types to allow values to on the stack to be used  
provided that they're not updated. This means that a function without  
side effects isn't *actually* pure if it works via mutation because  
the mutation *will be visible* when dealing with things like  
contracts. The additional type system machinery necessary to get  
around this is quite ugly.

3. References in a linear language must be mutable. This is because  
avoiding copying requires that you *remove* values from a reference  
cell, update them, and then replace them. This also means that  
accessing a reference cell may result in a runtime error if the cell  
is currently empty. Offering "pure" references would again require  
some sort of "read-only" type system extension. Of course, non-linear  
functional languages have no need for pure references to begin with as  
data is already easily sharable.

In short, in addition the obvious potential efficiency problems, there  
are a host of other issues that complicate the language, make  
programming more awkward, and increase the risk of runtime errors. I'm  
of the opinion that it makes much more sense to start with a non- 
linear language and add uniqueness types for the cases in which  
they're beneficial. Uniqueness types essentially prevent you from  
duplicating a "unique" value or any value that references a unique  
value. Such a type system extension is straightforward and non- 
obtrusive; it seems to be implementable in a concatenative language  
via essentially the same mechanism used in ML's equality types.

- John