[pro] why :key arguments?

[Pascal J. Bourguignon]

Tamas Papp <tkpapp at gmail.com> writes:

> I would appreciate advice on this.  I am especially interested in the 
> reason why some CL functions have :key arguments: is it because of 
> efficiency, backward-compatibility/history, or something else?

The rationals for Common Lisp are generally explained in the first
chapter of CLHS, and in the "Issues".

In short, the reason CL has &KEY is because most of the languages it
purposed to generalize had &KEY.  The reason  why some functions have a
:KEY argument is because they had it in (at least some of) the original
languages.

http://www.lispworks.com/documentation/HyperSpec/Body/01_ab.htm
http://www.lispworks.com/documentation/HyperSpec/Issues/iss017_w.htm
http://www.lispworks.com/documentation/HyperSpec/Issues/iss109_w.htm



Now about :KEY, each function processing sequence has the opportunity of
having to work from a "key" value of the element instead of directly on
the element.  The typical example is sort:

    (sort seq
          (lambda (a b) (< (element-key a) (element-key b))))

But remember that there are a lot of such functions:

    (merge 'list seq1 seq2 
           (lambda (a b) (< (element-key a) (element-key b))))


Now this lambda is not too much of a problem, we could even write HOFs
to make them easily, like: (compose-2 '< 'element-key).
But the problem here is that element-key will be called much more than
it is necessary.  Of course, the alternative is to wrap the sequence,
into a keyed sequence that caches it:

   (defun wrap (seq key) 
     (map 'vector (lambda (item) (cons (funcall key item) item)) seq))
   (defun wrapped-key (wrapped-item) (car wrapped-item))
   (defun unwrap (original-seq wrapped-seq)
     (map-into original-seq (function cdr) wrapped-seq))


   (unwrap seq
           (sort (wrap seq (function element-key))
                 (lambda (a b) (< (wrapped-key a) (wrapped-key b)))))

   (unwrap list
           (sort (wrap list (function car))
                 (lambda (a b) (string< (wrapped-key a) (wrapped-key b)))))

   (unwrap (make-list (+ (length seq1) (length seq2)))
           (merge 'vector (wrap seq1 (function element-key))
                          (wrap seq2 (function element-key))
                          (lambda (a b) (< (wrapped-key a) (wrapped-key b)))))

   ; and so on.

You may kind of notice some boilerplate coding there.

So what's the same, and what changes from one call to the other?
What's the same is the boilerplate unwrap/wrap/lambda.
What changes is the sequence, the lessp function and the key function.

Therefore we shall write:

        (sort seq lessp key)
        (merge result-type seq1 seq2 lessp key)

and leave the boilerplate inside those functions.  Some of them may
even spare some further calls to the (possibly costly) key function,
if they don't need to wrap the whole sequence to do their work.


Now, of course, 90% of the time, you will call:

        (sort seq lessp (function identity))
        (merge result-type seq1 seq2 lessp (function identity))

so it would be nice if that was optional.  No problem, we have
&OPTIONAL.  But then we have all those functions such as POSITION, FIND,
MEMBER, etc, who not only have an optional :KEY parameter, but also, for
the same reason, an optional :TEST or :START :END or any other
parameter, and it becomes difficult to use if you want the third
optional but not the previous.  Hence the invention of &key parameters.

Remember that &KEY covers &REST parameters.  &KEY parameters are only
&REST parameters structured in a specific way, structured like a p-list.

And since for functions such as POSITION, FIND, MEMBER, etc we have to
use &KEY parameters for :KEY, we generalize and use &KEY parameters even
for functions such as SORT and MERGE that only would have a :KEY
parameter.



Obviously it was done so that it would be a no brainer, so that YOU (the
language user) wouldn't have to think about it, but it failed
lamentably. :-)


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.