Re: linear types

[James Knight <jknight@xxxxxxxx>]

On Friday, April 19, 2002, at 03:20  PM, Allen Short wrote:
> On Fri, 2002-04-19 at 03:06, James Knight wrote:
>
>> After an initial reading of that paper, I'm quite unconvinced that
>> linear types as described there are a useful concept. As far as I can
>> tell, the main argument for them is to make it impossible for one to be
>> accessed by multiple threads. However, this is a _*great*_ cost in
>> complexity for single-threaded programs. I can tell you right now I'd
>> hate to use a language that makes me go through the hoops described in
>> that paper.
>
> well, yes -- *non*-linear types are extremely useful as well, i'm
> certainly not advocating a linear-types-only language, as Mr Baker does
> in the "lively linear lisp" paper.

But having both would involve making a duplicate version of almost every 
library function. Having to do mutating and copying versions of all the 
collections modifying functions is already bad enough. Now we need two 
versions of all the I/O functions, pretty much all the other collections 
functions, etcetc. Otherwise how do you take care of having to give the 
object back to the caller to let him keep a reference to it?

>> The rest of the
>> arguments seem to me like they're basically premature optimizations
>> exposed to the programmer.
>
> Hmm. how so? to my mind, linearity is a property that would be hard to
> recover via inference. I dont see any disadvantages to allowing its
> explicit declaration.

Disadvantages above. In terms of optimizability, I was thinking of the 
examples in the paper where its used while constructing an object. It 
should be (mostly) straightforward to make an optimizer that can figure 
out that an object does not escape while its being constructed, and thus 
allow free (non-copying) coercion from a mutable form used for 
construction to an immutable form exported to the world. You are 
certainly correct that it would be very hard to recover in general, but 
then again, in general, objects aren't used linearly.


>> However, I do believe that a similar concept, not applied to number of
>> references, but rather, to number of *different threads that have
>> references* is a great idea.
>
> Hmm. How would this "linearity-with-respect-to-threads" be accomplished?
> what do you mean by "as far as they can tell"?

In concept it is quite simple - when you create a new thread of 
execution, you copy all the memory of the current thread. This is 
generally called a "process" in the UNIX world and is efficiently 
implemented by the "fork" system call. :) Now, they cannot mess up each 
other's objects. The only issue is communicating efficiently. The usual 
unix way to do that is to package everything up into a stream of bytes, 
and send it over a socket. That, of course, is quite inefficient (and in 
most languages, quite irritating, as you need to do all the 
packing/unpacking yourself), but it gets the job done. IMO this has much 
cleaner semantics than any shared memory model. The only issue is then 
to make RPC calls as nearly free as possible between threads running in 
the same execution environment, even when sending complex data 
structures.

My comment about "as far as they can tell" was an attempt to note that 
lazy copying of objects is probably possible, thus allowing two threads 
to point to the same piece of memory representing an object, as long as 
it isn't modified.

James