s c h e m a t i c s : c o o k b o o k

/ Cookbook.IdiomLoopingConstructs

This Web


WebHome 
WebChanges 
TOC (with recipes)
NewRecipe 
WebTopicList 
WebStatistics 

Other Webs


Chicken
Cookbook
Erlang
Know
Main
Plugins
Sandbox
Scm
TWiki  

Schematics


Schematics Home
Sourceforge Page
SchemeWiki.org
Original Cookbook
RSS

Scheme Links


Schemers.org
Scheme FAQ
R5RS
SRFIs
Scheme Cross Reference
PLT Scheme SISC
Scheme48 SCM
MIT Scheme scsh
JScheme Kawa
Chicken Guile
Bigloo Tiny
Gambit LispMe
GaucheChez

Lambda the Ultimate
TWiki.org

The "missing" looping constructs while, repeat-until and for.

Problem

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?

Solution

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 return values 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 valuse 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 NamedLet? 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 akward 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)))

Contributors

-- JensAxelSoegaard

Comments

If it doesn't complicate your discussion, perhaps you could emphasize that Scheme makes it easy to code loops as recursive functions that pass many or all of the values that change on each iteration. And that it is very common to have named-let bind more than one variable.

-- NeilVanDyke - 20 May 2004

A comment on a matter of style. (Just mentioning this for consideration; I wouldn't go and change the discussion above, myself.) I almost never use do. Every time I want to, I have to look it up to remind myself of the semantics. I suspect do might also often obscure algorithmic improvements by biasing your code to fit its syntax (but I don't have strong anecdotal evidence of that, and don't use do often enough to be comfortable with it). I originally thought do was some well-founded black-magic that would make me more powerful once I mastered it, but lately it seems to obscure more than it simplifies. (Perhaps it captures some info that makes some compiler optimizations easier?) So, lately, I'm personally inclined to emphasize using named-let, if, cond, and case, and mention do more as an aside.

-- NeilVanDyke - 20 May 2004

I used to have the exact same opinion and to some degree still have. However since I began pronoucing do as do-until it suddenly fell into place. I see the above recipe as * an introduction to simple use of do * a place to refer people stating "Scheme doesn't have looping constructs" * show casing idiomatic uses of do The example is not meant to show idiomatic loops, which TailRecursion? and NamedLoop? ought to explain when written.

When do can be used it often looks pretty, but it isn't hard to change to a named loop. One advantage of do compared to named lets is that all the "loop logic" occurs at the top, where the initial value, the test and the step functions are scattered around in the named loop.

Hm. Perhaps this recipe shoud be renamed IdiomDo? ?

-- JensAxelSoegaard - 21 May 2004

I changed the presentation a little to include NamedLet?. Is it better, or does it become more confusing?

-- JensAxelSoegaard - 21 May 2004

Shouldn't someone mention how to write while, for etc. using syntax-rules and/or syntax-case? The discussion leaves that out, and these are powerful tools to solve exactly this kind of problem. It's true that you usually don't need them for something as simple as this, but OTOH this provides a great opportunity to introduce the concept of hygienic macros in as simple a situation as possible.

-- MichaelVanier - 17 Sep 2004

Feel free to add it either in the text or as a comment. Or better perhaps a reference to a separate recipe in the macro chapter?

-- JensAxelSoegaard - 17 Sep 2004

CookbookForm
TopicType: Recipe
ParentTopic: IdiomRecipes
TopicOrder:

 
 
Copyright © 2004 by the contributing authors. All material on the Schematics Cookbook web site is the property of the contributing authors.
The copyright for certain compilations of material taken from this website is held by the SchematicsEditorsGroup - see ContributorAgreement & LGPL.
Other than such compilations, this material can be redistributed and/or modified under the terms of the GNU Lesser General Public License (LGPL), version 2.1, as published by the Free Software Foundation.
Ideas, requests, problems regarding Schematics Cookbook? Send feedback.
/ You are Main.guest