Issue: EXIT-EXTENT (Version 3)

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

    Date: 1 Oct 88 16:06 PDT
    From: masinter.pa@Xerox.COM
    
    Sigh, I started to edit this....but I'm afraid it needs more work
    than I have time for right now.

Okay, here's a revision with some wording changes.  I included most of
your edits, except for a few that simply messed up the formatting and
one that was based on a misunderstanding.  I've made the terminology
definitions much more explicit, and I hope much clearer.

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).
               Cleanup issue UNWIND-PROTECT-NON-LOCAL-EXIT is superseded
               by this one.

Category:      CLARIFICATION

Edit history:  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

Problem description:

CLtL does not specify precisely when the dynamic extent (lifetime)
of a nonlocal exit such as a CATCH, BLOCK, or TAGBODY ends.

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.  (According to CLtL p.125, there is no possibility of a
normal exit from DO.)

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

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

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.

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

Test Cases/Examples:

Each of the following programs is an error:

(funcall (block nil #'(lambda () (return))))            ;case 1

(block nil                                              ;case 2
  (unwind-protect (return)
    (return)))

(block a                                                ;case 3
  (block b
    (unwind-protect (return-from a)
      (return-from b))))

(let ((a nil))                                          ;case 1
  (tagbody t (setq a #'(lambda () (go t))))
  (funcall a))

(funcall (block nil                                     ;case 3
           (tagbody a (return #'(lambda () (go a))))))

(catch nil                                              ;case 2
  (unwind-protect (throw nil t)
    (throw nil t)))

(catch 'a                                               ;case 3
  (catch 'b
    (unwind-protect (throw 'a t)
      (throw 'b t))))

The above program is an error 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 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))))

Rationale:

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

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.

Cost to Implementors:

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

Cost to Users:

Since this is a clarification and current implementations differ, this
issue ostensibly does not affect current portable programs.

Cost of non-adoption:

The semantics of exits will remain ambiguous.

Benefits:

Common Lisp will be more precisely defined, and the precise definition
will be consistent with current practice in a way that has no cost for
implementors nor for users.

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:

One aspect of this issue, namely the particular behavior of non-local
exits from unwind protect cleanup clauses, was discussed at great
length. Some of that discussion centered around the possibility of
creating "unstoppable loops" that could not be exited, by constructs
like 
    (tagbody retry (unwind-protect ....  (go retry)))

The goal of this proposal is to clarify the ambiguity in CLtL while
minimizing changes to the current situation.  An alternative proposal
would define the extent of an exit to end at the last moment possible
within some particular reference implementation.  That alternative would
have a cost to implementors whose implementation is not identical to the
reference implementation.  Another alternative proposal 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.

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.