From: greg@harvey.qualcomm.com (Greg Noel)
Subject: Re: Use of nested functions (Was: Proposal for default scope)
Organization: Qualcomm, Inc., San Diego, CA
Date: Mon, 11 Jan 1993 21:51:11 GMT

I'm beginning to wish I'd never mentioned nested functions in my original
article.  Now people are trying to cast me in the role of opposing nested
functions, when I really don't care at all.

At the risk of being accused of going for the pun, let me put nested
functions in context.

What I said in my original article was that C++ needed some sort of type-
safe way of providing helper functions within an implementation.  The syntax
in Marko Kohtala's suggestion seemed to provide that and I thought it was
interesting in that it might provide a basis for eventually providing
modules/packages in C++.

Out of about 75 lines, most of the reaction has been due to one sentence that
pointed out that this approach might take away the need for nested functions.
Now, that was overstated; nested functions can also be used for callbacks.
That's a very different capability; if that needs to be mooted, you should
be discussing if the costs of providing it are worth the benefits.

John MAX Skaller <maxtal@extro.ucc.su.OZ.AU> writes:
>>>If a local function never has its address taken, then it does not use
>>>the full power of nested functions.
>>
>>This is a valid point, but this is exactly the part that is expensive to
>>implement.  
>
>	Not necessarily.

As long as you never take the address of a nested function, they can be
implemented very efficiently since the compiler has full control---no need
for a display or for trampolines.  Once you take the address of a nested
function, you are talking about callbacks, which are more expensive and
have some, ah, interesting interactions with other language features.  It
is my impression that these costs cannot be eliminated.

Ignoring displays and trampolines for the moment, which I think can be
pretty much confined to the functions which have nested functions, both
recursion and non-local gotos have to be handled.  These may have costs
even when nested functions are never used.

Recursion implies that the context of a pointer must be kept as part of
the pointer, which leads to either expanding the size of a function pointer
or generating trampoline code dynamically.  Expanding function pointers
would be a cost even when nested functions are not used and there are
some architectures where code cannot be generated on the fly.

Non-local gotos mean that the compiler has to be able to unwind the stack
to get to the label being referenced.  C++ already has two mechanisms to
unwind the stack, and one of them is a time-encrusted grotty hack; I don't
know if we need a third.

I'm sure there are other interactions; those are just the first two that
popped to mind.

Returning to displays and trampolines, the usual implementation of displays
uses implicit static variables, which means the code is not thread-safe.
If static variables are not used, an extra machine register is usually
needed to keep track of where the display lives.  And to pass the context
implicitly to the inner function, trampoline code may need to be generated
on the fly.  Again, there are some architectures where this is not possible.

It's been more than ten years since we discussed these issues on the DOD-1
committee, so there may be some newer implementation techinques that don't
imply these costs.  If so, I'd be pleased to hear about them.  But as far
as I know, there's no magic wand that will make them disappear.

>>The ``Spirit of C'' is that expensive things are exposed to
>>the programmer; C++ inherits much of this spirit.
>
>	Not entirely. Building objects can be VERY expensive.
>Have a look at some non-optimised code for a constructor of
>a complex object sometime.

Like a function call, the cost of which cannot always be determined from
the outside, it is under the control of the programmer.  If necessary,
it can be replaced.  Cost due to the language is not always possible to
avoid, and is not (directly) under the control of the programmer.  Perhaps
``exposed'' was a poor word choice, but ``accessible'' doesn't have quite
the right flavor, either.  Maybe ``controlled?''  Or ``can be managed by?''

>	And the flip side: C traditionally provides facilities
>corresponding to the underlying hardware. Many CISC machines,
>including the 386 and 68000 have instructions and architecture
>*specifically* designed to support nested functions.
>
>	Thus NOT providing nested functions is against the spirit of C.

Hmmmm....  I don't think I buy into this point.  There are some machines
that have hardware garbage collection, and I don't see that being used as
an argument for garbage collection in C/C++.  (That is NOT a statement
either for _or_ against garbage collection!)

>>In
>>a heavily optimizing compiler that keeps many values in registers, it can
>>be costly to have to re-sync memory every time a nested function _might_
>>be invoked.
>	Dont understand '_might_'. Either one is invoked or not.

As an example, once you've taken the address of a nested function, it _might_
be executed when _any_ external function is called.  In general, the compiler
can't tell where the pointer was stashed, so it has to assume that memory
has to be re-synced.  You and I may know that strcmp() or qsort() don't do
a callback, but the compiler can't be sure.

>>(BTW, I'd like to have nested functions, but I would not make pointers to
>>them be compatible with a ``normal'' function pointer.  
>
>	Do we require nested functions to have the same form
>as ordinary ones? If not, how are they to be distinguished?

Useful as it might be, I don't think that a special form for inexpensive
function pointers (similar to the member function pointer) would be what
the proponents of nested functions want.  I understand that position---I
could see the use of a facility that created a callback by wrapping a member
function and an object together and the same mechanism could then be used to
create a nested callback as well.  That way, the cost would be more visible;
it wouldn't be needed unless the programmer explicitly created a callback
pointer.

But I'm not really willing to argue either side of that one.

>>But, as others have pointed out, it's possible for you, the programmer, to
>>do the expensive thing 
>
>	Yes but VERY clumbsily :-)
>
>>that the compiler would have to do, 
>
>	For me to explicitly keep track of the display is sure
>to be slower --- even on a machine without hardware support
>for nested functions --- than proper compiler generated code.

Probably, but not necessarily.  If the compiler can create better code
for 99 and 44/100ths of the programs, it might be a net gain.  Yes,
your program might be slower, but the vast majority of programs might
be just a little bit faster and more than make up the difference.

That's another one I'm not willing to argue---I want _my_ programs to
run fast, too....
-- 
-- Greg Noel, Unix Guru         greg@qualcomm.com  or  greg@noel.cts.com
Newsgroups: comp.std.c++