Agenda Item 74: Interaction of BLOCK and RETURN

[MOON at SCRC-TENEX]

At the meeting we commissioned GLS and SEF to make a proposal about this.
But in the meantime Bawden has come up with a good proposal, hence I am
mailing off this writeup of it.

The problem:
Blocks, named and unnamed, are used to label a point to which the RETURN
special form will transfer control.  Some special forms are defined and
documented to create a block, thus RETURN may be used inside of them.  PROG,
DO, and DOLIST are examples.  Some of these special forms might be implemented
as macros, expanding into simpler special forms such as BLOCK or PROG.  It's
easy to see how to implement DOLIST this way, for example.

Sometimes one has a macro that needs to transfer control internally within
the code it writes, using BLOCK and RETURN or the equivalent.  However,
this block is purely the internal business of this macro and should not be
visible to the user.  This is different from DOLIST, where the user is told
that there is a block there.  If the macro takes a body, and the user
writes RETURN inside that body, the RETURN should return from the block the
user expects it to return from; it shouldn't be affected by the internal
block written by the macro.  The classic example of this occurs when a
compiler optimizes (MAPCAR #'(LAMBDA ...)) by translating it into an
iteration, rather than breaking off a separate function and passing it to
MAPCAR.  The iteration is done with PROG or DO, which creates a block.  If
RETURN was used inside the body of the lambda, it should not return
unexpectedly from the MAPCAR, it should return from some enclosing form,
assuming we are using a full-lexical-scoping language.  Another example is
an error-handling macro that generates code something like:
	(PROG () (CATCH tag (RETURN body))
		 error-body)
Here the idea is that in the normal case we want to return the value(s) of body
from the form; but if a throw occurs, we want to go off and do error-body.
However, the user might well write a RETURN inside body, and this RETURN should
not be captured by the PROG, which the user has no idea is there.

Macros may generate blocks for GO as well as for RETURN.  The MAPCAR example
above was an example of this.

A solution that doesn't quite work:
The 29July Common Lisp manual, on page 72, adopts a solution to this from
the Lisp machine.  The RETURN function returns from the innermost enclosing
block, named or unnamed, except that it ignores blocks named T.  Thus macros
that need to generate blocks that are invisible to the user just name them
T, and return from them with (RETURN-FROM T value).

There are two problems with this.  One is that the named-PROG and named-DO
features have been flushed from Common Lisp; only BLOCK can have a name.
This means that it is impossible to create something that loops but is
invisible to RETURN.  The other problem is that sometimes it is necessary
to nest invisible blocks.  There is no way to nest two invisible blocks
and put a return from the outer one inside both of them, since they both
have to have the same name (T).  This problem shows up as two macros that
work separately, but mysteriously generate wrong code when used together.

The proposed solution:
Define (RETURN value) to be (RETURN-FROM NIL value); allow RETURN to return
from unnamed blocks only.  Require RETURN-FROM to be used to return from
named blocks.  Thus to make a block which is invisible to RETURN, you just
give it a name.  You can choose a unique name for a macro-generated block
the same way you would for a macro-generated variable, perhaps by using
GENSYM.

This is incompatible with the Lisp machine, where RETURN returns from named
blocks as well as unnamed ones.  However, it isn't really incompatible since
all the Lisp machine ways to create a named block have been flushed from
Common Lisp, and the BLOCK special form is new.  In the Lisp machine, we can
keep around a compatibility kludge for a while, where named PROGs and DOs generate
two blocks, one named and one not named, unless the name is T, thus getting
the old behavior.

The other problem is that we need a way for macros to perform iteration without
"capturing" RETURN.  This is handled by introducing a new special form, which
is a "naked" PROG body without an associated block and without variable bindings.
I don't know of a good name for this, but the name doesn't matter much since
only macros that implement new control-structures should be using it.
The name could be GO-BODY, meaning a body with GOs and tags in it, or
PROG-BODY, meaning just the inside part of a PROG, or WITH-GO, meaning
something inside of which GO may be used.  I don't care; suggestions anyone?

(GO-BODY &body <body>)

<body> is treated like a prog body is now.  Symbols are labels and you can use
GO to branch.  GO-BODY always returns NIL (there are NO exceptions).

Now we can flush PROG as a special form and write it as a macro:

(defmacro prog (first &rest rest)
  (cond ((listp first)	;assuming we fix it so that (listp nil) => t
	 `(let ,first
	    (block nil
	      (go-body ,@rest))))
	((eq first t)
	 `(let ,(car rest)
	    (block t
	      (go-body ,@(cdr rest)))))
	(t
	 `(let ,(car rest)
	    (block ,first
	      (block nil
		(go-body ,@(cdr rest))))))))