SIDE-EFFECT-FREE/STATELESS Functions

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

re: . . .  Should "ERROR" and
    "CERROR" be considered side effect free for this purpose?
    If not then functions like division can't be considered side
    effect free, since division by zero must signal an error.

Hmmm, I think you've hit upon a good question.  The only way I can around 
the problem is to define these kinds of properties of a function based on 
"correct" arguments, and without regard to asynchronous interrupts.  After 
all, in virtually every implementation, you could interrupt almost any old 
random function, and cause whatever malevolent side-effects you want.  Thus
division should be considered "simple", even though there is a legal path
through it that calls a function with probable side-effects.

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.

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.  In the example:

   (let ((x (list '1 '2)))
     (print (CAR (cdr x)))			[1]
     (rplaca (cdr x) '3)			[2]
     (print (CAR (cdr x))))			[3]

One might be tempted to say that CAR is sensitive to the side-effect on
line [2]; but it certainly isn't sensitive to side-effects the way INTERN
is sensitive to the setting of *PACKAGE*.  That is, no state other than
the argument is needed to produce the result.  What is going on here is
that two _different_ arguments are being given to CAR at two different
times (times [1] and [3]);  even though they appear to be EQ at the times 
of call, they are not EQUAL, and that is the equivalence of importance when
talking about list accessors.  (EQ but not EQUAL -- quite iconoclastic, no?).

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.

By contrast, the arguments to + cannot be modified by any CLtL function, 
and this is presumably what LT:SIMPLE adds to LT:REDUCIBLE for Symbolics.
[Remember my previous note about SETN in Interlisp?].  Unfortunately, there 
aren't many read-only datatypes in Common Lisp.


-- JonL --


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