Subject: Re: COMPLEMENT and -IF-NOT functions
From: Erik Naggum <clerik@naggum.no>
Date: 1998/01/29
Newsgroups: comp.lang.lisp
Message-ID: <3095034865019317@naggum.no>


* Barry Margolin
| Almost no one has a copy of the FS (F* Standard).

  OK, so my attempted joke fell utterly on its face.  the point was really
  no more than to show that by using a silly abbreviation (nobody used "FM"
  for "F*cking Manual" before Pierpaolo Bernardi did) while getting on his
  high horse and engaging in hand-waving over the _entire_ standard, he
  communicated arrogance and uselessness in an unfunny way.  I tried to
  communicate arrogance and uselessness in a funny way, while including a
  Clinton clause with which I could show that I had given a very precise
  reference, should that be needed, or really hadn't given a reference at
  all, should that be needed.  oh, well.  sorry for wasting people's time.

  however, to the issue at hand:

  I believe there's a different issue at work than the one that appears to
  be the focal point.  Pierpaolo appears to believe that Common Lisp
  requires functions to honor a contract that says "unless you _know_ what
  will happen to a binding that you declare DYNAMIC-EXTENT, you cannot use
  that declaration" _and_ that his contract has indefinite extent, as it
  were: that any violation anywhere will render a program non-conforming
  and that the behavior is therefore undefined.  I contend that the latter
  part of this is not only silly, it's counter-productive in the extreme
  and renders DYNAMIC-EXTENT worthless, because it is _impossible_ to know
  how any function uses its arguments unless it is part of that function's
  contract (like the symbol name argument to INTERN, or the key to a hash
  function, which is subect to a whole separate clause, 18.1.2).

  whenever a function may destructively modify an argument, it has to say
  so in its specification, and we may safely assume that unless such is
  part of its specification, it does not destructively modify an argument.
  likewise, when the exported behavior requires the caller to refrain from
  destructively modifying an object passed as argument, that must be part
  of the specification.  however, there is no such requirement on functions
  to document their _internal_ use of their arguments.  if a function needs
  an object passed as an argument to remain the same for the rest of its
  lifetime (such as when memoizing) it can just _copy_ the object, in
  preference to imposing a "don't touch this" rule on all its callers in
  _violation_ of the contract.  there are a few exceptions to this rule;
  INTERN, in particular¹.

  in the context of COMPLEMENT, we are _clearly_ talking about predicates,
  the exported behavior of which is _clearly_ side-effect-free, and their
  contract _clearly_ precludes imposing a non-destructive policy on any of
  the arguments they were passed.

  finally, some quotes and references.  as part of the description of
  APPLY, we find:

When the function receives its arguments via &rest, it is permissible (but
not required) for the implementation to bind the rest parameter to an
object that shares structure with the last argument to apply.  Because a
function can neither detect whether it was called via apply nor whether (if
so) the last argument to apply was a constant, conforming programs must
neither rely on the list structure of a rest list to be freshly consed, nor
modify that list structure.

  as part of the description of DYNAMIC-EXTENT, we find:

In some containing form, F, this declaration asserts for each vari (which
need not be bound by F), and for each value vij that vari takes on, and for
each object xijk that is an otherwise inaccessible part of vij at any time
when vij becomes the value of vari, that just after the execution of F
terminates, xijk is either inaccessible (if F established a binding for
vari) or still an otherwise inaccessible part of the current value of vari
(if F did not establish a binding for vari).  The same relation holds for
each fni, except that the bindings are in the function namespace.

The compiler is permitted to use this information in any way that is
appropriate to the implementation and that does not conflict with the
semantics of Common Lisp.

  in the examples section of DYNAMIC-EXTENT, we find:

A variant of this is the so-called ``stack allocated rest list'' that can
be achieved (in implementations supporting the optimization) by:

 (defun f (&rest x)
   (declare (dynamic-extent x))
   ...)

Note that although the initial value of x is not explicit, the f function
is responsible for assembling the list x from the passed arguments, so the
f function can be optimized by the compiler to construct a stack-allocated
list instead of a heap-allocated list in implementations that support such.

  in the discussion of the DYNAMIC-EXTENT issue, we find:

KMP: ... it still raises the question of whether we should define
per-function for every CL function whether any of the arguments is
permitted to be "saved" so that CL programs don't get any funny
surprises. If we don't, it ends up being implementor's discretion how to
resolve cases ... and everyone might not agree that all cases are
... obvious ...

<URL:http://www.harlequin.com/books/HyperSpec/Issues/iss142-writeup.html>

#:Erik
-------
¹ although interns appear to be no exception elsewhere
-- 
I believe in life after Year 2000, four-digit years, and 24-hour clocks.  I
believe in ISO 8601 as the only external time representation.  I believe in
a monotonically increasing number of milliseconds as the only internal time
representation.  I pledge to fight time zones and other time formats.  Amen