Beginner trying to understand "DO" loops

Discussion of Common Lisp
Post Reply
Malren
Posts: 2
Joined: Wed Jan 21, 2015 9:31 pm

Beginner trying to understand "DO" loops

Post by Malren » Wed Jan 21, 2015 9:54 pm

Hello everyone,

I'm trying to learn LISP after about 7 years not doing any kind of coding. I am slowly working my way through the Practical Common LISP book and have run into an example that I can't seem to follow.

In chapter 7, there is an example of a DO loop which results in the 11th Fibonacci number, 55.

Here is the code:

Code: Select all

(do ((n 0 (1+ n))
     (cur 0 next)
     (next 1 (+ cur next)))
    ((= 10 n) cur))
When I throw that into the REPL I get 55, which makes sense. However, when I try to follow through the loops by hand, I reach 55 on the 6th (or 7th, not sure if I'm counting correctly) loop, but it doesn't terminate and return the value for cur until pass number 11.

I'm clearly not following it through correctly on paper; can anyone break this down so I can see where I'm going wrong?

Thanks so much for the help!

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Beginner trying to understand "DO" loops

Post by nuntius » Wed Jan 21, 2015 11:26 pm

I haven't read the code carefully, but this problem sounds familiar.
You're probably thinking that DO has the binding semantics of DO*.

In other words, all the variables created ("bound") by DO are evaluated in parallel.
A change in the first variable is not visible to the others until the next iteration.

In DO*, all the updates ripple down every time.

Here's the manual for these macros.
http://www.lispworks.com/documentation/ ... _do_do.htm

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Beginner trying to understand "DO" loops

Post by edgar-rft » Thu Jan 22, 2015 6:38 am

Malren wrote:... can anyone break this down so I can see where I'm going wrong?
Try the following in the REPL to see how the values of the variables change during the DO loop:

Code: Select all

(do ((n 0 (1+ n))
     (cur 0 next)
     (next 1 (+ cur next)))
    ((progn (format t "n ~2d  cur ~2d  next ~2d~%" n cur next)
            (= 10 n))  ; termination test
      cur))            ; return value

Malren
Posts: 2
Joined: Wed Jan 21, 2015 9:31 pm

Re: Beginner trying to understand "DO" loops

Post by Malren » Thu Jan 22, 2015 10:18 am

nuntius, edgar-rft, thank you both!

I was making two mistakes, which I now understand.

First, I was assuming that when assigning the new value to next on each iteration that it did have access to the current value of "cur", rather than using the value of "cur" from the previous iteration.

The second assumption was in how the variables were assigned. I wasn't sure if they were incremented by the step-form, or if they became the step-form. As in, did "cur" become the value of the previous "next", or was it incremented by the previous value of "next". Same thing for "next", did it become the value of "cur + next" or was it incremented by "cur + next". Thankfully, I'm clear on that now.

Also, huge thanks for that addition to the code to print the values, I had been trying to do that but didn't know how.

Thanks again for the help!

edgar-rft
Posts: 226
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Beginner trying to understand "DO" loops

Post by edgar-rft » Thu Jan 22, 2015 7:18 pm

DOTIMES, DOLIST and LOOP are the looping constructs you will see most often in Common Lisp code. DO and DO* are remainders from antique Lisp dialects and IMO pretty awkward to use and understand. Both DO and DO* are part of Common Lisp, so you should at least have an idea how they work, but don't waste too much time with them. There _are_ situations where DO and DO* _can_ be useful, but they are very rare and nearly always covered by LOOP. I can't remeber a single situation where I had to use DO or DO* because there was no better understandable solution.

- edgar

Post Reply