Tamas Papp tkpapp@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. :-)