Hi, I'm stuck with loop and recursion. Lisp is quite different from other
languages I'm used to.
I'd like to know how to escape a loop before it finishes the entire loop.
I want to escape the loop when some condition is met. It easy in C/C++/Java.
I can put simple "if" statement and "retrun" state. But it doesn't work in
Lisp.
Could you correct my mistake?
Here is what I tried.
(dotimes (alphaCount (length children))
(setf valueOfCurrentChild
(alphabeta (nth alphaCount children)
alpha beta (- depth 1) (not whoseturn)))
(setf beta (min beta valueOfCurrentChild))
(if (<= beta alpha)
(return alpha)
)
)
I wanted to escape the loop "if beta <= alpha", but sometimes it seemed to
be working. I got a correct result with small test case, but ....
Thanks in advance.
From: vsync
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <877l7ucqcm.fsf@piro.quadium.net>
"Young-Jin Lee" <······@uiuc.edu> writes:
> Hi, I'm stuck with loop and recursion. Lisp is quite different from other
> languages I'm used to.
> I'd like to know how to escape a loop before it finishes the entire loop.
> I want to escape the loop when some condition is met. It easy in C/C++/Java.
> I can put simple "if" statement and "retrun" state. But it doesn't work in
> Lisp.
> Could you correct my mistake?
>
> Here is what I tried.
>
> (dotimes (alphaCount (length children))
> (setf valueOfCurrentChild
> (alphabeta (nth alphaCount children)
> alpha beta (- depth 1) (not whoseturn)))
>
> (setf beta (min beta valueOfCurrentChild))
>
> (if (<= beta alpha)
> (return alpha)
> )
> )
Hm. I notice several things here, the first being your use of special
variables (SETF instead of LET). Secondly, since you're going through
a list, it doesn't seem to make much sense to use DOTIMES rather than,
say, DO or DOLIST, especially since you don't always want to DO x
TIMES.
I was going to rewrite your example for you, but it uses a lot of
symbols that I don't know the purpose of, so here's just a random
function that counts up the numbers in a list as long as they stay
level or keep increasing, but stops when they start to go down.
(defun count-elements (things &optional (top 0))
(if (or (null things)
(< (car things) top))
0
(let ((current (car things)))
(+ current (count-elements (cdr things) (max current top))))))
* (count-elements '(1))
1
* (count-elements '(1 2))
3
* (count-elements '(1 2 3))
6
* (count-elements '(1 2 3 2))
6
Hope this helps...
--
vsync
http://quadium.net/ - last updated Thu Sep 28 00:51:25 PDT 2000
(cons (cons (car (cons 'c 'r)) (cdr (cons 'a 'o))) ; Orjner
(cons (cons (car (cons 'n 'c)) (cdr (cons nil 's))) nil))
From: Paul F. Dietz
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <39D5E05A.55B88E6@interaccess.com>
"Young-Jin Lee" <······@uiuc.edu> writes:
> Hi, I'm stuck with loop and recursion. Lisp is quite different from other
> languages I'm used to.
> I'd like to know how to escape a loop before it finishes the entire loop.
> I want to escape the loop when some condition is met. It easy in C/C++/Java.
> I can put simple "if" statement and "retrun" state. But it doesn't work in
> Lisp.
> Could you correct my mistake?
>
> Here is what I tried.
>
> (dotimes (alphaCount (length children))
> (setf valueOfCurrentChild
> (alphabeta (nth alphaCount children)
> alpha beta (- depth 1) (not whoseturn)))
>
> (setf beta (min beta valueOfCurrentChild))
>
> (if (<= beta alpha)
> (return alpha)
> )
> )
You can certainly use RETURN inside loops in Lisp.
It cause the loop to stop and returns that value
-- returns it *from the loop*, not from the enclosing
function definition (to do that, use RETURN-FROM
with the function name.) In this case a simple
RETURN would work.
Have you considered the LOOP macro? Some Lisp
purists dislike it, but I find it's more understandable
than recursion-fetishism. You can use its UNTIL or WHILE
clauses to terminate iteration early.
Paul
From: vsync
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <87pullbk1x.fsf@piro.quadium.net>
vsync <·····@quadium.net> writes:
> I was going to rewrite your example for you, but it uses a lot of
> symbols that I don't know the purpose of, so here's just a random
> function that counts up the numbers in a list as long as they stay
> level or keep increasing, but stops when they start to go down.
>
> (defun count-elements (things &optional (top 0))
> (if (or (null things)
> (< (car things) top))
> 0
> (let ((current (car things)))
> (+ current (count-elements (cdr things) (max current top))))))
I forgot to mention I'm a big recursion fan =). Also, this code is
not as efficient as it could be, since it isn't tail-recursive. It
was late at night... Anyway, here's a tail-recursive version. This
shouldn't run out of stack space for huge lists, and it should be
faster.
(defun tr-count-elements (things &optional (top 0) (subtotal 0))
(if (or (null things)
(< (car things) top))
subtotal
(let ((current (car things)))
(tr-count-elements (cdr things)
(max current top)
(+ subtotal current)))))
--
vsync
http://quadium.net/ - last updated Thu Sep 28 00:51:25 PDT 2000
(cons (cons (car (cons 'c 'r)) (cdr (cons 'a 'o))) ; Orjner
(cons (cons (car (cons 'n 'c)) (cdr (cons nil 's))) nil))
In article <··············@piro.quadium.net>, vsync <·····@quadium.net>
wrote:
> vsync <·····@quadium.net> writes:
>
> > I was going to rewrite your example for you, but it uses a lot of
> > symbols that I don't know the purpose of, so here's just a random
> > function that counts up the numbers in a list as long as they stay
> > level or keep increasing, but stops when they start to go down.
> >
> > (defun count-elements (things &optional (top 0))
> > (if (or (null things)
> > (< (car things) top))
> > 0
> > (let ((current (car things)))
> > (+ current (count-elements (cdr things) (max current top))))))
>
> I forgot to mention I'm a big recursion fan =). Also, this code is
> not as efficient as it could be, since it isn't tail-recursive. It
> was late at night... Anyway, here's a tail-recursive version. This
> shouldn't run out of stack space for huge lists, and it should be
> faster.
>
> (defun tr-count-elements (things &optional (top 0) (subtotal 0))
> (if (or (null things)
> (< (car things) top))
> subtotal
> (let ((current (car things)))
> (tr-count-elements (cdr things)
> (max current top)
> (+ subtotal current)))))
Remember that Common Lisp implementations are not required
to optimize this. Some implementations don't do it.
--
Rainer Joswig, Hamburg, Germany
Email: ·············@corporate-world.lisp.de
Web: http://corporate-world.lisp.de/
From: vsync
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <87lmw8amnv.fsf@piro.quadium.net>
Rainer Joswig <······@corporate-world.lisp.de> writes:
> > I forgot to mention I'm a big recursion fan =). Also, this code is
> > not as efficient as it could be, since it isn't tail-recursive. It
> > was late at night... Anyway, here's a tail-recursive version. This
> > shouldn't run out of stack space for huge lists, and it should be
> > faster.
[...]
> Remember that Common Lisp implementations are not required
> to optimize this. Some implementations don't do it.
Hmm... I didn't know that. I'm guessing CLISP does, because a while
back I was playing around with some recursive code and changed it into
a tail-recursive form, which improved its performance considerably. I
tested this on CMUCL, but didn't bother TIMEing it since it would be
0.0 seconds no matter what.
I am curious to find out which implementations support which
optimizations...
--
vsync
http://quadium.net/ - last updated Thu Sep 28 00:51:25 PDT 2000
(cons (cons (car (cons 'c 'r)) (cdr (cons 'a 'o))) ; Orjner
(cons (cons (car (cons 'n 'c)) (cdr (cons nil 's))) nil))
In article <··············@piro.quadium.net>, vsync <·····@quadium.net>
wrote:
> Rainer Joswig <······@corporate-world.lisp.de> writes:
>
> > > I forgot to mention I'm a big recursion fan =). Also, this code is
> > > not as efficient as it could be, since it isn't tail-recursive. It
> > > was late at night... Anyway, here's a tail-recursive version. This
> > > shouldn't run out of stack space for huge lists, and it should be
> > > faster.
>
> [...]
>
> > Remember that Common Lisp implementations are not required
> > to optimize this. Some implementations don't do it.
>
> Hmm... I didn't know that.
It may also depend on the optimizations settings of the
Lisp.
The general version is tail-call elimination.
(defun foo (bar)
(baz (+ bar 42)))
(defun baz (bar)
(+ bar 21))
In this case the call to BAZ inside FOO can be
compiled to a jump instruction, since the value
is not used inside FOO, so BAZ may return the
value directly.
This is a nice facility, but it often makes debugging
considerably harder, since you won't see stack frames
for all function calls anymore in the debugger.
Again, Common Lisp implementations are not required
to do this. Portable code should not use it - unless
you know that your code will run only in
Lisp implementations that are supporting it.
--
Rainer Joswig, Hamburg, Germany
Email: ·············@corporate-world.lisp.de
Web: http://corporate-world.lisp.de/
From: vsync
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <87d7hk9xt1.fsf@piro.quadium.net>
Rainer Joswig <······@corporate-world.lisp.de> writes:
> The general version is tail-call elimination.
[...]
> Again, Common Lisp implementations are not required
> to do this. Portable code should not use it - unless
> you know that your code will run only in
> Lisp implementations that are supporting it.
But only because it will make debugging harder? I mean, both versions
will run in any implementation, right?
--
vsync
http://quadium.net/ - last updated Thu Sep 28 00:51:25 PDT 2000
(cons (cons (car (cons 'c 'r)) (cdr (cons 'a 'o))) ; Orjner
(cons (cons (car (cons 'n 'c)) (cdr (cons nil 's))) nil))
In article <··············@piro.quadium.net>, vsync <·····@quadium.net>
wrote:
> Rainer Joswig <······@corporate-world.lisp.de> writes:
>
> > The general version is tail-call elimination.
>
> [...]
>
> > Again, Common Lisp implementations are not required
> > to do this. Portable code should not use it - unless
> > you know that your code will run only in
> > Lisp implementations that are supporting it.
>
> But only because it will make debugging harder? I mean, both versions
> will run in any implementation, right?
Minus stack overflow.
--
Rainer Joswig, Hamburg, Germany
Email: ·············@corporate-world.lisp.de
Web: http://corporate-world.lisp.de/
From: Paul F. Dietz
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <39D7A10B.AF8D065E@interaccess.com>
Rainer Joswig wrote:
> > But only because it will make debugging harder? I mean, both versions
> > will run in any implementation, right?
>
> Minus stack overflow.
Also, (temporary) memory leaks from the dead pointers
on the stack.
Paul
From: vsync
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <87wvfs8cqj.fsf@piro.quadium.net>
"Paul F. Dietz" <·····@interaccess.com> writes:
> Rainer Joswig wrote:
>
> > > But only because it will make debugging harder? I mean, both versions
> > > will run in any implementation, right?
> >
> > Minus stack overflow.
>
> Also, (temporary) memory leaks from the dead pointers
> on the stack.
But this would happen with any recursive algorithm, no? If you're
saying that one shouldn't depend on this being optimized without
knowing the details of their particular implementation, then of course
you're right.
I'm still interested in finding a list of which implementations do or
do not perform this optimization.
--
vsync
http://quadium.net/ - last updated Thu Sep 28 00:51:25 PDT 2000
(cons (cons (car (cons 'c 'r)) (cdr (cons 'a 'o))) ; Orjner
(cons (cons (car (cons 'n 'c)) (cdr (cons nil 's))) nil))
From: Paul F. Dietz
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <39D80431.F4110D8C@interaccess.com>
vsync wrote:
> > Also, (temporary) memory leaks from the dead pointers
> > on the stack.
>
> But this would happen with any recursive algorithm, no?
Not necessarily, if the tail recursion optimization can
be, and is, applied.
Paul
In article <··············@piro.quadium.net>, vsync <·····@quadium.net>
wrote:
>I'm still interested in finding a list of which implementations do or
>do not perform this optimization.
MCL does. Others will know about Allegro, Xanalys (formerly Harlequin),
Corman, CMUCL, SBCL etc.
Raffael
--
Raffael Cavallaro, Ph.D.
·······@mediaone.net
From: Reini Urban
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <39db6fdb.361013249@judy>
Raffael Cavallaro wrote:
>MCL does. Others will know about Allegro, Xanalys (formerly Harlequin),
>Corman, CMUCL, SBCL etc.
all of them do tail call elimination.
even kawa does now to some extent, which was one of he majors which
didn't do some time ago.
--
"Bildung kann nicht frei sein" - Gehrer 21.9.00
"Was nichts kostet, ist auch nichts wert."
Andreas Khol, Standard, 20.9.00, Ministerin Gehrer, O�N, 21.9.00,
Christoph Leitl, Wirtschaftsblatt, 21.9.00, etc.
http://xarch.tu-graz.ac.at/error_bildung.html
From: Paul F. Dietz
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <39D79B92.3B2D7CE@interaccess.com>
vsync wrote:
> But only because it will make debugging harder? I mean, both versions
> will run in any implementation, right?
Stack overflow could occur.
Paul
From: Erik Naggum
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <3179473508179600@naggum.net>
* vsync <·····@quadium.net>
| I am curious to find out which implementations support which
| optimizations...
Optimize your quest by delaying this curiosity until it matters.
Then you will have learned two important issues in optimization.
#:Erik
--
If this is not what you expected, please alter your expectations.
From: vsync
Subject: Re: [Q] Lisp beginner's another question, how to escape loop
Date:
Message-ID: <87aecn8bm4.fsf@piro.quadium.net>
Erik Naggum <····@naggum.net> writes:
> * vsync <·····@quadium.net>
> | I am curious to find out which implementations support which
> | optimizations...
>
> Optimize your quest by delaying this curiosity until it matters.
> Then you will have learned two important issues in optimization.
=)
--
vsync
http://quadium.net/ - last updated Thu Sep 28 00:51:25 PDT 2000
(cons (cons (car (cons 'c 'r)) (cdr (cons 'a 'o))) ; Orjner
(cons (cons (car (cons 'n 'c)) (cdr (cons nil 's))) nil))
"Young-Jin Lee" <······@uiuc.edu> writes:
> Hi, I'm stuck with loop and recursion. Lisp is quite different from other
> languages I'm used to.
> I'd like to know how to escape a loop before it finishes the entire loop.
> I want to escape the loop when some condition is met. It easy in C/C++/Java.
> I can put simple "if" statement and "retrun" state. But it doesn't work in
> Lisp.
> Could you correct my mistake?
>
> Here is what I tried.
>
> (dotimes (alphaCount (length children))
> (setf valueOfCurrentChild
> (alphabeta (nth alphaCount children)
> alpha beta (- depth 1) (not whoseturn)))
>
> (setf beta (min beta valueOfCurrentChild))
>
> (if (<= beta alpha)
> (return alpha)
> )
> )
>
> I wanted to escape the loop "if beta <= alpha", but sometimes it seemed to
> be working. I got a correct result with small test case, but ....
A few random remarks:
You have a O(N^2) algorithm where you can easily have a O(N) algorithm
where N is the size of the list. First you determine the length, which
fully traverses the list, and then you use NTH which will again
traverse the list. Use DOLIST instead.
Use lexical variables where appropriate.
To answer your question: here is a quote from the Hyperspec:
An implicit block named nil surrounds dolist. return may be used to
terminate the loop immediately without performing any further
iterations, returning zero or more values.
You might want to look at LOOP for something a bit more familiar.
If I understood your code correctly, this is the equivalent with loop:
(loop for child in children
minimizing (alphabeta child alpha beta (1- depth) (not whoseturn)) into beta
when (<= beta alpha) do (loop-finish)
finally (return beta))
--
Lieven Marchand <···@bewoner.dma.be>
Lambda calculus - Call us a mad club