Re: Is multi-level function return possible?

Kaz Kylheku <kaz@kylheku.com>
Tue, 11 Mar 2014 05:20:27 +0000 (UTC)

          From comp.compilers

Related articles
Is multi-level function return possible? noitalmost@cox.net (noitalmost) (2014-03-10)
Re: Is multi-level function return possible? kaz@kylheku.com (Kaz Kylheku) (2014-03-11)
Re: Is multi-level function return possible? anton@mips.complang.tuwien.ac.at (2014-03-11)
Re: Is multi-level function return possible? gneuner2@comcast.net (George Neuner) (2014-03-11)
Re: Is multi-level function return possible? lkrupp@pssw.com (Louis Krupp) (2014-03-11)
Re: Is multi-level function return possible? kaz@kylheku.com (Kaz Kylheku) (2014-03-11)
Re: Is multi-level function return possible? tkowaltowski@gmail.com (Tomasz Kowaltowski) (2014-03-12)
Re: Is multi-level function return possible? anton@mips.complang.tuwien.ac.at (2014-03-13)
[29 later articles]
| List of all articles for this month |

From: Kaz Kylheku <kaz@kylheku.com>
Newsgroups: comp.compilers
Date: Tue, 11 Mar 2014 05:20:27 +0000 (UTC)
Organization: Aioe.org NNTP Server
References: 14-03-020
Keywords: code, Lisp
Posted-Date: 11 Mar 2014 16:59:47 EDT

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.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.