[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
- To: email@example.com
- Subject: SIDE-EFFECT-FREE/STATELESS Functions
- From: Jon L White <firstname.lastname@example.org>
- Date: Fri, 13 May 88 01:56:30 PDT
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
A compiler can perform the following optimization on a stateless and
(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
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 --