[pro] why :key arguments?
Why do some CL library functions have :key arguments? I am asking because I am working on some statistics functions, and the design choice came up. Specifically, I can write functions like (defun quantiles (sequence quantiles key (key #'identity)) ...) but it is a bit cumbersome. I can make my code simpler by relying on calls like (quantiles (map 'vector key vector) quantiles) but this conses a bit more. Not a major concern at the moment, but if it ever becomes one, I could just define a compiler macro to take care of forms like this and transform to something like (quantile-with-keys vector quantiles key) I also thought of defining something like (defgeneric map1 (function object) (:method (function (list list)) (mapcar function list)) ...) for the sole purpose of mapping objects to similar objects (eg lists to lists, arrays to arrays, etc) and allow it to be optimized away (like above) by compiler macros. 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? Thanks, Tamas ___ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
Re: [pro] why :key arguments?
On Mon, 04 Jul 2011 11:39:39 +0200, Hans Hübner wrote: On Mon, Jul 4, 2011 at 11:31 AM, Tamas Papp tkp...@gmail.com wrote: Why do some CL library functions have :key arguments? [...] but it is a bit cumbersome. I can make my code simpler by relying on calls like (quantiles (map 'vector key vector) quantiles) This not only conses a bit more, it also duplicates traversal efforts - The original list must be traversed, and the consed-up list of key values as well. I think it is prudent that the CL library functions offer ways to reduce consing for cases where a bit is too much (and a bit can become a lot if a program operates on long lists). I understand this. My main question is: why not do this with compiler macros? Is there any reason for this, other than historical? Note that I am not complaining about the standard, I just want to learn the reason for this design choice so that I can take it into account when writing my own libraries. Best, Tamas ___ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
Re: [pro] why :key arguments?
Tamas Papp tkp...@gmail.com writes: On Mon, 04 Jul 2011 11:39:39 +0200, Hans Hübner wrote: On Mon, Jul 4, 2011 at 11:31 AM, Tamas Papp tkp...@gmail.com wrote: Why do some CL library functions have :key arguments? [...] but it is a bit cumbersome. I can make my code simpler by relying on calls like (quantiles (map 'vector key vector) quantiles) This not only conses a bit more, it also duplicates traversal efforts - The original list must be traversed, and the consed-up list of key values as well. I think it is prudent that the CL library functions offer ways to reduce consing for cases where a bit is too much (and a bit can become a lot if a program operates on long lists). I understand this. My main question is: why not do this with compiler macros? Is there any reason for this, other than historical? Because it's not easy to do with compiler macros. Note that I am not complaining about the standard, I just want to learn the reason for this design choice so that I can take it into account when writing my own libraries. I find (foo sequence :key #'key) much nicer than (foo (map 'sequence #'key sequence)) -- With best regards, Stas. ___ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
Re: [pro] why :key arguments?
On Mon, 04 Jul 2011 12:12:33 +0200, Svante Carl v. Erichsen wrote: -BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Am 04.07.2011 11:31, schrieb Tamas Papp: Why do some CL library functions have :key arguments? I am asking because I am working on some statistics functions, and the design choice came up. Specifically, I can write functions like (defun quantiles (sequence quantiles key (key #'identity)) ...) but it is a bit cumbersome. I can make my code simpler by relying on calls like (quantiles (map 'vector key vector) quantiles) but this conses a bit more. Doesn't quantiles just pass the key to sort? Is there some smarter algorithm I am not aware of right now? Eg @inproceedings{greenwald2001space, title={Space-efficient online computation of quantile summaries}, author={Greenwald, M. and Khanna, S.}, booktitle={ACM SIGMOD Record}, volume={30}, number={2}, pages={58--66}, year={2001}, organization={ACM} } I am making quantiles a generic function: it should work on objects returned by the method above, and also on vectors. My problem was that (quantiles quantile-summary #(0.25 0.5 0.75) :key something) makes little sense, since the summary is already accumulated. So I will drop key for the moment, and will probably use compiler macros. I also thought of a lazy solution that would just save the function and the object, and traverse once, eg (quantiles (with-key function object) ...) but I need to think about that. Also, passing the key lets you return the complete objects (or whatever), not just the keys as in the map call. For example, compare That's a good point, I didn't think of that. Best, Tamas ___ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
Re: [pro] why :key arguments?
On Mon, 04 Jul 2011 14:20:32 +0400, Stas Boukarev wrote: Tamas Papp tkp...@gmail.com writes: On Mon, 04 Jul 2011 11:39:39 +0200, Hans Hübner wrote: On Mon, Jul 4, 2011 at 11:31 AM, Tamas Papp tkp...@gmail.com wrote: Why do some CL library functions have :key arguments? [...] but it is a bit cumbersome. I can make my code simpler by relying on calls like (quantiles (map 'vector key vector) quantiles) This not only conses a bit more, it also duplicates traversal efforts - The original list must be traversed, and the consed-up list of key values as well. I think it is prudent that the CL library functions offer ways to reduce consing for cases where a bit is too much (and a bit can become a lot if a program operates on long lists). I understand this. My main question is: why not do this with compiler macros? Is there any reason for this, other than historical? Because it's not easy to do with compiler macros. Can you (or someone) please elaborate on that? I have just started reading up on compiler macros, and I don't understand why. Thanks, Tamas ___ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
Re: [pro] why :key arguments?
Tamas Papp tkp...@gmail.com writes: On Mon, 04 Jul 2011 14:20:32 +0400, Stas Boukarev wrote: Tamas Papp tkp...@gmail.com writes: On Mon, 04 Jul 2011 11:39:39 +0200, Hans Hübner wrote: On Mon, Jul 4, 2011 at 11:31 AM, Tamas Papp tkp...@gmail.com wrote: Why do some CL library functions have :key arguments? [...] but it is a bit cumbersome. I can make my code simpler by relying on calls like (quantiles (map 'vector key vector) quantiles) This not only conses a bit more, it also duplicates traversal efforts - The original list must be traversed, and the consed-up list of key values as well. I think it is prudent that the CL library functions offer ways to reduce consing for cases where a bit is too much (and a bit can become a lot if a program operates on long lists). I understand this. My main question is: why not do this with compiler macros? Is there any reason for this, other than historical? Because it's not easy to do with compiler macros. Can you (or someone) please elaborate on that? I have just started reading up on compiler macros, and I don't understand why. Suppose you have a function SUM, (defun sum (list) (loop for i in list sum i)) Now if you want to optimize (sum (map 'list KEY list)), you would need to write an additional function. (defun sum-key (list key) (loop for i in list sum (funcall key i))) And then you would need to write a compiler macro, which would match (map 'list KEY sequence) and transform it into (sum-key sequence KEY), which is not that hard, if that's only what you have. Now what if you want it to work with (mapcar KEY list) too. It becomes more and more cumbersome as it gets more general. And now you need two functions, a clever compiler macro (perhaps using some pattern matching library), and which may not do what the user expects. While you could have all that with just one function: (defun sum (list key key) (loop for i in list sum (if key (funcall key i) i))) Other disadvantages of compiler-macros: * They are not guaranteed to be expanded. Some implementations may ignore them. * They can't be used with APPLY or FUNCALL. * You can't compose them e.g. if you wanted to write (defun two-sum (list1 list2) (+ (sum list1) (sum list2))) You would need to write a second compiler macro. While with KEY keyword you could just pass it along. -- With best regards, Stas. ___ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
Re: [pro] why :key arguments?
On 4 July 2011 19:42, Pascal J. Bourguignon p...@informatimago.com wrote: I don't think so. I disagree strongly, and I'm pretty sure CLHS agrees with me, since it goes to the trouble of specifying what happens with FUNCALL. CLHS, DEFINE-COMPILER-MACRO: The whole argument is bound to the form argument that is passed to the compiler macro function. The remaining lambda-list parameters are specified as if this form contained the function name in the car and the actual arguments in the cdr, but if the car of the actual form is the symbol funcall, then the destructuring of the arguments is actually performed using its cddr instead. (I'm not really interested in fencing re. compiler-macros here, just trying to keep the record only moderately crooked. This is a sidetrack of epic proportions already: the OP asked about :KEY, not compiler-macros.) Cheers, -- nikodemus ___ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro