Picture the scene: it is 1958, and FORTRAN has just been invented. Lit only by the afterglow of atomic tests, primitive Lisp programmers are writing loops in primitive Lisp the way primitive FORTRAN programmers always had:
(prog ((i 0)) ;i is 0
start ;label beginning of loop
(if (>= i 10)
(go end)) ;skip to end when finished
(do-hard-sums-on i) ;hard sums!
(setf i (+ i 1)) ;increment i
(go start) ;jump to start
end) ;end
(Except, of course this would all be in CAPITALS because lower-case had not been invented then, and the thing I wrote as setf would be something uglier, because setf (a macro!) also had not been invented then).
Enter, in clouds of only-slightly toxic smoke from their jetpack, another Lisp programmer who had escaped to 1958 from the future. 'Look', they said, 'we could write this strange future thing':
(defmacro sloop ((var init limit &optional (step 1)) &body forms)
(let ((<start> (make-symbol "START")) ;avoid hygiene problems ...
(<end> (make-symbol "END"))
(<limit> (make-symbol "LIMIT")) ;... and multiple evaluation problems
(<step> (make-symbol "STEP")))
`(prog ((,var ,init)
(,<limit> ,limit)
(,<step> ,step))
,<start>
(if (>= ,var ,<limit>)
(go ,<end>))
,@forms
(setf ,var (+ ,var ,<step>))
(go ,<start>)
,<end>)))
'And now', they say, 'you can write this':
(sloop (i 0 10)
(do-hard-sums i))
And thus were simple loops invented.
Back here in the future we can see what this loop expands into:
(sloop (i 0 10)
(format t "~&i = ~D~%" i))
->
(prog ((i 0) (#:limit 10) (#:step 1))
#:start (if (>= i #:limit) (go #:end))
(format t "~&i = ~D~%" i)
(setf i (+ i #:step))
(go #:start)
#:end)
Which is the code that the primitive Lisp programmers used to type in by hand. And we can run this:
> (sloop (i 0 10)
(format t "~&i = ~D~%" i))
i = 0
i = 1
i = 2
i = 3
i = 4
i = 5
i = 6
i = 7
i = 8
i = 9
nil
And in fact this is how loops work in Lisp today. If I try a simple do loop, one of Common Lisp's predefined macros, we can see what it expands into:
(do ((i 0 (+ i 1)))
((>= i 10))
(format t "~&i = ~D~%" i))
->
(block nil
(let ((i 0))
(declare (ignorable i))
(declare)
(tagbody
#:g1481 (if (>= i 10) (go #:g1480))
(tagbody (format t "~&i = ~D~%" i)
(setq i (+ i 1)))
(go #:g1481)
#:g1480)))
Well, this expansion is not the same and it uses constructs I haven't talked about, but you can see the important thing: this loop has been rewritten to use GO. And, although Common Lisp does not define the expansion of it's looping macros, it is almost certainly the case that all the standard ones expand into something like this (but more complicated in general).
In other words: Lisp doesn't have any primitive looping constructs, but all such constructs are added to the language by macros. These macros as well as other macros to extend the language in other ways, can be written by users: they do not have to be provided by the language itself.
Lisp is a programmable programming language.
