From ...
From: Erik Naggum <clerik@naggum.no>
Subject: COMPLEMENT and -IF-NOT functions
Date: 1998/01/25
Message-ID: <3094693129413453@naggum.no>
X-Deja-AN: 318998935
mail-copies-to: never
Organization: Naggum Software; +47 8800 8879; http://www.naggum.no
Newsgroups: comp.lang.lisp


  although DELETE-IF-NOT and friends are deprecated, I find myself using
  them quite often and not really finding a much better replacement.  what
  do people do when you want to delete an element that does not satisfy a
  particular predicate?  is COMPLEMENT your choice?

  these are the ways that I have thought of to delete an element that fails
  to satisfy <predicate> from <list>:

(delete-if (complement <predicate>) <list>)

  although this was intended as the preferred replacement, it neither looks
  right to me nor performs right, not the least of which is because it
  throws away any knowledge I or the system might have about the function
  being complemented.  it seems to be extremely hard to make this function
  yield a reasonably fast function as a result.  when defined as

(defun complement (function)
  (lambda (&rest arguments)
    (declare (dynamic-extent arguments))
    (not (apply function arguments))))

  it should have been possible for this function to call directly to the
  closed-over function without changing its own arguments or restifying
  them, but to my (somewhat limited) knowledge, no Lisp compiler does that.
  CMUCL, known to be good at suggesting where it could need a declaration,
  complains about the lack of a type declaration so it cannot inline the
  COMPLEMENT function if it does not know the number of arguments, but
  supplying that doesn't help.  on average, using COMPLEMENT costs as much
  or more than the predicate I wish to negate.

(delete-if #'not <list> :key <predicate>)

  with this form, I have saved myself a lot of execution time relative to
  the COMPLEMENT case, but this feels even more wrong than COMPLEMENT does,
  so I include it only because I twisted my brain and this came out.

(delete-if (lambda (item) (not (<predicate> item))) <list>)

  now we're getting somewhere, at least in terms of execution time.  this
  also "feels" better than COMPLEMENT in that my knowledge of the function
  whose complement I'm asking for is retained.

(defun not-<predicate> (item) (not (<predicate> item)))
(delete-if #'not-<predicate> <list>)

  in many cases, it makes sense to define an apparent negative of some
  existing predicate with some useful name that is not just NOT-<WHATEVER>,
  and the opportunity to design things better can thus be appreciated.
  whenever this option is available, the deprecation of DELETE-IF-NOT is
  either moot or makes it easier to exercise this option.

  finally, another option is to rename REMOVE-IF-NOT to EXTRACT-IF and
  DELETE-IF-NOT to KEEP-IF or somesuch and perhaps invent useful names of
  the other -IF-NOT functions, but this seems somewhat dubious.  however,
  it could be defended by assessing current practice.

  I'm dissatisfied with all the options, really.  while it has merit,
  -IF-NOT is also not an _obviously_ great idea.  the messy situation with
  both :TEST and :TEST-NOT is certainly a prime candidate for cleanup.
  COMPLEMENT goes halfway towards a better world, but as of now, it has too
  high costs and too few benefits to be worth bothering with in my view.

  so, would anything make me happier about COMPLEMENT?  it would have
  helped a lot if the returned function had a recognizable wrapper that
  told the caller it should invert a test.  this would be a fundamental
  change to some parts of the Common Lisp system in that we have no such
  properties of functions at present.

  however, one conceptually simple way to obtain this would be if the
  FUNCTION class could have a subclass PREDICATE which meant that using the
  value always turned it magically into NIL or T.  any function instance
  could be coerced to a predicate by a declaration or a (special) operator
  PREDICATE which would affect the calling semantics.  properly recognized
  by the called function, this could be used to refrain from returning
  multiple values and other useful performance improvements.  (while we're
  at it, this could make a function return either NIL or T instead of the
  generalized boolean if it were being used as a predicate in a situation
  where the returned value might linger and inhibit garbage collection.)
  with this in place, a subclass COMPLEMENT-PREDICATE of PREDICATE could
  mean that using the value always turned it magically into T or NIL where
  PREDICATE would return NIL or T, respectively.  (both PREDICATE and
  COMPLEMENT-PREDICATE would be system classes, of course.)

  this may sound like a lot of work to help realize the deprecation of the
  -IF-NOT functions and the :TEST-NOT arguments, and it may just be too
  costly, but it appears to me that if something like COMPLEMENT is to
  succeed for real, it needs more than a hand-waving over the performance
  issues involved.  (I imagine that performance and some form of language
  elegance went into the original -IF-NOT and :TEST-NOT design to begin
  with.  it appears that some of this rationale got lost in the translation
  to COMPLEMENT.)  to support COMPLEMENT fully already requires extensive
  and depressingly unique optimizations in the compiler.  with a subclass
  of FUNCTION that enforced the knowledge that it was being used as a
  predicate, numerous optimizations are suddenly available.  also, as long
  as the value is used as a predicate, there would be no difference apart
  from performance gains over using the old function call semantics, if we
  assume that the necessary testing for whether a function is called with
  known predicate behavior or regular value-returning semantics is "free".
  this means that this work has no impact on the behavior of existing code,
  but adds a sizable opportunity for both conceptual and performance
  improvements if supported and implemented.

  finally, it is my understanding that by "deprecating" a language feature,
  the intent is to remove it at a later stage, but if there is an unclear
  need for such a feature, it will forever be "deprecated" yet remain in
  the language, and thus work against its stated goals.  therefore, I think
  we have an obligation to either support the deprecating with much better
  ways to solve the same problem, or work to revoke the deprecated status.

  I look forward to your comments.
  
#:Erik
-- 
The year "98" was new 1900 years ago.  |  Help fight MULE in GNU Emacs 20!
Be year 2000 compliant, write "1998"!  |  http://sourcery.naggum.no/emacs/