Subject: COMPLEMENT and -IF-NOT functions From: Erik Naggum <clerik@naggum.no> Date: 1998/01/25 Newsgroups: comp.lang.lisp Message-ID: <3094693129413453@naggum.no> 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/