Re: Is multi-level function return possible?

From	Kaz Kylheku <kaz@kylheku.com>
Newsgroups	comp.compilers
Subject	Re: Is multi-level function return possible?
Date	2014-03-11 05:20 +0000
Organization	Aioe.org NNTP Server
Message-ID	<14-03-021@comp.compilers> (permalink)
References	<14-03-020@comp.compilers>

Show all headers | View raw

On 2014-03-10, noitalmost <noitalmost@cox.net> wrote:
> Is this a doable thing for a Pascal-like language that is meant to be
> compiled? I have a multi-level break which works within a procedure, but the
> return across procedure boundaries seems to add a lot of complications.

This is called a "dynamic, non-local exit" in Lisp terms.

> I don't recall this being discussed in the dragon book, perhaps because it's
> just a silly idea.

It's not a silly idea; it's just not featured in the kind of Blub languages
that the dargon book concerns itself with.

On the contrary, it is a central idea in various languages.

The C longjmp function is a form of dynamic non-local exit: a bull-headed,
brute force approach that throws issues to the wind.

Lisp has dynamic non-local exits, along with the unwind-protect special
form.

Early forms of this already appeared in Lisp 2 (1967) which had a special
form called TRY: the predecessor to "try/catch". The syntax was:

  (try <variable> <try-form> <cleanup-form>)

First, <try-form> was evaluated. If no "exit statement" was encountered
during the evaluation of <try-form> (not just in that form, I think, but
in any functions called out of that form), then control would just pass
to the next form after the (try ...). But if an exit statement was
encountered, then <variable> would be set to its value, and then
<cleanup-form> would be evaluated.

Modern Lisp's unwind-protect goes like this:

  (unwind <protected-form> <cleanup-forms> ...)

it guards against all dynamic, non-local exits, such as throw/catch
or invoke-restart, return/return-from and go.

Among the "Zoo" of dynamic exits are:

* blocks:

Blocks are lexically scoped, but they can be invoked from a closure
dynamically. Demo:

   ;; define a function which calls a function

   (defun please-call (fun)
     (unwind-protect
       (funcall fun)
       (format t "terminating please-call via dynamic exit!~%")))

   ;; named block

   (block foo
     (please-call (lambda () (return-from foo 42))))

Here, the please-call function is invoked, with a function as its argument.
please-call calls that function. That function's body executes (return-from foo 42).
The function is a lexical closure in the scope of the foo block.

Whether or not this is allowed depends on whether or not the block is still
active: this is one rare use of closures in Lisp that works "downward only".

The return-from works and constitutes a dynamic local exit which has the
block foo as its "exit point". The block terminates and returns 42.
For that to happen, we have to abandon the lambda, and the please-call
function. Those stack frames are all thrown away. Moreovr, the unwind-protect
inside please-call is activated, and its cleanup form prints the message
"terminating please call via dynamic exit!".

This, however, won't work:

   (please-call (block foo (lambda () (return-from foo 42))))

Here, block foo terminates, returning the lambda function, which is then passed
as an argument to please-call, which invokes it. The (return-from foo 42)
body of the lambda executes. block foo is in the lexical scope so the
lookup resolves just fine: Lisp knows what you want to do. However, the block
has already terminated, oops! It cannot be returned from. An error results,
like "block foo is not active".

Lisp's form of goto, the go operator, can also trigger a non-local exit.

Normally it is a pedestrian thing like this:

  (tagbody
  again
    (print 10)
    (go again)) ;; endless loop

Once again, when lambdas come into the picture, there is the possiblity
that the body is re-entered by a chain of function calls. It is permissible
for a lambda to jump out of it body via GO to a surrounding tagbody label
which is still active:

  (tagbody
  again
    (please-call (lambda () (go again)))) ;; infinite loop

There is throw and catch, which isn't exception handling (Lisp has condition
handling which is based on a whole other set of primitives).

Catch establishes a symbol that serves as an exit point for a throw
which specifies the same symbol.

   (defun definitely-throws (arg)
     (throw 'foo arg))

   (defun might-throw ()
     (unwind-protect
       (definitely-throws 42))
       (format t "there she goes!~%"))

  (catch 'foo (might-throw))

Here, the catch establies a catch by the name foo. Then it calls the function
might-throw.  might-throw has an unwind protect. In the protected form it calls
a function definitely-throws with argument 42. definitely-throws throws its
argument to the foo catch.

So, what happens next is the unwind-protect kicks in and "there she goes!" is printed.

The search for the exit point continues. Finally, the catch named foo is found
and control transfers there. The catch form's execution is terminated, and it
returns the thrown value, 42.

The language C++ has exceptions, which are a non-local exit facility. The role
of unwind protect is played by class objects allocated on the stack, whose
destructors are called as part of the unwinding. The try/catch syntax
establishes exit points for exceptions, and the type system is used for
matching throws with catches. An exception that is thrown is an object of some
C++ type, and catches also specify types. The compiler and run-time support work
out where a throw goes.

Thread

Is multi-level function return possible? noitalmost <noitalmost@cox.net> - 2014-03-10 15:46 -0400
  Re: Is multi-level function return possible? Kaz Kylheku <kaz@kylheku.com> - 2014-03-11 05:20 +0000
  Re: Is multi-level function return possible? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-03-11 13:04 +0000
    Re: Is multi-level function return possible? Kaz Kylheku <kaz@kylheku.com> - 2014-03-11 22:15 +0000
      Re: Is multi-level function return possible? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-03-13 17:05 +0000
        Re: Is multi-level function return possible? Bill Findlay <yaldnif.w@blueyonder.co.uk> - 2014-03-14 01:28 +0000
        Re: Is multi-level function return possible? Ivan Godard <ivan@ootbcomp.com> - 2014-03-13 18:32 -0700
          Re: Is multi-level function return possible? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-03-14 20:27 +0000
      Re: Is multi-level function return possible? George Neuner <gneuner2@comcast.net> - 2014-03-14 02:39 -0400
        Re: Is multi-level function return possible? Kaz Kylheku <kaz@kylheku.com> - 2014-03-14 21:34 +0000
          Re: Is multi-level function return possible? Marco van de Voort <marcov@toad.stack.nl> - 2014-03-14 22:59 +0000
        Re: Is multi-level function return possible? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-03-16 17:19 +0000
          Re: Is multi-level function return possible? Marco van de Voort <marcov@toad.stack.nl> - 2014-03-16 18:39 +0000
          Re: Is multi-level function return possible? Andy Walker <news@cuboid.co.uk> - 2014-03-16 19:45 +0000
            Re: Is multi-level function return possible? Bill Findlay <yaldnif.w@blueyonder.co.uk> - 2014-03-17 16:15 +0000
              Re: Is multi-level function return possible? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-03-18 17:36 +0000
                Re: Is multi-level function return possible? Andy Walker <news@cuboid.co.uk> - 2014-03-21 02:04 +0000
                Re: Is multi-level function return possible? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-03-21 02:50 +0000
                Re: design of PL/I, was Is multi-level function return possible? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-03-21 06:43 +0000
                Re: design of PL/I, was Is multi-level function return possible? noitalmost <noitalmost@cox.net> - 2014-03-26 14:16 -0400
                Re: exception catching in PL/I, was Is multi-level function return possible? "Robin Vowels" <robin51@dodo.com.au> - 2014-03-27 21:08 +1100
                Re: Is multi-level function return possible? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-03-24 17:06 +0000
                Re: Is multi-level function return possible? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-03-24 20:01 +0000
                Re: Is multi-level function return possible? George Neuner <gneuner2@comcast.net> - 2014-03-26 04:00 -0400
                Re: Is multi-level function return possible? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-03-27 01:58 +0100
                Re: Is multi-level function return possible? Stefan Monnier <monnier@iro.umontreal.ca> - 2014-04-07 14:48 -0400
                Re: Is multi-level function return possible? Andy Walker <news@cuboid.co.uk> - 2014-03-26 12:16 +0000
                Re: Is multi-level function return possible? Andy Walker <news@cuboid.co.uk> - 2014-03-26 17:34 +0000
                Re: history of C, was Is multi-level function return possible? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-03-27 00:05 +0000
      Re: Is multi-level function return possible? Bakul Shah <usenet@bitblocks.com> - 2014-03-15 10:28 -0700
    Re: Is multi-level function return possible? George Neuner <gneuner2@comcast.net> - 2014-03-14 02:44 -0400
      Re: Is multi-level function return possible? Marco van de Voort <marcov@toad.stack.nl> - 2014-03-14 19:38 +0000
      Re: Is multi-level function return possible? Kaz Kylheku <kaz@kylheku.com> - 2014-03-14 21:36 +0000
      Re: Is multi-level function return possible? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-03-14 21:47 +0000
        Re: Is multi-level function return possible? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2014-03-15 13:34 +0100
      Re: Is multi-level function return possible? Ian Lance Taylor <ian@airs.com> - 2014-03-14 16:55 -0700
  Re: Is multi-level function return possible? George Neuner <gneuner2@comcast.net> - 2014-03-11 13:56 -0400
    Re: Is multi-level function return possible? federation2005@netzero.com - 2014-03-26 17:39 -0700
      Re: catch and throw, was Is multi-level function return possible? rpw3@rpw3.org (Rob Warnock) - 2014-03-27 04:23 +0000
        Re: catch and throw, was Is multi-level function return possible? Kaz Kylheku <kaz@kylheku.com> - 2014-03-27 05:44 +0000
        Re: catch and throw, was Is multi-level function return possible? Bakul Shah <usenet@bitblocks.com> - 2014-03-26 23:20 -0700
          Re: catch and throw, was Is multi-level function return possible? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-03-27 19:21 +0000
          Re: exception catching in PL/I "Robin Vowels" <robin51@dodo.com.au> - 2014-03-28 10:50 +1100
            Re: exception catching in PL/I Martin Ward <martin@gkc.org.uk> - 2014-04-16 14:32 +0100
          Re: catch and throw, was Is multi-level function return possible? mac <acolvin@efunct.com> - 2014-03-28 23:08 +0000
            Re: catch and throw, was Is multi-level function return possible? Ivan Godard <ivan@ootbcomp.com> - 2014-03-28 18:24 -0700
              Re: catch and throw, was Is multi-level function return possible? Kaz Kylheku <kaz@kylheku.com> - 2014-03-29 02:47 +0000
                Re: catch and throw, was Is multi-level function return possible? Ivan Godard <ivan@ootbcomp.com> - 2014-03-28 21:32 -0700
              Re: catch and throw, was Is multi-level function return possible? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-03-29 03:38 +0000
                Re: precise and imprecise, was catch and throw, was Is multi-level function return possible? Ivan Godard <ivan@ootbcomp.com> - 2014-03-28 22:12 -0700
            Re: catch and throw, was Is multi-level function return possible? Kaz Kylheku <kaz@kylheku.com> - 2014-03-29 02:07 +0000
              Re: catch and throw, was Is multi-level function return possible? Alan Bawden <alan@scooby-doo.csail.mit.edu> - 2014-03-29 02:44 -0400
            Re: PL/I exceptions, was catch and throw, was Is multi-level function return possible? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-03-29 02:40 +0000
              Re: PL/I exceptions "Robin Vowels" <robin51@dodo.com.au> - 2014-03-30 01:58 +1100
      Re: catch and throw, was Is multi-level function return possible? George Neuner <gneuner2@comcast.net> - 2014-03-28 03:52 -0400
  Re: Is multi-level function return possible? Louis Krupp <lkrupp@pssw.com> - 2014-03-11 15:16 -0600
  Re: Is multi-level function return possible? noitalmost <noitalmost@cox.net> - 2014-03-15 12:21 -0400

csiph-web