# 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