SIDE-EFFECT-FREE/STATELESS Functions

[Jon L White <edsel!jonl@labrea.stanford.edu>]

The discussion on "constant functions" seems to me to have reached a
dead end.  But one good thing to come from it is the discovery that
CL provides no declaration that enables "constant folding", a very
useful optimization in quite a number of compilers.

In a more general sense, a user would want to be able to tell the
compiler that a certain named function has no internal state and that:
   (1) it has no side effects, and
   (2) its value is completely determined by its arguments.
Thus RANDOM is not side-effect-free, since it updates *random-state*; and 
while FIND-SYMBOL is side-effect-free, it is not stateless since it is 
sensitive to the setting of the global variable *package* as well as to 
the entries in the package database. AREF is both side-effect-free and
stateless.  

A compiler can perform the following optimization on a stateless and
side-effect-free function:
  (A) Calls with arguments that are compile-time constant may be "folded"
      into the literal data object evaluable at compile time;
  (B) Common subexpressions that are calls to such a function may be 
      "reduced" [in the sense described by barmar and Soley];
  (C) A call to such a function, whose return value is not consumed by
      subsequent program parts, can be eliminated [this is also true if 
      the function is merely side-effect-free];
  (D) Calls to such a function might be commutable with other program
      segments ["communting" arguments in function calls is an optimization 
      that some compilers will try to do], since the call itself to such a
      function doesn't have interactions with other program parts.

Would it be desirable to have two new declarations:  SIDE-EFFECT-FREE and
STATELESS?  Is there already a terminology somewhere in use for these 
properties?


Oddly enough, functions which return a feshly-allocated pointer to some
updatable storage are not stateless, even though they are side-effect-free 
-- CONS, APPEND, and MAKE-ARRAY are examples -- because the value of this 
kind of function is essentially an address; and that address is sensitive 
to the internal pointer to the "free list".  Consider the following:

    (let ((l '(1 2)))
      (setq a (copy-list l))
      (setq b (copy-list l)))

If COPY-LIST were stateless, then a and b should be identical; but the 
existence of RPLACA means they can't be identical in a fundamental sense.
Note that the critical argument in this paragraph depends on the word
"updatable".  For example, * is a stateless function; and in

     (let ((x (factorial 100))
           (y (factorial 200)))
       (setq a (* x y))		;surely a bignum
       (setq b (* x y)))	;surely another bignum, of same value

a and b will hold identical results.  True, they will likely be 
distinguishable by EQ, but there is _no_ update function such that an 
update to a would not be seen as an update to b also.  The EQL comparison 
is the relevant one for "identicalness", rather than EQ, even though a and 
b are both pointers to freshly-allocated storage. 

Long ago, PDP10 Interlisp provided a primitive language function called SETN
that would do just this -- it would bash the bits of a stored  number object
 -- but happily CL has nothing like this; if it did, then generic 
multiplication would not be a stateless function.



-- JonL --