Issue: EXIT-EXTENT (Version 4)

[masinter.pa@Xerox.COM]

My previous attempt at merging the alternate proposals for
SETF-FUNCTION-VS-MACRO and SETF-PLACES aroused some ire.

Undaunted, this is my attempt to merge EXIT-EXIT and
UNWIND-PROTECT-NON-LOCAL-EXIT into one Issue with two
proposals. I've tried to respond to and incorporate
the comments from Sandra Loosemore and Kim Barrett.

!
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.

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. 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.

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.

This proposal is called "minimal" because it gives exits the smallest
extent consistent with CLtL.

Proposal (EXIT-EXTENT:MEDIUM):

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

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.

!
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 following cases are errors under MINIMAL, and have
the following interpretation under 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
      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. 

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).