Hi c.l.l
I'm a newbie working through Graham's ACL with the help of Chris
Riesbeck's online annotations and Lisp Critic tool. The latter always
scolds me when I accumulate values in the body of a dolist using setf
and friends, telling me to use 'do' instead. Trouble is, I can't see a
reasonable way to to do this transformation in general.
Here's an example (which started life as Graham's 'random-next'
Figure 8.3 ACL):
;; 'choices' is an alist, not empty, whose entries are pairs
;; (symbol . weight). Make a weighted random choice of symbol.
(defun weight-sum (choices)
(reduce #'+ choices :key #'cdr))
;; Graham has a snippet similar to this.
;; Lisp Critic thinks that 'i' should be updated in a 'do'.
(defun weighted-roulette-choice (choices)
(let ((i (random (weight-sum choices))))
(dolist (pair choices)
(when (minusp (decf i (cdr pair)))
(return (car pair))))))
;; Here's an equivalent 'do'. Lisp Critic still hates the setq of
;; course, but I need the new value of 'pair' when updating 'i'.
(defun weighted-roulette-choice (choices)
(do ((l choices (cdr l))
(pair nil)
(i (random (weight-sum choices)) (- i (cdr pair))))
((minusp i) (car pair))
(setq pair (car l))))
;; I can get rid of the assignment at the cost of using do* and an extra
;; variable. Lisp Critic is happy.
(defun weighted-roulette-choice (choices)
(do* ((l choices (cdr l))
(lastpair nil pair)
(pair (car l) (car l))
(i (random (weight-sum choices)) (- i (cdr lastpair))))
((< i (cdr pair)) (car pair))))
To my naive newbie eyes, this is unreadable compared to the 'dolist'
version. However, both the assignment in the body and the early return
seem tailor-made for 'do'. Is there some idiomatic way to write such
a dolist as a do?
In the end I used a cowardly 'loop':
(defun weighted-roulette-choice (choices)
(let ((roulette-spin (random (weight-sum choices))))
(loop for pair in choices
sum (cdr pair) into cumulative-weight
until (> cumulative-weight roulette-spin)
finally (return (car pair)))))
On Jan 5, 8:23 pm, sean <············@blueyonder.co.uk> wrote:
> Hi c.l.l
>
> I'm a newbie working through Graham's ACL with the help of Chris
> Riesbeck's online annotations and Lisp Critic tool. The latter always
> scolds me when I accumulate values in the body of a dolist using setf
> and friends, telling me to use 'do' instead. Trouble is, I can't see a
> reasonable way to to do this transformation in general.
>
> Here's an example (which started life as Graham's 'random-next'
> Figure 8.3 ACL):
>
> ;; 'choices' is an alist, not empty, whose entries are pairs
> ;; (symbol . weight). Make a weighted random choice of symbol.
>
> (defun weight-sum (choices)
> (reduce #'+ choices :key #'cdr))
>
> ;; Graham has a snippet similar to this.
> ;; Lisp Critic thinks that 'i' should be updated in a 'do'.
> (defun weighted-roulette-choice (choices)
> (let ((i (random (weight-sum choices))))
> (dolist (pair choices)
> (when (minusp (decf i (cdr pair)))
> (return (car pair))))))
>
> ;; Here's an equivalent 'do'. Lisp Critic still hates the setq of
> ;; course, but I need the new value of 'pair' when updating 'i'.
> (defun weighted-roulette-choice (choices)
> (do ((l choices (cdr l))
> (pair nil)
> (i (random (weight-sum choices)) (- i (cdr pair))))
> ((minusp i) (car pair))
> (setq pair (car l))))
>
> ;; I can get rid of the assignment at the cost of using do* and an extra
> ;; variable. Lisp Critic is happy.
> (defun weighted-roulette-choice (choices)
> (do* ((l choices (cdr l))
> (lastpair nil pair)
> (pair (car l) (car l))
> (i (random (weight-sum choices)) (- i (cdr lastpair))))
> ((< i (cdr pair)) (car pair))))
>
> To my naive newbie eyes, this is unreadable compared to the 'dolist'
> version. However, both the assignment in the body and the early return
> seem tailor-made for 'do'. Is there some idiomatic way to write such
> a dolist as a do?
>
> In the end I used a cowardly 'loop':
>
> (defun weighted-roulette-choice (choices)
> (let ((roulette-spin (random (weight-sum choices))))
> (loop for pair in choices
> sum (cdr pair) into cumulative-weight
> until (> cumulative-weight roulette-spin)
> finally (return (car pair)))))
I think that in these cases, the dolist is easier to read than the do/
do* constructs, but that the loop is more readable than the dolist.
The loop can be even clearer:
(defun weighted-roulette-choice (choices)
(loop with roulette-spin = (random (weight-sum choices))
for (pocket . weight) in choices
summing weight into cumulative-weight
when (> cumulative-weight roulette-spin)
return pocket))
It's a bit more verbose than a very concise do/do*, but the generated
code isn't really all that different, and this one is much easier to
read.
//J
On 6 Jan, 01:23, sean <············@blueyonder.co.uk> wrote:
> Hi c.l.l
>
> I'm a newbie working through Graham's ACL with the help of Chris
> Riesbeck's online annotations and Lisp Critic tool. The latter always
> scolds me when I accumulate values in the body of a dolist using setf
> and friends, telling me to use 'do' instead. Trouble is, I can't see a
> reasonable way to to do this transformation in general.
If you're looking to avoid setting local variables as you move across
sequences, map and reduce are often a good choice.
(defun weighted-roulette-choice (choices)
(block nil
(reduce (lambda(x y) (if (> x (cdr y))
(- x (cdr y))
(return (car y))))
choices :initial-value (random (weight-sum choices)))))
Chris Russell <·····················@gmail.com> writes:
> ...
> If you're looking to avoid setting local variables as you move across
> sequences, map and reduce are often a good choice.
Very true.
> (defun weighted-roulette-choice (choices)
> (block nil
> (reduce (lambda(x y) (if (> x (cdr y))
> (- x (cdr y))
> (return (car y))))
> choices :initial-value (random (weight-sum choices)))))
Nice.
I hate to be nit-picking, but I find this indentation makes it
clearer, especially moving CHOICES so it is aligned with the lambda
expression (as well as using RETURN-FROM and swapping the cases,
though these are higher-order corrections):
(defun weighted-roulette-choice (choices)
(reduce (lambda (x y)
(if (<= x (cdr y))
(return-from weighted-roulette-choice (car y))
(- x (cdr y))))
choices
:initial-value (random (weight-sum choices))))
---Vassil.
--
Bound variables, free programmers.
On 6 Jan, 05:32, Vassil Nikolov <···············@pobox.com> wrote:
> Nice.
Thanks.
>
> I hate to be nit-picking, but I find this indentation makes it
> clearer, especially moving CHOICES so it is aligned with the lambda
> expression (as well as using RETURN-FROM and swapping the cases,
> though these are higher-order corrections):
>
> (defun weighted-roulette-choice (choices)
> (reduce (lambda (x y)
> (if (<= x (cdr y))
> (return-from weighted-roulette-choice (car y))
> (- x (cdr y))))
> choices
> :initial-value (random (weight-sum choices))))
>
> ---Vassil.
I agree with most of your comments. Google groups disagrees with emacs
about what a tab means, and my reason for using block...return was so
that I could exactly mimic the behaviour of the do loop, rather than
just the function output. But why did you switch the cases?
On 6 Jan, 15:10, Vassil Nikolov <···············@pobox.com> wrote:
> (defun choose (init choices)
> (flet ((first-pocket (pairs) (caar pairs))
> (first-weight (pairs) (cdar pairs)))
> (do ((i init (- i (first-weight pairs)))
> (pairs choices (rest pairs)))
> ((< i (first-weight pairs))
> (first-pocket pairs)))))
>
> (in the context of the larger program, FIRST-POCKET and FIRST-WEIGHT
> might be global functions (declaimed inline) as (part of) the
> abstractions for dealing with weighted pockets). Note that we
> _have_ to represent somewhere the way our lists of conses carry the
> data, whether it is with functions as the above ones or with
> destructuring as in the solution with LOOP.
Personally I much prefer the implicit destructuring of loop. It seems
to hit the sweet spot in terms of being terse, localised and easy to
read.
So after Joshua's and Kenny's loop examples I did this:
(defmacro ^ (vars &body body)
"Destructuring lambda"
`(lambda (&rest ,(third (setf body `(destructuring-bind ,vars ,
(gensym) ,@body))))
,body))
Which you can use like:
(defun weighted-roulette-choice (choices)
(reduce (^ (x (obj . val))
(if (<= x val)
(return-from weighted-roulette-choice obj)
(- x val)))
choices
:initial-value (random (weight-sum choices))))
And I'd rather do something similar with do.
Chris Russell <·····················@gmail.com> writes:
> On 6 Jan, 05:32, Vassil Nikolov <···············@pobox.com> wrote:
> ...
>> I hate to be nit-picking, but I find this indentation makes it
>> clearer, especially moving CHOICES so it is aligned with the lambda
>> expression (as well as using RETURN-FROM and swapping the cases,
>> though these are higher-order corrections):
>>
>> (defun weighted-roulette-choice (choices)
>> (reduce (lambda (x y)
>> (if (<= x (cdr y))
>> (return-from weighted-roulette-choice (car y))
>> (- x (cdr y))))
>> choices
>> :initial-value (random (weight-sum choices))))
>>
>> ---Vassil.
> I agree with most of your comments. Google groups disagrees with emacs
> about what a tab means, and my reason for using block...return was so
> that I could exactly mimic the behaviour of the do loop, rather than
> just the function output.
Fair enough.
> But why did you switch the cases?
Just because I'm so used to having the base case come first.
Again, this is secondary (or tertiary).
> ...
> (defmacro ^ (vars &body body)
> "Destructuring lambda"
> `(lambda (&rest ,(third (setf body `(destructuring-bind ,vars ,
> (gensym) ,@body))))
> ,body))
>
> Which you can use like:
>
> (defun weighted-roulette-choice (choices)
> (reduce (^ (x (obj . val))
> (if (<= x val)
> (return-from weighted-roulette-choice obj)
> (- x val)))
> choices
> :initial-value (random (weight-sum choices))))
Yes, that seems a useful tool. (Perhaps an alphabetic name would be
better; DLAMBDA?)
> And I'd rather do something similar with do.
There could certainly be a descendant of DO that provides
destructuring, but I don't know if anyone would set about to
implement it, or if it would gain any popularity.
---Vassil.
P.S. I didn't untabify the quoted portions above...
--
Bound variables, free programmers.
On Sat, 5 Jan 2008 20:47:06 -0800 (PST),
Chris Russell <·····················@gmail.com> wrote:
> If you're looking to avoid setting local variables as you move across
> sequences, map and reduce are often a good choice.
>
> (defun weighted-roulette-choice (choices)
> (block nil
> (reduce (lambda(x y) (if (> x (cdr y))
> (- x (cdr y))
> (return (car y))))
> choices :initial-value (random (weight-sum choices)))))
Very nice. Minor quibble: the test should be
(if (>= x (cdr y)) etc
sean wrote:
> Hi c.l.l
>
> I'm a newbie working through Graham's ACL with the help of Chris
> Riesbeck's online annotations and Lisp Critic tool. The latter always
> scolds me when I accumulate values in the body of a dolist using setf
> and friends, telling me to use 'do' instead. Trouble is, I can't see a
> reasonable way to to do this transformation in general.
>
> Here's an example (which started life as Graham's 'random-next'
> Figure 8.3 ACL):
>
>
> ;; 'choices' is an alist, not empty, whose entries are pairs
> ;; (symbol . weight). Make a weighted random choice of symbol.
>
> (defun weight-sum (choices)
> (reduce #'+ choices :key #'cdr))
>
> ;; Graham has a snippet similar to this.
> ;; Lisp Critic thinks that 'i' should be updated in a 'do'.
> (defun weighted-roulette-choice (choices)
> (let ((i (random (weight-sum choices))))
> (dolist (pair choices)
> (when (minusp (decf i (cdr pair)))
> (return (car pair))))))
>
> ;; Here's an equivalent 'do'. Lisp Critic still hates the setq of
> ;; course, but I need the new value of 'pair' when updating 'i'.
> (defun weighted-roulette-choice (choices)
> (do ((l choices (cdr l))
> (pair nil)
> (i (random (weight-sum choices)) (- i (cdr pair))))
> ((minusp i) (car pair))
> (setq pair (car l))))
>
> ;; I can get rid of the assignment at the cost of using do* and an extra
> ;; variable. Lisp Critic is happy.
> (defun weighted-roulette-choice (choices)
> (do* ((l choices (cdr l))
> (lastpair nil pair)
> (pair (car l) (car l))
> (i (random (weight-sum choices)) (- i (cdr lastpair))))
> ((< i (cdr pair)) (car pair))))
>
>
> To my naive newbie eyes, this is unreadable compared to the 'dolist'
> version. However, both the assignment in the body and the early return
> seem tailor-made for 'do'. Is there some idiomatic way to write such
> a dolist as a do?
>
>
> In the end I used a cowardly 'loop':
>
> (defun weighted-roulette-choice (choices)
> (let ((roulette-spin (random (weight-sum choices))))
> (loop for pair in choices
> sum (cdr pair) into cumulative-weight
> until (> cumulative-weight roulette-spin)
> finally (return (car pair)))))
>
>
I chickened out with:
(defun weighted-roulette-choice (choices)
(loop with i = (random (weight-sum choices))
for (choice . weight) in choices
when (minusp (decf i weight))
return choice))
Exactly half the parentheses of PG's version! Note that IMHO the right
name for a variable (choice vs pair) is the semantics of its content,
not a doc string for its representation. Fixing i left as an exercise.
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
sean <············@blueyonder.co.uk> writes:
> ...
> (defun weighted-roulette-choice (choices)
> (let ((i (random (weight-sum choices))))
> (dolist (pair choices)
> (when (minusp (decf i (cdr pair)))
> (return (car pair))))))
There are many ways of doing this, of course. I can't promise you
that the way I'd do it is the most pedagogical of them...
First, let's rewrite the DOLIST in functional style, as the least
error-prone way---this is probably the most difficult step:
(defun choose (i choices)
(if (< i (cdar choices))
(caar choices)
(choose (- i (cdar choices)) (cdr choices))))
(choose 7 '((a . 2) (b . 4) (c . 6)))
=> c
The above should be obviously correct, except for those pesky CxyR's
(but that's for another day (the CxyR's do not reduce the
correctness, only the obviousness!)).
Then, the above can be rewritten (mechanically, even) into a DO:
(defun choose (init choices)
(do ((i init (- i (cdar pairs)))
(pairs choices (cdr pairs)))
((< i (cdar pairs))
(caar pairs))))
(choose 7 '((a . 2) (b . 4) (c . 6)))
=> c
The last step is "cosmetic":
(defun weighted-roulette-choice (choices
&optional (init (random (weight-sum choices))))
(do ((i init (- i (cdar pairs)))
(pairs choices (cdr pairs)))
((< i (cdar pairs))
(caar pairs))))
(the optional second parameter is just so we can exercise this
repeatedly with the same values if we want to---obviously, we have
to be careful not to supply too large a value).
(weighted-roulette-choice '((a . 2) (b . 4) (c . 6)) 7)
=> c
"And nobody played synthesizer... again..."
* * *
Needless to say, this kind of workout that you are doing, as well as
using a tool such as Lisp Critic and paying attention to it in order
to improve one's programming skills, are both _excellent_ ideas.
Good luck,
Vassil.
--
Bound variables, free programmers.
Vassil Nikolov wrote:
> sean <············@blueyonder.co.uk> writes:
>
>
>>...
>>(defun weighted-roulette-choice (choices)
>> (let ((i (random (weight-sum choices))))
>> (dolist (pair choices)
>> (when (minusp (decf i (cdr pair)))
>> (return (car pair))))))
>
>
> There are many ways of doing this, of course. I can't promise you
> that the way I'd do it is the most pedagogical of them...
>
> First, let's rewrite the DOLIST in functional style, as the least
> error-prone way---this is probably the most difficult step:
>
> (defun choose (i choices)
> (if (< i (cdar choices))
> (caar choices)
> (choose (- i (cdar choices)) (cdr choices))))
Since this obscures perfectly any semantics of any of the data, you have
been awarded full marks and promoted to CLO (Chief Lisp Obfuscator).
ie, Nice!
>
> (choose 7 '((a . 2) (b . 4) (c . 6)))
> => c
>
> The above should be obviously correct, except for those pesky CxyR's
> (but that's for another day (the CxyR's do not reduce the
> correctness, only the obviousness!)).
Glorious. A defense against non-obviousness conceding, nay, embracing
non-obviousness. You are The One.
>
> Then, the above can be rewritten (mechanically, even) into a DO:
>
> (defun choose (init choices)
> (do ((i init (- i (cdar pairs)))
> (pairs choices (cdr pairs)))
> ((< i (cdar pairs))
> (caar pairs))))
>
> (choose 7 '((a . 2) (b . 4) (c . 6)))
> => c
>
> The last step is "cosmetic":
>
> (defun weighted-roulette-choice (choices
> &optional (init (random (weight-sum choices))))
> (do ((i init (- i (cdar pairs)))
> (pairs choices (cdr pairs)))
> ((< i (cdar pairs))
> (caar pairs))))
Stunning!
> Needless to say, this kind of workout that you are doing, as well as
> using a tool such as Lisp Critic and paying attention to it in order
> to improve one's programming skills, are both _excellent_ ideas.
Oh. I thought we were trying to write applications. Did you thin this
was c.l.scheme? They love issues having nothing to do with getting
actula work done.
kt
ps. wtf is Lisp Critic? I want to run it on my 200kloc of Lisp, watch it
cry. k
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On 2008-01-06 05:12:57 +0000, Ken Tilton <···········@optonline.net> said:
> ps. wtf is Lisp Critic? I want to run it on my 200kloc of Lisp, watch it cry. k
http://www.cs.northwestern.edu/academics/courses/325/programs/lisp-critic.lisp
--
JFB
verec wrote:
> On 2008-01-06 05:12:57 +0000, Ken Tilton <···········@optonline.net> said:
>
>> ps. wtf is Lisp Critic? I want to run it on my 200kloc of Lisp, watch
>> it cry. k
>
>
> http://www.cs.northwestern.edu/academics/courses/325/programs/lisp-critic.lisp
>
Thx. It seems to like me. Weird thing about "don't use EQ unless you are
doing something special". Makes me wonder what would be special. I
assume it does mean "when you know when EQ is correct for the things
being compared".
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
Ken Tilton wrote:
>
>
> verec wrote:
>> On 2008-01-06 05:12:57 +0000, Ken Tilton <···········@optonline.net>
>> said:
>>
>>> ps. wtf is Lisp Critic? I want to run it on my 200kloc of Lisp, watch
>>> it cry. k
>>
>>
>> http://www.cs.northwestern.edu/academics/courses/325/programs/lisp-critic.lisp
>>
>
> Thx. It seems to like me.
Ah, good, the "be nice to Tilton" check is working.
> Weird thing about "don't use EQ unless you are
> doing something special". Makes me wonder what would be special. I
> assume it does mean "when you know when EQ is correct for the things
> being compared".
The current phrasing is more prescriptive than I tend to write these
days, but your alternative is probably too circular for students just
learning Lisp. For pedagogical purposes, I mostly want to raise red
flags and have them go off to the book or Hyperspec to find out more.
So, while I'll probably rephrase the above, wondering what 'special'
means in this context is an OK reaction for me.
Chris Riesbeck wrote:
> Ken Tilton wrote:
>
>>
>>
>> verec wrote:
>>
>>> On 2008-01-06 05:12:57 +0000, Ken Tilton <···········@optonline.net>
>>> said:
>>>
>>>> ps. wtf is Lisp Critic? I want to run it on my 200kloc of Lisp,
>>>> watch it cry. k
>>>
>>>
>>>
>>> http://www.cs.northwestern.edu/academics/courses/325/programs/lisp-critic.lisp
>>>
>>
>>
>> Thx. It seems to like me.
>
>
> Ah, good, the "be nice to Tilton" check is working.
I had a feeling. But we won't know for sure until you teach it to read
in a .lisp file (preferably all found in a directory tree) and then
rewrite the source as a .txt with criticism inserted.
You can use print instead of format where you do need the extra
flexibility of format. <hint>
>
>> Weird thing about "don't use EQ unless you are doing something
>> special". Makes me wonder what would be special. I assume it does mean
>> "when you know when EQ is correct for the things being compared".
>
>
> The current phrasing is more prescriptive than I tend to write these
> days, but your alternative is probably too circular for students just
> learning Lisp.
Actually that was not an alternative, that was sarcasm (with the
circularity implying they should learn EQ vs EQL vs EQUAL in which case
the critic could leave EQ alone unless see below) spoiled by a crucial typo.
> For pedagogical purposes, I mostly want to raise red
> flags and have them go off to the book or Hyperspec to find out more.
> So, while I'll probably rephrase the above, wondering what 'special'
> means in this context is an OK reaction for me.
It might be easier to lose the rule. EQ can be wrong, but it cannot be
bad style. Of course if you can spot "wrong" because of inappropriate
literals at hand, holler at will. In my two red flags on this issue you
would have found one symbol in each comparison.
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Sat, 05 Jan 2008 21:36:14 -0500,
Vassil Nikolov <···············@pobox.com> wrote:
<snip>
> The above should be obviously correct, except for those pesky CxyR's
<snip>
> (defun choose (init choices)
> (do ((i init (- i (cdar pairs)))
> (pairs choices (cdr pairs)))
> ((< i (cdar pairs))
> (caar pairs))))
I think those 'pesky CxyR's are the nub of the problem. They mask the
fact that if you use a variable to cdr down a list, then you have no
easy way to get the car of that list into a do variable. You have to
implicitly call car in the update expression for i, the test expression
and the result expression. I like this slightly less than the hideous
do* with extra variable in my OP.
I thought I might be missing some nuance of the update rules for do/do*,
but it looks like do/do* are just the wrong tools for the job.
sean <············@blueyonder.co.uk> writes:
> On Sat, 05 Jan 2008 21:36:14 -0500,
> Vassil Nikolov <···············@pobox.com> wrote:
> ...
>> (defun choose (init choices)
>> (do ((i init (- i (cdar pairs)))
>> (pairs choices (cdr pairs)))
>> ((< i (cdar pairs))
>> (caar pairs))))
>
> I think those 'pesky CxyR's are the nub of the problem. They mask the
> fact that if you use a variable to cdr down a list, then you have no
> easy way to get the car of that list into a do variable. You have to
> implicitly call car in the update expression for i, the test expression
> and the result expression. I like this slightly less than the hideous
> do* with extra variable in my OP.
I wanted to separate that from the matter of laying the DO out. One
could claim that the use of CxyR is idiomatic, but let's say that is
debatable, and so one way to deal with the CxyR's is this:
(defun choose (init choices)
(flet ((first-pocket (pairs) (caar pairs))
(first-weight (pairs) (cdar pairs)))
(do ((i init (- i (first-weight pairs)))
(pairs choices (rest pairs)))
((< i (first-weight pairs))
(first-pocket pairs)))))
(in the context of the larger program, FIRST-POCKET and FIRST-WEIGHT
might be global functions (declaimed inline) as (part of) the
abstractions for dealing with weighted pockets). Note that we
_have_ to represent somewhere the way our lists of conses carry the
data, whether it is with functions as the above ones or with
destructuring as in the solution with LOOP.
Probably the way to go in general is what Chris Russell suggested.
Note how both the solution with REDUCE he posted and the one with DO
follow a patter that is independent of the operation (in this case,
subtraction) on the values in the list. On the other hand, a
solution with LOOP changes somewhat abruptly between a case where
LOOP has a built-in facility (such as SUMMING) for the operation and
where it doesn't, so in order to fully manage with LOOP, the
programmer has to master two patterns instead of one.
Moreover, with REDUCE as well as with DO, there are only two
variables of the iteration, while with LOOP there are three, and
fewer are better, in my opinion at least.
---Vassil.
--
Bound variables, free programmers.