Re: [stack] problems with high-level purely linear languages

On Mar 14, 2008, at 19:12 , John Nowak wrote:

> 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


While I have not done the level of thinking and experimenting with
linearity you clearly have, I have a few suggested rules regarding
the use of linearity in concatenative languages:

(1) Only temporary objects (on the stack) need be linear. Persistent
(named) objects may have any number of references simply by not
allowing them to be deleted -- once created, they exist for the life
of the program.

(2) Named objects are immutable.

(3) Mutable objects must exist in a closure, thus maintaining a
single reference.

If these rules are followed, it seems to me that linearity can be a
useful tool in these languages.
--
don