Scheme/Racket: do loop order of evaluation

Question

The following procedure is valid in both scheme r6rs and Racket:

;; create a list of all the numbers from 1 to n
(define (make-nums n)
  (do [(x n (- x 1)) (lst (list) (cons x lst))]
    ((= x 0)
     lst)))

I've tested it for both r6rs and Racket and it does work properly, but I only know that for sure for DrRacket.

My question is if it is guaranteed that the step expressions ((- x 1) and (cons x lst) in this case) will be evaluated in order. If it's not guaranteed, then my procedure isn't very stable.

I didn't see anything specifying this in the standards for either language, but I'm asking here because when I tested it was evaulated in order.

Answer 1

They're generally not guaranteed to be evaluated in order, but the result will still be the same. This is because there are no side-effects here -- the loop doesn't change x or lst, it just rebinds them to new values, so the order in which the two step expressions are evaluated is irrelevant.

To see this, start with a cleaner-looking version of your code:

(define (make-nums n)
  (do ([x n (- x 1)] [lst null (cons x lst)])
      [(zero? x) lst]))

translate to a named-let:

(define (make-nums n)
  (let loop ([x n] [lst null])
    (if (zero? x)
      lst
      (loop (- x 1) (cons x lst)))))

and further translate that to a helper function (which is what a named-let really is):

(define (make-nums n)
  (define (loop x lst)
    (if (zero? x)
      lst
      (loop (- x 1) (cons x lst))))
  (loop n null))

It should be clear now that the order of evaluating the two expressions in the recursive loop call doesn't make it do anything different.

Finally, note that in Racket evaluation is guaranteed to be left-to-right. This matters when there are side-effects -- Racket prefers a predictable behavior, whereas others object to it, claiming that this leads people to code that implicitly relies on this. A common small example that shows the difference is:

(list (read-line) (read-line))

which in Racket is guaranteed to return a list of the first line read, and then the second. Other implementations might return the two lines in a different order.