New linked list

[Sean Kelly]

You know, this whole sequence optimization business seems to be linked 
to mutability: if no mutating operations are performed then optimize 
away!  Unfortunately, I haven't seen a high-level construct for method 
classification that can't be violated by the user.  And while this may 
be irritating in some cases, it could lead to nasty bugs in the face of 
such optimizations.  In some respects, it would be nice if each 
operation in the language could be labeled as mutating or non-mutating 
and then functions could be analyzed for atomicity during compilation, 
so a function would considered atomic if it does not perform a mutating 
operation on non-local data.  But this may be overly restrictive.  For 
example, the body of a foreach loop must be able to perform some 
mutating operations, but different categorites would impose different 
restrictions on optimization:

     int sum = 0;
     foreach( int val; values ) {
         sum += val;
     }

Here, the code could be heavily parallelized because the result doesn't 
depend on the sequence in which operations are performed.  However:

     foreach( int val; values ) {
         printf( "val: %d\n", val );
     }

Here, the code could be optimized somewhat but must still be executed 
sequentially.  By comparison:

     void fn() {
         values ~= 5;
     }

     foreach( int val; values ) {
         if( val > 10 ) fn();
     }

No optimizations may be performed here because the iteration sequence is 
being modified during processing.  To make matters worse, this could 
occur through an untraceable sequence of pointers and such that the 
compiler can't make sense of.  What would be wonderful is if there were 
a way to distinguish these three categories of code somehow.  I know, 
that's the million dollar question, but I harbor a secret hope that if 
it's asked frequently enough then perhaps someone will think of an answer.


Sean