while break and continue

while break and continue

[Kevin Ryde]

I was going to add some words to the manual about break and continue
in a while loop, but noticed continue doesn't do what I might have
thought.  For instance,

	(define n 0)
	(while (begin
	         (format #t "test ~a\n" n)
	         (< n 2))
	       (format #t "body ~a\n" n)
	       (set! n (1+ n))
	       (if #t
	           (continue))
	       (format #t "unreachable ~a\n" n))

prints

	test 0
	body 0
	test 1
	body 1
	test 2
	unreachable 2
	test 2
	unreachable 2
	test 2

whereas I might have hoped "unreachable" would indeed have been
unreachable, and the test wouldn't be evaluated again once false (at
n=2).

Is a throw the best way for continue to extricate itself from the
body?  I take it that's the intention.  If so perhaps something like
the following (only tested a bit),

(define while
  (procedure->memoizing-macro
   (lambda (expr env)
     (let* ((break-key     (gensym " while break-key"))
	    (continue-key  (gensym " while continue-key"))
	    (break-proc    (lambda (value) (throw break-key value)))
	    (continue-proc (lambda ()      (throw continue-key))))
       `(catch ',break-key
	       (lambda ()
		 (do ()
		     ((not ,(cadr expr)))
		   (let ((break    ,break-proc)
			 (continue ,continue-proc))
		     (catch ',continue-key
			    (lambda ()
			      ,@(cddr expr))
			    noop))))
	       (lambda args (cadr args)))))))

Each while loop gets its own break and continue keys and procedures,
to allow those procedures to be used from inner nested loops.  The new
bindings are only for the body forms, maybe they should be available
to the condition expression too.

Not really a thing of beauty, and probably not fast.  A good reason
not to use unstructured stuff like "continue" I guess :-).


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Marius Vollmer]

Kevin Ryde <user42@zip.com.au> writes:

> I was going to add some words to the manual about break and continue
> in a while loop, but noticed continue doesn't do what I might have
> thought.

Oops.  Yes, that is unexpected.  I think your solution is essentially
correct, except that you shouldn't use procedure->memoizing-macro (use
define-macro instead) and that you inject literal procedures into the
expanded code.  This is not good style since the procedures are
created in the compile time environment but used in the run-time
environment.  A compiler might not like this.

This old post might be interesting as well, but the 'tagbody'
implementation in it is not properly tail recursive:

  http://sources.redhat.com/ml/guile/2000-07/msg00339.html

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Kevin Ryde]

Marius Vollmer <mvo@zagadka.de> writes:
>
> you shouldn't use procedure->memoizing-macro (use
> define-macro instead) and that you inject literal procedures into the
> expanded code.

Ah right, yep.  New code and prospective documentation below.

The code is still pretty ugly, I suppose that's what you get for
non-local exits :-).  Maybe should have a caveat in the docs about
style, to discourage their use.

I wonder if the value parameter for break should be optional, and have
while return unspecified when not given.  That might be a reasonably
common usage.  Unless the whole thing is emulating some established
convention.

Incidentally, where would be a good place to put some tests?
syntax.test maybe, or a new file?


(define-macro (while cond . body)
  (let ((break-key    (gensym " while break-key"))
	(continue-key (gensym " while continue-key")))
    `(catch ',break-key
	    (lambda ()
	      (do ((break    (lambda (value) (throw ',break-key value)))
		   (continue (lambda ()      (throw ',continue-key))))
		  ((not (catch ',continue-key
			       (lambda ()
				 ,(if (null? body)
				      cond  ;; avoid some code if body empty
				      `(and ,cond
					    (begin
					      ,@body
					      #t))))
			       (lambda args #t))))))
	    (lambda (key value)
	      value))))



 - syntax: while cond body ...
     Run a loop executing BODY while COND is true.  COND is tested at
     the start of each iteration, so if it's `#f' the first time then
     BODY is not executed at all.  The return value is unspecified.

     Within `while' two additional bindings are provided, and can be
     used from both COND and BODY.

      - Scheme Procedure: break value
          Break out of the `while' form, and have it return the given
          VALUE.

      - Scheme Procedure: continue
          Abandon the current iteration, and continue with the next.
          Ie. go to the top of the loop, test COND again, etc.

     Each `while' provides separate `break' and `continue' procedures,
     and they operate on that `while'.  So for instance when `while'
     loops are nested the outer `break' can be used from within the
     inner loop to get all the way out.

          (while (test1)
            (let ((outer-break break))
              (while (test2)
                (if (something)
                  (outer-break #f)))))

     Note that each `break' and `continue' procedure can only be used
     within the dynamic extent of their corresponding `while'.  Once
     the `while' has been exited their behaviour is unspecified.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Kevin Ryde]

Marius Vollmer <mvo@zagadka.de> writes:
>
> inject literal procedures into the expanded code.

Yes, that was for some wrong reasons.

On this subject though, is it worth expanding to actual procedures
rather than symbols, so one gets the intended effect irrespective of
local bindings at the point used?

I don't suppose anyone goes out of their way to shadow standard stuff,
but it's probably nice to take precautions.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Marius Vollmer]

Kevin Ryde <user42@zip.com.au> writes:

> The code is still pretty ugly, I suppose that's what you get for
> non-local exits :-).  Maybe should have a caveat in the docs about
> style, to discourage their use.

Discourage the use of 'while' or merely 'continue' and 'break'?  I
think, pointing in the docs of 'while' to 'do' and the other ways of
doing loops in Scheme would be good.

I do think we definitely need to efficiently support non-Schemey
styles, for the translators and maybe also for people used to them.
But that should probably be done together with a compiler so that the
common usage can be properly optimized.  (A 'while' that doesn't use
'break' should not have a 'catch', etc...)

Your macro is not necessarily he most efficient, but it is as
efficient as possible without some kind of comiler-style analysis, I'd
say.

What is more important is the interface: does it have the right
semantics?  I think it does, and we should change our old while to
your new version, even if the implementation is ugly and maybe
inefficient.

> I wonder if the value parameter for break should be optional, and
> have while return unspecified when not given.  That might be a
> reasonably common usage.

I think the value of a while loop is ill-specified anyway and we
should always return unspecified.  What should be returned when the
condition becomes false?  Your macro arranges to return #t, wich seems
arbitrary.  People who want their loop to return a specific value
should use 'do', named 'let', or some other mechanism, I'd say.

> Unless the whole thing is emulating some established
> convention.

Not that I know of.

> Incidentally, where would be a good place to put some tests?
> syntax.test maybe, or a new file?

syntax.test seems fine.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Marius Vollmer]

Kevin Ryde <user42@zip.com.au> writes:

> On this subject though, is it worth expanding to actual procedures
> rather than symbols, so one gets the intended effect irrespective of
> local bindings at the point used?

I don't understand.  What usage are you worried about?  Can you give
an example?

> I don't suppose anyone goes out of their way to shadow standard stuff,
> but it's probably nice to take precautions.

Yes, definitely.  That's what (ice-9 syncase) is for...

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Kevin Ryde]

Marius Vollmer <mvo@zagadka.de> writes:
>
> What usage are you worried about?

Only the sort of thing you can imagine.  Eg. with the current "while",

	(let ((not      1)
	      (sensible 2))
	  (while (< sensible 4)
	    (set sensible (+ sensible not))))

gives

	ERROR: Wrong type to apply: 1

> Yes, definitely.  That's what (ice-9 syncase) is for...

Yep.  I guess it's a bit big and ugly to drag into boot-9.scm though.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Kevin Ryde]

Marius Vollmer <mvo@zagadka.de> writes:
>
> Discourage the use of 'while' or merely 'continue' and 'break'?

Oh, well, continue and break I guess.

> I
> think, pointing in the docs of 'while' to 'do' and the other ways of
> doing loops in Scheme would be good.

Might have a go at more in the introductory para of the "while do"
node.

> I think the value of a while loop is ill-specified anyway and we
> should always return unspecified.  What should be returned when the
> condition becomes false?  Your macro arranges to return #t, wich seems
> arbitrary.

I think I return unspecified, since there's no final value expr in the
"do" loop.  I'll make sure that's the case though.

> People who want their loop to return a specific value
> should use 'do', named 'let', or some other mechanism, I'd say.

As long as no-one has peeked at boot-9.scm and used break with a
value.  Would seem unlikely, but could perhaps make it optional, for
maximum compatibility.

I suppose a radical alternative would be to drop break and continue
completely, having never been documented (and continue not really
working).


I simplified my code, per below.  The theory is to have only one
catch, for efficiency, and to have an inner "do" loop so that if break
and continue are not used then the catch isn't re-established on each
iteration.


(define-macro (while cond . body)
  (let ((key (make-symbol "while-key")))
    `(do ((break    (lambda () (throw ',key #t)))
	  (continue (lambda () (throw ',key #f))))
	 ((catch ',key
		 (lambda ()
		   (do ()
		       ((not ,cond))
		     ,@body)
		   #t)
		 (lambda (key arg) arg))))))


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Marius Vollmer]

Kevin Ryde <user42@zip.com.au> writes:

> I simplified my code, per below.  The theory is to have only one
> catch, for efficiency, and to have an inner "do" loop so that if break
> and continue are not used then the catch isn't re-established on each
> iteration.

This looks very nice.  Do you want to put it into boot-9.scm?

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Kevin Ryde]

Marius Vollmer <mvo@zagadka.de> writes:
>
> Do you want to put it into boot-9.scm?

Yes, I think it'd be good.  Actually what I'd like to put in is
something like

(define-macro (while cond . body)
  (let* ((key           (make-symbol "while-key"))
	 (break-proc    (lambda () (throw key #t)))
	 (continue-proc (lambda () (throw key #f))))
    `(,do ((break    ,break-proc)
	   (continue ,continue-proc))
	 ((,catch (,quote ,key)
		  (,lambda ()
		    (,do ()
			((,not ,cond))
		      ,@body)
		    #t)
		  ,(lambda (key arg) arg))))))

All the backquoting being designed to protect against local bindings
at expansion time.  I know what you said about compiler friendliness,
but I think for the moment protection against local defines would be
better.

(I imagine a compiler might want to try to cooperate with application
macros like this using only basic list or procedure stuff, through
some sort of eval in a restricted environment or whatever.  But no
doubt plenty of people smarter than me have thought about such things
before.)


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Matthias Koeppe]

Kevin Ryde <user42@zip.com.au> writes:

+(define-macro (while cond . body)
+  (let ((key (make-symbol "while-key")))
+    `(,do ((break    ,(lambda () (throw key #t)))
+	   (continue ,(lambda () (throw key #f))))
+	 ((,catch (,quote ,key)
+		  (,lambda ()
+		    (,do ()
+			((,not ,cond))
+		      ,@body)
+		    #t)
+		  ,(lambda (key arg) arg))))))

I think you need a fresh catch tag for every invocation (not only for
every macro expansion site) of WHILE.  Consider this recursive
example:

(define (rec branch breaker)
  (while #t
    (case branch
      ((1)
       (display ".")
       (breaker))    ; should break the (dynamically) outer loop
                     ; but only breaks the inner loop
      ((2)
       (rec 1 break)))))

(rec 2 (lambda () #t))

This should display one "." and return because the dynamically outer
loop (branch = 2) is broken.  But with your implementation, both loops
share the same catch tag, so only the inner loop (branch = 1) is
broken, hence the outer loop continues indefinitely.

-- 
Matthias Koeppe -- http://www.math.uni-magdeburg.de/~mkoeppe


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Kevin Ryde]

[-- Attachment #1: Type: text/plain, Size: 1594 bytes --]

I applied this

        * boot-9.scm (while): Rewrite, continue as a proper escape, break
        doesn't take a return value, break and continue procs new for each
        while form allowing use in nested whiles, don't depend on bindings in
        expansion environment.

        * tests/syntax.test (while): New tests.

        * scheme-control.texi (while do): Update `while' for code rewrite, in
        particular describe break and continue.


 - syntax: while cond body ...
     Run a loop executing the BODY forms while COND is true.  COND is
     tested at the start of each iteration, so if it's `#f' the first
     time then BODY is not executed at all.  The return value is
     unspecified.

     Within `while', two extra bindings are provided, they can be used
     from both COND and BODY.

      - Scheme Procedure: break
          Break out of the `while' form.

      - Scheme Procedure: continue
          Abandon the current iteration, go back to the start and test
          COND again, etc.

     Each `while' form gets its own `break' and `continue' procedures,
     operating on that `while'.  This means when loops are nested the
     outer `break' can be used to escape all the way out.  For example,

          (while (test1)
            (let ((outer-break break))
              (while (test2)
                (if (something)
                  (outer-break #f))
                ...)))

     Note that each `break' and `continue' procedure can only be used
     within the dynamic extent of its `while'.  Outside the `while'
     their behaviour is unspecified.




[-- Attachment #2: boot-9.scm.while.diff --]
[-- Type: text/plain, Size: 1252 bytes --]

--- boot-9.scm.~1.316.~	2003-05-30 08:40:07.000000000 +1000
+++ boot-9.scm	2003-08-14 07:38:41.000000000 +1000
@@ -2491,18 +2491,6 @@
         (loop (1- count) (cons count result)))))
 
 \f
-;;; {While}
-;;;
-;;; with `continue' and `break'.
-;;;
-
-(defmacro while (cond . body)
-  `(letrec ((continue (lambda () (or (not ,cond) (begin (begin ,@ body) (continue)))))
-	    (break (lambda val (apply throw 'break val))))
-     (catch 'break
-	    (lambda () (continue))
-	    (lambda v (cadr v)))))
-
 ;;; {collect}
 ;;;
 ;;; Similar to `begin' but returns a list of the results of all constituent
@@ -2560,6 +2548,26 @@
       (else
        (error "define-syntax-macro can only be used at the top level")))))
 
+;;; {While}
+;;;
+;;; with `continue' and `break'.
+;;;
+
+;; The inner `do' loop avoids re-establishing a catch every iteration,
+;; that's only necessary if continue is actually used.
+;;
+(define-macro (while cond . body)
+  (let ((key (make-symbol "while-key")))
+    `(,do ((break    ,(lambda () (throw key #t)))
+	   (continue ,(lambda () (throw key #f))))
+	 ((,catch (,quote ,key)
+		  (,lambda ()
+		    (,do ()
+			((,not ,cond))
+		      ,@body)
+		    #t)
+		  ,(lambda (key arg) arg))))))
+
 \f
 ;;; {Module System Macros}
 ;;;

[-- Attachment #3: syntax.test.while.diff --]
[-- Type: text/plain, Size: 3788 bytes --]

--- syntax.test.~1.10.~	2003-04-28 07:51:30.000000000 +1000
+++ syntax.test	2003-08-12 22:30:55.000000000 +1000
@@ -550,3 +550,171 @@
       exception:missing/extra-expr
       (eval '(quote a b)
 	    (interaction-environment)))))
+
+(with-test-prefix "while"
+  
+  (define (unreachable)
+    (error "unreachable code has been reached!"))
+  
+  ;; an environment with no bindings at all
+  (define empty-environment
+    (make-module 1))
+  
+  ;; Return a new procedure COND which when called (COND) will return #t the
+  ;; first N times, then #f, then any further call is an error.  N=0 is
+  ;; allowed, in which case #f is returned by the first call.
+  (define (make-iterations-cond n)
+    (lambda ()
+      (cond ((not n)
+	     (error "oops, condition re-tested after giving false"))
+	    ((= 0 n)
+	     (set! n #f)
+	     #f)
+	    (else
+	     (set! n (1- n))
+	     #t))))
+  
+
+  (pass-if-exception "too few args" exception:wrong-num-args
+    (while))
+  
+  (with-test-prefix "empty body"
+    (do ((n 0 (1+ n)))
+	((> n 5))
+      (pass-if n
+	(let ((cond (make-iterations-cond n)))
+	  (while (cond)))
+	#t)))
+  
+  (pass-if "initially false"
+    (while #f
+      (unreachable))
+    #t)
+  
+  (with-test-prefix "in empty environment"
+    
+    (pass-if "empty body"
+      (eval `(,while #f)
+	    empty-environment)
+      #t)
+    
+    (pass-if "initially false"
+      (eval `(,while #f
+	       #f)
+	    empty-environment)
+      #t)
+    
+    (pass-if "iterating"
+      (let ((cond (make-iterations-cond 3)))
+	(eval `(,while (,cond)
+		 123 456)
+	      empty-environment))
+      #t))
+  
+  (with-test-prefix "iterations"
+    (do ((n 0 (1+ n)))
+	((> n 5))
+      (pass-if n
+	(let ((cond (make-iterations-cond n))
+	      (i    0))
+	  (while (cond)
+	    (set! i (1+ i)))
+	  (= i n)))))
+  
+  (with-test-prefix "break"
+    
+    (pass-if-exception "too many args" exception:wrong-num-args
+      (while #t
+	(break 1)))
+    
+    (with-test-prefix "from cond"
+      (pass-if "first"
+	(while (begin
+		 (break)
+		 (unreachable))
+	  (unreachable))
+	#t)
+      
+      (do ((n 0 (1+ n)))
+	  ((> n 5))
+	(pass-if n
+	  (let ((cond (make-iterations-cond n))
+		(i    0))
+	    (while (if (cond)
+		       #t
+		       (begin
+			 (break)
+			 (unreachable)))
+	      (set! i (1+ i)))
+	    (= i n)))))
+    
+    (with-test-prefix "from body"
+      (pass-if "first"
+	(while #t
+	  (break)
+	  (unreachable))
+	#t)
+      
+      (do ((n 0 (1+ n)))
+	  ((> n 5))
+	(pass-if n
+	  (let ((cond (make-iterations-cond n))
+		(i    0))
+	    (while #t
+	      (if (not (cond))
+		  (begin
+		    (break)
+		    (unreachable)))
+	      (set! i (1+ i)))
+	    (= i n)))))
+    
+    (pass-if "from nested"
+      (while #t
+	(let ((outer-break break))
+	  (while #t
+	    (outer-break)
+	    (unreachable)))
+	(unreachable))
+      #t))
+  
+  (with-test-prefix "continue"
+    
+    (pass-if-exception "too many args" exception:wrong-num-args
+      (while #t
+	(continue 1)))
+    
+    (with-test-prefix "from cond"
+      (do ((n 0 (1+ n)))
+	  ((> n 5))
+	(pass-if n
+	  (let ((cond (make-iterations-cond n))
+		(i    0))
+	    (while (if (cond)
+		       (begin
+			 (set! i (1+ i))
+			 (continue)
+			 (unreachable))
+		       #f)
+	      (unreachable))
+	    (= i n)))))
+    
+    (with-test-prefix "from body"
+      (do ((n 0 (1+ n)))
+	  ((> n 5))
+	(pass-if n
+	  (let ((cond (make-iterations-cond n))
+		(i    0))
+	    (while (cond)
+	      (set! i (1+ i))
+	      (continue)
+	      (unreachable))
+	    (= i n)))))
+    
+    (pass-if "from nested"
+      (let ((cond (make-iterations-cond 3)))
+	(while (cond)
+	  (let ((outer-continue continue))
+	    (while #t
+	      (outer-continue)
+	      (unreachable)))))
+      #t)))

[-- Attachment #4: Type: text/plain, Size: 142 bytes --]

_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Kevin Ryde]

Matthias Koeppe <mkoeppe@merkur.math.uni-magdeburg.de> writes:
>
> I think you need a fresh catch tag for every invocation (not only for
> every macro expansion site) of WHILE.  Consider this recursive
> example:

Ah yes, I'll look into that.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: while break and continue

[Kevin Ryde]

Matthias Koeppe <mkoeppe@merkur.math.uni-magdeburg.de> writes:
>
> I think you need a fresh catch tag for every invocation (not only for
> every macro expansion site) of WHILE.

I think this might do the trick.  A separate helper is an easy way to
keep the "key" binding from being exposed to the cond and body.

(define-macro (while cond . body)
  (define (while-helper proc)
    (do ((key (make-symbol "while-key")))
        ((catch key
                (lambda ()
                  (proc (lambda () (throw key #t))
                        (lambda () (throw key #f))))
                (lambda (key arg) arg)))))
  `(,while-helper (,lambda (break continue)
                    (,do ()
                        ((,not ,cond))
                      ,@body)
                    #t)))


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel