Subject: [clisp-list] clisp crash with recursive function

From: Elvin Peterson <[email-masked]>
Date: Thu Jun 24 11:25:43 2004

Hello,
  I have an function (described below), which crashes
clisp for inputs greater than 1500.  The limit is
substantially larger if the function is compiled.  An
empty stackdump file is generated under cygwin.

[18]> (eratosthenes 1500)
$

I suspect this might be a problem with large lists,
but shouldn't there be a graceful recovery and a
message rather than a crash?

$ clisp --version
GNU CLISP 2.33 (2004-03-17) (built on winsteingoldlap
[10.0.19.22])
Software: GNU C 3.3.1 (cygming special) ANSI C program
Features:
(CLOS LOOP COMPILER CLISP ANSI-CL COMMON-LISP LISP=CL
INTERPRETER SOCKETS
 GENERIC-STREAMS LOGICAL-PATHNAMES SCREEN FFI GETTEXT
UNICODE
 BASE-CHAR=CHARACTER UNIX CYGWIN)
Installation directory: /usr/lib/clisp/
User language: ENGLISH

TIA.

;; Implements the sieve of Eratosthenes

(defun generate-list (n)
  "Provides the list 2...n"
  (labels ((generate-reversed-list (n)
				   "Generates the list 2...n in the reverse order"
				   (if (= n 2)
				       (cons 2 nil)
				     (cons n (generate-reversed-list (1- n))))))
    (reverse (generate-reversed-list n))))

(defun sieve (x n) 
  "The actual sieve, repeatedly deleting multiples."
  (labels ((multiple-of (x y)
			"Is the number a multiple (greater than 2)?"
			(and (integerp (/ x y)) (> x y))))
    (if (> n (sqrt (first (last x)))) ;no need to
check for numbers > sqrt (n)
	x			 ;stopping condition for the recursion
      (sieve (delete-if 
	      #'(lambda (num)
		  (multiple-of num (nth (1- n) x)))
	      x)	       ;delete multiples of positions
starting
	     (1+ n)))))			;from n, incrementing by 1

(defun eratosthenes (n)
  "Find all primes till n"
  (sieve (generate-list n) 1)) ;start the sieve using
the first element

__________________________________
Do you Yahoo!?
Take Yahoo! Mail with you! Get it on your mobile phone.
http://mobile.yahoo.com/maildemo

---

From: Pascal J.Bourguignon <[email-masked]>
Date: Thu Jun 24 13:00:23 2004

> message rather than a crash?

The problem is not with large lists, but with deep stacks.  The
interpreter uses more stack space than compiled functions.

>     (reverse (generate-reversed-list n))))

Rather use an iterative version:

(defun generate-numbers>=2  (n)
  (let ((result nil))
    (dotimes (i n) (push i result))
    (cddr (nreverse result))))

(defun nremove-prime-multiples (list)
  (do* ((prime          (car list))
        (prime-multiple (+ prime prime))
        (next           list))
      ((null (cdr next)) list)
    (cond
     ((> (cadr next) prime-multiple)   (incf prime-multiple prime))
     ((= (cadr next) prime-multiple)   (setf (cdr next) (cddr next))
                                       (incf prime-multiple prime))
     (t                                (setf next (cdr next))))))

(defun sieve (list-of-integer)
  (do* ((result (copy-seq list-of-integer))
        (next (nremove-prime-multiples result)
              (nremove-prime-multiples (cdr next))))
      ((null (cdr next)) result)));;sieve

[52]> (time (sieve (generate-numbers>=2 10000))) 

Real time: 3.300211 sec.  ;; NOT COMPILED!
Run time: 3.28 sec.
Space: 159984 Bytes
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103
 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313
 [...]
 9319 9323 9337 9341 9343 9349 9371 9377 9391 9397 9403 9413 9419 9421 9431
 9433 9437 9439 9461 9463 9467 9473 9479 9491 9497 9511 9521 9533 9539 9547
 9551 9587 9601 9613 9619 9623 9629 9631 9643 9649 9661 9677 9679 9689 9697
 9719 9721 9733 9739 9743 9749 9767 9769 9781 9787 9791 9803 9811 9817 9829
 9833 9839 9851 9857 9859 9871 9883 9887 9901 9907 9923 9929 9931 9941 9949
 9967 9973)

[53]> (map nil (function compile)
        '(generate-numbers>=2  nremove-prime-multiples sieve))
NIL

[54]> (time (every (function primep) (sieve (generate-numbers>=2 100000))))

Real time: 210.57819 sec.  ;; NOT COMPILED!
Run time: 203.1 sec.
Space: 1599984 Bytes
GC: 1, GC time: 0.06 sec.
T

Of course, it's much faster to implement the Eratostene sieve with bitmaps:

[55]> (package:load-package :com.informatimago.common-lisp.primes)
T
[56]> (time (every (function primep) (com.informatimago.common-lisp.primes:compute-primes-to 100000)))

Real time: 7.245507 sec.
Run time: 7.17 sec.
Space: 48284 Bytes
T

[67]> (time (prog1 nil (com.informatimago.common-lisp.primes:compute-primes-to 100000)))

Real time: 0.695663 sec.
Run time: 0.69 sec.
Space: 44784 Bytes
NIL

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein

---

From: Elvin Peterson <[email-masked]>
Date: Mon Jun 28 06:00:04 2004

> interpreter uses more stack space than compiled

How much stack space is allocated?  I did measurements
with the "time" function and the space requirements
seemed quite small to me.

> Rather use an iterative version:

That is much better than what I posted, but from what
I have read in books about Lisp, iterative programming
should be avoided by new users because of all the side
effects.  However, the code for reversing a list seems
to be an idiom.

> :com.informatimago.common-lisp.primes)

I suppose this is your personal code, and not part of
the clisp distribution.

Thank you for all the help!

		
__________________________________
Do you Yahoo!?
New and Improved Yahoo! Mail - 100MB free storage!
http://promotions.yahoo.com/new_mail

---

From: Sam Steingold <[email-masked]>
Date: Mon Jun 28 07:03:00 2004

> * Elvin Peterson <[email-masked]> [2004-06-28 05:59:32 -0700]:
>
> How much stack space is allocated?

<http://clisp.cons.org/faq.html#stack>.

> That is much better than what I posted, but from what I have read in
> books about Lisp, iterative programming should be avoided by new users
> because of all the side effects.  However, the code for reversing a
> list seems to be an idiom.

the only things to avoid are brittle code and inefficient algorithms.

CL is a multi-paradigm language (OO, Functional &c &c), and one should
use the paradigm best suited to one's specific problem, not the one
touted by the "CS fashion of the day".

-- 
Sam Steingold (http://www.podval.org/~sds) running w2k
<http://www.camera.org> <http://www.iris.org.il> <http://www.memri.org/>
<http://www.mideasttruth.com/> <http://www.honestreporting.com>
A man paints with his brains and not with his hands.

---

From: Elvin Peterson <[email-masked]>
Date: Mon Jun 28 10:23:01 2004

> > * Elvin Peterson <[email-masked]>

Sorry about that.  This mentioned in the manpage, but
I unfortunately stopped reading after the "dynamically
allocated" part.

> the only things to avoid are brittle code and

Of course, the question is how one goes about doing
that. :-(

Thanks for all the help.

__________________________________
Do you Yahoo!?
Yahoo! Mail is new and improved - Check it out!
http://promotions.yahoo.com/new_mail