problems with high-level purely linear languages
John Nowak — 2008-03-14 07:12:03
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
Don Groves — 2008-03-14 19:53:31
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
John Nowak — 2008-03-15 01:32:02
On Mar 14, 2008, at 3:53 PM, Don Groves wrote:
> 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.
Aye, I've taken a similar approach. Top-level definitions bind a name
to the result of some (pure) expression that operates on an empty
stack and returns a function. This can be implemented either by
evaluating the expressions at compile time or by evaluating them the
first time they're called and caching the result. By putting values on
the stack and then quoting them, names can be bound to functions that
return the *same* value each time they're called. In order to ensure
type system soundness, it is necessary to prevent things like
expressions that return a quoted mutable reference with a polymorphic
type. This isn't difficult to do.
> (2) Named objects are immutable.
I don't see this as necessary. References are safe provided that
they're not polymorphic (e.g. [Ref Int] is fine but [Ref [List a]]
isn't) and provided that you're willing to accept a runtime error if
they're empty (as I discussed in the previous email).
- John