Would you please criticize this routine?
Shin
I am self-studying Common Lisp and as a self-assignement I have written
this sieve of Eratosthenes working on cdr's of a list but I am not sure
whether I do it safely or the function works because of how Allegro CL
DELETEs elements... would you please comment on this code?
(defun primes-up-to (n)
"Sieve of Eratosthenes"
(when (< n 2) (return-from primes-up-to ()))
(when (= n 2) (return-from primes-up-to '(2)))
(when (evenp n) (decf n))
(let ((upper-bound (floor (sqrt n)))
(result (do ((l (list n) (cons n l))
(n (- n 2) (- n 2)))
((= n 1) l))))
(do ((to-filter result (rest to-filter)))
((< upper-bound (first to-filter)) (cons 2 result))
(setq to-filter
(delete-if
(lambda (a) (zerop (mod a (first to-filter))))
(rest to-filter))))))
Thank you very much,
-- Shin
Shin
I am very sorry, the SETQ here isn't what I had in mind:
: (do ((to-filter result (rest to-filter)))
: ((< upper-bound (first to-filter)) (cons 2 result))
: (setq to-filter
: (delete-if
: (lambda (a) (zerop (mod a (first to-filter))))
: (rest to-filter))))))
Should read:
(do* ((to-filter result (rest to-filter))
(p (first to-filter) (first to-filter)))
((< upper-bound p) (cons 2 result))
(rplacd to-filter
(delete-if (lambda (a) (zerop (mod a p))) (rest to-filter))))))
-- Shin
Shin
: I am self-studying Common Lisp and as a self-assignement I have written
: this sieve of Eratosthenes working on cdr's of a list but I am not sure
: whether I do it safely or the function works because of how Allegro CL
: DELETEs elements... would you please comment on this code?
<snip>
I have isolated my real doubt, which hadn't to do with DELETE but with
knowing whether RPLACD is equivalent to SETF + REST.
This is explained in Cltl2.
Thanks anyway,
-- Shin
Tom Breton
> Hello,
>
> I am self-studying Common Lisp and as a self-assignement I have written
> this sieve of Eratosthenes working on cdr's of a list but I am not sure
> whether I do it safely or the function works because of how Allegro CL
> DELETEs elements... would you please comment on this code?
First, use comments. I'm reluctant to say "use comments *more*", as
if more equalled better. But when a comment is called for, don't
hesitate. Getting your comments correct, while it may seem to make no
difference, makes a world of difference when you come back to your
code and have no idea why the code does a certain thing.
What's really important is to make your comments informative. The
basic thing to keep in mind with comments is that the reader *can
already read Lisp*. Comments should usually explain *why* certain
things are done. And I mean "why" in terms of what it needs to do to
co-operate with other code, usually. Comments that repeat what the
code says are pointless. OTOH, summing up what a complex or obscure
block of code does is helpful. (it shouldn't be complex or obscure,
but sometimes it can't be helped). For code that massages data, I
also find that state comments like ";;Now the data meets such and such
condition" are good.
> (defun primes-up-to (n)
> "Sieve of Eratosthenes"
Canonically, documentation strings first say what the function gives,
eg "return all primes below N". Then they say what the arguments
should be. In this case, "N is an integer" is so obvious that it may
be superfluous unless you're meeting some formal standard. Then
miscellaneous information helpful to the caller.
"Sieve of Eratosthenes" is really a comment wrt the algorithm being
used, not function documentation. It tells the caller nothing.
> (when (< n 2) (return-from primes-up-to ()))
> (when (= n 2) (return-from primes-up-to '(2)))
> (when (evenp n) (decf n))
A single `cond' is clearer than these multiple `when's.
> (let ((upper-bound (floor (sqrt n)))
> (result (do ((l (list n) (cons n l))
> (n (- n 2) (- n 2)))
> ((= n 1) l))))
IIUC, this is not the calculation's result *yet*, but a list of
numbers that will be sieved. Re-using variable names like that is
confusing. I'd call it something like `numbers-being-sieved'.
Making your code self-documenting is worth the effort.
> (do ((to-filter result (rest to-filter)))
This is a bit hard to follow because you've stepped to-filter in 2
different places. Try to make the action clearer, perhaps by using
more variable names.
> ((< upper-bound (first to-filter)) (cons 2 result))
One potential problem is that `delete-if' could have removed the first
element of `result' and `result' wouldn't know it. As it happens,
ISTM you lucked out because the flow of control never actually does
that.
It may not be worth coding around, but at the least this surprising
condition should be noted in comments. Frankly, I think relying on
that condition is too clever-clever. Code shouldn't be clever, it
should be clear.
> (setq to-filter
> (delete-if
> (lambda (a) (zerop (mod a (first to-filter))))
> (rest to-filter))))))
As you asked, this does destructively modify the list. You "own" all
the elements, so that's OK. But as I mentioned above, you want to be
much clearer about its effect on `result'.
> Thank you very much,
You're welcome.
--
Tom Breton, http://world.std.com/~tob
Not using "gh" since 1997. http://world.std.com/~tob/ugh-free.html
Will Deakin
an idea of a number `stream' (That is if I remember this correctly: I
don't have SCIP to hand :()
Best Regards,
:) will
Sent via Deja.com http://www.deja.com/
Before you buy.
Erik Naggum
| Should read:
|
| (do* ((to-filter result (rest to-filter))
| (p (first to-filter) (first to-filter)))
| ((< upper-bound p) (cons 2 result))
| (delete-if (lambda (a) (zerop (mod a p))) (rest to-filter))))))
I'd highly recommend (setf (rest to-filter) ...) over RPLACD, or at least
using CDR instead of REST if you use RPLACD.
#:Erik
Shin
<lots of helpful observations snipped>
I have received some messages both in c.l.l. and via email with lots of
useful hints. Thank you very much for the careful reading of the code,
your patience and your time!
The most remarkable faults, I think, were that
1 the doc string didn't say what it is expected to say;
2 the code wasn't commented;
3 some variables could be named more appropriately;
4 Lisp provides cleaner ways to do some things I did; and that
5 some parts of the code were somewhat obscure.
That is, I broke almost every rule of good programming I am aware of.
I have now rewritten the routine taking those remarks into account.
Also, the function is a bit more efficient now because it uses a
pre-computed list of primes. I think this approach gives it a sort of
generality that makes the algorithm more evident.
Do you think is better written now?
Thanks again,
-- Shin
(defun primes-up-to (n)
"Returns a list containing the primes up to n in increasing order."
;; Algorithm: a sort of sieve of Eratosthenes.
(let* (;; Primes up to 50. (This list can be enlarged as much as
;; one wishes with the primes up to some integer. If you
;; do it the function will work as is, without the need of
;; further modifications.)
(known '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47))
(last-known (first (last known))))
(cond ((<= n last-known)
(return-from primes-up-to (delete n known :test #'<)))
((evenp n)
(decf n)))
(let (;; We will use PRODUCT to identify multiples.
(product (apply #'* (rest known)))
(sieve ()))
(loop for k from n downto (+ last-known 2) by 2 do
(when (= 1 (gcd k product))
(push k sieve)))
(flet ((multiple-of (m) (lambda (a) (zerop (mod a m)))))
(let ((upper-bound (isqrt n)))
;; We perform the sifting cdr'ing on SIEVE.
(do ((p (first sieve) (first yet-not-sieved))
(yet-not-sieved (rest sieve) (rest yet-not-sieved)))
;; It is important to do the tests as we do for otherwise
;; P could be NIL and the comparison wouldn't make sense.
((or (null yet-not-sieved) (< upper-bound p))
(append known sieve))
(setq yet-not-sieved
(delete-if (multiple-of p) yet-not-sieved))))))))
Robert Monfera
A few quick comments:
- there is no need to nest FLETs - one will do
- you may place multple-line comments between #| and |#
- you could do a real pre-calculation of primes rather than listing them
Robert
Will Fitzgerald
>
><lots of helpful observations snipped>
>
>I have received some messages both in c.l.l. and via email with lots of
>useful hints. Thank you very much for the careful reading of the code,
>your patience and your time!
>
>The most remarkable faults, I think, were that
>
> 1 the doc string didn't say what it is expected to say;
>
> 2 the code wasn't commented;
>
> 3 some variables could be named more appropriately;
>
> 4 Lisp provides cleaner ways to do some things I did; and that
>
> 5 some parts of the code were somewhat obscure.
>
>That is, I broke almost every rule of good programming I am aware of.
>
>I have now rewritten the routine taking those remarks into account.
>Also, the function is a bit more efficient now because it uses a
>pre-computed list of primes. I think this approach gives it a sort of
>generality that makes the algorithm more evident.
>
>Do you think is better written now?
>
>Thanks again,
>
>-- Shin
>
Since the sieve most easily is implemented if you can quickly access the
integers as indexes, I would use a vector and convert this to a list
afterwards. Note that this will look a lot like a standard procedural
program. This shouldn't be surprising, since Eratosthenes used a beta
version of the "C" programming language, Gamma.
(defun sieve (n)
"Returns a list containing the primes up to n in increasing order."
(let ((prime-vector (make-array n :initial-element t)))
;; mark the primes
(do ((i 2 (1+ i)))
((>= i (isqrt n)))
(do* ((j i (1+ j))
(index (* i j) (* i j)))
((>= index n))
(setf (svref prime-vector index) nil)))
;; convert to a list
(let ((prime-list '()))
(do ((i (1- (length prime-vector)) (1- i)))
((<= i 0))
(if (svref prime-vector i)
(push i prime-list)))
prime-list)))
Tom Breton
[]
> I have now rewritten the routine taking those remarks into account.
> Also, the function is a bit more efficient now because it uses a
> pre-computed list of primes. I think this approach gives it a sort of
> generality that makes the algorithm more evident.
>
> Do you think is better written now?
Yes, I think it's much, much clearer now.
> Thanks again,
>
> -- Shin
Pierre R. Mai
> Do you think is better written now?
Much better. One additional stylistic minor nit (look at the other
postings for additional algorithmic and data representation
improvements):
> (defun primes-up-to (n)
> "Returns a list containing the primes up to n in increasing order."
> ;; Algorithm: a sort of sieve of Eratosthenes.
> (let* (;; Primes up to 50. (This list can be enlarged as much as
> ;; one wishes with the primes up to some integer. If you
> ;; do it the function will work as is, without the need of
> ;; further modifications.)
> (known '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47))
> (last-known (first (last known))))
Putting comments (especially those containing parens) inside of let
bindings in this way seems very confusing to me. Try to move the
comment ahead of the let clause, or draw it into the body of the let
clause. A good general rule of thumb is to only put very short
comments with one semi-colon on the same line as code(-fragments),
whereas all comments with two or more semi-cola have to be on a line
by themselves (see general Lisp style guides). Experienced readers of
Lisp code have come to expect this, and get very quickly confused if
this rule is somehow violated.
Excursion:
In general it might be more useful to expose the known list as a
defparameter global variable, so that users can tune this list
without hacking/recompiling primes-up-to. In this instance of
course this is a bit dangerous, since a mangled known list will
silently cause primes-up-to to yield wrong answers. You could hide
the known list (i.e. not export it) behind accessor functions that
checked the given list before changing the known list:
(defparameter *known-primes-list* (list 2 3 5 7 11)
"List of known prime numbers. This is used by `primes-up-to' to
speed up the calculation of bigger prime numbers. WARNING: Don't
access or change this parameter directly, use the accessor function
`known-primes-list', which is setf-able and does some sanity checks
first, instead. BEWARE that a corrupted *known-primes-list* will
cause `primes-up-to' to yield WRONG answers!")
(defun known-primes-list ()
"Return the list of known prime numbers used by `primes-up-to' to
speed up the calculation of bigger prime numbers. This function is
setf-able."
*known-primes-list*)
(defun (setf known-primes-list) (newvalue)
;; Check newvalue for correctness in some simple way
(if (correct-known-primes-list-p newvalue)
(setq *known-primes-list* newvalue)
;; Raise error
(error "Trying to set known-primes-list to an incorrect value: ~S"
newvalue)))
This approach yields additional benefits: You are completely free in
the internal representation of your parameters, while offering a nice
external interface: You might want to keep the internal known list in
reverse order, or store it as a pre-populated sieve-fragment instead,
etc.
While the whole approach is probably a bit overblown for this sort of
function, it is often quite useful for problems that are only a little
bit more complex/expensive...
Side note: Note that checking such parameters on setting is much
better than only checking them on use, in the same way that "punishing"
children and animals directly is much better than waiting too long
before punishing (the child/user will have lost the context of the
actions which caused the punishment, and feel bewildered and wronged).
Regs, Pierre.
--
Pierre Mai <pm...@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
Scott D. Anderson
Shin <f...@retemail.es> wrote:
>
> (defun primes-up-to (n)
> "Returns a list containing the primes up to n in increasing order."
> ;; Algorithm: a sort of sieve of Eratosthenes.
> (let* (;; Primes up to 50. (This list can be enlarged as much as
> ;; one wishes with the primes up to some integer. If you
> ;; do it the function will work as is, without the need of
> ;; further modifications.)
> (known '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47))
> (last-known (first (last known))))
> (return-from primes-up-to (delete n known :test #'<)))
> ((evenp n)
> (decf n)))
> (let (;; We will use PRODUCT to identify multiples.
> (product (apply #'* (rest known)))
> (sieve ()))
> (loop for k from n downto (+ last-known 2) by 2 do
> (when (= 1 (gcd k product))
> (push k sieve)))
> (flet ((multiple-of (m) (lambda (a) (zerop (mod a m)))))
> (let ((upper-bound (isqrt n)))
> ;; We perform the sifting cdr'ing on SIEVE.
> (do ((p (first sieve) (first yet-not-sieved))
> (yet-not-sieved (rest sieve) (rest yet-not-sieved)))
> ;; It is important to do the tests as we do for
otherwise
> ;; P could be NIL and the comparison wouldn't make
sense.
> ((or (null yet-not-sieved) (< upper-bound p))
> (append known sieve))
> (setq yet-not-sieved
> (delete-if (multiple-of p) yet-not-sieved))))))))
>
I'd just like to comment that this program does not implement the
Sieve of Eratosthenes. At least as I learned it, the Sieve doesn't
do any division at all (no mod, either). You go up through the list,
crossing off the multiples of 2, 3, 5, and so forth. You can't remove
them, or that will mess up the indexing.
Perhaps the point of this code was just a programming exercise, which
is fine, but I think the algorithm is mis-named.
--
Scott D. Anderson
Spelman College, Atlanta, Georgia
anderson @ spelman.edu
http://www.spelman.edu/~anderson/
Shin
First of all, I would like to say that I am very grateful to people in
c.l.l. because I am learning Lisp by my own here in Barcelona with only
your most valuable aid, some classical references and the Lisp systems
one can download for free to study, and I think once one reads CLtL2
what follows is coding a lot and learn from the programmers. The
experience and knowledge you share is invaluable for me. Thanks a lot.
Let me elaborate a little further on this thread.
On 14 Jan 2000 10:46:07 +0100, pm...@acm.org (Pierre R. Mai) wrote:
: In general it might be more useful to expose the known list as a
: defparameter global variable, so that users can tune this list
: without hacking/recompiling primes-up-to. In this instance of
: course this is a bit dangerous, since a mangled known list will
: silently cause primes-up-to to yield wrong answers. You could hide
: the known list (i.e. not export it) behind accessor functions that
: checked the given list before changing the known list:
I see. Also, in that routine I considered the variable PRODUCT,
(product (apply #'* (rest known)))
to reduce the length of the initial list of numbers to be sieved with
GCD, but I did some trials with TIME in Allegro and there was a big
difference on the amount of memory used depending on whether PRODUCT
was or not a bignum.
If that list was implemented the way you suggest, we could take into
account the value of MOST-POSITIVE-FIXNUM in the implementation in
which PRIMES-UP-TO is going to run so that we could consider only those
primes that makes PRODUCT large, but a fixnum in that implementation
when initializing the list.
: (defparameter *known-primes-list* (list 2 3 5 7 11)
: "List of known prime numbers. This is used by `primes-up-to' to
: speed up the calculation of bigger prime numbers. WARNING: Don't
: access or change this parameter directly, use the accessor function
: `known-primes-list', which is setf-able and does some sanity checks
: first, instead. BEWARE that a corrupted *known-primes-list* will
: cause `primes-up-to' to yield WRONG answers!")
Is there a reason to use
(list 2 3 5 7 11)
instead of
'(2 3 5 7 11)
?
The other day, writing a function that starts considering the list
'(0 1))
and then modifies it to generate a named finite sequence in place
(Farey, just if you'd know it), I noticed that the subsequent calls to
the function remembered somewhat the last state of the list!
Then, by chance I changed it to
(list 0 1)
and worked as (I) expected. Why? Is there any relevant difference
between
(let ((n 0))
; body
)
and
(let ((fn '(0 1)))
; body
)
?
: This approach yields additional benefits: You are completely free in
: the internal representation of your parameters, while offering a nice
: external interface: You might want to keep the internal known list in
: reverse order, or store it as a pre-populated sieve-fragment instead,
: etc.
Yes, I agree with you.
: While the whole approach is probably a bit overblown for this sort of
: function, it is often quite useful for problems that are only a little
: bit more complex/expensive...
Yes, that is what I was looking for. Actually this sieve is a sort of
excuse to talk about general Lisp guidelines having handy as reference
a function that is known and short. I am not concerned to write the
smartest sieve (I couldn't anyway), but in learning Lisp playing with
simple routines that let me concentrate on the language.
Regards to all,
-- Shin
Michael Hudson
> Is there a reason to use
>
> (list 2 3 5 7 11)
>
> instead of
>
> '(2 3 5 7 11)
>
> ?
Well, mutating literals (like '(1 2 3)) is undefined. Or leads to
unspecified reults, I can't remember.
cltl2 says it "is an error", which means basically it's not valid
Common Lisp, and all bets are off as to what will happen.
Basically, don't do it, or ...
> The other day, writing a function that starts considering the list
>
> '(0 1))
>
> and then modifies it to generate a named finite sequence in place
> (Farey, just if you'd know it), I noticed that the subsequent calls to
> the function remembered somewhat the last state of the list!
... things like this happen.
> Then, by chance I changed it to
>
> (list 0 1)
>
> and worked as (I) expected. Why? Is there any relevant difference
> between
>
> (let ((n 0))
> ; body
> )
>
> and
>
> (let ((fn '(0 1)))
> ; body
> )
>
> ?
Well, one establishes a lexical environment in which 'n is bound to 0,
and another one in which 'fn is bound to a two element list...
The point is that there are no functions to "destructively modify" a
number, but there are plenty to destructively modify a cons ('rplaca,
'(setf car), ...).
You do understand the difference between changing a variable, e.g:
(setq a (1+ a))
and "destructive modification" of what the variable is bound to, e.g:
(setf (cdr list) 'bob)
I take it?
Here, read this:
$(path to Hyperspec)/Body/speope_quote.html#quote
HTH,
Michael
Robert Monfera
Shin wrote:
> Is there a reason to use
>
> (list 2 3 5 7 11)
>
> instead of
>
> '(2 3 5 7 11)
>
> ?
Hi Shin,
If you later want to be able to change the list, you need to use the
first one. In the second case, ANSI CL allows the compiler to perform
optimizations assuming the list will never change, because it is a
literal list. There was a thread about it around a couple of months
ago, when Barry and others gave detailed explanations - locate it with
deja.
Robert
Tom Breton
>
> Is there a reason to use
>
> (list 2 3 5 7 11)
>
> instead of
>
> '(2 3 5 7 11)
>
> ?
Yes. The first one makes a copy, the second one uses the literal
list.
If you're going to change any element in the list, you need it to be a
copy or else your literal will be silently changed to the new value.
Also, if something goes wrong and some of the elements get changed,
the second one will still be wrong even after the code is fixed,
because it was changed. That makes debugging very frustrating.
Usually reevaluating the entire defun (or however large region) sets
all the literal lists back to their correct values.
> The other day, writing a function that starts considering the list
>
> '(0 1))
>
> and then modifies it to generate a named finite sequence in place
> (Farey, just if you'd know it), I noticed that the subsequent calls to
> the function remembered somewhat the last state of the list!
>
> Then, by chance I changed it to
>
> (list 0 1)
>
> and worked as (I) expected. Why?
Because you changed it in place, I expect.