🚀 go-pugleaf

greg@harvey.qualcomm.com (Greg Noel) writes:
>David Chase <chased@rbbb.Eng.Sun.COM> writes:
>>This is not correct.  Nested functions are not expensive to implement.

>OK, how do you do it so that:
>     o	It's efficient enough on a wide class of architectures that I don't
>	care about the overhead involved in using it.

The best trick in my book uses run-time code generation.  There are
actually two ways to do this, depending upon the cache-flush penalty.
You can either generate the code in-line (in your activation record)
or you can keep a cache of code fragments.  The cached-fragment scheme
is probably cheapest -- that's probably fewer than a dozen RISC
instructions to get your hands on a "nested" function.

>     o	There is no penalty for _not_ using it.

That's the appeal of run-time code generation -- function pointers
remain as function pointers always were.

>     o	It invokes the subroutine in the context where its address was
>	evaluated, even under recursion.

Since this is necessary for correctness, it goes without saying.
See the definition of Modula-3.

>     o	It's thread-safe; that is, the compiler doesn't create any global
>	variables or the like behind my back.

Since this is necessary for correctness, it goes without saying.
See the definition of Modula-3.

>     o	The address of the function is compatible with a ``standard''
>	function variable.

This is necessary for correctness, but language designers like to wimp
out and let nested functions become dangling references in the same
way that pointers to auto variables can become dangling references.
This is not a new problem.  Garbage collection would solve both
problems, but that is another discussion.

>Note that if you can do this, it would be possible to bind a non-static class
>member function and a class object together, assign that to a ``standard''
>function variable, and arrange that when the function variable was invoked,
>the class member function would be invoked on the object.  The mechanisms
>involved are equivalent.

Of course.  I would hope that this would happen, since I have needed
to do it more than once.

>>I speak as someone who has done it.

> I'm willing to be proven wrong, but it will take more than just an
> assertion that it can be done.

Run-time code generation works well here.  For 68K and 386, the
compile-time version of a nested function has an additional first
parameter (the parameter is supplied by the run-time version of the
function, which pushes it into the stack).  For Sparc, one of the
global registers (2,3,4 are available) is used to pass a hidden
parameter to the compiler-time version of the routine.  I described
this in much gorier detail in an earlier post, including instruction
sequences.  I wouldn't be surprised if GCC used this trick.

Obviously, the compiler must take note of which variables are accessed
by the nested function, and which are not, and which are altered by
the nested function, and which are not.  There's several choices for
how you might represent the shared variables, once you've decided to
use the RTCG trick to get the data to the actual code that you want to
execute (I think Andrew Appel and Trevor Jim wrote a fairly through
Princeton tech report on this sometime within the past 5 years.)

>Don't get me wrong---I would like to have nested functions.  But the same
>logic that prevented the adoption of an exponention operator is in effect
>here: it can be ``unexpectedly'' costly.

I don't think this is unexpectedly costly, having implemented it and
used it in the past.  There are costs, but the run-time code
generation trick restricts them to the actual use of nested functions,
and that cost is typically not greater than the cost of faking the
nested function with objects.

David Chase
Sun