Re: loop translations (was: Re: language translator help)

[Marius Vollmer]

"John W. Eaton" <address@hidden> writes:

> I'd like to understand how to translate some simple loops.

Spot on.  I think loops with break and continue are the most confusing
point for people who aren't yet deep into Scheme.

Your approach is essentially right.  Let me try to formalize it a bit
with some macros:

    ;;;; How to loop, with break and continue.

    ;;; 'with-exit' lets you break out of a computation.

    (define-macro (with-exit sym . body)
      `(call-with-current-continuation (lambda (,sym) ,@body)))

    ;;; 'while'.  BODY can call a function named 'break' to exit the loop,
    ;;; and a function 'continue' to skip to the next iteration.  You
    ;;; don't have to call 'break' or 'continue' in a tail context.

    (define-macro (while test . body)
      (let ((loop-sym (gensym "loop")))
        `(with-exit break
           (let ,loop-sym ()
             (cond
              (,test
               (with-exit continue
                 ,@body)
               (,loop-sym)))))))

    ;;; 'for', like 'while'.  Also, each iteration gets a fresh binding
    ;;; for the iteration variable.

    ;; range is (var start stop)

    (define-macro (for range . body)
      (let ((var (car range))
            (start (cadr range))
            (stop (caddr range))
            (loop-sym (gensym "loop")))
        `(with-exit break
           (let ,loop-sym ((,var ,start))
             (cond
              ((< ,var ,stop)
               (with-exit continue
                 ,@body)
               (,loop-sym (1+ ,var))))))))

When you compare this with your code, you see that I put the
'continue' exit point immediately around the body, excluding the test.
The effect is that a call to 'continue' will skip the rest of the body
and call the loop function again the normal way.  Your way of
implementing 'continue' does work, but in a weird way: it first
executes the rest of the loop (by calling 'for' in the argument to
'continue') and then exits the loop by behaving like a 'break'.  The
functions created by '(let loop ...)' are totally ordinary functions
and calling them in a non-tail context will 'push stack' and they will
eventually return to the caller.  Thus, as you noticed, calling the
loop function does not behave like 'continue' in other languages.  If
you want to, you can use named let for things other than loops, for
example for tree walking.

The immediate problem with your way of implementing 'continue' is that
loops that use it do no longer run in constant space.

The problem with the macros above is that they are not hygienic, and
call/cc is quite inefficient in Guile.  Making them hygienic should
not be a problem, but avoiding call/cc is not so easy and is hopefully
not really necessary.  One could generate continuation-passing code
and hope that Guile will execute it more efficiently than the
occasional call/cc, or one could implement a cheaper version of
call/cc that is not as powerful but is sufficient for 'with-exit'.  I
think we should do the latter, if performance of call/cc turns out to
be too bad.

> For example, the following loop is valid in Octave.
> 
>   for i = 1:3
>     disp (i);
>     if (i == 2)
>       break;
>     endif
>   endfor

This would be, using the macros from above

    (for (i 1 4)
      (display i) (newline)
      (if (= i 2)
          (break)))

Or without:

    (with-exit break
     (let for ((i 1))
       (cond
        ((< i 4)
         (with-exit continue
           (display i) (newline)
             (if (= i 2)
             (break)))
         (for (1+ i))))))

> This works, but seems quite complex to me.  Is there a simpler way?

When using some macros, it's not really complex, I'd say.

> Here is another:
> 
>   for i = 1:4
>     if (i < 4)
>       disp ("foo-i-hithere");
>       if (i == 2)
>       continue;
>       endif
>     endif
>     disp (i);
>   endfor

    (for (i 1 5)
      (if (< i 4)
          (begin
            (display "foo-i-hithere") (newline)
            (if (= i 2)
                (continue))))
      (display i) (newline))

> For Guile, I came up with
> 
>   (let for ((i 1))
>     (call-with-current-continuation
>      (lambda (continue)
>        (if (<= i 4)
>            (begin
>              (if (< i 4)
>                  (begin
>                    (display "foo-i-hithere")
>                    (newline)
>                    (if (= i 2)
>                        (continue (for (+ 1 i))))))
                                   ^^^^^^^^^^^^^

This is where you recursively call the loop function 'for' and wait
for it to return.  This uses stack space.