Fwd: Loop macro question

[William.Lott@cs.cmu.edu]

I posted this to comp.lang.lisp 3 weeks ago, but got no responses.
I have no idea if X3J13 wants to address this issue at this time, but
if anyone wants to take a crack at it, we (the CMU Common Lisp Group)
could really use an answer.  Thanks in advance for your time.

-William Lott
CMU Common Lisp Group

---------- Forwarded message begins here ----------

Newsgroups: comp.lang.lisp
Message-Id: <IdRI0fW00jePI0bZUQ@cs.cmu.edu>
Date: Thu, 16 Jan 1992 03:19:55 -0500 
From: William.Lott@cs.cmu.edu
Subject: Loop macro question

I've been trying to fix CMUCL's version of the LOOP macro, but I'm not
sure I understand all the implications.  Specifically, in what order
are initializers, steppers, and termination-tests performed in?  For
example, assume a LOOP expression of the following form:

	(loop 
	  for x ...
	  for y ...
	  do (something)
	  finally return (result))

Assume (init-x) is the code to compute the initialize value for x,
(step-x) is the code to compute the new value for x, and
(x-end-test-p) is the code to determine for the "for x ..." has run
out.  Likewise for y.

Now there are many different ways these pieces can be combinded
together.  But I can't figure out which one is allowed/desired.  The
X3J13 cleanup LOOP-INITFORM-ENVIRONMENT specifically disallows any
expansion of the form:

	(let (x y)
	  (setf x (init-x))
	  (setf y (init-y))
	  ...)

because X and Y are bound during (init-x) and Y is bound during
(init-y).  My reading of LOOP-INITFORM-ENVIRONMENT seems to indicate
that the loop is expected to expand into something like:

	(let* ((x (init-x))
	       (y (init-y)))
	  ...)

Okay, so now we need to add the guts of the loop.  If the two clauses
were chained together with an ``and'' the expansion should obviously
be something like:

	(let* ((x (init-x)) (y (init-y)))
	  (block nil
	    (tagbody
	     AGAIN
	      (when (or (x-end-test-p) (y-end-test-p))
	        (go done))
	      (something)
	      (psetf x (step-x) y (step-y))
	      (go again)
	     DONE
	      (return (result)))))

But the clauses were not chained together with an ``and'' so they
should be done sequentially, not in parallel.  So what changes?
Obviously the psetf becomes a setf.  If that is all that changes, then
you can't use the end-test of one clause to protect steppers or
initializers of other clauses.  For example, the following code would
be in error:

	(loop
	  for x in *list-of-structs*
	  for y = (struct-slot x)
	  do (something x y))

Because after the loop has iterated of all the structs both x and y
would be stepped before it was noted that the list feeding x was
empty.  Therefore struct-slot would be called on a bogus value,
probably NIL.  You could protect against this yourself by saying:

	(loop
	  for x in *list-of-structs*
	  for y = (and x (struct-slot x))
	  do (something x y))

But this strikes me as rather cumbersome and non-intuitive.

So lets try to interleave the test forms with the init/step forms.  In
fact, I kinda remember someone asserting on this newsgroup a while
back that this is what was supposed to happen.  Then the guts of the
tagbody should have code looking kinda like:

	...
	(setf x (step-x))
	(when (x-end-test-p)
	  (go done))
	(setf y (step-y))
	(when (y-end-test-p)
	  (go done))
	...

But if the end-tests are interleaved with the steppers, then they
should also be interleaved with the initers.  Otherwise the n=0 case
would be semantically different from the n>0 cases.  In the
*list-of-structs* example above, we would still be required to say
(and x (struct-slot x)) instead of just (struct-slot x) if
*list-of-structs* could ever be empty.  This would result in a large
number of bugs, because people would not realize this and write their
loops in the straight forward way and only later find out they don't
work in all cases.  But how are you going to do that?  This obviously
won't work:

	(let ((x (init-x)))
	  (when (x-end-test-p)
	    (go done))
	  (let ((y (init-y)))
	    (when (y-end-test-p)
	      (go done))
	    ...))

because the (go done)'s are outside the tagbody.  Or the tagbody is
outside some of the bindings.  The only way I could think of to do
this is to do something like:

	(let (#:g1 #:g2)
	  (tagbody
	    (setf #:g1 (init-x))
	    (let ((x #:g1))
	      (when (x-end-test-p)
	        (go done)))
	    (let ((x #:g1))
	      (setf #:g2 (init-y)))
	   AGAIN
	    (let ((y #:g2))
	      (when (y-end-test-p)))
	    (let ((x #:g1) (y #:g2))
	      (something))
	    (let ((x #:g1) (y #:g2))
	      (setf #:g1 (step-x)))
	    (let ((x #:g1) (y #:g2))
	      (when (x-end-test-p)
	        (go done)))
	    (let ((x #:g1) (y #:g2))
	      (setf #:g2 (step-y)))
	    (go again)
	   DONE
	    (let ((x #:g1) (y #:g2))
	      (return (result)))))

Am I out to lunch here?  Does the expansion really have to be this
cumbersome?  Or am I wrong in assuming the end-tests and the
steppers/initers should be interleaved?

-William Lott
CMU Common Lisp Group