Re: multithread.txt

[<don...@is...>]

When I read this file originally I had some of these same reactions,
but only now that I look again do I bother to send them in.

 * Parallelizability Principle: 
   Simple formulation: 
    "A program that was developed for a single-threaded world and which shares 
     no application objects with programs running in other threads must run 
     fine, without problems." 
A better description would be "must execute as in the single threaded case".
To be even more precise, I'd say that the set of possible executions
ought to be the same.  An execution could be defined as a sequence of 
instructions (at some appropriate level) executed along with the data
read and written by each one.  IO behavior would be a coarse example.
  
  Extended formulation: 
    "If, in a single-threaded world, execution of program A before program B 
     produces semantically the same results as execution of program B before 
     program A, then in a multithreaded world, it is possible to run A and B 
     simultaneously in different threads, and the result will be the same as 
     in the two single-threaded cases (A before B, or B before A)." 
  That's what the users ultimately want. 

Again, it's not clear what you mean by "the result will be the same".
But I don't see that this statement (of what the users want) is true.
If A and B are both something like
(setf x 0 y 0)
(loop for i below 100 do
 (incf x)
 (sleep 1)
 (incf y)
 (unless (= x y) (error "hey, someone changed my data!")))
then I think it's pretty clear, or at least clearly possible, that the
user wanted the set of interleaved executions to include more than the
set of non-interleaved executions.


  - If A and B have no objects in common, then the implementation 
    ensures by itself that the principle is fulfilled. 

This makes sense, but in typical lisp programs it's not clear what the
set of objects really is.  If it includes all that I think it should,
it will be very unusual that A and B have no objects in common.  So
this statement is not very useful.

Also, I think this statement could be strengthened considerably by
restricting attention to the objects that are written by one process
and read by the other. 

  - If A and B shared some objects, the implementation allows the programs 
    to satisfy the principle with little effort. 

Although the statement of principle seems to be aimed at making
interleaved executions act like non-interleaved executions, I think
this is not what you're really trying to do, or what you should be
trying to do.

I think what you're trying to do, and should be trying to do, is

1. Specify the set of objects read and written by a piece of code so
that the programmer can figure out which ones are written by one 
process and read by another.

2. Define an execution model of lisp in terms of a sequence of states
and ensure that every lisp process can be accurately understood in
terms of that model.
I hope we can think of any parallel execution as a sequence of states
in which the transition between each pair of adjacent states is
defined by the execution of the next step of one of the running
processes.  The main point is that no process should ever be able to 
observe a state that is not predicted by that model.
For instance, the lisp statement (setf (gethash x y) z) should be
defined as a single state transition.  It should not be possible for
another process to observe a state of the hash table between the one 
before the setf and the one after.  And it is the job of the lisp
implementation to ensure that this is the case.
(Is this correct?  
If not then the programmer better be told what is!
The file says:
  If two threads evaluate 
   (INCF (GETHASH x global-ht 0)), 
  the results are undefined. 
I hope this means that the value in the hash table might be 1 or 2,
but NOT that lisp dies or that there are two different entries in the 
table for the value of x.
)

3. Provide ways for programmers to define their own larger "atomic"
operations, which prevent other processes from observing intermediate
states that violate their assumptions/requirements.

What I see in the rest of the file seems to be far down in the details
of these things.  Typical multiprocess documentation deals with #3,
and I presume clisp documentation will do that too.

Is there some reference (perhaps for another lisp implementation that
you think applies as well to clisp) that deals with #1 and #2 ?