I've ran against a Scheme procedure, that works using a so-called do procedure, but I don't know how it works, or how it is implemented. If anyone can help, I would greatly appreciate it.
The code is the following:
(define (storage-move-right vector i j)
(do ((idx j (- idx 1)))
O(n)
((< idx i))
(vector-set! vector (+ idx 1) (vector-ref vector idx))))
The control constructs while, repeat-until and for are present in most mainstream programming languages, but nevertheless they are not found in the Scheme standard. What is used in Scheme?
These constructs can all be "emulated" by using normal (tail recursive) function calls. However since these constructs are used so often, there are some more convenient syntactical sugar available. The two most used constructs are using named let and the do construct.
It is best to think of the do construct as a glorified "do-until"-loop. The simplest form of do is:
(do ()
[test return-exp]
exp
...)
If return-exp is omitted then the returned value is void, "the invisible value" (so named because it isn't printed in the interaction window).
At the beginning of each loop the test expression is evaluated. If it's non false, then return-exp is evaluated and its return value is the value of the entire do-loop. If the test is false, the body expressions are evaluated sequentially. After the evaluation of the last body expression, a new loop is started.
; Example 1
; WARNING: This is not good style.
; A better solution is found below.
; Pseudo Code
(define i 0) ; i := 0
(do () ; do
[(= i 5)] ; until i=5
(display i) ; display i
(set! i (+ i 1))) ; i := i +1
; displays: 01234
The alternative to do namely "named let" is a variant on the syntax of let which provides a more general looping construct than do and may also be used to express recursions. It has the almost the same syntax as a normal let, but the variable name can be used in the body to repeat the execution of body with new values for var1 ... by calling name with the new values.
(let name ([var1 exp1]
...)
body
...)
The list of variables can be empty. Rewriting a normal while -loop is now easy:
while test (do () (let while ()
begin [(not test)] (when test
exp1 exp1 exp1
exp2 exp2 exp2
... ...) ...
end (while)))
The (void) expression evaluates to the "invisible" value to indicate that the return value is not meant to be used. It is not printed by the interaction window (the REPL).
To write a for-loop with do requires us to look at the next simplest form of do:
(do ([var start-exp next-exp])
[test return-exp]
exp
...)
The evaluation of the do-expression begins with the evaluation of start-exp. The result is bound to the variable i which is visible in both next-exp as well as test, return-exp and the body expressions. When the loop is restarted next-exp is evaluated and the variable var is rebound to the result, before the test expression and (possibly) the body is reevaluated.
; Example 2
(do ([i 0 (+ i 1)]) (let loop ([i 0])
[(= i 5)] (unless (= i 5)
(display i)) (display i)
(loop (+ i 1))))
; displays: 01234
Now it is clear how to write a normal for loop with do:
for i=a to b step d (do ([i a (+ i d)]) (let for ([i a])
begin [(> i b)] (unless (> i b)
exp1 exp1 exp1
exp2 exp2 exp2
... ...) ...
end (for (+ i d))))
The repeat-until loop is awkard to write using do, but using named let we can do as follows:
repeat
begin (let loop () (let loop ()
exp1 exp1 exp1
exp2 exp2 exp2
... ... ...
end (if (not test) (unless test (loop)))
until test (loop)))
This answer was based on an entry in the SchemeCookbook. See the archives: https://web.archive.org/web/20131004034526/http://schemecookbook.org/Cookbook/IdiomLoopingConstructs