Could any Lisp pros give me their critique of this simple
implementation to prime factorize an integer? (I know there are
special purpose algorithms for this - my goal here is to learn Lisp
style, not number theory.)
;;; Used for automated testing
(defun ok (expected actual)
(if (equal expected actual)
(format t "okay: ~a~%" expected)
(format t "FAIL: ~a != ~a~%" expected actual)))
(defun prime-factors (n)
;; These are internal use only functions, so I
;; tucked them away here. I don't know how to
;; avoid the style warnings without resorting to lambdas.
;; (I find names more readable)
(defun next-candidate (candidate)
(if (= 2 candidate)
3
(+ 2 candidate)))
(defun prime-factorsa (n candidate factors)
(if (or (= n 1) (> candidate n))
factors
(if (= 0 (mod n candidate))
(prime-factorsa (/ n candidate) candidate (cons candidate
factors))
(prime-factorsa n (next-candidate candidate) factors))))
(prime-factorsa n 2 nil))
(ok nil (prime-factors 1))
(ok '(2) (prime-factors 2))
(ok '(3) (prime-factors 3))
(ok '(2 2) (prime-factors 4))
(ok '(5 5 2 2) (prime-factors 100))
S. Robert James wrote:
> Could any Lisp pros give me their critique of this simple
> implementation to prime factorize an integer? (I know there are
> special purpose algorithms for this - my goal here is to learn Lisp
> style, not number theory.)
(defun prime-factors (n)
(labels ((next (candidate)
(case candidate (2 3)
(t (+ 2 candidate))))
(primes (n candidate factors)
(cond
((> candidate n 0)
factors)
((zerop (mod n candidate))
(primes (/ n candidate) candidate (cons candidate
factors)))
(t
(primes n (next candidate) factors)))))
(primes n 2 nil)))
Thanks, Greg. I see that you made some line-by-line changes to naming
and shortcuts (eg zerop instead of = 0, cond instead of if), but not
to the actual execution. Am I correct that this is the execution flow
an experienced Lisper would use (again, using the same basic dumb
search)?
On Feb 7, 10:31 pm, "Greg Buchholz" <················@yahoo.com>
wrote:
> S. Robert James wrote:
> > Could any Lisp pros give me their critique of this simple
> > implementation to prime factorize an integer? (I know there are
> > special purpose algorithms for this - my goal here is to learn Lisp
> > style, not number theory.)
>
> (defun prime-factors (n)
> (labels ((next (candidate)
> (case candidate (2 3)
> (t (+ 2 candidate))))
> (primes (n candidate factors)
> (cond
> ((> candidate n 0)
> factors)
> ((zerop (mod n candidate))
> (primes (/ n candidate) candidate (cons candidate
> factors)))
> (t
> (primes n (next candidate) factors)))))
> (primes n 2 nil)))
S. Robert James wrote:
> Thanks, Greg. I see that you made some line-by-line changes to naming
> and shortcuts (eg zerop instead of = 0, cond instead of if), but not
> to the actual execution. Am I correct that this is the execution flow
> an experienced Lisper would use (again, using the same basic dumb
> search)?
Well, being tail recursive doesn't buy you much in this case, so
you could tighten it up a little...
(defun factorize (n)
(labels ((next (x) (case x (2 3)
(t (+ 2 x))))
(primes (n candidate)
(cond
((> candidate n) nil)
((zerop (mod n candidate))
(cons candidate (primes (/ n candidate) candidate)))
(t (primes n (next candidate))))))
(primes n 2)))
...other than that, I don't see that using DO or LOOP would improve
anything, if that's what you're asking.
Greg Buchholz
In article <························@v45g2000cwv.googlegroups.com>,
"S. Robert James" <············@gmail.com> wrote:
> (defun prime-factors (n)
> ;; These are internal use only functions, so I
> ;; tucked them away here. I don't know how to
> ;; avoid the style warnings without resorting to lambdas.
> ;; (I find names more readable)
> (defun next-candidate (candidate)
> (if (= 2 candidate)
> 3
> (+ 2 candidate)))
> (defun prime-factorsa (n candidate factors)
> (if (or (= n 1) (> candidate n))
> factors
> (if (= 0 (mod n candidate))
> (prime-factorsa (/ n candidate) candidate (cons candidate
> factors))
> (prime-factorsa n (next-candidate candidate) factors))))
> (prime-factorsa n 2 nil))
You want LABELS or FLET:
(defun prime-factors (n)
(labels ((next-candidate (candidate)
...)
(prime-factorsa (n candidate factors)
...))
(prime-factorsa n 2 nil)))
but don't feel obligated to emulate this aspect of SICP style. Making
functions local often makes them harder to debug, so use with caution.
Thanks for the feedback.
On Feb 7, 9:48 pm, Bill Atkins wrote:
> don't feel obligated to emulate this aspect of SICP style. Making
> functions local often makes them harder to debug, so use with caution.
How so? Is there another way to encapsulate "private" functions?
Any critiques or comments on the code itself?
On Feb 8, 3:19 am, "S. Robert James" <············@gmail.com> wrote:
> How so? Is there another way to encapsulate "private" functions?
I think what you're doing is reasonable (well, the LABELS / FLET
version of it). The other approach would be to define a package, but
that's kind of heavyweight for this.
--tim
"S. Robert James" <············@gmail.com> writes:
> Thanks for the feedback.
>
> On Feb 7, 9:48 pm, Bill Atkins wrote:
> > don't feel obligated to emulate this aspect of SICP style. Making
> > functions local often makes them harder to debug, so use with caution.
>
> How so? Is there another way to encapsulate "private" functions?
Your only real choice is FLET or LABELS if you want to do the
encapsulation.
Using DEFUN doesn't accomplish your goal, since DEFUN always produces a
global level binding of the function name. You can test this by trying
this:
(defun test () (print "top-level"))
(test) prints "top-level"n
(defun outer ()
(defun test () (print "Inner"))
(test))
(outer) prints "Inner" and redefines TEST
(test) prints "Inner" because DEFUN is global.
--
Thomas A. Russ, USC/Information Sciences Institute
"S. Robert James" <············@gmail.com> writes:
> Thanks for the feedback.
>
> On Feb 7, 9:48 pm, Bill Atkins wrote:
> > don't feel obligated to emulate this aspect of SICP style. Making
> > functions local often makes them harder to debug, so use with caution.
>
> How so? Is there another way to encapsulate "private" functions?
The reason it makes the functions harder to DEBUG is that you can't call
them directly. If you define PRIME-FACTORSA inside a labels, then you
can't call it from top level, and you can't usually use the TRACE macro
on it either. But if it turns out to be an issue, you can always pull
the function out of the LABELS and then use DEFUN.
--
Thomas A. Russ, USC/Information Sciences Institute
On Thu, 08 Feb 2007 18:35:43 +0100, Thomas A. Russ <···@sevak.isi.edu>
wrote:
> "S. Robert James" <············@gmail.com> writes:
>
>> Thanks for the feedback.
>>
>> On Feb 7, 9:48 pm, Bill Atkins wrote:
>> > don't feel obligated to emulate this aspect of SICP style. Making
>> > functions local often makes them harder to debug, so use with caution.
>>
>> How so? Is there another way to encapsulate "private" functions?
>
> The reason it makes the functions harder to DEBUG is that you can't call
> them directly. If you define PRIME-FACTORSA inside a labels, then you
> can't call it from top level, and you can't usually use the TRACE macro
> on it either. But if it turns out to be an issue, you can always pull
> the function out of the LABELS and then use DEFUN.
>
I second that and introduce closures.
The one reason you would want nested functions in Pascal
is because you can encapsulate data.
consider:
let (val1 val2)
(defun func1 (..) ...)
(defun func2 (..) ...))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Alain Picard
Subject: Re: Critique of prime factorization in Lisp
Date:
Message-ID: <87sldhjc15.fsf@memetrics.com>
"S. Robert James" <············@gmail.com> writes:
>
> How so? Is there another way to encapsulate "private" functions?
Define a package, and only export your "public" functions.
--ap
"S. Robert James" <············@gmail.com> writes:
> Could any Lisp pros give me their critique of this simple
> implementation to prime factorize an integer? (I know there are
> special purpose algorithms for this - my goal here is to learn Lisp
> style, not number theory.)
>
> ;;; Used for automated testing
> (defun ok (expected actual)
> (if (equal expected actual)
> (format t "okay: ~a~%" expected)
> (format t "FAIL: ~a != ~a~%" expected actual)))
>
> (defun prime-factors (n)
> ;; These are internal use only functions, so I
> ;; tucked them away here. I don't know how to
> ;; avoid the style warnings without resorting to lambdas.
> ;; (I find names more readable)
> (defun next-candidate (candidate)
> (if (= 2 candidate)
> 3
> (+ 2 candidate)))
> (defun prime-factorsa (n candidate factors)
> (if (or (= n 1) (> candidate n))
> factors
> (if (= 0 (mod n candidate))
> (prime-factorsa (/ n candidate) candidate (cons candidate
> factors))
> (prime-factorsa n (next-candidate candidate) factors))))
> (prime-factorsa n 2 nil))
Try this:
(defun prime-factors (n)
(labels ((next-candidate (candidate)
(if (= 2 candidate)
3
(+ 2 candidate)))
(rec (n candidate factors)
(cond ((or (= n 1) (> candidate n)) factors)
((zerop (mod n candidate))
(rec (/ n candidate) candidate (cons candidate factors)))
(t (rec n (next-candidate candidate) factors)))))
(rec n 2 nil)))
The key things I changed:
1. LABELS instead of DEFUNs for local functions. Your DEFUNs don't
make the functions local and quite possibly get executed each time you
run the function. This is not what you intended. LABELS is your
friend. If you want local functions and don't need recursion in them,
then you can use FLET instead.
2. Named the recursive function REC instead of PRIME-FACTORSA, which
is neither descriptive nor easy to tell apart from the main function
name, PRIME-FACTORS.
3. COND instead of nested IFs. If you find that the "else" clause of
your IF is another IF, COND is probably what you want.
"S. Robert James" <············@gmail.com> writes:
Generally this looks quite good. The only comments are really minor issues.
> Could any Lisp pros give me their critique of this simple
> implementation to prime factorize an integer? (I know there are
> special purpose algorithms for this - my goal here is to learn Lisp
> style, not number theory.)
>
> ;;; Used for automated testing
> (defun ok (expected actual)
> (if (equal expected actual)
> (format t "okay: ~a~%" expected)
> (format t "FAIL: ~a != ~a~%" expected actual)))
I might choose a slighly more evocative name such as test-same-p, but
since this is only used at top-level for nice print out, it isn't that
big of a deal.
You do use a properly general equality predicate, since you do need to
compare lists.
> (defun prime-factors (n)
> ;; These are internal use only functions, so I
> ;; tucked them away here. I don't know how to
> ;; avoid the style warnings without resorting to lambdas.
> ;; (I find names more readable)
> (defun next-candidate (candidate)
> (if (= 2 candidate)
> 3
> (+ 2 candidate)))
> (defun prime-factorsa (n candidate factors)
> (if (or (= n 1) (> candidate n))
> factors
> (if (= 0 (mod n candidate))
> (prime-factorsa (/ n candidate) candidate (cons candidate
> factors))
> (prime-factorsa n (next-candidate candidate) factors))))
> (prime-factorsa n 2 nil))
Good use of auxilliary functions, but as other threads have pointed out
you need to use LABELS for this. You need LABELS and not FLET because
PRIME-FACTORSA is recursive. The use of an accumulator is good and
shows that you have learned that important style technique. I
particularly like the way you abstract away the increment in
NEXT-CANDIDATE. It also means that if you come up with a different,
more efficient candidate generator, then you can easily substitute it
into the algorithm.
Algorithmically, you can use a minor improvement by making the limit be
something like (FLOOR (SQRT n)), but that isn't a style issue. It would
require another parameter to PRIME-FACTORSA or the use of lambda
binding:
(defun prime-factors (n)
(let ((limit (floor (sqrt n))))
(labels ((prime-factorsa (n candidate factors)
(if (or (= n 1) (> candidate limit))
...))))
(prime-factorsa n 2 nil)))
>
> (ok nil (prime-factors 1))
> (ok '(2) (prime-factors 2))
> (ok '(3) (prime-factors 3))
> (ok '(2 2) (prime-factors 4))
> (ok '(5 5 2 2) (prime-factors 100))
>
--
Thomas A. Russ, USC/Information Sciences Institute
On Feb 7, 8:50 pm, "S. Robert James" <············@gmail.com> wrote:
[...]
> (ok nil (prime-factors 1))
> (ok '(2) (prime-factors 2))
> (ok '(3) (prime-factors 3))
> (ok '(2 2) (prime-factors 4))
> (ok '(5 5 2 2) (prime-factors 100))
You can also test the function like so:
(defun test-prime-factors (n)
"Tests to see if N is equal to the product of the factors
returned by PRIME-FACTORS."
(let ((product (apply #'* (prime-factors n))))
(if (= n prod)
(format t "Test passed for N = ~D." n)
(format t "Test *FAILED* for N = ~D, product of factors = ~D!"
n prod))))
On one hand, it doesn't test the function as thoroughly,
verifying all the factors are prime[1], but on the other, it is much
easier to fit into a loop.
[1] Of course, you could add this, if you had a function PRIMEP to
test if a given number was prime....
Cheers,
Pillsy
"Pillsy" <·········@gmail.com> writes:
> On Feb 7, 8:50 pm, "S. Robert James" <············@gmail.com> wrote:
> [...]
> > (ok nil (prime-factors 1))
> > (ok '(2) (prime-factors 2))
> > (ok '(3) (prime-factors 3))
> > (ok '(2 2) (prime-factors 4))
> > (ok '(5 5 2 2) (prime-factors 100))
>
> You can also test the function like so:
>
> (defun test-prime-factors (n)
> "Tests to see if N is equal to the product of the factors
> returned by PRIME-FACTORS."
> ...)
>
> On one hand, it doesn't test the function as thoroughly,
> verifying all the factors are prime[1], but on the other, it is much
> easier to fit into a loop.
Or to run a bit further with this idea, one could provide the lists of
prime factors, multiply them together and then call the candidate
function on them:
(defun test-prime-factors (factor-list)
(let ((product (apply #'* factor-list)))
(if (equal factor-list (prime-factors product))
(format t "Test passed for N = ~D." product)
(format t "Test *FAILED* for N = ~D, should be ~A but is ~A"
product factor-list (prime-factors product)))))
--
Thomas A. Russ, USC/Information Sciences Institute
"S. Robert James" <············@gmail.com> writes:
> (defun prime-factors (n)
> ;; These are internal use only functions, so I
> ;; tucked them away here. I don't know how to
> ;; avoid the style warnings without resorting to lambdas.
> ;; (I find names more readable)
> (defun next-candidate (candidate)
> (if (= 2 candidate)
> 3
> (+ 2 candidate)))
> (defun prime-factorsa (n candidate factors)
> (if (or (= n 1) (> candidate n))
> factors
> (if (= 0 (mod n candidate))
> (prime-factorsa (/ n candidate) candidate (cons candidate factors))
> (prime-factorsa n (next-candidate candidate) factors))))
> (prime-factorsa n 2 nil))
This works, but it doesn't do what you think.
When you call PRIME-FACTORS, it defines, at run-time, two new
functions, NEXT-CANDIDATE and PRIME-FACTORSA, that are global
functions just like PRIME-FACTORS. The only difference is that before
you call the first time PRIME-FACTORS, they weren't defined.
When you call PRIME-FACTORS the second time, you are RE-defining these
two functions: the old functions are forgotten (and will be garbage
collected) and two new identical functions are defined again.
For secondary functions like PRIME-FACTORSA, there's a minor convention
which is to use -1, -2, ..., so: PRIME-FACTORS-1, not PRIME-FACTORSA
Innequality is /= (or ≠ in strings) not !=
It's always better to use < and <= rather than > or >=.
Write: (< n candidate).
For (= 0 ...) you can use (zerop ...)
You can prove that candidate is never less than 2, so you don't need
to test (= n 1), since when (= n 1), we have automatically (< n
candidate).
When you have chains of IF, better use COND.
I'd rather use TRUNCATE than / when working on integers.
Add documentation string!
(defun prime-factors (n)
"Returns a list of prime factors of N"
(labels ((collect-factors (submultiple candidate factors)
(cond
((< submultiple candidate) factors)
((zerop (mod submultiple candidate))
(collect-factors (truncate submultiple candidate)
candidate
(cons candidate factors)))
(t
(collect-factors submultiple
(if (= 2 candidate)
3
(+ 2 candidate))
factors)))))
(collect-factors n 2 '())))
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Indentation! -- I will show you how to indent when I indent your skull!"
"Alex Mizrahi" <········@users.sourceforge.net> writes:
> (message (Hello 'Pascal)
> (you :wrote :on '(Thu, 08 Feb 2007 16:08:21 +0100))
> (
>
> PB> It's always better to use < and <= rather than > or >=.
> PB> Write: (< n candidate).
>
> why?
It's an old pebble of wisdom I got from one of my teacher a long time
ago, and indeed, it makes code easier to read and understand.
In particular for cases such as: (and (<= 0 i) (< i n))
[ but of course, in CL we can just write (<= 0 i (1- n)) ]
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
"Alex Mizrahi" <········@users.sourceforge.net> writes:
> (message (Hello 'Pascal)
> (you :wrote :on '(Thu, 08 Feb 2007 16:08:21 +0100))
> (
>
> PB> It's always better to use < and <= rather than > or >=.
> PB> Write: (< n candidate).
>
> why?
Perhaps because in European writing systems we are used to reading left
to right, and the standard convention for numbering things, such as
graph axes has numbers increasing to the right.
I would imagine this is particularly useful for multi-argument < forms.
--
Thomas A. Russ, USC/Information Sciences Institute