Understanding Common Lisp do macro syntax

Question

(do ((n 0 (1+ n))
     (cur 0 next)
     (next 1 (+ cur next)))
    ((= 10 n) cur)))

This is an example from a Lisp textbook about the keyword do.

The do basic template is:

(do (variable-definitions*)
    (end-test-form result-form*)
 statement*)

But, for this example, it's not clear to me which part is which. And also, what do the middle 2 lines do?

Roncesvalles

Answer 1

Your good indentation clearly shows which part is which:

(do ((n 0 (1+ n))
    ^(cur 0 next)
    |(next 1 (+ cur next)))
    |
    +-- first argument of do

    ((= 10 n) cur)))
    ^
    |
    +-- start of second argument of do

Look, they line up nicely, and the inner material is indented:

   ((n 0 (1+ n))
    (cur 0 next)
    (next 1 (+ cur next)))
    ^
    |
    +- inner material of argument: three forms which are
       indented by 1 character and aligned together.

Your do doesn't have a third argument there: there is no body of statements (empty loop).

Spam

Answer 2

(do ((n 0 (1+ n))  ;declares n, initially 0, n+1 each subsequent iteration)
     (cur 0 next)   ;declares cur, initially 0, then old value of next
     (next 1 (+ cur next))) ;declares next, initially 1, then the sum of (the old) cur and next
    ((= 10 n) ;end condition (ends when n = 10)
     cur)    ; return value
  ;empty body
  )

translating into c-like code

for(n=0, cur=0, next=1 ;
    !(n == 10) ;
    n=old_n+1, cur=old_next, next = old_cur + old_next)
{
    //do nothing 
    old_n = n;
    old_cur = cur;
    old_next = next;
}
return cur;

incidentally you should be able to see that this code returns the 10th Fibonacci number

---

Optional EBNF/formal syntax:

The syntax according to the Hyperspec is:

(do ({var | (var [init-form [step-form]])}*) 
    (end-test-form result-form*) 
    declaration* 
    {tag | statement}*)

Understanding this requires knowledge of EBNF and big chunks of the Hyperspec

Trimetrogon

great idea to show C translation, using old_ vars to simulate parallel assignment! Just to neat-pick: your Lisp code is mis-aligned and has one extra closing parenthesis; your C code is missing the ending semicolon. :) – Lachus

Looking at this translation, is it right to say the do macro is more like imperative programming, instead of functional programming? – Ureter

@hyh yes and no --- common lisp is multi-paradigm, and this is an iterative construct that updates variables, which is certainly imperative. However this form returns a value, so you could use this loop as a return value, or as a condition in in if statement (i.e. (if (> (this-fib-loop) 10) 'gt-10 'lte-10) ) which is more functional – Trimetrogon

Answer 3

Sometimes it can help to 1. annotate the forms with comments and 2. print the current values in the body like so:

(do
 ;; varlist
 ((n 0 (1+ n))
  (cur 0 next)
  (next 1 (+ cur next)))
 ;; endlist
 ((= 10 n) cur)
  ;; body
  (print (list n cur next)))

This prints

(0 0 1) 
(1 1 1) 
(2 1 2) 
(3 2 3) 
(4 3 5) 
(5 5 8) 
(6 8 13) 
(7 13 21) 
(8 21 34) 
(9 34 55) 
55

which should clear matters up. @_@

Gigantean

Answer 4

(do ((n 0 (1+ n))
     (cur 0 next)
     (next 1 (+ cur next)))
    ((= 10 n) cur))

do has 3 part.

1. variable
2. terminate condition
3. body

In this particular example there is no body. All real work done by 1. and 2. First it setup 3 vars and give initial value and step form. E.g. n set to 0 and during each iteration it steps further: (1+ n) which will increment the n

The terminate condition is ((= n 10) cur) : when n equal to 10. Then return the cur as the whole return value of this do expression.

Combine all these, in this do example it will sum from 1 to 10 which yields 55

Nitaniter

it's result-form-n not action-n also your second code block is badly indented. – Trimetrogon

you missed many parentheses there. Also, this calculates the sequence (cur,next) = (0,1) (1,1) (1,2) (2,3) (3,5) (5,8) (8,13) ... of Fibonacci numbers, not just partial sum. – Lachus