SIDE-EFFECT-FREE/STATELESS Functions

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: Mon, 16 May 88 17:55:30 PDT
    From: Jon L White <edsel!jonl@labrea.stanford.edu>

    ....
    One more interesting question related to what is STATELESS arises out
    of noting the distinction drawn between Symbolic's declarations
    (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.  

CAR is certainly sensitive to side-effects, in the sense that a side-effect
on its argument can change its result.  It's true that CAR doesn't
reference any (obvious) free variables.

    So, I would prefer to say that the argument to CAR can be modified by 
    side-effecting functions; hence a compiler must keep track not only of the
    properties of the function it is compiling a call to, but also of the 
    potential alterations to the arguments to that function.  The same analysis 
    applies to arrays, hash-tables, defstructs and so on, as well as to cons cells.

As I said in my earlier message, the Symbolics declarations do not
attempt to keep track of aliasing.  Thus there is no distinction between
side-effects that are known to be connected with a particular object,
and side-effects in general.  Aliasing can be fairly difficult to
track in Lisp, and even more so in a language extended with locatives
(which allow non-type-specific operations to access aliases).