Issue: EXIT-EXTENT (Version 5)

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

I'm sorry I got behind reading the mail on this topic.  There are enough
mistakes in this released-to-X3J13 version (even though it is
considerably improved over my last version) that a line by line
commentary seems necessary.  Sorry about the length.  I've avoided
commenting on typos that don't affect the meaning, except to put -> in
the margin, to save space.

I'd volunteer to fix the writeup except that, as noted below, I can't
think of any implementation-independent way to say what I think the
MEDIUM proposal was intended to say, but does not actually say.

    Issue:         EXIT-EXTENT

    References:    CATCH, THROW,
		   BLOCK, RETURN, RETURN-FROM,
		   TAGBODY, GO, UNWIND-PROTECT,
		   Dynamic extent (CLtL p.37),
		   Nested dynamic extents (CLtL p.38),
		   Blocks can only be exited once (CLtL p.120),
		   Catch is disestablished just before the values 
		   are returned (CLtL p.139).
    Related issues: UNWIND-PROTECT-NON-LOCAL-EXIT is superseded
		    by this one.

    Category:      CLARIFICATION

    Edit history:  ... Version 5 of UNWIND-PROTECT-NON-LOCAL-EXIT, 23-May-88 ...
		   Version 1, 5-Sep-88, by Moon, for discussion
		   Version 2, 1-Oct-88, by Masinter, minor edits
		   Version 3, 7-Oct-88, by Moon, wording improvements
		   Version 4,  7-Dec-88, by Masinter, add MEDIUM from
					    UNWIND-PROTECT-NON-LOCAL-EXIT, discussion.
		   Version 5, 12-Dec-88, Masinter, clarify MINIMAL allows MEDIUM

    Problem description:

    CLtL does not specify precisely when the dynamic extent (lifetime)
    of a nonlocal exit such as a CATCH, BLOCK, or TAGBODY ends. 
    For example, at what point is it no longer possible to RETURN-FROM
    a particular BLOCK?

    (Terminology: In this issue writeup, the noun "exit" is
->  refera to the thing that can be exited from, rather than the
    act of exiting. 

That would be a good idea, but in fact the writeup still uses the word
"exit" to refer both to the door and to the act of walking out the door.
I guess the sentence is technically true, since the latter use is a verb
rather than a noun.  It would be better to use only "transfer of control"
to refer to the act of walking out the door.

		    When the extent of an exit has ended, it is
    no longer legal to exit from it. This is different from
    the scope of the exit. For example, a BLOCK has lexical
->  scope but dynamic extent; a the scope of a CATCH--the 
    visibility of the CATCH tag to corresponding THROWs--
    could differ from the extent of the CATCH.)

    The problem arises when there are nonlocal exits from the 
    "cleanup" clauses of an UNWIND-PROTECT.

    There are three cases of interest:

    (1) Normal exit from a CATCH, BLOCK, or TAGBODY, or equivalent such as
    PROG.  A normal exit occurs when the last form in the body of one of
    these constructs completes its evaluation without performing a transfer
    of control.

    (2) Nonlocal exit from the target of a THROW or RETURN.  A nonlocal exit
    occurs when control is transferred by THROW, RETURN, or RETURN-FROM.
    The CATCH or BLOCK named in the THROW, RETURN, or RETURN-FROM is
    referred to as the target.  The TAGBODY containing the tag named by a
    GO is also referred to as the target, but GO differs from the other
    nonlocal control transfer operators because GO does not exit its target.
->  For example,

    (3) Abandonment of an exit passed over by THROW, RETURN, or GO.  A
    CATCH, BLOCK, or TAGBODY that is dynamically nested inside the target of
    a nonlocal transfer of control is said to be passed over when control is
    transferred to the target.  The target itself is not said to be passed
    over.

    For example, in
       (block testem
	  (when (zilched) (return-from testem nil))
	  (when (zorked) (throw 'uh-oh))
	  (format t "Neither zilched nor zorked."))

    if (zilched) returns true, the block testem is exited via a 
    'nonlocal exit'. If (zorked) returns true, the block testem
    is 'passed over'. Otherwise, the block is exited normally.

    The terms "normal exit", "target", and "passed over" will be used with
    these meanings for the remainder of the discussion.

    CLtL is unambiguous about case 1.  In case 2, the extent could end
    anywhere from the time the THROW or RETURN commences, until the time the
    transfer of control is completed.  In case 3, the extent could end
    anywhere from the time the THROW, RETURN, or GO commences, until the
    time the transfer of control is completed.  In case 2, it is clear that
    the extent of the target ends before the transfer of control completes,
    since a block cannot be exited twice, but it is not made clear whether
    the extent ends before or after execution of UNWIND-PROTECT cleanup
    forms.  CLtL says nothing about case 3, although a note on p.38 implies
    that the extent of a passed-over exit should end no later than the end
    of the extent of the target exit.  It would make sense for the extent
    of an exit passed-over by GO to end no later than when the transfer of
    control is completed, but CLtL says nothing about this.

    !
    Proposal (EXIT-EXTENT:MINIMAL):

    The dynamic extent of an exit, whether target or passed-over, ends as
    soon as the THROW, RETURN, or GO commences.  In the language of the
    implementation note on p.142, the extent ends at the beginning of the
    second pass.  It is an error for an UNWIND-PROTECT cleanup form executed
    during a nonlocal transfer of control to attempt to use an exit whose
    dynamic extent ended when the nonlocal transfer of control commenced.

Actually this should just say "It is an error to attempt a transfer of
control to an exit whose dynamic extent has ended."  It doesn't really
matter when it ended nor exactly who attempts the transfer of control.

    Note that this does not affect the extent of the binding of CATCH
    tags; that is, under this proposal, a THROW to a CATCH which was
    already in the process of being exited would be an error.

I think the word "extent" in the first line of this paragraph should
have been "scope", but I can see how reasonable people might disagree.
A couple of places later in the writeup use "scope" in that way in
connection with CATCH, though.

    This proposal is called "minimal" because it gives exits the smallest
    extent consistent with CLtL. A program that presumed a longer extent
    would be in error. Implementations may support longer extents for
    exits than is required by this proposal; in particular, an 
    implementation which allowed the larger extent of the MEDIUM
    proposal below would still conform.


    Proposal (EXIT-EXTENT:MEDIUM):

    The dynamic extent of an exit, whether target or passed-over, ends
    only after the exit is complete. 

I doubt that that is what you intended to say.  For example,
  (block one
     (let ((f nil))
       (unwind-protect
           (block two
	     (flet ((g () (return-from two 2)))
	       (setq f #'g)
	       (return-from one 1)))
	 (funcall f))))
Under MINIMAL, this is an error because the block named two is passed
over by the return-from one before the return-from two is executed.
Under MEDIUM, this is not an error because at the time of the funcall f,
the exit is not complete and so the dynamic extent of the block named
two has not yet ended.  It either returns 2 or goes into an infinite
loop, depending on what it means to exit twice out of an UNWIND-PROTECT.

Probably this intended to say something about how the dynamic extent of
a passed-over exit ends when control reaches a frame that was
established before the exit was established.  I don't know how to say
that in an implementation-independent way.  This difficulty in defining
a clear semantics for passed-over exits is exactly why I have always
favored MINIMAL, which constrains portable programs maximally and
constrains implementations minimally (which allows us to say as little
as possible about the implementation).

I think we must only vote on what proposals actually say, not on what we
guess they might have been intended to say.  We can of course amend them
to say something different and then vote on them.

    A transfer of control from within an UNWIND-PROTECT cleanup form
    to a point outside of the UNWIND-PROTECT causes the original control
    transfer which initiated the execution of the cleanup forms to be
->  abandonded.

    During the execution of the cleanup forms of an UNWIND-PROTECT a
    non-local exit to a point outside of the scope of the UNWIND-PROTECT,
->  but still within the dynamic scope of of the target of the original
    non-local exit succeeds, and the original pending exit is discarded.

    Where an UNWIND-PROTECT cleanup form attempts a non-local exit to a
    point outside the original non-local exit, control is passed to the
    outer exit (and the pending original non-local exit is discarded.) 

    In no case will UNWIND-PROTECT cleanup forms ever be attempted more
    than once.

This can't be true, since everyone agrees that

  (unwind-protect nil
    (loop (print 1)))

prints 1 more than once.  Also if the UNWIND-PROTECT is entered more
than once, it cleanup forms can of course be called more than once.

I think I know what you intended to say, but that isn't what you
actually said.  I'm not sure why this needs to be in the proposal at all
once the problem I pointed out above is fixed, so maybe it would be
simpler just to remove it.

    !
    Examples:

->  Each of the following programs are an error under either
    proposal:

    ;; Error: BLOCK has normal exit before RETURN
    (funcall (block nil #'(lambda () (return))))

    ;; Error: normal exit before GO
    (let ((a nil)) 
      (tagbody t (setq a #'(lambda () (go t))))
      (funcall a))

    ;; Error: TAGBODY is passed over, before GO
    (funcall (block nil
	       (tagbody a (return #'(lambda () (go a))))))


->  Each of these programs are an error under MINIMAL, but
    not under MEDIUM:

    ;;returns 2 under MEDIUM, is error under MINIMAL
    (block nil   
      (unwind-protect (return 1)
	(return 2)))

    ;;returns 2 under MEDIUM, is error under MINIMAL
    (block a    
      (block b
	(unwind-protect (return-from a 1)
	  (return-from b 2))))

    ;; returns 2 under MEDIUM, is error under MINIMAL
    (catch nil 
      (unwind-protect (throw nil 1)
	(throw nil 2)))

    ;; returns 2 under MEDIUM, is error under MINIMAL
    (catch 'a
      (catch 'b
	(unwind-protect (throw 'a 1)
	  (throw 'b 2))))
    ;; An error under MINIMAL because the catch of b is passed over by
    ;; the first throw, hence portable programs must assume its dynamic extent
    ;; is terminated.  The catch is not yet disestablished and therefore it
    ;; is the target of the second throw.

    ;; the following is an error under MINIMAL; the extent of the
    ;; inner catch terminates as soon as the throw commences, even
    ;; though it remains in scope. Thus, the throw of :second-throw
    ;; sees the inner catch, but its extent has ended.
    ;; under MEDIUM, it prints "The inner catch returns :second-throw"
    ;; and then returns :outer-catch.
    (catch 'foo
	    (format t "The inner catch returns ~s.~%"
		    (catch 'foo
			(unwind-protect (throw 'foo :first-throw)
			    (throw 'foo :second-throw))))
	    :outer-catch))


    The following program is not an error.  It returns 10.  The inner
    catch of a is passed over, but this is not case 3 because that catch
    is disestablished before the throw to a is executed.

    (catch 'a
      (catch 'b
	(unwind-protect (1+ (catch 'a (throw 'b 1)))
	  (throw 'a 10))))

The way MEDIUM is actually written, this seems to return 11 under
MEDIUM, because the throw to a goes to the inner catch.  But I think you
intended for it to return 10.

    The following cases are errors under MINIMAL, and have
    the following interpretation under MEDIUM:

The second case is not an error under MINIMAL.  It behaves
identically in MINIMAL and MEDIUM.

    In 
	(CATCH 'FOO
	  (CATCH 'BAR
	      (UNWIND-PROTECT (THROW 'FOO 3)
		(THROW 'BAR 4)
		(PRINT 'XXX))))

    the pending exit to tag FOO is discarded by the second THROW 
    to BAR and the value 4 is transfered to (CATCH 'BAR ...),
    which returns 4. The (CATCH 'FOO ...) then returns the 4
    because its first argument has returned normally.
    XXX is not printed.

    In 
	(CATCH 'BAR
	  (CATCH 'FOO
	    (UNWIND-PROTECT (THROW 'FOO 3)
	      (THROW 'BAR 4)
	      (PRINT 'XXX))))

    the value 4 is returned from the (CATCH 'BAR ...); XXX is not printed.
	. 3 evaluates to itself and is saved by THROW which begins
	  searching for tag FOO. 
	. 4 evaluates to iself and is saved by THROW which begins
	  searching for tag BAR.
	. It is not an error, even though the
	  BAR tag is not found within the local dynamic scope of

I don't know what a "local dynamic scope" is.

	  the UNWIND-PROTECT cleanup form containing (THROW 'BAR 4)
	  but is found outside the scope of the target of the 
	  pending THROW to FOO.

    Rationale:

    For MINIMAL: Giving exits the smallest extent consistent with CLtL
    maximizes freedom for implementations; there are few applications,
    if any, that require a longer extent.

->  For MEDIUM: Giving exits a longer exent has cleaner semantics.

    Current practice:

    Both implementations of Symbolics Genera (3600 and Ivory) end the extent
    of a target block or catch at the moment the values are returned, and
    end the extent of a passed-over exit at the moment the THROW, RETURN, or
    GO commences.  This choice of extent maximizes efficiency within the
    particular stack structure used by these implementations, by avoiding
    the need to retain the control information needed to use a passed over
    exit through the transfer of control.  Genera signals an error if an
    attempt is made to use an exit that has been passed over.

    In some implementations, the extent of a target exit lasts until the
    exit has been completed; in those implementations, it is possible for a
    throw or non-local exit to be effectively "stopped" by an UNWIND-PROTECT
    cleanup clause that performs a nonlocal transfer of control to a
    passed-over exit.

    Some implementations crash or otherwise generate garbage code for
    non-local exits from cleanup clauses of UNWIND-PROTECT.

    Cost to Implementors:

    No currently valid implementation will be made invalid by the MINIMAL
    proposal. Some implementors may wish to add error checks if they
    do not already have them.

    MEDIUM would have a high cost for those implementations that currently
    have shorter exent.

    Cost to Users:

    Most user programs don't do this, so there is likely little cost
    of converting existing code in any case. In any case, current implementations
    differ enough that this issue ostensibly does not
    affect current portable programs. Some users might have code that
    relies on the "unstoppable loops" that can be created with the MEDIUM
    proposal.

    Benefits:

    Either proposal would make Common Lisp more precisely defined.

    Cost of non-adoption :

    The semantics of exits will remain ambiguous.


    Esthetics:

    Precisely specifying the meaning of dynamic extent improves the language.
    Leaving implementations free to implement a longer extent if they choose
    can be regarded as unesthetic, but consistent with Common Lisp philosophy.
    Having a CATCH that is in scope even though its extent has ended may
    seem unesthetic, but it is consistent with how BLOCK behaves.

    Discussion:

    This issue is controversial. It was first discussed under the issue 
    named UNWIND-PROTECT-CLEANUP-NON-LOCAL-EXIT. The issue was recast as
    the more global one of "extent of exits" rather than the specific 
    one of "what happens if a cleanup in an UNWIND-PROTECT does a non-
    local exit", but the problem cases for both topics are the same.

    The goal of the MINIMAL proposal is to clarify the ambiguity in CLtL while
    minimizing changes to the current situation. The MEDIUM proposal
    defines the extent of an exit to end at the last moment possible
    within some particular reference implementation.  It has
    a cost to implementors whose implementation is not identical to the
    reference implementation.  Another alternative proposal, not considered
    here, would duck the issue by outlawing all nonlocal exits from UNWIND-PROTECT
    cleanup forms. That alternative would have a substantial cost to some users.

    Scheme is cleaner: it avoids this issue by specifying that the extent
    of an exit never ends.

    An argument for the MEDIUM proposal was made based on the example:

      (block foo
	(block bar
	  (unwind-protect
	      (return-from foo 'foo)
	    (return-from bar 'bar))))

    Since there is no reason for FOO and BAR not to be treated interchangably,
    calling this an error would be inappropriate. 

This is no argument against the MINIMAL proposal.  Suppose FOO and BAR
are to be treated interchangeably.  Then the above example should be
equivalent to

      (block foo
	(unwind-protect
	    (return-from foo 'foo)
	  (return-from foo 'bar)))

In fact these two examples are equivalent under both proposals.  Under
MEDIUM they both return BAR.  Under MINIMAL they are both errors.

    It was argued that the MINIMAL proposal is equivalent to practically
    outlawing non-local exits from UNWIND-PROTECT cleanup clauses, because
    there is no general way to determine the target of the nonlocal exit
    that caused the cleanup clause to be invoked. 

    CLtL never says in what dynamic environment cleanup forms of
    UNWIND-PROTECT are executed.  The implementation note on p.142 may have
    been intended to cover this, but since it doesn't define the term
    "frame" that it uses, it doesn't actually say anything.  The extent of
    dynamic-extent entities other than exits should be the
    subject of a separate proposal. It was argued that the likely
    resolution of those issues would be more consistent with the
    MEDIUM proposal than MINIMAL.

    The following example was offered as an argument against MINIMAL. Given:

	(block nil
	  (handler-case
	      (unwind-protect (return)
		(error "foo"))             ;probably an error, under the proposal
	    (error ()
	      (print "foo"))))

    If the ERROR handler has the same scope and extent a CATCH in the same place
    would have (and that seems reasonable, though I'm not certain that the
    condition system specifically requires that interpretation), then the handler
    will be apparent to the call to ERROR, but will no longer be a valid target
    (its extent was exited by the RETURN in the UNWIND-PROTECT body).

"exited" in the preceding line should be "ended" or "passed over".

This is true, but interchanging the first two lines of the example would fix it.
It is quite intentional that the MINIMAL proposal says this style of coding
is non-portable.  In current practice it is non-portable.