I am an inexperienced Lisp user and would like some comment on Lisp
style. This
fragment is a depth first search for a simple puzzle (it requires
exactly 31 moves
to finish it). The first fragment is the best I could do without side
effects. But
with Clisp the program terminates with a stack overflow. Under CMUCL and
Allegro 6.2
it solves the problem without stack overflows (with version 1).
(defun find-solution (path-so-far solution)
(format t "length = ~a" (length path-so-far))
(print-pos (car path-so-far))
(cond ((null path-so-far) 'no-solution)
((solution? (car path-so-far)) (print-pos (car path-so-far)))
(t (find-solution-aux (car path-so-far) (cdr path-so-far) solution))))
(defun find-solution-aux (pos path-so-far solution)
(dolist (moves-todo (all-moves-from-pos pos))
(unless (null moves-todo)
(push (make-move pos moves-todo) path-so-far)))
(find-solution path-so-far solution))
My attempt to solve it under Clisp is this (version 2) :
(defun find-solution-2 ()
(let ((path-so-far (list start-pos)))
(do () (nil)
(cond ((null path-so-far) (return 'no-solution))
((solution? (car path-so-far)) (print-pos (car path-so-far))
(return 'success))
(t
(let ((pos (pop path-so-far)))
(dolist (move-todo (all-moves-from-pos pos))
(unless (null move-todo)
(setf path-so-far (push (make-move pos move-todo)
path-so-far))))))))))
This version works with Clisp without stack problems. My questions are:
1. Is the setf in the second version bad style because it modifies a let
variable ?
2. What other options are available to control the stack growth (I seem
to reach the
point quickly where bad style is traded for practicalities) ?
Thanks
Nico Swart.
Nico wrote:
> I am an inexperienced Lisp user and would like some comment on Lisp
> style. This
> fragment is a depth first search for a simple puzzle (it requires
> exactly 31 moves
> to finish it). The first fragment is the best I could do without side
> effects. But
> with Clisp the program terminates with a stack overflow. Under CMUCL and
> Allegro 6.2
> it solves the problem without stack overflows (with version 1).
>
> (defun find-solution (path-so-far solution)
> (format t "length = ~a" (length path-so-far))
> (print-pos (car path-so-far))
> (cond ((null path-so-far) 'no-solution)
> ((solution? (car path-so-far)) (print-pos (car path-so-far)))
> (t (find-solution-aux (car path-so-far) (cdr path-so-far) solution))))
>
> (defun find-solution-aux (pos path-so-far solution)
> (dolist (moves-todo (all-moves-from-pos pos))
> (unless (null moves-todo)
> (push (make-move pos moves-todo) path-so-far)))
> (find-solution path-so-far solution))
>
> My attempt to solve it under Clisp is this (version 2) :
>
> (defun find-solution-2 ()
> (let ((path-so-far (list start-pos)))
> (do () (nil)
> (cond ((null path-so-far) (return 'no-solution))
> ((solution? (car path-so-far)) (print-pos (car path-so-far))
> (return 'success))
> (t
> (let ((pos (pop path-so-far)))
> (dolist (move-todo (all-moves-from-pos pos))
> (unless (null move-todo)
> (setf path-so-far (push (make-move pos move-todo)
> path-so-far))))))))))
Real quick: (push x place) expands to (setf place (cons x place))
That might not answer your question, tho. Another non-response response:
(nconc (delete-if #'null (all-moves-from-pos pos)) path-so-far)
...would serve as well, but throw in an (nreverse of all the moves if
you really wanted that effect (which is what you get pushing one by one
from another list.
Finally, in answer to your question, hey, if your algorithm is otherwise
valid (I didn't look at that question) and an implementation is letting
you down, you gots to do what you gots to do, and what you are doing
reminds me of code I have done (and I do worry a lot about style).
My 2.
--
kenny tilton
clinisys, inc
http://www.tilton-technology.com/
---------------------------------------------------------------
"Everything is a cell." -- Alan Kay
Hi Kenny Tilton,
> Finally, in answer to your question, hey, if your algorithm is otherwise
> valid (I didn't look at that question) and an implementation is letting
> you down, you gots to do what you gots to do, and what you are doing
> reminds me of code I have done (and I do worry a lot about style).
Alternatively one can come to understand the implementation specific
details. I don't think it's good that CLISP can so easily run out of
stack. But I also know -m sets the default memory configuration and
this influences the size of the stack and how much a recursive process can
denial of service the computer:
$ clisp -norc -m 2MB [NB: refer man clisp, this is the default]
[1]> (labels ((test (i) (decf i) (when (plusp i) (test i)))) (test 3000))
*** - Lisp stack overflow. RESET
$ clisp -norc -m 512MB
[1]> (labels ((test (i) (decf i) (when (plusp i) (test i)))) (test 300000))
NIL
So I just managed to create a 100 times larger stack.
Currently I'm waiting on a 1,000,000 time recursive function to exit
successfully (using -m 1024MB and swapping like crazy).
Regards,
Adam
Nico <·······@stargate.net> wrote:
> 1. Is the setf in the second version bad style because it
> modifies a let variable ?
IMHO no.
> 2. What other options are available to control the stack
> growth (I seem to reach the point quickly where bad style
> is traded for practicalities) ?
No need to reach for "bad style" yet. I'm guessing that CLISP
is missing the mutual tail recursion:
Doing
(declaim (optimize (speed 3) (space 3) (debug 0)))
at the top of the file, and compiling code may help.
So may rolling the two into one: looks like you could replace
the T clause of cond with:
(t (let ((pos (car path-so-far))
(path-so-far (cdr path-so-far)))
;; body of find-solution-aux
...))))
Esp. combining these two may help: simple tail recursion is
easier for the compiler to detect, and the declaim makes
it likelier for the compiler to give it a serious try.
Cheers,
-- Nikodemus
"Nico" <·······@stargate.net> wrote in message
···················@corp.supernews.com...
> 1. Is the setf in the second version bad style because it modifies a let
> variable ?
I don't consider this is bad style, because the code in the function
modifies a variable that "belongs" to the function, so from outside the
function there is no side effect visible.
--
Matthieu Villeneuve
"Nico" <·······@stargate.net> wrote in message
···················@corp.supernews.com...
> 1. Is the setf in the second version bad style because it modifies a let
> variable ?
Nothing wrong with that on principle.
> 2. What other options are available to control the stack growth (I seem
Iterate rather than recurse when ever possible.
(Didn't look hard at your code, it passes the first glance test for style
though!)
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")