iterate.texinfo 103 KB
Newer Older
Luís Oliveira's avatar
Luís Oliveira committed
1
2
3
\input texinfo   @c -*- Mode: Texinfo; Mode: auto-fill -*-
@c %**start of header
@setfilename iterate.info
4
@settitle The Iterate Manual and Paper
Luís Oliveira's avatar
Luís Oliveira committed
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@exampleindent 2

@c @documentencoding utf-8

@macro iter {}
@code{iterate}
@end macro

@macro mathx {tex, non-tex}
@iftex
@math{\tex\}
@end iftex
@ifnottex
@emph{\non-tex\}
@end ifnottex
@end macro

@macro impnote {text}
23
24
@quotation Implementor's note
@emph{\text\}
Luís Oliveira's avatar
Luís Oliveira committed
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
@end quotation
@end macro

@c Set ROMANCOMMENTS to get comments in roman font.
@ifset ROMANCOMMENTS
@alias lispcmt = r
@end ifset
@ifclear ROMANCOMMENTS
@alias lispcmt = asis
@end ifclear

@c Index for iterate clauses.
@defindex it

@macro clauseu {name1}
@itindex \name1\
@c
@end macro

@macro claused {name1, name2}
@itindex \name1\@dots{}\name2\
@c
@end macro

@macro clauset {name1, name2, name3}
@itindex \name1\@dots{}\name2\@dots{}\name3\
@c
@end macro

@macro k {what}
@code{\what\}
@end macro

@iftex
@alias v = asis
@alias cl = code
@end iftex

@ifnottex
@alias v = var
@alias cl = strong
@end ifnottex

@c Show variables, clauses, and concepts in the same index.
@syncodeindex it cp
@syncodeindex vr cp

@copying
Copyright @copyright{} 1989 Jonathan Amsterdam <jba at ai.mit.edu> @*
@c Copyright @copyright{} 2006 Lu@'{@dotless{i}}s Oliveira
@c  <loliveira at common-lisp.net> @*

@quotation
78
79
The present manual is a conversion of Jonathan Amsterdam's ``The
Iterate Manual'', @acronym{MIT} @acronym{AI} Memo No.@: 1236.  Said memo
Luís Oliveira's avatar
Luís Oliveira committed
80
81
82
83
84
85
86
87
mentioned the following contract information:

@emph{This report describes research done at the Artificial
Intelligence Laboratory of the Massachusetts Institute of Technology.
Support for the laboratory's artificial intelligence research is
provided in part by the Advanced Research Projects Agency of the
Department of Defense under Office of Naval Research contract
N00014-85-K-0124.}
88
89
90

The appendix includes Jonathan Amsterdam's Working Paper 324,
MIT AI Lab entitled ``Don't Loop, Iterate.''
Luís Oliveira's avatar
Luís Oliveira committed
91
92
93
94
95
@end quotation
@end copying
@c %**end of header

@titlepage
96
@title The Iterate Manual and Paper
Luís Oliveira's avatar
Luís Oliveira committed
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
@c @subtitle Version X.X
@c @author Jonathan Amsterdam

@page
@vskip 0pt plus 1filll
@insertcopying
@end titlepage

@contents

@ifnottex
@node Top
@top iterate
@insertcopying
@end ifnottex

@menu
* Introduction::                
* Clauses::                     
* Other Features::              
* Types and Declarations::      
* Problems with Code Movement::  
* Differences Between Iterate and Loop::  
* Rolling Your Own::            
* Non-portable Extensions to Iterate (Contribs)::  
* Obtaining Iterate::           
* Acknowledgements::            
* Don't Loop Iterate::                 
* Comprehensive Index::         
@end menu

@c ===================================================================
@node Introduction
@chapter Introduction

This manual describes @iter{}, a powerful iteration facility for
Common Lisp.  @iter{} provides abstractions for many common iteration
patterns and allows for the definition of additional patterns.
@iter{} is a macro that expands into ordinary Lisp at compile-time, so
it is more efficient than higher-order functions like @code{map} and
137
@code{reduce}.  While it is similar to @code{loop}, @iter{} offers a
Luís Oliveira's avatar
Luís Oliveira committed
138
139
more Lisp-like syntax and enhanced extensibility.  (For a more
complete comparison of @iter{} with other iteration constructs, see
140
@acronym{MIT} @acronym{AI} Lab Working Paper No.@: 324, @emph{Don't
Luís Oliveira's avatar
Luís Oliveira committed
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
Loop, Iterate.} also included in this manual in @ref{Don't Loop
Iterate}.)

An @iter{} form consists of the symbol @code{iter}@footnote{You can
also use @code{iterate}, but @code{iter} is preferred because it
avoids potential conflicts with possible future additions to Common
Lisp, and because it saves horizontal space when writing code.}
followed by one or more forms, some of which may be @iter{}
@emph{clauses}.  Here is a simple example of @iter{} which collects
the numbers from 1 to 10 into a list, and returns the list.  The
return value is shown following the arrow.

@lisp
(iter (for i from 1 to 10)
      (collect i))          @result{} (1 2 3 4 5 6 7 8 9 10)
@end lisp

This form contains two clauses: a @code{for} clause that steps the
variable @code{i} over the integers from 1 to 10, and a @code{collect}
clause that accumulates its argument into a list.  With a few
exceptions, all @iter{} clauses have the same format: alternating
symbols (called @emph{keywords}) and expressions (called
@emph{arguments}).  The syntax and terminology are those of Common
Lisp's keyword lambda lists.  One difference is that @iter{}'s keywords
do not have to begin with a colon---though they may, except for the
first symbol of a clause.  So you can also write @code{(for i :from 1
:to 10)} if you prefer.

Any Lisp form can appear in the body of an @iter{}, where it will have
its usual meaning.  @iter{} walks the entire body, expanding macros,
and recognizing clauses at any level.  This example collects all the
odd numbers in a list:

@lisp
(iter (for el in list)
      (if (and (numberp el) (oddp el))
          (collect el)))
@end lisp

There are clauses for iterating over numbers, lists, arrays and other
objects, and for collecting, summing, counting, maximizing and other
useful operations.  @iter{} also supports the creation of new variable
bindings, stepping over multiple sequences at once, destructuring, and
compiler declarations of variable types.  The following example
illustrates some of these features:

@lisp
(iter (for (key . item) in alist)
      (for i from 0)
      (declare (fixnum i))
      (collect (cons i key)))
@end lisp

This loop takes the keys of an alist and returns a new alist
195
associating the keys with their positions in the original list.  The
Luís Oliveira's avatar
Luís Oliveira committed
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
compiler declaration for @code{i} will appear in the generated code in
the appropriate place.

@c ===================================================================
@node Clauses
@chapter Clauses

Most of @iter{}'s clauses will be familiar to @code{loop} programmers.
(@code{loop} is an iteration macro that has been incorporated into
Common Lisp.  See Guy Steele's @emph{Common Lisp, 2nd Edition}.)  In
nearly all cases they behave the same as their @code{loop}
counterparts, so a @code{loop} user can switch to @iter{} with little
pain (and much gain).

All clauses with the standard keyword-argument syntax consist of two
parts: a @emph{required} part, containing keywords that must be present and
in the right order; and an @emph{optional} part, containing keywords that
may be omitted and, if present, may occur in any order.  In the
descriptions below, the parts are separated by the Lisp lambda-list
keyword @code{&optional}.

@menu
* Drivers::                     
* Variable Binding and Setting::  
* Gathering Clauses::           
* Control Flow::                
222
* Predicates::                  
Luís Oliveira's avatar
Luís Oliveira committed
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
* Code Placement::              
@end menu

@c ===================================================================
@node Drivers
@section Drivers

An iteration-driving clause conceptually causes the iteration to go
forward.  Driver clauses in @iter{} allow iteration over numbers,
lists, vectors, hashtables, packages, files and streams.
Iteration-driving clauses must appear at the top level of an @iter{}
form; they cannot be nested inside another clause.  The driver
variable is updated at the point where the driver clause occurs.
Before the clause is executed for the first time, the value of the
variable is undefined.

@c Also, regardless of where the driver clause appears in the body,
@c the driver variable is stepped at the top of the loop; hence it is
@c stylistically preferable, though not required, to place driver
@c clauses at the beginning of the @iter{}.

Multiple drivers may appear in a single @iter{} form, in which case all
of the driver variables are updated each time through the loop, in the
order in which the clauses appear.  The first driver to terminate will
terminate the entire loop.

In all cases, the value of the driver variable on exit from the loop,
including within the epilogue code (see the @code{finally} clause), is
undefined.

All the parameters of a driver clause are evaluated once, before the
loop begins.  Hence it is not possible to change the bounds or other
properties of an iteration by side-effect from within the loop.

With one exception, driver clauses begin with the word @code{for} (or
the synonym @code{as}) and mention an iteration variable, which is
given a binding within the @iter{} form.  The exception is
@code{repeat}, which just executes a loop a specified number of times:

@clauseu{repeat}
@deffn Clause repeat @v{n}

Repeat the loop @var{n} times.  For example:

@lisp
(iter (repeat 100)
      (print "I will not talk in class."))
@end lisp

If @mathx{n \leq 0, n <= 0}, then loop will never be executed.  If @var{n} is
not an integer, the actual number of executions will be @mathx{\lceil n
\rceil, ceil(n)}.
@end deffn

@menu
* Numerical Iteration::         
* Sequence Iteration::          
* Generalized Drivers::         
* Generators::                  
* Previous Values of Driver Variables::  
@end menu

@c ===================================================================
@node Numerical Iteration
@subsection Numerical Iteration

@clauseu{for}
@deffn Clause for @v{var} @k{&sequence}

The general form for iterating over a sequence of numbers requires a
variable and, optionally, one or more keywords that provide the bounds
294
and step size of the iteration.  The @code{&sequence} lambda-list
Luís Oliveira's avatar
Luís Oliveira committed
295
296
297
298
299
300
301
keyword is a shorthand for these sequence keywords.  They are:
@code{from}, @code{upfrom}, @code{downfrom}, @code{to}, @code{downto},
@code{above}, @code{below} and @code{by}.  @code{from} provides the
starting value for @var{var} and defaults to zero.  @code{to} provides
a final value and implies that the successive values of @var{var} will
be increasing; @code{downto} implies that they will be decreasing.
The loop terminates when @var{var} passes the final value
302
(i.e.@: becomes smaller or larger than it, depending on the direction of
Luís Oliveira's avatar
Luís Oliveira committed
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
iteration); in other words, the loop body will never be executed for
values of @var{var} past the final value.  @code{below} and
@code{above} are similar to @code{to} and @code{downto}, except that
the loop terminates when @var{var} equals or passes the final value.

If no final value is specified, the variable will be stepped forever.
Using @code{from} or @code{upfrom} will result in increasing values,
while @code{downfrom} will give decreasing values.

On each iteration, @var{var} is incremented or decremented by the
value of the sequence keyword @code{by}, which defaults to 1.  It
should always be a positive number, even for downward iterations.

In the following examples, the sequence of numbers generated is shown
next to the clause.

@lisp
(for i upfrom 0) @result{} 0 1 2 @dots{}
(for i from 5) @result{} 5 6 7 @dots{}    ; either from or upfrom is okay
(for i downfrom 0) @result{} 0 -1 -2 @dots{}
(for i from 1 to 3) @result{} 1 2 3
(for i from 1 below 3) @result{} 1 2
(for i from 1 to 3 by 2) @result{} 1 3
(for i from 1 below 3 by 2) @result{} 1
(for i from 5 downto 3) @result{} 5 4 3
@end lisp
@end deffn

@c ===================================================================
@node Sequence Iteration
@subsection Sequence Iteration

There are a number of clauses for iterating over sequences.  In all of
them, the argument following @code{for} may be a list instead of a
337
symbol, in which case destructuring is performed.  See
Luís Oliveira's avatar
Luís Oliveira committed
338
339
340
341
342
343
344
@ref{Destructuring}.

@claused{for, in}
@deffn Clause for @v{var} @cl{in} @v{list} @k{&optional} @k{by} @v{step-function}

@var{var} is set to successive elements of list. @var{step-function},
which defaults to @code{cdr}, is used to obtain the next sublist.
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360

This clause uses @code{endp} to test for the end of a list, hence
should signal an error when processing an improper list whose final
@code{cdr} is not @code{nil}---like @code{loop}.  Prior to 2007,
@iter{} would default to @code{atom} and silently exit.

@vindex *list-end-test*
@quotation Compatibility Note
The original implementation used the variable
@code{iterate::*list-end-test*}, defaulting to @code{atom}.  Years
later, it was deemed unacceptable for the semantics @emph{not} to be
lexically apparent from the iteration form so this variable was
removed.  If your application depends on the original behaviour, the
ancient @code{for @v{var} in} is equivalent to
@code{for (@v{var}) on}.
@end quotation
Luís Oliveira's avatar
Luís Oliveira committed
361
362
363
364
365
@end deffn

@claused{for, on}
@deffn Clause for @v{var} @cl{on} @v{list} @k{&optional} @k{by} @v{step-function}

366
@var{var} is set to successive sublists of list.  @var{step-function}
Luís Oliveira's avatar
Luís Oliveira committed
367
(default @code{cdr}) is used as in @code{for@dots{} in}.
368
369
370

This clause uses @code{atom} to test for the end of a list, so it can
be used with dotted lists---like @code{loop}.
Luís Oliveira's avatar
Luís Oliveira committed
371
372
@end deffn

373
374
375
376
377
378
379
@c These two clauses use @code{atom} to test for the end of a list.
@c Hence, given a list whose final @code{cdr} is not @code{nil}, they
@c will silently ignore the last @code{cdr}.  Other choices are
@c @code{endp}, which would signal an error, and @code{null}, which would
@c probably result in an error somewhere else.  If you wish to use an
@c end-test other than @code{atom}, set the variable
@c @code{iterate::*list-end-test*} to the name of the desired function.
Luís Oliveira's avatar
Luís Oliveira committed
380
381
382
383

@claused{for, in-vector}
@deffn Clause for @v{var} @cl{in-vector} @v{vector} @k{&sequence}

384
@var{var} takes on successive elements from @var{vector}.  The vector's
Luís Oliveira's avatar
Luís Oliveira committed
385
386
387
388
389
fill-pointer is observed.  Here and in subsequent clauses, the
@code{&sequence} keywords include @code{with-index}, which takes a
symbol as argument and uses it for the index variable instead of an
internally generated symbol.  The other @code{&sequence} keywords
behave as in numerical iteration, except that the default iteration
390
bounds are the bounds of the vector.  E.g.@: in @code{(for i in-vector v
Luís Oliveira's avatar
Luís Oliveira committed
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
downto 3)}, @code{i} will start off being bound to the last element in
@code{v}, and will be set to preceding elements down to and including
the element with index 3.
@end deffn

@claused{for, in-sequence}
@deffn Clause for @v{var} @cl{in-sequence} @v{seq} @k{&sequence}

This uses Common Lisp's generalized sequence functions, @code{elt} and
@code{length}, to obtain elements and determine the length of
@var{seq}.  Hence it will work for any sequence, including lists, and
will observe the fill-pointers of vectors.
@end deffn

@claused{for, in-string}
@deffn Clause for @v{var} @cl{in-string} @v{string} @k{&sequence}

@var{var} is set to successive characters of @var{string}.
@end deffn

@claused{for, index-of-vector}
@claused{for, index-of-sequence}
@claused{for, index-of-string}
@deffn Clause for @v{var} @cl{index-of-vector} @v{vector} @k{&sequence}
@deffnx Clause for @v{var} @cl{index-of-sequence} @v{sequence} @k{&sequence}
@deffnx Clause for @v{var} @cl{index-of-string} @v{string} @k{&sequence}

@var{var} is set to successive indices of the sequence.  These clauses
avoid the overhead of accessing the sequence elements for those
applications where they do not need to be examined, or are examined
rarely.  They admit all the optional keywords of the other sequence
drivers except the (redundant) @code{with-index} keyword.
@end deffn

@claused{for, in-hashtable}
@deffn Clause for (@v{key} @v{value}) @cl{in-hashtable} @v{table}

@var{key} and @var{value}, which must appear as shown in a list and
may be destructuring templates, are set to the keys and values of
@var{table}.  If @var{key} is @code{nil}, then the hashtable's keys
will be ignored; similarly for @var{value}.  The order in which
elements of @var{table} will be retrieved is unpredictable.
@end deffn

@claused{for, in-package}
@deffn Clause for @v{var} @cl{in-package} @v{package} @
                  @k{&optional} @k{external-only} @v{ext}

Iterates over all the symbols in @var{package}, or over only the
external symbols if @var{ext} is specified and non-@code{nil}.
@var{ext} is not evaluated.  The same symbol may appear more than
once.
@end deffn

@claused{for, in-packages}
@deffn Clause for @v{var} @cl{in-packages} @
                  @k{&optional} @k{having-access} @v{symbol-types}

Iterates over all the symbols from the list of packages denoted by the
descriptor @var{packages} and having accessibility (or visibility)
given by @var{symbol-types}.  This defaults to the list
@code{(:external :internal :inherited)} and is not evaluated.
@var{var} must be a list of up to three variables: in each iteration,
these will be set to a symbol, its access-type and package (as per
@code{with-package-iterator} in ANSI CL).  The same symbol may appear
more than once.
@end deffn

@claused{for, in-file}
@deffn Clause for @v{var} @cl{in-file} @v{name} @
                  @k{&optional} @k{using} @v{reader}

Opens the file @var{name} (which may be a string or pathname) for
464
input, and iterates over its contents.  @var{reader} defaults to
Luís Oliveira's avatar
Luís Oliveira committed
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
@code{read}, so by default @emph{var} will be bound to the successive
forms in the file.  The @iter{} body is wrapped in an
@code{unwind-protect} to ensure that the file is closed no matter how
the @iter{} is exited.
@end deffn

@claused{for, in-stream}
@deffn Clause for @v{var} @cl{in-stream} @v{stream} @k{&optional} @k{using} @
              @v{reader}

Like @code{for@dots{} in-file}, except that @var{stream} should be an
existing stream object that supports input operations.
@end deffn

@c ===================================================================
@node Generalized Drivers
@subsection Generalized Drivers

These are primarily useful for writing drivers that can also be used
as generators (see @ref{Generators}).

@clauseu{terminate}
@claused{for, next}
@deffn Clause for @v{var} @cl{next} @v{expr}

@var{var} is set to @var{expr} each time through the loop.
Destructuring is performed.  When the clause is used as a generator,
@var{expr} is the code that is executed when @code{(next @emph{var})}
is encountered (see @ref{Generators}).  @var{expr} should compute the
first value for @var{var}, as well as all subsequent values, and is
responsible for terminating the loop.  For compatibility with future
versions of @iter{}, this termination should be done with
@code{terminate}, which can be considered a synonym for @code{finish}
(see @ref{Control Flow}).

As an example, the following clauses are equivalent to @code{(for i
from 1 to 10)}:

@lisp
(initially (setq i 0))
(for i next (if (> i 10) (terminate) (incf i)))
@end lisp
@end deffn

@claused{for, do-next}
@deffn Clause for @v{var} @k{do-next} @v{form}

@var{form} is evaluated each time through the loop.  Its value is
513
@var{not} set to @var{var}; that is @var{form}'s job.  @var{var} is
Luís Oliveira's avatar
Luís Oliveira committed
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
only present so that @iter{} knows it is a driver variable. @*
@code{(for @var{var} next @var{expr})} is equivalent to @code{(for
@var{var} do-next (dsetq @var{var} @var{expr}))}.  (See
@ref{Destructuring} for an explanation of @code{dsetq}.)
@end deffn

@c ===================================================================
@node Generators
@subsection Generators

In all of the above clauses, the driver variable is updated on each
iteration.  Sometimes it is desirable to have greater control over
updating.  For instance, consider the problem of associating numbers,
in increasing order and with no gaps, with the non-@code{nil} elements
of a list.  One obvious first pass at writing this is:

@lisp
(iter (for el in list)
      (for i upfrom 1)
      (if el (collect (cons el i))))
@end lisp

But on the list @code{(a b nil c)} this produces @code{((a . 1) (b
. 2) (c .  4))} instead of the desired @code{((a . 1) (b . 2) (c
. 3))}.  The problem is that @code{i} is incremented each time through
the loop, even when @code{el} is @code{nil}.

The problem could be solved elegantly if we could step @code{i} only
when we wished to.  This can be accomplished for any @iter{} driver by
writing @code{generate} (or its synonym @code{generating}) instead of
@code{for}.  Doing so produces a @emph{generator}---a driver whose
values are yielded explicitly.  To obtain the next value of a
generator variable @var{v}, write @code{(next @var{v})}.  The value of
a @code{next} form is the next value of @emph{v}, as determined by its
associated driver clause.  @code{next} also has the side-effect of
updating @var{v} to that value.  If there is no next value,
@code{next} will terminate the loop, just as with a normal driver.

Using generators, we can now write our example like this:

@lisp
(iter (for el in list)
      (generate i upfrom 1)
      (if el (collect (cons el (next i)))))
@end lisp

Now @code{i} is updated only when @code{(next i)} is executed, and
this occurs only when @code{el} is non-@code{nil}.

To better understand the relationship between ordinary drivers and
generators, observe that we can rewrite an ordinary driver using its
generator form immediately followed by @code{next}, as this example
shows:

@lisp
(iter (generating i from 1 to 10)
      (next i)
      @dots{})
@end lisp

Provided that the loop body contains no @code{(next i)} forms, this
will behave just as if we had written @code{(for i from 1 to 10)}.

We can still refer to a driver variable @var{v} without using
@code{next}; in this case, its value is that given to it by the last
evaluation of @code{(next @var{v})}.  Before @code{(next @var{v})} has
been called the first time, the value of @var{v} is undefined.

This semantics is more flexible than one in which @var{v} begins the
loop bound to its first value and calls of @code{next} supply
subsequent values, because it means the loop will not terminate too
soon if the generator's sequence is empty.  For instance, consider the
following code, which tags non-@code{nil} elements of a list using a
list of tags, and also counts the null elements.  (We assume there are
at least as many tags as non-@code{nil} elements.)

@lisp
(let* ((counter 0)
       (tagged-list (iter (for el in list)
                          (generating tag in tag-list) 
                          (if (null el)
                              (incf counter)
                              (collect (cons el (next tag)))))))
  @dots{})
@end lisp

It may be that there are just as many tags as non-null elements of
@code{list}.  If all the elements of @code{list} are null, we still
want the counting to proceed, even though @code{tag-list} is
@code{nil}.  If @code{tag} had to be assigned its first value before
the loop begins, we would have had to terminate the loop before the
first iteration, since when @code{tag-list} is @code{nil}, @code{tag}
has no first value.  With the existing semantics, however, @code{(next
tag)} will never execute, so the iteration will cover all the elements
of @code{list}.
        
When the ``variable'' of a driver clause is actually a destructuring
template containing several variables, all the variables are eligible
for use with @code{next}.  As before, @code{(next @var{v})} evaluates
to @var{v}'s next value; but the effect is to update all of the
template's variables.  For instance, the following code will return
the list @code{(a 2 c)}.

@lisp
(iter (generating (key . item) in '((a . 1) (b . 2) (c . 3)))
      (collect (next key))
      (collect (next item)))
@end lisp

Only driver clauses with variables can be made into generators.  This
includes all clauses mentioned so far except for @code{repeat}.  It
does @emph{not} include @code{for@dots{} previous}, @code{for@dots{}
=}, @code{for@dots{} initially@dots{} then} or @code{for@dots{}
first@dots{} then} (see below).

@c ===================================================================
@node Previous Values of Driver Variables
@subsection Previous Values of Driver Variables

Often one would like to access the value of a variable on a previous
iteration.  @iter{} provides a special clause for accomplishing this.

@claused{for, previous}
@deffn Clause for @v{pvar} @cl{previous} @v{var} @
                  @k{&optional} @k{initially} @v{init} @k{back} @v{n}

Sets @var{pvar} to the previous value of @var{var}, which should be a
driver variable, a variable from another @code{for@dots{} previous}
clause, or a variable established by a @code{for@dots{} =},
@code{for@dots{}  initially@dots{} then} or @code{for@dots{}
first@dots{} then} clause (see @ref{Variable Binding and Setting}).
Initially, @var{pvar} is given the value @var{init} (which defaults to
@code{nil}).  The @var{init} expression will be moved outside the loop
body, so it should not depend on anything computed within the loop.
@var{pvar} retains the value of @var{init} until @var{var} is set to
its second value, at which point @var{pvar} is set to @var{var}'s
first value; and so on.

The argument @var{n} to @code{back} must be a constant, positive
integer, and defaults to 1.  It determines how many iterations back
@var{pvar} should track @var{var}.  For example, when @var{n} is 2,
then @var{pvar} will be assigned @var{var}'s first value when
@var{var} is set to its third value.

A @code{for@dots{} previous} clause may occur after or before its
659
associated driver clause.  @code{for@dots{} previous} works with
Luís Oliveira's avatar
Luís Oliveira committed
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
generators as well as ordinary drivers.

Example:

@lisp
(iter (for el in '(1 2 3 4))
      (for p-el previous el)
      (for pp-el previous p-el initially 0)
      (collect pp-el))
@end lisp

This evaluates to @code{(0 0 1 2)}.  It could have been written more
economically as

@lisp
(iter (for el in '(1 2 3 4))
      (for pp-el previous el back 2 initially 0)
      (collect pp-el))
@end lisp
@end deffn

@c ===================================================================
@node Variable Binding and Setting
@section Variable Binding and Setting

Several clauses exist for establishing new variable bindings or for
setting variables in the loop.  They all support destructuring.

@clauseu{with}
@deffn Clause with @v{var} @k{&optional} @k{=} @v{value}

Causes @var{var} to be bound to value before the loop body is entered.
If @var{value} is not supplied, @var{var} assumes a default binding,
which will be @code{nil} in the absence of declarations.  Also, if
@var{value} is not supplied, no destructuring is performed; instead,
@var{var} may be a list of symbols, all of which are given default
bindings.  If @var{value} is supplied, @var{var} is bound to it, with
destructuring.

Because @code{with} creates bindings whose scope includes the entire
@iter{} form, it is good style to put all @code{with} clauses at the
beginning.

Successive occurrences of @code{with} result in sequential bindings
(as with @code{let*}).  There is no way to obtain parallel bindings;
705
see @ref{Parallel Binding and Stepping} for a rationale.
Luís Oliveira's avatar
Luís Oliveira committed
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
@end deffn

@claused{for, =}
@deffn Clause for @v{var} @cl{=} @v{expr}

On each iteration, @var{expr} is evaluated and @var{var} is set to its
value.

This clause may appear to do the same thing as @code{for@dots{} next}.
In fact, they are quite different.  @code{for@dots{} =} provides only
three services: it sets up a binding for @var{var}, sets it to
@var{expr} on each iteration, and makes it possible to use
@code{for@dots{}  previous} with @var{var}.  @code{for@dots{} next}
provides these services in addition to the ability to turn the driver
into a generator.

@c Also, the code which sets @var{var} appears in the loop body in the
@c same place as the @code{for@dots{} =} clause; the code for
@c @code{for@dots{} next} appears at the top of the loop, as with
@c other drivers (except when being used as a generator).
@end deffn

@clauset{for, initially, then}
@deffn Clause for @v{var} @cl{initially} @v{init-expr} @cl{then} @v{then-expr}

Before the loop begins, @var{var} is set to @var{init-expr;} on all
iterations after the first it is set to @var{then-expr.} This clause
must occur at top-level.  @var{init-expr} will be moved outside the
loop body and @var{then-expr} will be moved to the end of the loop
body, so they are subject to code motion problems (see @ref{Problems
with Code Movement}).

This clause may appear to be similar to @code{for@dots{} next}, but in
fact they differ significantly.  @code{for@dots{} initially@dots{}
then} is typically used to give @var{var} its first value before the
loop begins, and subsequent values on following iterations.  This is
incompatible with generators, whose first value and subsequent values
must all be computed by @code{(next @var{var})}.  Also, the update of
@var{var} in @code{for@dots{} initially@dots{} then} does not occur at
the location of the clause.

Use @code{for@dots{} initially@dots{} then} for one-shot computations
where its idiom is more convenient, but use @code{for@dots{} next} for
extending @iter{} with new drivers (see @ref{Rolling Your Own}).
@end deffn

@clauset{for, first, then}
@deffn Clause for @v{var} @cl{first} @v{first-expr} @cl{then} @v{then-expr}

The first time through the loop, @var{var} is set to @var{first-expr};
756
on subsequent iterations, it is set to @var{then-expr}.  This differs
Luís Oliveira's avatar
Luís Oliveira committed
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
from @code{for@dots{} initially} in that @var{var} is set to
@var{first-expr} inside the loop body, so @var{first-expr} may depend
on the results of other clauses.  For instance,

@lisp
(iter (for num in list)
      (for i first num then (1+ i))
      ...)
@end lisp

will set @code{i} to the first element of @code{list} on the first
iteration, whereas

@lisp
(iter (for num in list)
      (for i initially num then (1+ i))
      ...)
@end lisp

is probably erroneous; @code{i} will be bound to @code{num}'s default
binding (usually @code{nil}) for the first iteration.
@end deffn

@quotation Compatibility Note
@code{loop}'s @code{for@dots{} =} works like @iter{}'s, but
@code{loop} used the syntax @code{for@dots{} =@dots{} then} to mean
@code{for@dots{} initially@dots{} then}.  It was felt that these two
operations were sufficiently different to warrant different keywords.

Also, the @code{for} in the above three clauses is misleading, since
787
none is true driver (e.g.@: none has a corresponding @code{generate}
Luís Oliveira's avatar
Luís Oliveira committed
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
form).  @code{setting} would have been a better choice, but @code{for}
was used to retain some compatibility with @code{loop}.
@end quotation

@c ===================================================================
@node Gathering Clauses
@section Gathering Clauses

Many of @iter{}'s clauses accumulate values into a variable, or set a
variable under certain conditions.  At the end of the loop, this
variable contains the desired result.  All these clauses have an
optional @code{into} keyword, whose argument should be a symbol.  If
the @code{into} keyword is not supplied, the accumulation variable
will be internally generated and its value will be returned at the end
of the loop; if a variable is specified, that variable is used for the
accumulation, and is not returned as a result---it is up to the user
to return it explicitly, in the loop's epilogue code (see
@code{finally}).  It is safe to examine the accumulation variable
during the loop, but it should not be modified.

These clauses all begin with a verb.  When the verb does not conflict
with an existing Common Lisp function, then it may be used in either
810
its infinitival or present-participle form (e.g.@: @code{sum},
Luís Oliveira's avatar
Luís Oliveira committed
811
@code{summing}).  However, when there is a conflict with Common Lisp,
812
only the present-participle form may be used (e.g.@: @code{unioning}).
Luís Oliveira's avatar
Luís Oliveira committed
813
814
815
816
817
818
This is to prevent @iter{} clauses from clashing with Common Lisp
functions.

@c although these clauses are described as ``producing a value,'' it
@c is a mistake to think of the lisp list representing the clause as a
@c value-producing form in the usual way.  clauses may legally be
819
@c written where a value is expected, e.g.@: @code{(setq x (sum i))},
Luís Oliveira's avatar
Luís Oliveira committed
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
@c but the lisp value of a clause in such a context is undefined.

@menu
* Reductions::                  
* Accumulations::               
* Finders::                     
* Aggregated Boolean Tests::    
@end menu

@c ===================================================================
@node Reductions
@subsection Reductions

@emph{Reduction} is an extremely common iteration pattern in which the
results of successive applications of a binary operation are
accumulated.  For example, a loop that computes the sum of the
elements of a list is performing a reduction with the addition
operation.  This could be written in Common Lisp as @code{(reduce #'+
list)} or with @iter{} as

@lisp
(iter (for el in list)
      (sum el))
@end lisp

@clauseu{sum}
@deffn Clause sum @v{expr} @k{&optional} @k{into} @v{var}

Each time through the loop, @var{expr} is evaluated and added to a
variable, which is bound initially to zero.  If @var{expr} has a type,
it is @emph{not} used as the type of the sum variable, which is always
@code{number}.  To get the result variable to be of a more specific
type, use an explicit variable, as in

@lisp
(iter (for el in number-list)
      (sum el into x)
      (declare (fixnum x))
      (finally (return x)))
@end lisp
@end deffn

@clauseu{multiply}
@deffn Clause multiply @v{expr} @k{&optional} @k{into} @v{var}

Like @code{sum}, but the initial value of the result variable is
@math{1}, and the variable is updated by multiplying @var{expr} into
it.
@end deffn

@clauseu{counting}
@deffn Clause counting @v{expr} @k{&optional} @k{into} @v{var}

@var{expr} is evaluated on each iteration.  If it is non-@code{nil},
the accumulation variable, initially zero, is incremented.
@end deffn

@clauseu{maximize}
@clauseu{minimize}
@deffn Clause maximize @v{expr} @k{&optional} @k{into} @v{var}
@deffnx Clause minimize @v{expr} @k{&optional} @k{into} @v{var}

@var{expr} is evaluated on each iteration and its extremum (maximum or
minimum) is stored in the accumulation variable.  If @var{expr} is
never evaluated, then the result is @code{nil} (if the accumulation
variable is untyped) or @math{0} (if it has a numeric type).
@end deffn

@clauseu{reducing}
@deffn Clause reducing @v{expr} @k{by} @v{func} @k{&optional}
                       @k{initial-value} @v{init-val} @k{into} @v{var}

892
This is a general way to perform reductions.  @var{func} should be a
Luís Oliveira's avatar
Luís Oliveira committed
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
function of two arguments, the first of which will be the value
computed so far and the second of which will be the value of
@var{expr}.  It should return the new value.  @code{reducing} is
roughly equivalent to the Common Lisp @code{(reduce @var{func}
@var{sequence} :key @var{expr-function})}, where @var{expr-function}
is used to derive values from the successive elements of
@var{sequence}.

If the @code{reducing} clause is never executed, the result is
undefined.

It is not necessary to provide an initial value, but better code can
be generated if one is supplied.  Regardless of its location in the
@iter{} body, @var{init-val} will be evaluated before the loop is
entered, so it should not depend on any value computed inside the
@iter{} form.

@c if a @var{var} is not specified, you can get @iter{} to declare the
@c type of the internal variable by putting a @code{the} expression
@c around @var{func}.  see @ref{Types}.
@end deffn

@c @impnote{in principle, |maximize| and |minimize| can be thought of
@c as reductions where the initial value is the smallest (or largest)
@c value that the accumulation variable can assume.  because lisp's
@c bignums can represent arbitrary integers, these clauses cannot be
@c implemented as reductions in general.  if, however, the type of
@c ~expr~ or ~var~ can be determined to be a fixnum or a float,
@c @iter{} will implement the clause as a true reduction, using one of
@c the constants |most-negative-fixnum|, |@c most-positive-fixnum|,
923
@c |most-negative-short-float|, etc.@: as appropriate.}
Luís Oliveira's avatar
Luís Oliveira committed
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938

@c ===================================================================
@node Accumulations
@subsection Accumulations

All the predefined accumulation clauses add values to a sequence.  If
the sequence is a list, they all have the property that the partial
list is kept in the correct order and available for inspection at any
point in the loop.

@clauseu{collect}
@deffn Clause collect @v{exptr} @k{&optional}
                      @k{into} @v{var} @k{at} @v{place} @k{result-type} @v{type}

Produces a sequence of the values of @var{exptr} on each
939
iteration.  @var{place} indicates where the next value of @var{exptr}
Luís Oliveira's avatar
Luís Oliveira committed
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
is added to the list and may be one of the symbols @code{start},
@code{beginning} (a synonym for @code{start}) or @code{end}.  The
symbol may be quoted, but need not be.  The default is @code{end}.
For example,

@lisp
(iter (for i from 1 to 5)
      (collect i))
@end lisp

produces @code{(1 2 3 4 5)}, whereas

@lisp
(iter (for i from 1 to 5)
      (collect i at beginning))
@end lisp

produces @code{(5 4 3 2 1)} (and is likely to be faster in most Common
Lisp implementations).

If @var{type} is provided, it should be a subtype of @code{sequence}.
The default is @code{list}.  Specifying a type other than @code{list}
will result in @code{collect} returning a sequence of that type.
@emph{However}, the type of the sequence being constructed when inside
the loop body is undefined when a non-@code{list} type is specified.
(As with @var{place}, quoting @var{type} is optional.)
@end deffn

@clauseu{adjoining}
@deffn Clause adjoining @v{exptr} @k{&optional} @k{into} @v{var} @
                        @k{test} @v{test} @k{at} @v{place} @
                        @k{result-type} @v{type}

Like @code{collect}, but only adds the value of @var{exptr} if it is
not already present.  @var{test}, which defaults to @code{#'eql}, is
the test to be used with @code{member}.
@end deffn

@clauseu{appending}
@clauseu{nconcing}
@clauseu{unioning}
@clauseu{nunioning}
@deffn Clause appending @v{expr} @k{&optional} @k{into} @v{var} @k{at} @v{place}
@deffnx Clause nconcing @v{expr} @k{&optional} @k{into} @v{var} @k{at} @v{place}
@deffnx Clause unioning @v{expr} @k{&optional} @k{into} @v{var} @
                        @k{test} @v{test} @k{at} @v{place}
@deffnx Clause nunioning @v{expr} @k{&optional} @k{into} @v{var} @
                         @k{test} @v{test} @k{at} @v{place}

These are like @code{collect}, but behave like the Common Lisp
functions @code{append}, @code{nconc}, @code{union} or @code{nunion}.
As in Common Lisp, they work only on lists.  Also as in Common Lisp,
@code{unioning} and @code{nunioning} assume that the value of
@var{expr} contains no duplicates.
@end deffn

@clauseu{accumulate}
@deffn Clause accumulate @v{expr} @k{by} @v{func} @k{&optional} @
                         @k{initial-value} @v{init-val} @k{into} @v{var}

1000
This is a general-purpose accumulation clause.  @var{func} should be a
Luís Oliveira's avatar
Luís Oliveira committed
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
function of two arguments, the value of @var{expr} and the value
accumulated so far in the iteration, and it should return the updated
value.  If no initial value is supplied, @code{nil} is used.

@c If a @var{var} is not specified, you can get @iter{} to declare the
@c type of the internal variable by putting a @code{the} expression
@c around @var{func}.  see section \ref{types}.

The differences between @code{accumulate} and @code{reducing} are
slight.  One difference is that the functions take their arguments in
a different order.  Another is that in the absence of @var{init-val},
@code{accumulate} will use @code{nil}, whereas @code{reducing} will
generate different code that avoids any dependence on the initial
value.  The reason for having both clauses is that one usually thinks
of reductions (like @code{sum}) and accumulations (like
@code{collect}) as different beasts.
@end deffn

@c ===================================================================
@node Finders
@subsection Finders

A @emph{finder} is a clause whose value is an expression that meets
some condition.

@claused{finding, such-that}
@deffn Clause finding @var{expr} @cl{such-that} @v{test} @k{&optionally} @
                      @k{into} @v{var} @k{on-failure} @v{failure-value}

If @var{test} (which is an expression) ever evaluates to
non-@code{nil}, the loop is terminated, the epilogue code is run and
the value of @var{expr} is returned.  Otherwise, @code{nil} (or
@var{failure-value}, if provided) is returned.  If @var{var} is
provided, it will have either the non-@code{nil} value of @var{expr}
or @var{failure-value} when the epilogue code is run.

As a special case, if the @var{test} expression is a sharp-quoted
function, then it is applied to @var{expr} instead of being simply
1039
evaluated.  E.g.@: @code{(finding x such-that #'evenp)} is equivalent to
Luís Oliveira's avatar
Luís Oliveira committed
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
@code{(finding x such-that (evenp x))}.

@c \cpar although @var{test} need have nothing to do with ~@c expr~ as in
@c |(finding j such-that (> i 3))|, it usually 
@c will: |(finding (length el) such-that (oddp (length el)))|.  to
@c avoid performing the |length| computation twice, you could write
@c |(finding (length el) such-that \#'oddp)| or |(finding (length
@c el) such-that 'oddp)|; for these cases, @iter{} generates code that
@c executes @var{expr} only once.  the code for |\#'oddp|
@c is slightly different from that for {\lisp 'oddp}; see the discussion
@c under {\lisp for\dots in} and {\lisp for\dots on}.

1052
@code{On-failure} is a misnomer.  Because it is always evaluated, it
Luís Oliveira's avatar
Luís Oliveira committed
1053
behaves more like the default third argument to the @code{gethash}
1054
1055
function.  As a result, @code{on-failure (error "Not found")} makes no
sense.  Instead, the clauses @code{leave} or @code{thereis} can be used
Luís Oliveira's avatar
Luís Oliveira committed
1056
1057
1058
1059
1060
1061
1062
1063
1064
in conjunction with @code{finally} as follows:

@lisp
(iter (for x in '(1 2 3))
      (if (evenp x) (leave x))
      (finally (error "not found")))
@end lisp

This clause may appear multiple times when all defaults are
1065
identical.  It can also be used together with either
Luís Oliveira's avatar
Luís Oliveira committed
1066
@code{always}/@code{never} or @code{thereis} if their defaults
1067
match.  More specifically, @code{on-failure nil} is compatible with
Luís Oliveira's avatar
Luís Oliveira committed
1068
1069
1070
1071
1072
1073
@code{thereis}, while @code{on-failure t} is compatible with
@code{always} and @code{never} clauses.

@lisp
(iter (for i in '(7 -4 2 -3))
      (if (plusp i)
1074
1075
        (finding i such-that (evenp i))
        (finding (- i) such-that (oddp i))))
Luís Oliveira's avatar
Luís Oliveira committed
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
@end lisp
@end deffn

@claused{finding, maximizing}
@claused{finding, minimizing}
@deffn Clause finding @v{expr} @cl{maximizing} @v{m-expr} @
                      @k{&optional} @k{into} @v{var}
@deffnx Clause finding @v{expr} @cl{minimizing} @v{m-expr} @
                       @k{&optional} @k{into} @v{var}

Computes the extremum (maximum or minimum) value of @var{m-expr} over
all iterations, and returns the value of @var{expr} corresponding to
the extremum.  @var{expr} is evaluated inside the loop at the time the
new extremum is established.  If @var{m-expr} is never evaluated (due
to, for example, being embedded in a conditional clause), then the
returned value depends on the type, if any, of @var{expr} (or
@var{var}, if one is supplied).  If there is no type, the returned
1093
1094
value will be @code{nil}; if the type is numeric, the returned value
will be zero.
Luís Oliveira's avatar
Luís Oliveira committed
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125

For these two clauses, @var{var} may be a list of two symbols; in that
case, the first is used to record @var{expr} and the second,
@var{m-expr}.

As with @code{finding@dots{} such-that}, if @var{m-expr} is a
sharp-quoted function, then it is called on @var{expr} instead of
being evaluated.
@end deffn

@c ===================================================================
@node Aggregated Boolean Tests
@subsection Aggregated Boolean Tests

@clauseu{always}
@deffn Clause always @v{expr}

If @var{expr} ever evaluates to @code{nil}, then @code{nil} is
immediately returned; the epilogue code is not executed.  If
@var{expr} never evaluates to @code{nil}, the epilogue code is
executed and the last value of @var{expr} (or @code{t} if @var{expr}
was never evaluated) is returned (whereas @code{loop} would constantly
return @code{t}).

@c mention last evaluated clause when multiple always clauses?
@end deffn

@clauseu{never}
@deffn Clause never @v{expr}

Like @code{(always (not @var{expr}))}, except it does not influence
1126
the last value returned by a possible other @code{always} clause.  That
Luís Oliveira's avatar
Luís Oliveira committed
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
is,

@lisp
(iter (repeat 2)
      (always 2)
      (never nil)) @result{} 2 ; not t
@end lisp
@end deffn

@clauseu{thereis}
@deffn Clause thereis @v{expr}

If @var{expr} is ever non-@code{nil}, its value is immediately
returned without running epilogue code.  Otherwise, the epilogue code
is performed and @code{nil} is returned.

This clause cannot be used together with @code{always} or
@code{never}, because their defaults are opposed (similarly,
@code{(loop always 3 thereis nil)} refuses to compile in some
implementations of @code{loop}).
@end deffn

@c ===================================================================
@node Control Flow
@section Control Flow

Several clauses can be used to alter the usual flow of control in a
loop.

1156
1157
@quotation Note
The clauses of this and subsequent sections don't adhere to
Luís Oliveira's avatar
Luís Oliveira committed
1158
1159
1160
1161
@iter{}'s usual syntax, but instead use standard Common Lisp syntax.
Hence the format for describing syntax subsequently is like the
standard format used in the Common Lisp manual, not like the
descriptions of clauses above.
1162
@end quotation
Luís Oliveira's avatar
Luís Oliveira committed
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182

@clauseu{finish}
@deffn Clause finish

Stops the loop and runs the epilogue code.
@end deffn

@c for example:
@c 
@c @lisp
@c (iter (with answer = nil)
@c          (initially (make-a-mess))
@c          (for i from 1 to 10)
@c          (when (correct? i)
@c            (setq answer i)
@c            (finish))
@c          (finally (cleanup)))
@c @end lisp
@c 
@c this code will execute |cleanup| whether or not the test |(correct?
1183
@c i)| ever succeeds.
Luís Oliveira's avatar
Luís Oliveira committed
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
@c the (more elegant) formulation,
@c @lisp
@c (iter (initially (make-a-mess))
@c          (for i from 1 to 10)
@c          (finding i such-that (correct? i))
@c          (finally (cleanup)))
@c @end lisp
@c would not execute |cleanup| if |(correct? i)| succeeded; it
@c would do an immediate return.

@clauseu{leave}
@deffn Clause leave @k{&optional} @v{value}

Immediately returns @var{value} (default @code{nil}) from the current
@iter{} form, skipping the epilogue code.  Equivalent to using
@code{return-from}.
@end deffn

@clauseu{next-iteration}
@deffn Clause next-iteration

Skips the remainder of the loop body and begins the next iteration of
the loop.
@end deffn

@clauseu{while}
@deffn Clause while @v{expr}

If @var{expr} ever evaluates to @code{nil}, the loop is terminated and
the epilogue code executed.  Equivalent to @code{(if (not @var{expr})
(finish))}.
@end deffn

@clauseu{until}
1218
@deffn Clause until @v{expr}
Luís Oliveira's avatar
Luís Oliveira committed
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241

Equivalent to @code{(if @var{expr} (finish))}.
@end deffn

@clauseu{if-first-time}
@deffn Clause if-first-time @v{then} @k{&optional} @v{else}

If this clause is being executed for the first time in this invocation
of the @iter{} form, then the @var{then} code is evaluated; otherwise
the @var{else} code is evaluated.

@code{(for @var{var} first @var{expr1} then @var{expr2})} is almost
equivalent to

@lisp
(if-first-time (dsetq @var{var} @var{expr1})
               (dsetq @var{var} @var{expr2}))
@end lisp

The only difference is that the @code{for} version makes @var{var}
available for use with @code{for@dots{} previous}.
@end deffn

1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
@c ===================================================================
@node Predicates
@section Predicates

@quotation Compatibility Note
The clauses in this section were added in the twenty-first century and
not part of Jonathan Amsterdam's original design.
@end quotation

@clauseu{first-iteration-p}
@deffn Clause first-iteration-p

Returns @code{t} in the first cycle of the loop, otherwise @code{nil}.
@end deffn

@clauseu{first-time-p}
@deffn Clause first-time-p

Returns @code{t} the first time the expression is evaluated, and then
@code{nil} forever.  This clause comes handy when printing (optional)
elements separated by a comma:

@lisp
(iter (for el in '(nil 1 2 nil 3))
      (when el
        (unless (first-time-p)
          (princ ", "))
        (princ el)))
@print{} 1, 2, 3
@end lisp
@end deffn

Luís Oliveira's avatar
Luís Oliveira committed
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
@c ===================================================================
@node Code Placement
@section Code Placement

When fine control is desired over where code appears in a loop
generated by @iter{}, the following special clauses may be useful.
They are all subject to code-motion problems (see @ref{Problems with
Code Movement}).

@clauseu{initially}
@deffn Clause initially @k{&rest} @var{forms}

The lisp @var{forms} are placed in the prologue section of the loop,
where they are executed once, before the loop body is entered.
@end deffn

@clauseu{after-each}
@deffn Clause after-each @k{&rest} @v{forms}

The @var{forms} are placed at the end of the loop body, where they
are executed after each iteration.  Unlike the other clauses in this
section, @var{forms} may contain @iter{} clauses.
@end deffn

@clauseu{else}
@deffn Clause else @k{&rest} @v{forms}

The lisp @var{forms} are placed in the epilogue section of the loop,
where they are executed if this @code{else} clause is never met during
execution of the loop and the loop terminates normally.
@end deffn

@clauseu{finally}
@deffn Clause finally @k{&rest} @v{forms}

The lisp @var{forms} are placed in the epilogue section of the loop,
where they are executed after the loop has terminated normally.
@end deffn

@clauseu{finally-protected}
@deffn finally-protected @k{&rest} @v{forms}

The lisp @var{forms} are placed in the second form of an
@code{unwind-protect} outside the loop.  They are always executed
after the loop has terminated, regardless of how the termination
occurred.
@end deffn

@c ===================================================================
@node Other Features
@chapter Other Features

@section Multiple Accumulations

It is permitted to have more than one clause accumulate into the same
variable, as in the following:

@lisp
(iter (for i from 1 to 10)
      (collect i into nums)
      (collect (sqrt i) into nums)
      (finally (return nums)))
@end lisp

Clauses can only accumulate into the same variable if they are
compatible.  @code{collect}, @code{adjoining}, @code{appending},
@code{nconcing}, @code{unioning} and @code{nunioning} are compatible
with each other; @code{sum}, @code{multiply} and @code{counting} are
compatible; @code{always} and @code{never} are compatible;
@code{finding}@dots{} @code{such-that} is compatible with either
@code{thereis} or @code{always} and @code{never} when their defaults
match; and @code{maximize} and @code{minimize} clauses are compatible
only with other @code{maximize} and @code{minimize} clauses,
respectively.

@c note that the same variable ~cannot~ be both an accumulation
@c variable and an ordinary variable; there can be only one variable
@c with a given name within an @iter{} form.

@menu
* Named Blocks::                
* Destructuring::               
* On-line Help::                
* Parallel Binding and Stepping::  
@end menu

@c ===================================================================
@node Named Blocks
@section Named Blocks

Like Common Lisp @code{block}s, @iter{} forms can be given names.  The
name should be a single symbol, and it must be the first form in the
@iter{}.  The generated code behaves exactly like a named block; in
particular, @code{(return-from @var{name})} can be used to exit it:

@lisp
(iter fred
      (for i from 1 to 10)
      (iter barney
            (for j from i to 10)
            (if (> (* i j) 17)
                (return-from fred j))))
@end lisp

An @iter{} form that is not given a name is implicitly named
@code{nil}.

Sometimes one would like to write an expression in an inner @iter{}
form, but have it processed by an outer @iter{} form.  This is
possible with the @code{in} clause.

@clauseu{in}
@deffn Clause in @v{name} @k{&rest} @v{forms}

Evaluates @var{forms} as if they were part of the @iter{} form named
@var{name}.  In other words, @iter{} clauses are processed by the
@iter{} form named @var{name}, and not by any @iter{} forms that occur
inside @var{name}.

As an example, consider the problem of collecting a list of the
elements in a two-dimensional array.  The naive solution,
@lisp
(iter (for i below (array-dimension ar 0))
      (iter (for j below (array-dimension ar 1))
            (collect (aref ar i j))))
@end lisp
is wrong because the list created by the inner @iter{} is simply
ignored by the outer one.  But using @code{in} we can write:
@lisp
(iter outer (for i below (array-dimension ar 0))
      (iter (for j below (array-dimension ar 1))
            (in outer (collect (aref ar i j)))))
@end lisp
which has the desired result.
@end deffn

@c ===================================================================
@node Destructuring
@section Destructuring

In many places within @iter{} clauses where a variable is expected, a
list can be written instead.  In these cases, the value to be assigned
is @emph{destructured} according to the pattern described by the list.
As a simple example, the clause
@lisp
(for (key . item) in alist)
@end lisp
will result in @code{key} being set to the @code{car} of each element
in @code{alist}, and @code{item} being set to the @code{cdr}.  The
pattern list may be nested to arbitrary depth, and (as the example
shows) need not be terminated with @code{nil}; the only requirement is
that each leaf be a bindable symbol (or @code{nil}, in which case no
binding is generated for that piece of the structure).

Sometimes, you might like to do the equivalent of a
@code{multiple-value-setq} in a clause.  This ``multiple-value
1430
1431
destructuring'' can be expressed by writing @code{(values @var{pat_1}
@var{pat_2} @dots{})} for a destructuring pattern, as in
Luís Oliveira's avatar
Luís Oliveira committed
1432
1433
1434
1435
1436

@lisp
(for (values (a . b) c d) = (three-valued-function ...))
@end lisp

1437
Note that the @var{pat_i} can themselves be destructuring patterns
Luís Oliveira's avatar
Luís Oliveira committed
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
(though not multiple-value destructuring patterns).  You can't do
multiple-value destructuring in a @code{with} clause; instead wrap the
whole @iter{} form in a @code{multiple-value-bind}.

@quotation Rationale
There are subtle interactions between variable declarations and
evaluation order that make the correct implementation of
multiple-value destructuring in a @code{with} somewhat tricky.
@end quotation

The destructuring feature of @iter{} is available as a separate
mechanism, using the @code{dsetq} macro:

@itindex dsetq
@defmac dsetq @v{template} @v{expr}

Performs destructuring of @var{expr} using @var{template}.  May be
1455
used outside of an @iter{} form.  Yields the primary value of
Luís Oliveira's avatar
Luís Oliveira committed
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
@var{expr}.
@end defmac

@c ===================================================================
@node On-line Help
@section On-line Help

There is a limited facility for on-line help, in the form of the
@code{display-iterate-clauses} function.

@itindex display-iterate-clauses
@defun display-iterate-clauses @k{&optional} @v{clause-spec}

Displays a list of @iter{} clauses.  If @var{clause-spec} is not
provided, all clauses are shown; if it is a symbol, all clauses
beginning with that symbol are shown; and if it is a list of symbols,
all clauses for which @var{clause-spec} is a prefix are shown.
@end defun

@c ===================================================================
@node Parallel Binding and Stepping
@section Parallel Binding and Stepping

The parallel binding and stepping of variables is a feature that
@iter{} does @emph{not} have.  This section attempts to provide a
rationale.

We say that two variables are bound @emph{in parallel} if neither
binding shadows the other.  This is the usual semantics of @code{let}
(as opposed to @code{let*}).  Similarly, we can say that iteration
variables are stepped in parallel if neither variable is updated
before the other, conceptually speaking; in other words, if the code
to update each variable can reference the old values of both
variables.

@code{loop} allows parallel binding of variables and parallel stepping
of driver variables.  My view is that if you are depending on the
serial/parallel distinction, you are doing something obscure.  If you
need to bind variables in parallel using @code{with}, then you must be
using a variable name that shadows a name in the existing lexical
environment.  Don't do that.  The most common use for parallel
stepping is to track the values of variables on the previous
iteration, but in fact this does not require parallel stepping at all;
the following will work:

@lisp
(iter (for current in list)
      (for prev previous current)
      @dots{})
@end lisp

@c ===================================================================
@node Types and Declarations
@chapter Types and Declarations

@section Discussion

Sometimes efficiency dictates that the types of variables be declared.
This type information needs to be communicated to @iter{} so it can
bind variables to appropriate values.  Furthermore, @iter{} must often
generate internal variables invisible to the user; there needs to be a
way for these to be declared.

As an example, consider this code, which will return the number of
odd elements in @code{number-list}:

@lisp
(iter (for el in number-list)
      (count (oddp el)))
@end lisp

In processing this form, @iter{} will create an internal variable, let
us call it @code{list17}, to hold the successive @code{cdr}s of
@code{number-list}, and will bind the variable to @code{number-list}.
It will also generate a default binding for @code{el}; only inside the
body of the loop will @code{el} be set to the @code{car} of
@code{list17}.  Finally, @iter{} will generate a variable, call it
@code{result}, to hold the result of the count, and will bind it to
zero.

When dealing with type declarations, @iter{} observes one simple rule:
@emph{it will never generate a declaration unless requested to do so}.
The reason is that such declarations might mask errors in compiled
code by avoiding error-checks; the resulting problems would be doubly
hard to track down because the declarations would be hidden from the
programmer.  Of course, a compiler might omit error-checks even in the
absence of declarations, though this behavior can usually be avoided,
1543
e.g.@: by saying @code{(declaim (optimize (safety 3)))}.
Luís Oliveira's avatar
Luís Oliveira committed
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790

So, the above @iter{} form will generate code with no declarations.
But say we wish to declare the types of @code{el} and the internal
variables @code{list17} and @code{result}.  How is this done?

Declaring the type of @code{el} is easy, since the programmer knows
the variable's name:

@lisp
(iter (for el in number-list)
      (declare (fixnum el))
      (counting (oddp el)))
@end lisp

@iter{} can read variable type declarations like this one.  Before
processing any clauses, it scans the entire top-level form for type
declarations and records the types, so that variable bindings can be
performed correctly.  In this case, @code{el} will be bound to zero
instead of @code{nil}.  Also, @iter{} collects all the top-level
declarations and puts them at the begining of the generated code, so
it is not necessary to place all declarations at the beginning of an
@iter{} form; instead, they can be written near the variables whose
types they declare.

Since @iter{} is not part of the compiler, it will not know
about declarations that occur outside an @iter{} form; these
declarations must be repeated inside the form.

Here is another way we could have declared the type of @code{el}:

@lisp
(iter (for (the fixnum el) in number-list)
      (counting (oddp el)))
@end lisp

@itindex the
@iter{} extends the Common Lisp @code{the} form to apply to variables
as well as value-producing forms; anywhere a variable is allowed---in
a @code{with} clause, as the iteration variable in a driver clause, as
the @code{into} argument of an accumulation clause, even inside a
destructuring template---you can write @code{(the @var{type}
@var{symbol})} instead.

There is one crucial difference between using a @code{the} form and
actually declaring the variable: explicit declarations are always
placed in the generated code, but type information from a @code{the}
form is not turned into an actual declaration unless you tell @iter{}
to do so using @code{iterate:declare-variables}.  See below.

Declaring the types of internal variables is harder than declaring the
types of explicitly mentioned variables, since their names are
unknown.  You do it by declaring @code{iterate:declare-variables}
somewhere inside the top level of the @iter{} form.  (This will also
generate declarations for variables declared using @code{the}.)
@iter{} does not provide much selectivity here: it's all or none.  And
unfortunately, since @iter{} is not privy to compiler information but
instead reads declarations itself, it will not hear if you
@code{(declaim (iterate:declare-variables))}.  Instead, set the
variable @code{iterate::*always-declare-variables*} to @code{t} at
compile-time, using @code{eval-when}.

To determine the appropriate types for internal variables, @iter{}
uses three sources of information:

@itemize
@item
Often, the particular clause dictates a certain type for a
variable; @iter{} will use this information when available.  In the
current example, the variable @code{list17} will be given the type
@code{list}, since that is the only type that makes sense; and the
variable @code{result} will be given the type @code{fixnum}, on the
assumption that you will not be counting high enough to need bignums.
You can override this assumption only by using and explicitly declaring a
variable: 

@lisp
(iter (declare (iterate:declare-variables))
      (for el in number-list)
      (count (oddp el) into my-result)
      (declare (integer my-result))
      (finally (return my-result)))
@end lisp

Other examples of the type assumptions that @iter{} makes are: type
@code{list} for @code{into} variables of collection clauses; type
@code{list} for expressions that are to be destructured; type
@code{vector} for the variable holding the vector in a
@code{for@dots{} in-vector} clause, and similarly for @code{string}
and the @code{for@dots{} in-string} clause; and the
implementation-dependent type @code{(type-of array-dimension-limit)}
for the index and limit variables generated by sequence iteration
drivers like @code{for@dots{} in-vector} and @code{for@dots{}
in-string} (but not @code{for@dots{} in-sequence}, because it may be
used to iterate over a list).

@item
Sometimes, @iter{} will examine expressions and try to determine their
types in a simple-minded way.  If the expression is self-evaluating
(like a number, for instance), @iter{} knows that the expression's
type is the same as the type of the value it denotes, so it can use
that type.  If the expression is of the form @code{(the @var{type}
@var{expr})}, @iter{} is smart enough to extract @var{type} and use
it.  However, the current version of @iter{} does not examine
declarations of function result types or do any type inference.  It
will not determine, for example, that the type of @code{(+ 3 4)} is
@code{fixnum}, or even @code{number}.

@item
In some cases, the type of an internal variable should match the type
of some other variable.  For instance, @iter{} generates an internal
variable for @code{(f x)} in the clause @code{(for i from 1 to (f
x))}, and in the absence of other information will give it the same
type as @code{i}.  If, however, the expression had been written
@code{(the fixnum (f x))}, then @iter{} would have given the internal
variable the type @code{fixnum} regardless of @code{i}'s type.  The
type incompatibility errors that could arise in this situation are not
checked for.
@end itemize

Note that if you do declare @code{iterate:declare-variables}, then
@iter{} may declare user variables as well as internal ones if they do
not already have declarations, though only for variables that it
binds.  For instance, in this code:

@lisp
(iter (declare (iterate:declare-variables))
      (for i from 1 to 10)
      (collect i into var))
@end lisp

the variable @code{var} will be declared to be of type @code{list}.

@section Summary

@itindex declare-variables
@itindex *always-declare-variables*
@iter{} understands standard Common Lisp variable type declarations
that occur within an @iter{} form and will pass them through to the
generated code.  If the declaration @code{(iterate:declare-variables)}
appears at the top level of an @iter{} form, or if
@code{iterate::*always-declare-variables*} is non-@code{nil}, then
@iter{} will use the type information gleaned from user declarations,
self-evaluating expressions and @code{the} expressions, combined with
reasonable assumptions, to determine variable types and declare them.

@c ===================================================================
@node Problems with Code Movement
@chapter Problems with Code Movement

Some @iter{} clauses, or parts of clauses, result in code being moved
from the location of the clause to other parts of the loop.  Drivers
behave this way, as do code-placement clauses like @code{initially}
and @code{finally}.  When using these clauses, there is a danger of
writing an expression that makes sense in its apparent location but
will be invalid or have a different meaning in another location.  For
example:

@lisp
(iter (for i from 1 to 10)
      (let ((x 3))
        (initially (setq x 4))))
@end lisp

While it may appear that the @code{x} of @code{(initially (setq x 4))}
is the same as the @code{x} of @code{(let ((x 3)) @dots{}}, in fact
they are not: @code{initially} moves its code outside the loop body,
so @code{x} would refer to a global variable.  Here is another example
of the same problem:

@lisp
(iter (for i from 1 to 10)
      (let ((x 3))
        (collect i into x)))
@end lisp

If this code were executed, @code{collect} would create a binding for
its @code{x} at the top level of the @iter{} form that the @code{let}
will shadow.

Happily, @iter{} is smart enough to catch these errors; it walks all
problematical code to ensure that free variables are not bound inside
the loop body, and checks all variables it binds for the same problem.

However, some errors cannot be caught:

@lisp
(iter (with x = 3)
      (for el in list)
      (setq x 1)
      (reducing el by #'+ initial-value x))
@end lisp

@code{reducing} moves its @code{initial-value} argument to the
initialization part of the loop in order to produce more efficient
code.  Since @iter{} does not perform data-flow analysis, it cannot
determine that @code{x} is changed inside the loop; all it can
establish is that @code{x} is not bound internally.  Hence this code
will not signal an error and will use @math{3} as the initial value of
the reduction.

The following list summarizes all cases that are subject to these code
motion and variable-shadowing problems.

@itemize
@item
Any variable for which @iter{} creates a binding, including those used
in @code{with} and the @code{into} keyword of many clauses.

@item
The special clauses which place code: @code{initially},
@code{after-each}, @code{else}, @code{finally} and
@code{finally-protected}.

@item
The variables of a @code{next} or @code{do-next} form.

@item
The @code{initially} arguments of @code{for@dots{} initially@dots{}
then} and @code{for@dots{} previous}.

@item
The @code{then} argument of @code{for@dots{} initially@dots{} then}.

@item
The @code{initial-value} arguments of @code{reducing} and
@code{accumulate}.

@item
The @code{on-failure} argument of @code{finding@dots{} such-that}.
@end itemize

@c ===================================================================
@node Differences Between Iterate and Loop
@chapter Differences Between @code{Iterate} and @code{Loop}

@code{loop} contains a great deal of complexity which @iter{} tries to
avoid.  Hence many esoteric features of @code{loop} don't exist in
@iter{}.  Other features have been carried over, but in a cleaned-up
form.  And of course, many new features have been added; they are not
mentioned in this list.

@itemize
@item
@iter{}'s syntax is more Lisp-like than @code{loop}'s, having a higher
density of parens.

@item
1791
1792
The current implementation of @iter{}, unlike the standardised version
of @code{loop}, is extensible (see @ref{Rolling Your Own}).
Luís Oliveira's avatar
Luís Oliveira committed
1793
1794
1795

@item
@code{loop} puts the updates of all driver variables at the top of the
1796
1797
loop; @iter{} leaves them where the driver clauses appear.  In
particular, @iter{} allows to place drivers after @code{while} clauses.
Luís Oliveira's avatar
Luís Oliveira committed
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910

@item
While for the most part @iter{} clauses that resemble @code{loop}
clauses behave similarly, there are some differences.  For instance,
there is no @code{for@dots{} =@dots{} then} in @iter{}; instead use
@code{for@dots{} initially@dots{} then}.

@item
@code{loop} binds the variable @code{it} at certain times to allow
pseudo-English expressions like @code{when @var{expr} return it}.  In
@iter{}, you must bind @var{expr} to a variable yourself.  Note that
@code{when @var{expr} return it} is like @code{thereis @var{expr}}
except that the latter is an accumulation clause and therefore
competes with other accumulations (remember ``Multiple Accumulations''
in @ref{Other Features}).

@c repeat different behaviour of |always| clause here?

@item
@code{loop} has a special @code{return} clause, illustrated in the
previous item.  @iter{} doesn't need one, since an ordinary Lisp
@code{return} has the same effect.

@item
@code{loop} allows for parallel binding and stepping of iteration
variables.  @iter{} does not.  (See @ref{Parallel Binding and
Stepping}.)

@item
@code{loop} and @iter{} handle variable type declarations very
differently.  @code{loop} provides a special syntax for declaring
variable types, and does not examine declarations.  Moreover, the
standard implementation of @code{loop} will generate declarations when
none are requested.  @iter{} parses standard Common Lisp type
declarations, and will never declare a variable itself unless
declarations are specifically requested.
@end itemize

@c ===================================================================
@node Rolling Your Own
@chapter Rolling Your Own

@section Introduction

@iter{} is extensible---you can write new clauses that embody new
iteration patterns.  You might want to write a new driver clause for a
data structure of your own, or you might want to write a clause that
collects or manipulates elements in a way not provided by @iter{}.

This section describes how to write clauses for @iter{}.  Writing a
clause is like writing a macro.  In fact, writing a clause @emph{is}
writing a macro: since @iter{} code-walks its body and macroexpands,
you can add new abstractions to @iter{} with good old @code{defmacro}.

Actually, there are two extensions you can make to @iter{} that are
even easier than writing a macro.  They are adding a synonym for an
existing clause and defining a driver clause for an indexable
sequence.  These can be done with @code{defsynonym} and
@code{defclause-sequence}, respectively.  See @ref{Extensibility
Aids}.

The rest of this section explains how to write macros that expand into
@iter{} clauses.  Here's how you could add a simplified version of
@iter{}'s @code{multiply} clause, if @iter{} didn't already have one:

@lisp
(defmacro multiply (expr)
  `(reducing ,expr by #'* initial-value 1))
@end lisp

If you found yourself summing the square of an expression often, you
might want to write a macro for that.  A first cut might be

@lisp
(defmacro sum-of-squares (expr)
  `(sum (* ,expr ,expr)))
@end lisp

but if you are an experienced macro writer, you will realize that this
code will evaluate @var{expr} twice, which is probably a bad idea.  A
better version would use a temporary:

@lisp
(defmacro sum-of-squares (expr)
  (let ((temp (gensym)))
    `(let ((,temp ,expr))
       (sum (* ,temp ,temp)))))
@end lisp

Although this may seem complex, it is just the sort of thing you'd
have to go through to write any macro, which illustrates the point of
this section: if you can write macros, you can extend @iter{}.

Our macros don't use @iter{}'s keyword-argument syntax.  We could just
use keywords with @code{defmacro}, but we would still not be using
@iter{}'s clause indexing mechanism.  Unlike Lisp, which uses just the
first symbol of a form to determine what function to call, @iter{}
individuates clauses by the list of required keywords.  For instance,
@code{for@dots{} in} and @code{for@dots{} in-vector} are different
clauses implemented by distinct Lisp functions.

To buy into this indexing scheme, as well as the keyword-argument
syntax, use @code{defmacro-clause}:

@itindex defmacro-clause
@defmac defmacro-clause @v{arglist} @k{&body} @v{body}

Defines a new @iter{} clause.  @var{arglist} is a list of symbols
which are alternating keywords and arguments.  @code{&optional} may be
used, and the list may be terminated by @code{&sequence}.  @var{body}
is an ordinary macro body, as with @code{defmacro}.  If the first form
of @var{body} is a string, it is considered a documentation string and
will be shown by
1911
1912
@code{display-iterate-clauses}.  @code{defmacro-clause} will signal an
error if defining the clause would result in an ambiguity.  E.g.@: you
Luís Oliveira's avatar
Luís Oliveira committed
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
cannot define the clause @code{for@dots{} from} because there would be
no way to distinguish it from a use of the @code{for} clause with
optional keyword @code{from}.
@end defmac

Here is @code{multiply} using @code{defmacro-clause}.  The keywords
are capitalized for readability.

@lisp
(defmacro-clause (MULTIPLY expr &optional INTO var)
  `(reducing ,expr by #'* into ,var initial-value 1))
@end lisp

You don't have to worry about the case when @code{var} is not
supplied; for any clause with an @code{into} keyword, saying
@code{into nil} is equivalent to omitting the @code{into} entirely.

As another, more extended example, consider the fairly common
iteration pattern that involves finding the sequence element that
maximizes (or minimizes) some function.  @iter{} provides this as
@code{finding@dots{} maximizing}, but it's instructive to see how to
write it.  Here, in pseudocode, is how you might write such a loop for
maximizing a function F:

@example
@r{set variable MAX-VAL to NIL;}
@r{set variable WINNER to NIL;}
@r{for each element EL in the sequence}
    @r{if MAX-VAL is NIL or F(EL) > MAX-VAL then}
        @r{set MAX-VAL to F(EL);}
        @r{set WINNER to EL;}
    @r{end if;}
@r{end for;}
@r{return WINNER.}
@end example

Here is the macro:

@lisp
(defmacro-clause (FINDING expr MAXIMIZING func &optional INTO var)
  (let ((max-val (gensym))
        (temp1 (gensym))
        (temp2 (gensym))
        (winner (or var iterate::*result-var*)))
    `(progn 
       (with ,max-val = nil)
       (with ,winner = nil)
       (cond 
        ((null ,max-val)
         (setq ,winner ,expr)
         (setq ,max-val (funcall ,func ,winner))
        (t
         (let* ((,temp1 ,expr)
                (,temp2 (funcall ,func ,temp1)))
           (when (> ,temp2 ,max-val)
             (setq ,max-val ,temp2)
             (setq ,winner ,temp1))))))
       (finally (leave ,winner)))))
@end lisp

Note that if no @code{into} variable is supplied, we use
@code{iterate::*result-var*}, which contains the internal variable
into which all clauses place their results.  If this variable is bound
by some clause, then @iter{} will return its value automatically;
otherwise, @code{nil} will be returned.

@menu
* Writing Drivers::             
* Extensibility Aids::          
* Subtleties::                  
@end menu

@c ===================================================================
@node Writing Drivers
@section Writing Drivers

In principle, drivers can be implemented just as easily as other
@iter{} clauses.  In practice, they are a little harder to get right.
As an example, consider writing a driver that iterates over all the
elements of a vector, ignoring its fill-pointer.  @code{for@dots{}
in-vector} won't work for this, because it observes the fill-pointer.
It's necessary to use @code{array-dimension} instead of @code{length}
to obtain the size of the vector.  Here is one approach:

@lisp
(defmacro-clause (FOR var IN-WHOLE-VECTOR v)
  "All the elements of a vector (disregards fill-pointer)"
  (let ((vect (gensym))
        (index (gensym)))
    `(progn
       (with ,vect = ,v)
       (for ,index from 0 below (array-dimension ,vect 0))
       (for ,var = (aref ,vect ,index)))))
@end lisp

Note that we immediately put @code{v} in a variable, in case it is an
expression.  Again, this is just good Lisp macrology.  It also has a
subtle effect on the semantics of the driver: @code{v} is evaluated
only once, at the beginning of the loop, so changes to @code{v} in the
loop have no effect on the driver.  Similarly, the bounds for
2013
numerical iteration e.g.@: the above @code{array-dimension} are also
Luís Oliveira's avatar
Luís Oliveira committed
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
evaluated once only.  This is how all of @iter{}'s drivers work.

There is an important point concerning the @code{progn} in this code.
We need the @code{progn}, of course, because we are returning several
forms, one of which is a driver.  But @iter{} drivers must occur at
top-level.  Is this code in error?  No, because @emph{top-level} is
defined in @iter{} to include forms inside a @code{progn}.  This is
just the definition of top-level that Common Lisp uses, and for the
same reason: to allow macros to return multiple forms at top-level.

While our @code{for@dots{} in-whole-vector} clause will work, it is
not ideal.  In particular, it does not support generating.  Do do so,
we need to use @code{for@dots{} next} or @code{for@dots{} do-next}.
The job is simplified by the @code{defmacro-driver} macro.

@itindex defmacro-driver
@defmac defmacro-driver @v{arglist} @k{&body} @v{body}

Defines a driver clause in both the @code{for} and @code{generate}
forms, and provides a parameter @code{generate} which @var{body} can
examine to determine how it was invoked.  @var{arglist} is as in
@code{defmacro-clause}, and should begin with the symbol @code{for}.
@end defmac

With @code{defmacro-driver}, our driver looks like this:

@lisp
(defmacro-driver (FOR var IN-WHOLE-VECTOR v)
  "All the elements of a vector (disregards fill-pointer)"
   (let ((vect (gensym))
         (end (gensym))
         (index (gensym))
         (kwd (if generate 'generate 'for)))
     `(progn
        (with ,vect = ,v)
        (with ,end = (array-dimension ,vect 0))
        (with ,index = -1)
        (,kwd ,var next (progn (incf ,index)
                               (if (>= ,index ,end) (terminate))
                               (aref ,vect ,index))))))
@end lisp

We are still missing one thing: the @code{&sequence} keywords.
We can get them easily enough, by writing

@lisp
(defmacro-driver (FOR var IN-WHOLE-VECTOR v &sequence) 
  @dots{})
@end lisp

We can now refer to parameters @code{from}, @code{to}, @code{by},
2065
etc.@: which contain either the values for the corresponding keyword, or
Luís Oliveira's avatar
Luís Oliveira committed
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
@code{nil} if the keyword was not supplied.  Implementing the right
code for these keywords is cumbersome but not difficult; it is left as
an exercise.  But before you begin, see @code{defclause-sequence}
below for an easier way.

@c ===================================================================
@node Extensibility Aids
@section Extensibility Aids

This section documents assorted features that may be of use in
extending @iter{}.

@itindex *result-var*
@defvr {Unexported Variable} *result-var*

Holds the variable that is used to return a value as a result of the
@iter{} form.  You may examine this and use it in a @code{with}
clause, but you should not change it.
@end defvr

@itindex defsynonym
@defmac defsynonym @v{syn} @v{word}

Makes @var{syn} a synonym for the existing @iter{} keyword @var{word}.
Only the first word in each clause can have synonyms.
@end defmac

@itindex defclause-sequence
@defmac defclause-sequence @v{element-name} @v{index-name} @k{&key} @
                           @v{access-fn} @v{size-fn} @v{sequence-type} @
                           @v{element-type} @v{element-doc-string} @
                           @v{index-doc-string}
  
Provides a simple way to define sequence clauses.  Generates two
clauses, one for iterating over the sequence's elements, the other for
iterating over its indices.  The first symbol of both clauses will
have print-name @code{for}.  @var{element-name} and @var{index-name}
should be symbols.  @var{element-name} is the second keyword of the
element iterator (typically of the form
@code{in-@var{sequence-type}}), and @var{index-name} is the second
keyword of the index-iterator (typically of the form
@code{index-of-@var{sequence-type}}).  Either name may be @code{nil},
in which case the corresponding clause is not defined.  If both
symbols are supplied, they should be in the same package.  The
@code{for} that begins the clauses will be in this package.

@var{access-fn} is the function to be used to access elements of the
sequence in the element iterator.  The function should take two
arguments, a sequence and an index, and return the appropriate
element.  @var{size-fn} should denote a function of one argument, a
sequence, that returns its size.  Both @var{access-fn} and
@var{size-fn} are required for the element iterator, but only
@var{size-fn} is needed for the index iterator.

The @var{sequence-type} and @var{element-type} keywords are used to
suggest types for the variables used to hold the sequence and the
sequence elements, respectively.  The usual rules about @iter{}'s
treatment of variable type declarations apply (see @ref{Types and
Declarations}).

@var{element-doc-string} and @var{index-doc-string} are the
documentation strings, for use with @code{display-iterate-clauses}.

The generated element-iterator performs destructuring on the element
variable.
2131
@end defmac
Luís Oliveira's avatar
Luís Oliveira committed
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167

As an example, the above @code{for@dots{} in-whole-vector} example
could have been written:

@lisp
(defclause-sequence IN-WHOLE-VECTOR INDEX-OF-WHOLE-VECTOR
  :access-fn 'aref
  :size-fn (lambda (v) (array-dimension v 0))
  :sequence-type 'vector
  :element-type t
  :element-doc-string "Elements of a vector, disregarding fill-pointer"
  :index-doc-string  "Indices of vector, disregarding fill-pointer")
@end lisp

@c ===================================================================
@node Subtleties
@section Subtleties

There are some subtleties to be aware of when writing @iter{} clauses.
First, the code returned by your macros may be @code{nconc}'ed into a
list, so you should always returned freshly consed lists, rather than
constants.  Second, @iter{} matches clauses by using @code{eq} on the
first symbol and @code{string=} on the subsequent ones, so the package
of the first symbol of a clause is relevant.  All of the clauses in
this manual have their first word in the @iter{} package.  You can use
the package system in the usual way to shadow @iter{} clauses without
replacing them.

@c say more here, about the badness that only the first word of a
@c clause is packagey.

@c ===================================================================
@node Non-portable Extensions to Iterate (Contribs)
@chapter Non-portable Extensions to Iterate (Contribs)

Currently, there is only one non-portable extension to iterate in the
2168
2169
2170
distribution: @code{iterate-pg}.  If you have made an extension that
depends on non-portable features, feel free to send them to
the @iter{} project team for inclusion in the iterate distribution.
Luís Oliveira's avatar
Luís Oliveira committed
2171

2172
@section An SQL Query Driver for Iterate
Luís Oliveira's avatar
Luís Oliveira committed
2173
2174

The pg package by Eric Marsden (see @url{http://cliki.net/pg})
2175
2176
2177
provides an interface to the PostgreSQL database.  Using the
@code{in-relation} driver, it is possible to handle the results of SQL
queries with @iter{}.
Luís Oliveira's avatar
Luís Oliveira committed
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187

This usage example should give you an idea of how to use it:

@lisp
(pg:with-pg-connection (c "somedb" "someuser")
  (iter (for (impl version date) in-relation "select * from version"
                                 on-connection *dbconn*)
        (collect version)))
@end lisp

2188
2189
2190
2191
2192
2193
The distribution now contains an @file{iterate.asd} system definition
file for the @iter{} package.
To use the extension via @acronym{ASDF, Another System Definition
Facility}, simply make your system depend on the @code{iterate-pg}
system instead of the @code{iterate} system.  To load it manually,
use:
Luís Oliveira's avatar
Luís Oliveira committed
2194
2195
2196
2197
2198
2199
2200
2201
2202

@lisp
(asdf:oos 'asdf:load-op :iterate-pg)
@end lisp

@c ===================================================================
@node Obtaining Iterate
@chapter Obtaining @code{Iterate}

2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
@iter{} has been successfully ported to most implementations that
purport to conform to ANSI CL.  Since 2006, source and project
information is available from
@url{http://common-lisp.net/project/iterate/}.  The mailing list for
all purposes is @email{iterate-devel@@common-lisp.net}, but you need
to subscribe to it before posting.

The source file was split into two files in 2003: @file{package.lisp}
contains the package definition, @file{iterate.lisp} the main code.
Other files in the distribution contain user contributions, test cases
and documentation.

@iter{} resides in the @code{iterate} package (nickname @code{iter}).
Just say @code{(use-package :iterate)} to make all the necessary
symbols available.  If a symbol is not exported, it appears in this
manual with an ``@code{iterate::}'' prefix.

The regression test suite in @file{iterate-test.lisp}, based on
@acronym{MIT}'s @code{RT} package, contains many examples.
Luís Oliveira's avatar
Luís Oliveira committed
2222

2223
2224
2225
@quotation Note
The rest of this chapter serves history.
@end quotation
Luís Oliveira's avatar
Luís Oliveira committed
2226
2227
2228

@iter{} currently runs on Lisp Machines, and on HP's, Sun3's and
Sparcstations under Lucid.  @iter{} source and binaries are available
2229
2230
at the @acronym{MIT} @acronym{AI} Lab in the subdirectories of
@file{/src/local/lisplib/}.
Luís Oliveira's avatar
Luís Oliveira committed
2231
The source file, @code{iterate.lisp}, is also available for anonymous
2232
FTP in the directory @file{/com/ftp/pub/} on the machine
Luís Oliveira's avatar
Luís Oliveira committed
2233
2234
@code{TRIX.AI.MIT.EDU} (Internet number 128.52.32.6).  If you are
unable to obtain @code{iterate} in one of these ways, send mail to
2235
@email{jba@@ai.mit.edu} and I will send you the source file.
Luís Oliveira's avatar
Luís Oliveira committed
2236

2237
Send bug reports to @email{bug-iterate@@ai.mit.edu}.  The
Luís Oliveira's avatar
Luís Oliveira committed
2238
2239
@code{info-iterate} mailing list will have notices of changes and
problems; to have yourself added, send mail to
2240
@email{info-iterate-request@@ai.mit.edu}.
Luís Oliveira's avatar
Luís Oliveira committed
2241
2242
2243
2244
2245
2246
2247
2248
2249

@c ===================================================================
@node Acknowledgements
@chapter Acknowledgements

Richard Waters provided invaluable criticism which spurred me to
improve @iter{} greatly.  As early users, David Clemens, Oren Etzioni
and Jeff Siskind helped ferret out many bugs.

2250
2251
2252
2253
Thanks to Andreas Fuch, J@"org H@"ohle and Attila Lendvai, who more
than a decade after the original release, ported the code to ANSI CL
and fixed long-standing bugs.

Luís Oliveira's avatar
Luís Oliveira committed
2254
2255
2256
2257
2258
@c ===================================================================
@node Don't Loop Iterate
@appendix Don't Loop, Iterate

@quotation Note
2259
2260
2261
This appendix is a Texinfo conversion performed by Lu@'{@dotless{i}}s
Oliveira of Jonathan Amsterdam's Working Paper 324, MIT AI Lab
entitled ``Don't Loop, Iterate.''
Luís Oliveira's avatar
Luís Oliveira committed
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
@end quotation

@section Introduction

Above all the wonders of Lisp's pantheon stand its metalinguistic
tools; by their grace have Lisp's acolytes been liberated from the
rigid asceticism of lesser faiths.  Thanks to Macro and kin, the
jolly, complacent Lisp hacker can gaze through a fragrant cloud of
setfs and defstructs at the emaciated unfortunates below, scraping out
their meager code in inflexible notation, and sneer superciliously.
It's a good feeling.

But all's not joy in Consville.  For---I beg your pardon, but---there
really is no good way to @emph{iterate} in Lisp.  Now, some are happy
to map their way about, whether for real with @code{mapcar} and
friends, or with the make-believe of Series; others are so satisfied
with @code{do} it's a wonder they're not C hackers.@footnote{Hey,
don't get mad---I'll be much more polite later, when the real paper
starts.}  Still others have gotten by with @code{loop}, but are
getting tired of looking up the syntax in the manual over and over
again.  And in the elegant schemes of some, only tail recursion and
lambdas figure.  But that still leaves a sizeable majority of
folk---well, me, at least---who would simply like to @emph{iterate},
thank you, but in a way that provides nice abstractions, is
extensible, and looks like honest-to-God Lisp.

In what follows I describe a macro package, called @iter{}, that
provides the power and convenient abstractions of @code{loop} but in a
more syntactically palatable way.  @code{iter} also has many features
that @code{loop} lacks, like generators and better support for nested
loops.  @iter{} generates inline code, so it's more efficient than
using the higher-order function approach.  And @iter{} is also
extensible---it's easy to add new clauses to its vocabulary in order
to express new patterns of iteration in a convenient way.

2297
@c \iter\ is fully documented in AI Lab Memo No.@: 1236, \iman.
Luís Oliveira's avatar
Luís Oliveira committed
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432

@section More about @iter{}

A Common Lisp programmer who wonders what's lacking with present-day
iteration features would do well to consider @code{setf}.  Of course,
@code{setf} doesn't iterate, but it has some other nice properties.
It's easy to use, for one thing.  It's extensible---you can define new
@code{setf} methods very easily, so that @code{setf} will work with
new forms.  @code{setf} is also efficient, turning into code that's as
good as anyone could write by hand.  Arguably, @code{setf} provides a
nice abstraction: it allows you to view value-returning forms, like
@code{(car @dots{})} or @code{(get @dots{})} as locations that can be
stored into.  Finally and most obviously, @code{setf} @emph{looks}
like Lisp; it's got a syntax right out of @code{setq}.

@iter{} attempts to provide all of these properties.  Here is a simple
use of @iter{} that returns all the elements of @code{num-list} that
are greater than three:

@lisp
(iterate (for el in num-list)
         (when (> el 3)
           (collect el)))
@end lisp

An @iter{} form consists of the symbol @iter{} followed by some Lisp
forms.  Any legal Lisp form is allowed, as well as certain forms that
@iter{} treats specially, called @emph{clauses}.  @code{for@dots{}in}
and @code{collect} are the two clauses in the above example.  An
@iter{} clause can appear anywhere a Lisp form can appear; @iter{}
walks its body, looking inside every form, processing @iter{} clauses
when it finds them.  It even expands macros, so you can write macros
that contain @iter{} clauses.  Almost all clauses use the syntax of
function keyword-argument lists: alternating keywords and arguments.
@iter{} keywords don't require a preceding colon, but you can use one
if you like.

@iter{} provides many convenient iteration abstractions, most of them
familiar to @code{loop} users.  Iteration-driving clauses (those
beginning with @code{for}) can iterate over numbers, lists, arrays,
hashtables, packages and files.  There are clauses for collecting
values into a list, summing and counting, maximizing, finding maximal
elements, and various other things.  Here are a few examples, for
extra flavor.

To sum a list of numbers:

@lisp
(iterate (for i in list)
         (sum i))
@end lisp

To find the length of the shortest element in a list:

@lisp
(iterate (for el in list)
         (minimize (length el)))
@end lisp

To find the shortest element in a list:

@lisp
(iterate (for el in list)
         (finding el minimizing (length el)))
@end lisp

To return @code{t} only if every other element of a list is odd:

@lisp
(iterate (for els on list by #'cddr)
         (always (oddp (car els))))
@end lisp

To split an association list into two separate lists (this example
uses @iter{}'s ability to do destructuring):

@lisp
(iterate (for (key . item) in alist)
         (collect key into keys)
         (collect item into items)
         (finally (return (values keys items))))
@end lisp

@section Comparisons With Other Iteration Methods

As with any aspect of coding, how to iterate is a matter of taste.  I
do not wish to dictate taste or even to suggest that @iter{} is a
``better'' way to iterate than other methods.  I would, however, like
to examine the options, and explain why I prefer @iter{} to its
competitors.

@subsection @code{do}, @code{dotimes} and @code{dolist}

The @code{do} form has long been a Lisp iteration staple.  It provides
for binding of iteration variables, an end-test, and a body of
arbitrary code.  It can be a bit cumbersome for simple applications,
but the most common special cases---iterating over the integers from
zero and over the members of a list---appear more conveniently as
@code{dotimes} and @code{dolist}.

@code{do}'s major problem is that it provides no abstraction.  For
example, collection is typically handled by binding a variable to
@code{nil}, pushing elements onto the variable, and @code{nreverse}ing
the result before returning it.  Such a common iteration pattern
should be easier to write.  (It is, using @code{mapcar}---but see
below.)

Another problem with @code{do}, for me at least, is that it's hard to
read.  The crucial end-test is buried between the bindings and the
body, marked off only by an extra set of parens (and some
indentation).  It is also unclear, until after a moment of
recollection, whether the end-test has the sense of a ``while'' or an
``until.''

Despite its flaws, @code{do} is superior to the iteration facilities
of every other major programming language except CLU.  Perhaps that is
the reason many Lisp programmers don't mind using it.

@subsection Tail Recursion
@c FIXME: removed citation due to laziness

Tail-recursive implementations of loops, like those found in Scheme
code [SchemeBook], are parsimonious and illuminating.  They have the
advantage of looking like recursion, hence unifying the notation for
two different types of processes.  For example, if only tail-recursion
is used, a loop that operates on list elements from front to back
looks very much like a recursion that operates on them from back to
front.

However, using tail-recursion exclusively can lead to cumbersome code
and a proliferation of functions, especially when one would like to
embed a loop inside a function.  Tail-recursion also provides no
abstraction for iteration; in Scheme, that is typically done with
higher-order functions.

2433
@subsection High-order Functions
Luís Oliveira's avatar
Luís Oliveira committed
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517

Lisp's age-old mapping functions, recently revamped for Common Lisp
[CLM], are another favorite for iteration.  They provide a pleasing
abstraction, and it's easy to write new higher-order functions to
express common iteration patterns.  Common Lisp already comes with
many such useful functions, for removing, searching, and performing
reductions on lists.  Another Common Lisp advantage is that these
functions work on any sequence---vectors as well as lists.

One problem with higher-order functions is that they are inefficient,
requiring multiple calls on their argument function.  While the the
built-ins, like @code{map} and @code{mapcar}, can be open-coded, that
cannot be so easily done for user-written functions.  Also, using
higher-order functions often results in the creation of intermediate
sequences that could be avoided if the iteration were written out
explicitly.

The second problem with higher-order functions is very much a matter
of personal taste.  While higher-order functions are theoretically
elegant, they are often cumbersome to read and write.  The unpleasant
sharp-quote required by Common Lisp is particularly annoying here, and
even in Scheme, I find the presence of a lambda with its argument list
visually distracting.

Another problem is that it's difficult to express iteration of
sequences of integers without creating such sequences explicitly as
lists or arrays.  One could resort to tail-recursion or
@code{dotimes}---but then it becomes very messy to express double
iterations where one driver is over integers.  Multiple iteration is
easy in @iter{}, as illustrated by the following example, which creates
an alist of list elements and their positions:

@lisp
(iterate (for el in list)
         (for i from 0)
         (collect (cons el i)))
@end lisp

@subsection Streams and Generators

For really heavy-duty iteration jobs, nothing less than a
coroutine-like mechanism will do.  Such mechanisms hide the state of
the iteration behind a convenient abstraction.  A @emph{generator} is
a procedure that returns the next element in the iteration each time
it is called.  A @emph{stream} (in the terminology of [SchemeBook]) is
a data structure which represents the iteration, but which computes
the next element only on demand.  Generators and streams support a
similar style of programming.  Here, for example, is how you might
enumerate the leaves of a tree (represented as a Lisp list with atoms
at the leaves) using streams:

@lisp
(defun tree-leaves (tree)
  (if (atom tree)
      (stream-cons tree empty-stream)
      (stream-append (tree-leaves (car tree)) 
                     (tree-leaves (cdr tree)))))
@end lisp

Although @code{tree-leaves} looks like an ordinary recursion, it will
only do enough work to find the first leaf before returning.  The
stream it returns can be accessed with @code{stream-car}, which will
yield the (already computed) first leaf of the tree, or with
@code{stream-cdr}, which will initiate computation of the next leaf.

Such a computation would be cumbersome to write using @iter{}, or any
of the other standard iteration constructs; in fact, it is not even
technically speaking an iteration, if we confine that term to
processes that take constant space and linear time.  Streams, then,
are definitely more powerful than standard iteration machinery.

Unfortunately, streams are very expensive, since they must somehow
save the state of the computation.  Generators are typically cheaper,
but are less powerful and still require at least a function call.  So
these powerful tools should be used only when necessary, and that is
not very often; most of the time, ordinary iteration suffices.

There is one aspect of generators that @iter{} can capture, and that
is the ability to produce elements on demand.  Say we wish to create
an alist that pairs the non-null elements of a list with the positive
integers.  We saw above that it is easy to iterate over a list and a
series of numbers simultaneously, but here we would like to do
something a little different: we want to iterate over the list of
elements, but only draw a number when we need one (namely, when a list
2518
element is non-null).  The solution employs the @iter{} @code{generate}
Luís Oliveira's avatar
Luís Oliveira committed
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
keyword in place of @code{for} and the special clause @code{next}:

@lisp
(iterate (for el in list)
         (generate i from 1)
         (if el
             (collect (cons el (next i)))))
@end lisp

Using @code{next} with any driver variable changes how that driver
works.  Instead of supplying its values one at a time on each
iteration, the driver computes a value only when a @code{next} clause
is executed.  This ability to obtain values on demand greatly
increases @iter{}'s power.  Here, @code{el} is set to the next element
of the list on each iteration, as usual; but @code{i} is set only when
@code{(next i)} is executed.

@subsection Series

Richard C. Waters has developed a very elegant notation called Series
which allows iteration to be expressed as sequence-mapping somewhat in
the style of APL, but which compiles to efficient looping code
[Series].

My reasons for not using Series are, again, matters of taste.  Like
many elegant notations, Series can be somewhat cryptic.  Understanding
what a Series expression does can require some effort until one has
mastered the idiom.  And if you wish to share your code with others,
they will have to learn Series as well.  @iter{} suffers from this
problem to some extent, but since the iteration metaphor it proposes
is much more familiar to most programmers than that of Series, it is
considerably easier to learn and read.

@subsection @code{Prog} and @code{Go}

Oh, don't be silly.

@subsection @code{Loop}

@code{loop} is the iteration construct most similar to @iter{} in
appearance.  @code{loop} is a macro written originally for MacLisp and
in widespread use [Loop].  It has been adopted as part of Common Lisp.
@code{loop} provides high-level iteration with abstractions for
collecting, summing, maximizing and so on.  Recall our first @iter{}
example:

@lisp
(iterate (for el in num-list)
         (when (> el 3)
           (collect el)))
@end lisp

2571
Expressed with @code{loop}, it would read
Luís Oliveira's avatar
Luís Oliveira committed
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638

@lisp
(loop for el in list
      when (> el 3)
        collect el)
@end lisp

The similarity between the two macros should immediately be apparent.
Most of @iter{}'s clauses were borrowed from @code{loop}.  But
compared to @iter{}, @code{loop} has a paucity of parens.  Though
touted as more readable than heavily-parenthesized code, @code{loop}'s
Pascalish syntax creates several problems.  First, many
dyed-in-the-wool Lisp hackers simply find it ugly.  Second, it
requires learning the syntax of a whole new sublanguage.  Third, the
absence of parens makes it hard to parse, both by machine and, more
importantly, by human.  Fourth, one often has to consult the manual to
recall lesser-used aspects of the strange syntax.  Fifth, there is no
good interface with the rest of Lisp, so @code{loop} clauses cannot
appear inside Lisp forms and macros cannot expand to pieces of
@code{loop}.  And Sixth, pretty-printers and indenters that don't know
about @code{loop} will invariably display it wrongly.  This is
particularly a problem with program-editor indenters.  A reasonably
clever indenter, like that of Gnu Emacs, can indent nearly any normal
Lisp form correctly, and can be easily customized for most new forms.
But it can't at present handle @code{loop}.  The syntax of @iter{} was
designed to keep parens to a minimum, but conform close enough to Lisp
so as not to confuse code-display tools.  Gnu Emacs indents @iter{}
reasonably with no modifications.

Indenting is a mere annoyance; @code{loop}'s lack of extensibility is
a more serious problem.  The original @code{loop} was completely
extensible, but the Symbolics version only provides for the definition
of new iteration-driving clauses, and the Common Lisp specification
does not have any extension mechanism.  But extensibility is a boon.
Consider first the problem of adding the elements of a list together,
which can be accomplished with @iter{} by

@lisp
(iterate (for el in list)
         (sum el))
@end lisp

and in @code{loop} with

@lisp
(loop for el in list
      sum el)
@end lisp

But now, say that you wished to compute the sum of the square roots of
the elements.  You could of course write, in either @code{loop} or
@iter{},

@lisp
(iterate (for el in list)
         (sum (sqrt el)))
@end lisp

But perhaps you find yourself writing such loops often enough to make
it worthwhile to create a new abstraction.  There is nothing you can
do in @code{loop}, but in @iter{} you could simply write a macro:

@lisp
(defmacro (sum-of-sqrts expr &optional into-var)
  `(sum (sqrt ,expr) into ,into-var))
@end lisp

2639
@code{sum-of-sqrts} is a perfectly ordinary Lisp macro.  Since @iter{}
Luís Oliveira's avatar
Luís Oliveira committed
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
expands all macros and processes the results, @code{(sum-of-sqrts el)}
will behave exactly as if we'd written @code{(sum (sqrt el))}.

There's also a way to define macros that use @iter{}'s clause syntax.
@c removed citation again

@c Just to beat a dead horse, I'd like to point out that there's no
@c way to define {\lisp for...maximizing} in \looP.\footnote{In fact,
@c it was in part the frustration of knowing that \looP\ could
@c generate code to maximize a value, but could not be easily altered
@c to supply the element associated with that maximum, that prompted
@c me to write \iter.}

@section Implementation

A Common Lisp implementation of @iter{} has existed for well over a
year.  It runs under Lucid for HP 300's, Sun 3's and SPARCstations,
and on Symbolics Lisp machines.
@c See \iman\ for details.

@section Conclusion

Iteration is a matter of taste.  I find @iter{} more palatable than
other iteration constructs: it's more readable, more efficient than
most, provides nice abstractions, and can be extended.

If you're new to Lisp iteration, start with @iter{}---look before you
@code{loop}.  If you're already using @code{loop} and like the power
that it offers, but have had enough of its syntax and inflexibility,
2669
then my advice to you is, don't @code{loop}---@iter{}.
Luís Oliveira's avatar
Luís Oliveira committed
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682

@section Acknowledgments

Thanks to David Clemens for many helpful suggestions and for the
egregious pun near the end.  Conversations with Richard Waters
prompted me to add many improvements to @iter{}.  Alan Bawden, Sundar
Narasimhan, and Jerry Roylance also provided useful comments.  David
Clemens and Oren Etzioni shared with me the joys of beta-testing.

@section Bibliography

@itemize
@item
2683
[SchemeBook] Abelson, Harold and Gerald Jay Sussman.  @emph{Structure
Luís Oliveira's avatar
Luís Oliveira committed
2684
2685
2686
2687
2688
2689
and Interpretation of Computer Programs.} Cambridge, MA: The MIT
Press, 1985.

@item
[Loop] ``The loop Iteration Macro.'' In @emph{Symbolics Common
Lisp---Language Concepts}, manual 2A of the Symbolics documentation,
2690
pp.@: 541--567.
Luís Oliveira's avatar
Luís Oliveira committed
2691
2692

@item
2693
[CLM] Steele, Guy L@.  @emph{Common Lisp: The Language}.  Bedford, MA:
Luís Oliveira's avatar
Luís Oliveira committed
2694
2695
2696
Digital Press, 1984.

@item
2697
[Series] Waters, Richard C@.  @emph{Optimization of Series Expressions:
Luís Oliveira's avatar
Luís Oliveira committed
2698
Part I: User's Manual for the Series Macro Package}.  MIT AI Lab Memo
2699
No.@: 1082.
Luís Oliveira's avatar
Luís Oliveira committed
2700
2701
2702
2703
2704
2705
2706
2707
@end itemize

@c ===================================================================
@node Comprehensive Index
@unnumbered Index
@printindex cp

@bye