chickadee » foof-loop » DOWN-FROM

Usage:

   (FOR <number> (UP-FROM   <low>  [(TO <high>)] [(BY <step>)]))
   (FOR <number> (DOWN-FROM <high> [(TO <low>)]  [(BY <step>)]))

Iterates for each successive number starting at <low> and incrementing by <step> at every iteration, for UP-FROM; or starting at <high> and decrementing by <step> at every iteration, for DOWN-FROM. <Number> is bound to the current number. If the TO parameter is supplied, iteration terminates when the number exceeds the given bound.

<Low>, <high>, and <step> must all be exact numbers. If a TO parameter is supplied, they must furthermore all be real numbers. They are all evaluated once before the loop begins.

<Number> is a loop variable in UP-FROM. In DOWN-FROM, the treatment of <number> is somewhat subtle in order to do the right thing as much as possible, illustrated in the examples (to which the baffled reader may wish to skip immediately). <Number> is a loop variable, and alternately an entry variable or a body variable, depending on the use of DOWN-FROM. If DOWN-FROM is given a lower bound, then <number> is a body variable, and its value will never descend below <low> as a body variable. The final value of the variable will be not <low>, but the least value it attains before descending below <low>, which may or may not be <low>. If DOWN-FROM is not given a lower bound, then <number> is an entry variable, initialized to <step> less than the value of the loop variable <number>. There are two consequences to this, and two reasons motivating it:

(C1) After updating <number> as a loop variable to some number N, <number> as a body variable in the next iteration will be <step> *less* than N.

(C2) <Number> will be initialized to the value of <high>, but unless the loop terminates with zero iterations, neither the loop variable <number> nor the body variable <number> will ever be observed with the value <high>. In the rare case that the loop terminates with zero iterations, <number> may be observed in the final expression with the value of <high>.

(R1) As repeated in the introduction, lower bounds are inclusive, and upper bounds are exclusive. However, <high> - <low> may not be an integral multiple of <step>, so that <number> may never be <low>. With the semantics chosen, <number> will at least always be in the interval [<low>, <high>], and in fact as a body variable always in the interval [<low>, <high>); only in the rare case of a loop terminated after zero iterations will <number> be observable with the value <high>. (Of course, with explicit updates, it may take on any value.)

(R2) When there is no lower bound, it is often useful (a) to write user-supplied termination conditions in terms of <number>, and (b) to use, in the final expression, the value of <number> that induced termination of the loop. The example of a vector quick-sorting routine below illustrates such a use of <number> in scanning backward from the end of a subvector past elements greater than the pivot.

The more persevering reader, no doubt now exhausted by the above tortuous contortions of explanation, will be relieved to escape into a collection of illustrative examples.

   (define (iota count start step)
     (loop ((for n (up-from 0 (to count)))
            (for result (listing (+ start (* n step)))))
       => result))
   
   ;;; Note that the following is incorrect, if the arguments to IOTA
   ;;; may be inexact numbers:
   
   (define (iota count start step)
     (loop ((for n (up-from start
                            (to (+ start (* count step)))
                            (by step)))
            (for result (listing n)))
       => result))
   
   (define (sieve n)
     (let ((table (make-bit-string (- n 2) #t)))
       (define (prime? k) (bit-string-ref table (- k 2)))
       (define (not-prime! k) (bit-string-clear! table (- k 2)))
       (define (purge-multiples i)
         (loop ((for j (up-from (* i i)
                                (to n)
                                (by i))))
           (not-prime! j)))
       (loop proceed ((for i (up-from 2 (to n)))
                      (with primes '()))
         => (reverse primes)
         (if (prime? i)
             (begin (purge-multiples i)
                    (proceed (=> primes (cons i primes))))
             (proceed)))))
   
   (define (vector-quick-sort! elt< vector start end)
     (loop sort ((start start) (end end))
       (if (< 1 (- end start))
           (let ((pivot (select-pivot vector start end)))
             (loop continue ((i start) (j end))
               (let ((i (loop ((for i (up-from i))
                               (while (elt< (vector-ref vector i) pivot)))
                          => i))
                     (j (loop ((for j (down-from j))
                               (while (elt< pivot (vector-ref vector j))))
                          => j)))
                 (if (< i j)
                     (begin (vector-exchange! vector i j)
                            (continue (+ i 1) j))
                     (begin (sort (=> end i))
                            (sort (=> start (+ j 1)))))))))))