Re: [pro] why :key arguments?
On Mon, 04 Jul 2011 20:11:56 +0300, Nikodemus Siivola wrote: 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.) I am very happy to learn about these things. Currently I am working on the algorithms and my main concern is to ensure correctness; speed is secondary at this point, but even though I am not optimizing, I want to keep my code optimizable later on. My problem with the key argument is that it complicates the interface. I would like to use the same interface for sample statistics and random variables, eg currently in CL-NUM-UTILS and CL-RANDOM I have (mean #(1d0 2d0 3d0)) ; = 2, a sample mean (mean (r-normal 2 1)) ; = 2d0, mean of a univariate normal distribution If I had a :KEY argument, I would have to check that it is EQ to #'identity or not provided in methods for random variables. APPLY is not a major concern for me at the moment, all of these functions have a fixed number of arguments (usually one or two). So compiler macros still look attractive: I guess I could just write them for the function I define (eg MAP1), with the understanding that if the user wants speed, he should stick to mapping with this function. I also thought of the following possibility using runtime dispatch: (defstruct (w/key (:constructor w/key (key object))) key object) (defgeneric mean (object) (:method ((obj w/key)) (mean-w/key (w/key-object obj) (w/key-key obj))) (:method ((obj sequence)) (/ (reduce #'+ obj) (length obj (defmethod mean-w/key ((obj sequence) key) (/ (reduce #'+ obj :key key) (length obj))) (mean #(1 2 3)); = 2 (mean (w/key #'1+ #(1 2 3))) ; = 3 Tamas ___ pro mailing list pro@common-lisp.net http://lists.common-lisp.net/cgi-bin/mailman/listinfo/pro
[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
