STATELESS/SIDE-EFFECT-FREE Functions

[ELIOT@cs.umass.edu]

   From: Jon L White <edsel!jonl@labrea.stanford.EDU>

   re: . . .  Should "ERROR" and ...

   re: . . . if a compiler can check these properties it could
       also compute them.  But currently it would not be allowed
       to use those computed properties.
   
   I agree with you that a compiler (and maybe even interpreter?) should do as
   much consistency checking as possible.  As moon implied in previous mail, 
   an SSC(*) should be able to determine "simpleness" mechanically.  But the 
   danger of using that information is that it may not have been the user's 
   _intent_  that this function be marked as "simple" (e.g., he may want to 
   alter it incompatibly at a later time).  An explicit proclamation (or 
   whatever) is the right vehicle for conveying that intent.

The previous paragraph describes the situation accurately.  There seems
to be general agreement that an SSC(*) could mechanically determine 
a number of properties of functions that would help a compiler
optimize code.   MOON lists a veritable conspiracy of such properties
that are used by the Symbolics compiler.  Most people agree that by
default a compiler should not use these properties without some
explicit proclamation (or whatever) indicating that it is OK.
(GZ seems to disagree with this.)  There does seem to be a reasonable
amount of interest in making these properties known to compilers.

Using a set of ad-hoc declarations to specify these properties has
several problems.  It is inevitable that these declarations will be
defined for the purpose of enabling specific optimizations.
MOON's description of the Symbolics declarations
refered to specific optimization techniques several times.  The
STATELESS/SIDE-EFFECT-FREE proposal is intended to enable constant
folding.

More importantly there are subtle semantic difficulties with these
declarations.  The "curious property" of functions which allocate
modifyable structures seems like a dangerous trap to me.  I have
difficulty understanding the meaning and distinctions of the
Symbolics declarations.  This means they have to be used slowing and
carefully, and therefore infrequently, and therefore they are not
very useful.

Even worse is the kind of bugs that can be caused.  An incorrect
STATELESS declaration might be ignored in one programing environment
and eventually cause bugs only when the code is ported to another
environment, perhaps years and generations of programmers later.  
I consider language features which can cause hidden
bugs of this nature dangerous, and generaly think they should
be avoided.  This is why (integer 0 100) is a better type specifyer
that FIXNUM.

The only way to safely use these declarations is with a SSC(*) that
checks to verify that the function definition agrees with the
declaration.  But an SSC can compute any of these properties that
it can check, so why make the programmer use the congitive
overhead required to figure out where, when and which declarations
are needed if the compiler could do it automatically?  Simply
because the compiler cannot assume that that is the intended
definition of the functions involved.  

 From this analysis it seems very desirable to have some way to
specify that a compiler should compute and use any implementation
dependant optimization properties that it can.  All of the declarations
listed by MOON are examples of things that a compiler might compute
from a function definition and use for later optimizations.
Doing so automatically would save programmers from having to learn
the meaning of all these declarations, and prevent the possible bugs
caused by their incorrect use. 

So, can anyone suggest a good way to specify that a compiler
should commpute and use any implementation dependant optimizations
properties that it knows about (such as those properties listed by MOON),
preferably a mechanism with sufficient flexibility to offer both
corse and fine grained control?
   
   One more interesting question related to what is STATELESS arises out
   of noting the distinction drawn between Symbolic's declarations

[Translation: One more obscure fact that makes these declarations
harder to use correctly. :-) --CRE]

   (LT:SIDE-EFFECTS LT:REDUCIBLE) and (LT:SIDE-EFFECTS LT:SIMPLE REDUCIBLE).
   Is CAR STATELESS?  I say yes, even though the Symbolics terminology
   seems to imply that it is sensitive to side-effects.  In the example:

   (*) SSC -- acronym for "Sufficiently Smart Compiler"