CODEWITHSUNDEEP
lispiterationcommon-lisp
Anders Lind
Anders Lind

Reputation: 4840

Understanding Common Lisp do macro syntax

(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?

Upvotes: 10

Views: 8690

Answers (4)

lupl
lupl

Reputation: 944

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. @_@

Upvotes: 1

tobyodavies
tobyodavies

Reputation: 28099

(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

Upvotes: 30

Juanito Fatas
Juanito Fatas

Reputation: 9969

(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

Upvotes: 0

Kaz
Kaz

Reputation: 58627

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).

Upvotes: 14

Related Questions