[plt-scheme] trying to figure out the do form

From: Joe Marshall (jrm at ccs.neu.edu)
Date: Tue Oct 12 09:59:20 EDT 2004

"Sanjeev Sharma" <throwit1 at hotmail.com> writes:

>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> I thought these 2 would be equivalent, and the description seems to
> say they should be.
> My self-appointed exercise was to move the update clauses around, so
> the (-
> i 1) was deleted from the (var val update) line & put into the
> do-if-false expression list.
> Can someone show me where I'm messing up?

I think the key to understanding your problem is in the statement: 
``move the update clauses... put into the do-if-false expression list.''

I think of DO expressions like this:

   (do ((<var0>  <start0>  <next0>)
        (<var1>  <start1>  <next1>)
        (<var2>  <start2>  <next2>))
       (<test-for-done>  <result-expression>)

We have a set of variables, each starts with an initial value.  At
each iteration, we test if we are done.  If so, we compute the final
result (with <result-expression>), otherwise, we perform the side
effects and the result is what is returned from the next iteration.

The DO expression defines an anonymous function that takes N
variables.  The first time it is called, those variables are bound to
the <start> expressions.  Each subsequent time it is called, the
variables are bound to the values computed by the <next> expressions.

So in your first version:

> (define factorial
>   (lambda (n)
>     (do ((i n (- i 1)) 
>          (a 1 (* a i)))
>         ((zero? i)  (display "ans is  ")(display `("i, a",i",",a))(newline) a)
>       (display `("i, a",i", ",a))
>       (newline))))

The iteration steps say that

   (-anonymous-  i a)  has the *same answer* as 

   (-anonymous- (- i 1) (* a i))

The initialization step says that

   (factorial n) has the same answer as (-anonymous- n 1)

In the second example, you say that

  (-anonymous- i a) has the same answer as
  (-anonymous- i (* a i))

This isn't true, so you patch things up changing the value of i in the
side-effects part.  But by doing this, you are introducing a time
dependency.  The variable i now has two values at each step --- the
value at the start of the step, and the value after you side-effect
it.  When you introduce this time dependency, you have to make sure
that all the code that uses the variable looks at the value at the
correct time.

The problem is that the `end test' looks at the variable *before* you
decrement it, but the `next step' looks at the variable *after* you
decrement it.

> (define factorial
>   (lambda (n)
>     (do ((i n ) (a 1 (* a i)))
>       ((zero? i) (display "ans is  ")(display `("i, a",i",",a))(newline))
>       (display `("i, a",i", ",a))(newline)(set! i(- i 1)))))
> (factorial 4)

If you think of a DO expression as having `update clauses' that you
can move to the `do-if-false' part, then you might think that you
didn't really change what is happening.  But DO expressions don't
update anything:  they express the original problem as a *different*
(but related) problem that *has the same answer* as the original.

So you didn't `move the update clause', you deleted it and attempted
to back-patch the code via side effects.  If you look at it this way,
it seems that this approach would be error prone and require a lot of
careful thought to make work.

Posted on the users mailing list.