Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1142 > unrolled thread

Is multi-level function return possible?

Back to article view | Back to comp.compilers

Contents

  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

Page 1 of 3  [1] 2 3  Next page →

#1142 — Is multi-level function return possible?

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.

I don't recall this being discussed in the dragon book, perhaps because it's
just a silly idea. But implementing the multi-level break got me curious
whether it's possible.
[Sure, you can do it.  PL/I let you jump out of a routine and I think Algol60
may have, too.  You just need to keep your stack frames sufficiently linked
so that you can find the one you want and unwind everything below it.  Look
at the way Algol and Pascal reference variables in blocks outside the current
routine and you'll get most of what you need. -John]

[toc] | [next] | [standalone]

#1143

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.

[toc] | [prev] | [next] | [standalone]

#1144

noitalmost <noitalmost@cox.net> writes:
>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.

Yes, in Pascal you can goto a label that is in a containing procedure
or function, even across several levels.  That is a very rarely used
feature of the language, and Wirth removed it (along with goto) from
his later languages.

The more common feature is to have exceptions that you can throw and
that can be caught in a function/procedure/method several levels
further out.

The difference between these languages features is that Pascal's goto
is statically scoped, whereas exceptions are dynamically scoped.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#1147

On 2014-03-11, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> noitalmost <noitalmost@cox.net> writes:
>>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.
>
> Yes, in Pascal you can goto a label that is in a containing procedure
> or function, even across several levels.  That is a very rarely used

I.e. you can jump out of a "downward funarg" closure in that original Pascal,
back to the parent environment, just like in Lisp.

> feature of the language, and Wirth removed it (along with goto) from
> his later languages.

Then Cardelli added lexically scoped symbol macros to Modula-3, not
unlike (symbol-macrolet ...) in the form of the new, improved version
of the WITH statement.

Maybe one day these Pascalites will assemble a complete language that
has everything at the same time.


> The more common feature is to have exceptions that you can throw and
> that can be caught in a function/procedure/method several levels
> further out.
>
> The difference between these languages features is that Pascal's goto
> is statically scoped, whereas exceptions are dynamically scoped.

But if Pascal had upward funargs (closures that can be returned from the scope
in which they are created), then the goto, though lexically scoped, would have
have a test to detect that its target is no longer in the dynamic scope.

I.e. it's not really purely lexical. Resolving the label identifier is lexical,
but the situation is dynamic.

Also, never mind full closures: consider the situation that the function is
simply recursive.

Recursion means there is possibly more than one activation of the environment
which contains the target label of the goto. Which activation is chosen as the
jump target? Does the goto return to the same recursion level in which
the closure was created or does it just find the innermost activation of
that label?

If the closure jsut goes to the innermost block which has the label,
then the target resolution is in fact dynamically scoped, even though
the label is lexical. (Because the target block is not lexically captured
along with the closure, but chosen just from whatever is visible at the
time the goto takes place.)

[toc] | [prev] | [next] | [standalone]

#1149

Kaz Kylheku <kaz@kylheku.com> writes:
>On 2014-03-11, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> noitalmost <noitalmost@cox.net> writes:
>> The difference between these languages features is that Pascal's goto
>> is statically scoped, whereas exceptions are dynamically scoped.
>
>But if Pascal had upward funargs (closures that can be returned from the scope
>in which they are created), then the goto, though lexically scoped, would have
>have a test to detect that its target is no longer in the dynamic scope.

Pascal does not have full closures.  You can pass a function/procedure
as a parameter (which allows cool things), but that's all; no general
function/procedure variables, no and no returning of
functions/procedures or otherwise treating them as values.

>Also, never mind full closures: consider the situation that the function is
>simply recursive.
>
>Recursion means there is possibly more than one activation of the environment
>which contains the target label of the goto. Which activation is chosen as the
>jump target? Does the goto return to the same recursion level in which
>the closure was created or does it just find the innermost activation of
>that label?
>
>If the closure just goes to the innermost block which has the label,
>then the target resolution is in fact dynamically scoped, even though
>the label is lexical. (Because the target block is not lexically captured
>along with the closure, but chosen just from whatever is visible at the
>time the goto takes place.)

From what I remember it's truly lexically scoped (and the mechanism to
implement it is the same as for local variables), but if you want to
make sure, you can read the spec.

But thinking about it makes me wonder: Can you come up with an example
that shows the difference?  And can you come up with a useful example
where there is a difference?

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/
[Yes, it's lexically scoped.  Pascal functions use displays, which
keep the frame pointers of all of the lexically enclosing blocks with
variables visible in a routine, which are filled in by chasing
pointers to the calling function's display.  So in case of recursion,
the display has the most recent frame pointer.  You can't get much
more complicated than this and still use a single stack.  -John]

[toc] | [prev] | [next] | [standalone]

#1150

> [Yes, it's lexically scoped.  Pascal functions use displays, which
> keep the frame pointers of all of the lexically enclosing blocks with
> variables visible in a routine, which are filled in by chasing
> pointers to the calling function's display.  So in case of recursion,
> the display has the most recent frame pointer.  You can't get much
> more complicated than this and still use a single stack.  -John]

None of the Pascal compilers I worked on used a display; instead they chased
the static chain if necessary to access a non-local.

--
Bill Findlay
with blueyonder.co.uk;
use  surname & forename;
[Oh, right.  That works, too, and is probably better if non-local references
are uncommon. -John]

[toc] | [prev] | [next] | [standalone]

#1151

On 3/13/2014 10:05 AM, Anton Ertl wrote:
<snip>

> From what I remember it's truly lexically scoped (and the mechanism
> to implement it is the same as for local variables), but if you want
> to make sure, you can read the spec.
>
> But thinking about it makes me wonder: Can you come up with an
> example that shows the difference?  And can you come up with a useful
> example where there is a difference?

The standard practical example is an integration package which takes
an argument function to integrate over the range. The argument
function is not in the scope of the integration package. It may not
even be in the scope of the caller of the integration routine.
Consequently it must use either a closure (so it can be a lambda) or
the function-pointer format must contain a static link pointer as well
as a code pointer. A display doesn't help this.

True closures are more powerful than static nesting, because a closure
can be invoked even when the scope in which it was created has exited,
which cannot be done with static nesting. However this means that the
representation of a closure has unbounded size (and so must use the
heap), whereas static nesting has bounded size, e.g. two pointers. It
also has unbounded lifetime, so it requires garbage collection. As an
alternative, some languages define a poor-man's-lambda that cannot
escape its scope of creation. That lets the PML be allocated on the
stack (an alloca) and requires neither heap nor garbage collection, but
is less powerful than true closures.

In addition, one can create an unbounded number of closures with
different bindings, whereas the number of statically nested functions is
statically bound. In effect, a statically bound function receives its
bindings as global (to it) variables passed by reference, whereas a
closure receives its bindings as arguments passed by value. Thus
statically nested functions have all the well-known issues of passing
arguments via global data, while closures avoid that.

The C++ approach of creating a temporary class to hold the bindings and
then using operator() to invoke the result is a syntactic variant of a
closure rather than of statically nested functions. However, the
temporary class is a nuisance to write, so recent C++ has provided more
convenient syntax to create lambda/closures.

[toc] | [prev] | [next] | [standalone]

#1156

Ivan Godard <ivan@ootbcomp.com> wrote:
> On 3/13/2014 10:05 AM, Anton Ertl wrote:
<snip>

>> But thinking about it makes me wonder: Can you come up with an
>> example that shows the difference?  And can you come up with a useful
>> example where there is a difference?

> The standard practical example is an integration package which takes
> an argument function to integrate over the range.

Integration routines and minimization routines go back to at least
Fortran II, when FUNCTION and SUBROUTINE were added. (Fortran I used
ASSIGN and assigned GOTO as a sort-of internal subroutine call, along
with "extended range of the DO" so you could use it inside DO loops.)

> The argument > function is not in the scope of the integration
> package. It may not even be in the scope of the caller of the
> integration routine.  Consequently it must use either a closure (so
> it can be a lambda) or the function-pointer format must contain a
> static link pointer as well as a code pointer. A display doesn't
> help this.

Reasonably often you don't need to pass any other data to the called
routine, but in Fortran you use COMMON (or, in newer Fortran, module
variables).

The other possiblity is for the integration (or other) routine to pass
data, such as a pointer, through to the called routine.  That seems to
be rare.

PL/I internal procedures can be passed in this way, and reference data
from the procedure that they are internal to.  This ability has, I
believe been added to Fortran in the 2008 standard. (Internal
procedures were added earlier, but couldn't be used this way.)  As I
understand it, this isn't quite what closure allows, but works most of
the time in practical use.

The other place this is commonly needed is in sort programs, such
as C's qsort(). I did it once using a C file scope (static) variable.

> True closures are more powerful than static nesting, because a closure
> can be invoked even when the scope in which it was created has exited,
> which cannot be done with static nesting. However this means that the
> representation of a closure has unbounded size (and so must use the
> heap), whereas static nesting has bounded size, e.g. two pointers. It
> also has unbounded lifetime, so it requires garbage collection. As an
> alternative, some languages define a poor-man's-lambda that cannot
> escape its scope of creation. That lets the PML be allocated on the
> stack (an alloca) and requires neither heap nor garbage collection, but
> is less powerful than true closures.

I am not so sure what you mean by "static" here. The Fortran COMMON or
module variable are static allocated, and so will fail when reentrant
code is needed, such as recursion.  The PL/I version is designed to
work properly in the case of recursion, such that data from the
appropriate instance is seen by the called routine.

As I understand it, most of the PL/I language was defined before
anyone tried writing a compiler for it. Getting this right may have
complicated the implementation. Otherwise, is hard to see why it took
until 2008 for Fortran to allow it.  (and still maybe not implemented
in any compilers.)

> In addition, one can create an unbounded number of closures with
> different bindings, whereas the number of statically nested functions is
> statically bound. In effect, a statically bound function receives its
> bindings as global (to it) variables passed by reference, whereas a
> closure receives its bindings as arguments passed by value. Thus
> statically nested functions have all the well-known issues of passing
> arguments via global data, while closures avoid that.

I am still not sure how this works in the case of recursion.

> The C++ approach of creating a temporary class to hold the bindings and
> then using operator() to invoke the result is a syntactic variant of a
> closure rather than of statically nested functions. However, the
> temporary class is a nuisance to write, so recent C++ has provided more
> convenient syntax to create lambda/closures.

-- glen
[Closures are dandy, but they need a garbage collected heap of stack
frames.  In many environments, e.g., embedded devices, that's too
slow or takes too much space. -John]

[toc] | [prev] | [next] | [standalone]

#1152

On Tue, 11 Mar 2014 22:15:36 +0000 (UTC), Kaz Kylheku
<kaz@kylheku.com> wrote:

>Recursion means there is possibly more than one activation of the environment
>which contains the target label of the goto. Which activation is chosen as the
>jump target? Does the goto return to the same recursion level in which
>the closure was created or does it just find the innermost activation of
>that label?

YMMV, but ISTM that recursion is not really relevant to the issue:
lexical scoping by itself introduces the potential for name shadowing
and the rule always has been to reference the instance which is
defined "closest" to the point of use.  The addition of recursion
simply makes locating that closest instance - at least in part - a
runtime operation rather than a compile time operation.

We can argue about whether the type should be part of the name: e.g.,
if x:string shadows x:integer then does an arithmetic operation on x
find x:integer or does it fail for incompatible types?  But this is a
discussion at a different level.


>If the closure jsut goes to the innermost block which has the label,
>then the target resolution is in fact dynamically scoped, even though
>the label is lexical. (Because the target block is not lexically captured
>along with the closure, but chosen just from whatever is visible at the
>time the goto takes place.)

Your Lisp is showing 8-) ... "nested function" is not synonymous with
"closure".

Standard Pascal did have not have closures: you could pass a function
by name as an argument to another, but its definition had to be
visible both at the point of passing the name and at the point of
invocation [through the aliasing argument].

Various extended Pascals have provided function types and function
pointers - mostly with the caveat that the pointers could be used only
where their function definition was visible.  GPC, however, has
implemented real closures: AFAIK they can passed only by name and not
stored, but they have dynamic extent and can be invoked where they are
not visible lexically.

George

[toc] | [prev] | [next] | [standalone]

#1157

On 2014-03-14, George Neuner <gneuner2@comcast.net> wrote:
> On Tue, 11 Mar 2014 22:15:36 +0000 (UTC), Kaz Kylheku
><kaz@kylheku.com> wrote:
>
>>Recursion means there is possibly more than one activation of the environment
>>which contains the target label of the goto. Which activation is chosen as the
>>jump target? Does the goto return to the same recursion level in which
>>the closure was created or does it just find the innermost activation of
>>that label?
>
> YMMV, but ISTM that recursion is not really relevant to the issue:
> lexical scoping by itself introduces the potential for name shadowing
> and the rule always has been to reference the instance which is
> defined "closest" to the point of use.  The addition of recursion
> simply makes locating that closest instance - at least in part - a
> runtime operation rather than a compile time operation.

But we have the option that we don't want the closest instance, since
this isn't lexical scope.

E.g. restarts in Common Lisp. compute-restarts can return all the
restarts that are visible. There can be more than one which share teh
same symbol (for instance due to recursion). You can pick one that
isn't the first one on the list, and then invoke-restart.

CLISP example session:

  $ clisp -q
  [1]> (compute-restarts)
  (#S(RESTART :NAME ABORT
      :TEST #<COMPILED-FUNCTION SYSTEM::DEFAULT-RESTART-TEST>
      :INVOKE-TAG NIL
      :INVOKE-FUNCTION #<COMPILED-FUNCTION SYSTEM::MAIN-LOOP-1-1>
      :REPORT #<COMPILED-FUNCTION SYSTEM::MAIN-LOOP-1-2>
      :INTERACTIVE #<COMPILED-FUNCTION SYSTEM::DEFAULT-RESTART-INTERACTIVE>
      :MEANINGFULP T))

Only one restart is visible from the repl.

Let's make an error to get into a nested error-recovery repl, then
see what restarts are visible:

  [2]> (+ "a" 3)

  *** - +: "a" is not a number
  The following restarts are available:
  USE-VALUE      :R1      Input a value to be used instead.
  ABORT          :R2      Abort main loop
  Break 1 [3]> (compute-restarts)
  (#S(RESTART :NAME ABORT
      :TEST #<COMPILED-FUNCTION SYSTEM::DEFAULT-RESTART-TEST>
      :INVOKE-TAG NIL
      :INVOKE-FUNCTION #<COMPILED-FUNCTION SYSTEM::BREAK-LOOP-2-1>
      :REPORT #<COMPILED-FUNCTION SYSTEM::BREAK-LOOP-2-2>
      :INTERACTIVE #<COMPILED-FUNCTION SYSTEM::DEFAULT-RESTART-INTERACTIVE>
      :MEANINGFULP T)
   #S(RESTART :NAME USE-VALUE
      :TEST #<COMPILED-FUNCTION SYSTEM::DEFAULT-RESTART-TEST> :INVOKE-TAG NIL
      :INVOKE-FUNCTION #<COMPILED-FUNCTION SYSTEM::CHECK-VALUE-5>
      :REPORT #<COMPILED-FUNCTION SYSTEM::CHECK-VALUE-3>
      :INTERACTIVE #<COMPILED-FUNCTION SYSTEM::CHECK-VALUE-4> :MEANINGFULP T)
   #S(RESTART :NAME ABORT
      :TEST #<COMPILED-FUNCTION SYSTEM::DEFAULT-RESTART-TEST>
      :INVOKE-TAG NIL
      :INVOKE-FUNCTION #<COMPILED-FUNCTION SYSTEM::MAIN-LOOP-1-1>
      :REPORT #<COMPILED-FUNCTION SYSTEM::MAIN-LOOP-1-2>
      :INTERACTIVE #<COMPILED-FUNCTION SYSTEM::DEFAULT-RESTART-INTERACTIVE>
      :MEANINGFULP T))

Now there are two restarts with the same name.  If we do
(invoke-restart 'abort), of course it will go to the innermost one.
But we can search the list of restarts for the other one and do
invoke-restart on the restart object.

> We can argue about whether the type should be part of the name: e.g.,
> if x:string shadows x:integer then does an arithmetic operation on x
> find x:integer or does it fail for incompatible types?  But this is a
> discussion at a different level.

I would not go farther than separation of function and value bindings.

Separate namespaces for strings and numbers seems ... hokey.

It erquires static typing, with no overloading. What if x is an integer in one
scope, and a string in another scope, and then we call foo(x) which is
overloaded for strings and integers.  Probably we resolve in favor of the inner
nesting. Then, of what value is the separation if we abandon it at the
slightest appearance of a problem. :)

>>If the closure jsut goes to the innermost block which has the label,
>>then the target resolution is in fact dynamically scoped, even though
>>the label is lexical. (Because the target block is not lexically captured
>>along with the closure, but chosen just from whatever is visible at the
>>time the goto takes place.)
>
> Your Lisp is showing 8-) ... "nested function" is not synonymous with
> "closure".

It can be if everything is downward. Downward funargs still close over
their lexical environment; they coach which arries the bindings,
however, turns into a pumpking when the closure tries to escape.

I'm only thinking of the downward situation in this whole thread;
whose main topic is non-local returns! Jumping out to a closure whose
creation environment is still active and which is not set up to try to
escape.

> Standard Pascal did have not have closures: you could pass a function
> by name as an argument to another, but its definition had to be
> visible both at the point of passing the name and at the point of
> invocation [through the aliasing argument].

Okay, forget Pascal then with these bizarre restrictions. Let's
pretend that "Pascal" really means "GNU C" (with its local functions).

http://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html

GNU C has real downard funargs, a.k.a. non escaping closures.

(I thought Pascal was like this; but if not, it's too broken to
warrant another thought.)

So your comment could have said "your GNU C is showing". :)

[toc] | [prev] | [next] | [standalone]

#1160

On 2014-03-14, Kaz Kylheku <kaz@kylheku.com> wrote:

>> Standard Pascal did have not have closures: you could pass a function
>> by name as an argument to another, but its definition had to be
>> visible both at the point of passing the name and at the point of
>> invocation [through the aliasing argument].
>
> Okay, forget Pascal then with these bizarre restrictions. Let's
> pretend that "Pascal" really means "GNU C" (with its local functions).

> http://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html
>
> GNU C has real downard funargs, a.k.a. non escaping closures.
>
> (I thought Pascal was like this; but if not, it's too broken to
> warrant another thought.)
>
> So your comment could have said "your GNU C is showing". :)

Syntax is similar, but most Pascal implementations don't use
trampolines, but simply expand the procedure type to be wider (frame
pointer and address).

Gnu Pascal inherited the C school of thought, and uses trampolines
afaik to keep function pointers (single) pointers at all cost.

The earlier mentioned Delphi anonymous functions (closure-likes)
internally are ref counted interfaces to my best knowledge.

P.s. quickreading your URL I didn't really see if GNU C can have
multiple levels of nesting. Pascal can.
[Yes, it can. -John]

[toc] | [prev] | [next] | [standalone]

#1166

George Neuner <gneuner2@comcast.net> writes:
>YMMV, but ISTM that recursion is not really relevant to the issue:
>lexical scoping by itself introduces the potential for name shadowing
>and the rule always has been to reference the instance which is
>defined "closest" to the point of use.  The addition of recursion
>simply makes locating that closest instance - at least in part - a
>runtime operation rather than a compile time operation.

Take a look at the example from Bakul Shah in
http://compilers.iecc.com/comparch/article/14-03-042.  There the "goto
lab1" skips one invocation of top to jump into a top frame that is
further out.  There is no more run-time operation necessary than
without recursion: the goto just follows the static link chain for as
many levels as are lexically between the goto and the target label (in
this case one), that's all.

>Standard Pascal did have not have closures: you could pass a function
>by name as an argument to another, but its definition had to be
>visible both at the point of passing the name and at the point of
>invocation [through the aliasing argument].

Not sure what you mean with "the aliasing argument", but the original
name need not be visible at the point of invocation.  Pascal's
function/procedure arguments have many properties of full closures, in
particular access to variables of enclosing scopes, but unlike
first-class closures, you could not store them into variables or pass
them out from functions.

Language design note: Given that nested functions have fallen out of
favour in the Algol-family world (in C and its offspring), I wonder if
they only really gain usefulness when combined with first-class
closures.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#1167

On 2014-03-16, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Language design note: Given that nested functions have fallen out of
> favour in the Algol-family world (in C and its offspring), I wonder if
> they only really gain usefulness when combined with first-class
> closures.

It's more the rise of OOP in Pascal than need for a real closure. This
functionality was mostly used to parameterize code with other code,
something that was steered more in the direction of OOP and
inheritance/virtual methods.

Fun fact is that Turbo Pascal, while not supporting the functionality, still
used it for a generic ForEach functionality on its container type. Using
some assembler frame trickery.

[toc] | [prev] | [next] | [standalone]

#1168

On 16/03/14 17:19, Anton Ertl wrote:
> Language design note: Given that nested functions have fallen out of
> favour in the Algol-family world (in C and its offspring), I wonder if
> they only really gain usefulness when combined with first-class
> closures.

	They are also useful for variable hiding and space reclamation.
If all functions are at the outermost level, then they can only access
local or global variables, and so can communicate with each other only
via globals or parameters.  Global space can never be reclaimed except
through sophisticated optimisations, and parameters have a run-time cost.
I assume that the designers of "C and its offspring" decided that the
cost of single-level functions was outweighed by the relative ease of
compilation and code generation.  Whether that was a correct decision,
I don't know, but it was a major hassle for me in the days when we had
to convert a mass of Algol code to C.

--
Andy Walker,
Nottingham.

[toc] | [prev] | [next] | [standalone]

#1169

On 16/03/2014 19:45, "Andy Walker" <news@cuboid.co.uk> wrote:

> On 16/03/14 17:19, Anton Ertl wrote:
>> Language design note: Given that nested functions have fallen out of
>> favour in the Algol-family world (in C and its offspring), I wonder if
>> they only really gain usefulness when combined with first-class
>> closures.

It would be wrong to imply that "the Algol-family world" consists of "C and
its offspring".  Algol has many descendants that have have remained more
loyal to their family traditions, Ada 2012 first among them.

> They are also useful for variable hiding and space reclamation.
> If all functions are at the outermost level, then they can only access
> local or global variables, and so can communicate with each other only
> via globals or parameters.  Global space can never be reclaimed except
> through sophisticated optimisations, and parameters have a run-time cost.

Exactly.  Nested functions also permit information hiding and the tidying of
code by the introduction of abstractions that have only local relevance.

--
Bill Findlay
with blueyonder.co.uk;
use  surname & forename;
[C fakes it with module static, but I take your point. -John]

[toc] | [prev] | [next] | [standalone]

#1170

Bill Findlay <yaldnif.w@blueyonder.co.uk> writes:
>On 16/03/2014 19:45, "Andy Walker" <news@cuboid.co.uk> wrote:
>
>> On 16/03/14 17:19, Anton Ertl wrote:
>>> Language design note: Given that nested functions have fallen out of
>>> favour in the Algol-family world (in C and its offspring), I wonder if
>>> they only really gain usefulness when combined with first-class
>>> closures.
>
>It would be wrong to imply that "the Algol-family world" consists of "C and
>its offspring".  Algol has many descendants that have have remained more
>loyal to their family traditions, Ada 2012 first among them.

True.  But I find it more revealing what features were added back in
after the C branch of the family went through the B bottleneck.
Keeping a feature may just be loyalty, but adding it back after it had
been removed says something about what the language designer thought
about the usefulness of the feature.

Ok, let's look at the arguments I have seen until now:

Name management (information hiding, variable hiding): Languages like
Modula-2 added additional mechanisms for that despite having nested
procedures; C++ did not add nested functions, but did add name spaces.
That argument is not very convincing to me.

"Parameters have a run-time cost": So has access to non-local
variables.  Languages that put high priority on run-time cost like C
and C++ did not add that feature (except GNU C), so this argument did
not convince their designers.  And it does not convince me.

Hassle when converting Algol to C: I can believe that, but that does
not tell me about the value of the feature in other contexts.

Did I miss any arguments?

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#1175

On 18/03/14 17:36, Anton Ertl wrote:
> Keeping a feature may just be loyalty, but adding it back after it had
> been removed says something about what the language designer thought
> about the usefulness of the feature.

	Well, it certainly implies that the designer [or the committee!]
is admitting to a mistake.  *Not* adding it back in may be because the
feature really was useless, because the particular user base sees no
need for the feature, because the feature is too expensive, or because
of pig-headedness.  I expect contributors could write long articles of
examples of each of these ....

[...]
> "Parameters have a run-time cost": So has access to non-local
> variables.

	That depends on the machine and compiler.  The first compiler I
used extensively [for Atlas Autocode] accessed variables at lexical
depth N by offsetting from register N, so all variables were accessed
at exactly the same cost.  But that would have been difficult on a
machine with few registers.

[...]
> Did I miss any arguments?

	Not so much an argument as a philosophy.  You can ask about the
usefulness of a feature from several viewpoints.  Is it needed?  Is it
something the users want?  Is it something they should want, or would
want if only they knew about it?  Is it something that would attract
new users or new applications?  Is it consonant with the rest of the
language?  Is it easy to parse and to generate code for?  Is it easy
to explain?  Is it efficient?  And so on.  You seem to be approaching
your question from the point of view of a compiler writer;  I'm more
interested in writing programs.  Writing programs is itself a very
personal activity depending on experience and context, so different
people may perfectly reasonably have very different attitudes to any
particular feature.

	In other words, "Are nested functions useful?" does not have
a clear and definite answer.  They're useful to me [marginally so, and
there are things I would add to C more urgently, if urgency makes any
sense after 40-ish years];  I guess they'd be more useful to those with
a more Pascal-oriented background;  they were clearly of very little
use to the designers of C and Unix, and by now to the many programmers
whose formative years were based around C and its derivatives.  They
can be worked around;  should we have to?

--
Andy Walker,
Nottingham.
[It occurs that a lot of the stuff people used to do with small
nested functions we now do with macros, or sometimes with complex
types that do dereferencing that used to need explicit code. -John]

[toc] | [prev] | [next] | [standalone]

#1176

Andy Walker <news@cuboid.co.uk> wrote:

(snip, someone wrote)

>> "Parameters have a run-time cost": So has access to non-local
>> variables.

(snip)

>        Not so much an argument as a philosophy.  You can ask about the
> usefulness of a feature from several viewpoints.  Is it needed?  Is it
> something the users want?  Is it something they should want, or would
> want if only they knew about it?  Is it something that would attract
> new users or new applications?  Is it consonant with the rest of the
> language?  Is it easy to parse and to generate code for?  Is it easy
> to explain?  Is it efficient?  And so on.  You seem to be approaching
> your question from the point of view of a compiler writer;  I'm more
> interested in writing programs.  Writing programs is itself a very
> personal activity depending on experience and context, so different
> people may perfectly reasonably have very different attitudes to any
> particular feature.

The first language I knew with this feature is PL/I.

As well as I understand it, the language was pretty well defined
before anyone tried writing a compiler for it. They didn't ask many
users, though attracting new users would have been important.  Seems
to me they didn't ask so much what was easy to parse (among other
features, no reserved words) and, at least the way it looks, rarely
considered how hard it might be to generate code for, or generate
efficient code for.

Many languages were defined at the same time as the first compiler
was written, with that compiler defining the language.

-- glen

[PL/I was, as I understand it, defined largely by glomming together
parts of Fortran and Cobol with some bits of Algol60.  They assumed it
would be possible to implement since all of the pieces were, although
there turned out to be a lot of dark corners where things that seemed
reasonable individually weren't so reasonable in combination. -John]

[toc] | [prev] | [next] | [standalone]

#1177 — Re: design of PL/I, was Is multi-level function return possible?

(snip, I wrote)
> As well as I understand it, the language was pretty well defined
> before anyone tried writing a compiler for it.

(snip)
> [PL/I was, as I understand it, defined largely by glomming together
> parts of Fortran and Cobol with some bits of Algol60.  They assumed it
> would be possible to implement since all of the pieces were, although
> there turned out to be a lot of dark corners where things that seemed
> reasonable individually weren't so reasonable in combination. -John]

I know Fortran and ALGOL well enough from that time, but not COBOL.

I only recently learned that COBOL only has 1D arrays, so that
arrays of structures of arrays of ... are used instead.

One feature of PL/I (F) that, as I understand it, complicated
the implementation is multitasking. I don't know COBOL well
enough to know if it was in there.

Otherwise, even without dark corners things still get somewhat
more complicated in combination.

But also, it seems that they intentionally allowed the combinations
of features to work together. When new features are added to Fortran
(and many original PL/I features have now been added) they have
restrictions on how they can be used in combination with other
features. That complicates programming, as you have to be careful
which features you use.

On the other hand, there are more PL/I compilers than Fortran 2008
compilers.

-- glen
[None of the predecessor languages had any sort of multitasking.  PL/I
F had a lot of features that directly mapped on to OS/360 features,
e.g. locate mode I/O, and multitasking was one of them.  -John]

[toc] | [prev] | [next] | [standalone]

#1185 — Re: design of PL/I, was Is multi-level function return possible?

I would just like to express my appreciation for these forrays into all the
old (pre-1980s) machines and their compilers. It really helps to put into
context features and lack thereof of languages and compilers that grew out of
that time period. There's so much that a grammar, the section in an
architecture or survey of languages textbook, and maybe an old user's guide
don't say.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.compilers

csiph-web