Issue: UNWIND-PROTECT-CLEANUP-NON-LOCAL-EXIT (Version 4)

[masinter.pa@Xerox.COM]

My notes from the subcommittee meeting that I broadcast  21 March were that
"JonL and Moon have comments. Moon has a description of stack model and unwind
as atomic."  Through the fuzz of time I'm no longer sure what I meant by that
(much less what David meant.)

I'd like to get this one out of committee, in whatever form is necessary.


!
Issue:          UNWIND-PROTECT-CLEANUP-NON-LOCAL-EXIT
References:     UNWIND-PROTECT (p140, p142, p39)
                Issue IGNORE-ERRORS, Draft error proposal.
Category:       CLARIFICATION/CHANGE
Edit history:   Version 1 by Pitman   27-Feb-87
                Version 2 by Masinter 24-Oct-87
                Version 3 by Masinter 27-Oct-87
                Version 4 by Masinter 13-Feb-88
                Version 5 by Masinter 23-May-88

Problem Description:

If a non-local return is done while in the cleanup form of an UNWIND-PROTECT,
the behavior is not always well-defined.

There are three basic cases:

Situation 0. Transfer to another point within the cleanup form.
   (UNWIND-PROTECT 3 (BLOCK NIL (RETURN 4)) (PRINT 'XXX))

There is no ambiguity about how this form is to be interpreted.
Effectively: 

      . 3 evaluates to itself, which is queued for return
        from the UNWIND-PROTECT. 
      . The BLOCK expression is entered, 4 is returned to
	it and discarded because this is a not-for-value 
	situation.
      . XXX is printed, XXX is returned by the PRINT and
	that value is discarded because this is a not-for-value
	situation.
      . The 3 which was yielded earlier is retrieved and
	returned as the value of the UNWIND-PROTECT.

Situation 1. Transfer to a point inside the point to which control 
    would have transferred.
    (CATCH 'FOO
      (CATCH 'BAR
	  (UNWIND-PROTECT (THROW 'FOO 3)
	    (THROW 'BAR 4)
	    (PRINT 'XXX))))

    This is a subject of controversy because:
    . 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.
    . Disagreement exists as to whether it is an error if the
      BAR tag is not found within the local dynamic scope of
      the UNWIND-PROTECT cleanup form containing (THROW 'BAR 4)
      but is found within the scope of the target of the 
      pending THROW (to FOO).

Situation 2. Transfer to a point outside the point to which return would
    already have been. For example:
    (CATCH 'BAR
      (CATCH 'FOO
	(UNWIND-PROTECT (THROW 'FOO 3)
	  (THROW 'BAR 4)
	  (PRINT 'XXX))))
    This is a subject of controversy because:
    . 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.
    . Disagreement exists as to whether it is an error if 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).

What is the appropriate behavior for situation 1 and situation 2 and similar
ones? For example, suppose that when WITH-OPEN-FILE tries to close the file upon
unwinding, it signals an error, and the condition handler also attempts to
throw? The question applies to all non-local transfers, whether performed by
THROW, RETURN-FROM, RETURN, GO.

Proposal (UNWIND-PROTECT-CLEANUP-NON-LOCAL-EXIT:CONTINUATION-MODEL):

In all cases, a transfer of control 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. For example, in Situation 1, the pending
seek for 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.

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.) For example, in Situation 2,
the value 4 is returned from the (CATCH 'BAR ...); XXX is not printed.

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


Rationale:

The primary issues have to do with the safety of the language vs. the uniformity
of the model behind non-local transfer of control.

Current Practice:

Some implementations generate garbage code in situations 1 and 2.  Some have
differing behavior compiled and interpreted.

Most that have implementations seem to implement the proposed semantics for
situation 2, but there is some divergence in Situation 1. For example, Spice
Lisp and Xerox implement the proposed semantics, while Symbolics Common Lisp
signals an error.

Cost to Implementors:

While require some compiler modifications in some implementations, in most
cases, that work was in order anyway since compilers may currently be doing
nothing particularly useful or defensible with the code in question. 

Cost to Users:

Most user programs don't do this so the cost of converting existing code is
probably minimal. (There is some evidence that there are programs that expect
this behavior, so there is no conversion cost for those programs.)

Benefits:

Having this situation uniformly treated seems critical:

Programs that do this accidentally should behave the same on all systems so that
bugs can be detected and fixed very early rather than being found later on a
system which disagrees.

Programs that do this on purpose generally are trying to do something fairly
intricate and really need to be able to depend on it being uniformly treated. A
portable error/signal system and debugger may be among these. For example, one
programmer created his own "top level", to which the system "abort" character
would return, by doing:

 (DEFUN MY-TOPLEVEL ()
   (TAGBODY LOOP (UNWIND-PROTECT (REALLY-MY-TOPLEVEL)
			      (GO LOOP))))

Aesthetics:

This proposal is more intuitive to programmers who reason about programs in
terms of continuation passing. It falls out of the normal scoping rules as a
consequence of the fact that the cleaup code is evaluated in the lexical and
dynamic environment in which the UNWIND-PROTECT form appears. The action of
THROW is usefully described by saying that it is just like any other function.
It happens to discard the current continuation,  run some cleanup things (like
variable unbindings and UNWIND-PROTECT actions), and transfer control elsewhere
in the program. In doing so, the function uses data structure primitives not
generally available to other programs, but it is not linguistically different
and receives no special exemption with regard to THROWs or other non-local
transfers of control done within its execution. A THROW from within an
UNWIND-PROTECT cleanup is not different than one in any other code; it discards
the ongoing action (stack unwinding) and replaces it by another action (as it
happens, another stack unwinding). The previous unwind is never resumed.

Discussion:

This issue is controversial. While the proposal included here had
a number of strong endorsements, there were also some strenuous 
objections. 

Two alternatives for situation 2 were seriously considered: that it should
signal an error, and that it the second non-local exit instead continues the
original (more extensive) one; e.g., in Situation 1, the second THROW to BAR
would be discarded in lieu of continuing the THROW to FOO.

Either of these alternatives would help prevent users from (either intentionally
or unintentionally) creating situations where it is impossible to abort a
computation with a THROW or other non-local return (e.g., an interrupt
implemented via THROW.)

For example,  given

  (LOOP
    (CATCH 'FOO
      (UNWIND-PROTECT (LOOP ... )
        (THROW 'FOO T))))

With this proposal there is no way of exiting such a form. Signalling an error
would prevent programmers from getting into this unfortunate situation.

However, similar "unstoppable" loops can be created, without resorting to
non-nested non-local transfers within UNWIND-PROTECT clauses; for example:

(LABELS ((HA () (UNWIND-PROTECT (LOOP) (HA)))) (HA))

While it would be unfortunate for a programmer to accidentally create such an
unstoppable loop, the user has pretty clearly asked to have a loop that cannot
be exited and deserves to have that request carried out.

One implication is that it is likely that programming environments need to
provide some mechanism other than THROW to stop a truly run-away computation.

An interesting example which supports this proposal is one where there are two
BLOCKs 

  (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,
signalling an error in this situation would be inappropriate. 

Guy Steele:
"We have here a classic case of the irresistible force (QUIT, dammit!)
versus the immovable mountain (UNWIND-PROTECT).  I find that the
suggestion that situation 1 produce an error, but one that IGNORE-ERRORS
won't ignore, to be at least one level of epicycle too many.

Which mechanism are to we regard as primitive: the error system or the
catch/throw system?  Or are they disjoint?  I prefer, for simplicity, a
model in which the error system can be explained. as much as possible, as a
complex thing built on top of catch, throw, and unwind-protect."

David Moon:
"Of the several alternative proposals for this issue, the only one
that seemed appropriate to me has been removed. After re-reading the
12 messages on the topic that I thought were worth saving, I get the
feeling that the issues have not really been clarified and that the
discussion is largely dealing with strawmen.  It seems like the
cleanup committee is heading towards making a serious mistake here.


Consider the form

  (loop
    (catch 'foo
      (unwind-protect (loop)
        (throw 'foo t))))

With the proposed semantics, it is impossible to stop this program
except by hitting it with two throws in rapid succession, with exactly
the right amount of delay between them so that the catch and
unwind-protect have not yet been re-established when the second throw
strikes.  Consider any program-stopping operation that aborts execution
by throwing to a catch in the top-level read-eval-print loop (control-G
in Maclisp or c-Abort in Genera; most other systems have their own
equivalent of this).  With the proposed semantics, when this throw
executes the unwind-protect cleanup handler, as it must, the throw will
be abandoned and execution will resume looping.

To me, the inability to stop a program is a much worse problem than
providing so-called correct semantics for a contrived program that
doesn't correspond to any real application.  It was suggested that the
error system might depend on the ability to abort throws like this.  If
that were demonstrated, I would change my tune, but until it's
demonstrated I am completely skeptical of the notion that any error
system would do this."