Fergus James HENDERSON <fjh@munta.cs.mu.OZ.AU> writes:
>Many people seem to think that the purpose of nested functions is purely
>as encapsulation, a sort of code organization/modularization feature.
>... the real reason that they are useful is that ... their addresses can
>be passed to any function that just expects a function parameter.
>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.  The ``Spirit of C'' is that expensive things are exposed to
the programmer; C++ inherits much of this spirit.

If you look at what a compiler must do to implement this, it has to create
a ``structure'' (the stack frame) that contains all the local variables,
the parameters, and so forth, and arrange for the nested function to be
able to find that structure with a sort of implicit ``this'' pointer.  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.

On top of that, if you wish a function to retain its scope during a potentially
recursive invocation, it means that the implicit ``this'' pointer must be
kept as a part of the pointer, which would increase the size of _every_
pointer, whether the feature is used or not.  That was a real killer for
PL/I function pointers and very much against the C philosophy.

(BTW, I'd like to have nested functions, but I would not make pointers to
them be compatible with a ``normal'' function pointer.  Nested functions
are handy to improve the clarity of code, but I'd want the compiler to
have total knowledge over when they were invoked and allow it to optimize
them as it saw fit, so that it could inline them or use special lightweight
calling sequences if it wished.  If a pointer syntax is needed, I'd make
it similar to the C++ class pointer notation, using the function name as
the class---after all, that's really what's going on....)

But, as others have pointed out, it's possible for you, the programmer, to
do the expensive thing that the compiler would have to do, by putting the
variables you need in a structure and keeping a pointer to it where the
helper function can find it.  I won't claim that it's fun to do it this
way, but this is essentially what the compiler would have to generate, so
the overhead would be the same.
--
-- Greg Noel, Unix Guru         greg@qualcomm.com  or  greg@noel.cts.com

>Fergus James HENDERSON <fjh@munta.cs.mu.OZ.AU> writes:
>>Many people seem to think that the purpose of nested functions is purely
>>as encapsulation, a sort of code organization/modularization feature.
>>... the real reason that they are useful is that ... their addresses can
>>be passed to any function that just expects a function parameter.
>>If a local function never has its address taken, then it does not use
>>the full power of nested functions.

greg@qualcom.qualcomm.com (Greg Noel) writes:
>This is a valid point, but this is exactly the part that is expensive to
>implement.

This is not correct.  Nested functions are not expensive to implement.
I speak as someone who has done it.  Compared to the costs of
programming, and the potential wins (simpler interfaces, less
temptation to use thread/signal-unsafe global variables) nested
functions are a clear win.

>The ``Spirit of C'' is that expensive things are exposed to the
>programmer; C++ inherits much of this spirit.

Is this good or bad?  Does this decrease the cost of
writing/maintaining programs?  Does it make it easier for you to write
reusable code?  Does it lower the rate at which you introduce bugs to
a program?

David Chase
Sun

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.
     o There is no penalty for _not_ using it.
     o It invokes the subroutine in the context where its address was
 evaluated, even under recursion.
     o It's thread-safe; that is, the compiler doesn't create any global
 variables or the like behind my back.
     o The address of the function is compatible with a ``standard''
 function variable.

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.

>I speak as someone who has done it.

Well, I haven't done it myself, but in a previous incarnation I got to grovel
through a lot of PL/I code that used the equivalent of function pointers.  The
code generated on an IBM/360 was astoundingly inefficient.

Of course, one can't make a general argument from one data point, but if
function pointers are that expensive on a not-unreasonable architecture,
you'll have to convince me that they can be considered ``inexpensive''
in the general case.  I'm willing to be proven wrong, but it will take
more than just an assertion that it can be done.

>Compared to the costs of programming, and the potential wins ... nested
>functions are a clear win.

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.

>>The ``Spirit of C'' ... ; C++ inherits much of this spirit.
>Is this good or bad?

It's neither good nor bad; it just is.  But it must be understood when
considering how the language is put together.
--
-- Greg Noel, Unix Guru         greg@qualcomm.com  or  greg@noel.cts.com

greg@qualcom.qualcomm.com (Greg Noel) writes:

>The ``Spirit of C'' is that expensive things are exposed to
>the programmer; C++ inherits much of this spirit.

I have to disagree with this point.  C++ hides a lot of grungy detail
from the programmer, with the consequence that simple constructs may
require a lot of compiler-generated code.

Example 1:  A class in a multiply-inherited hierarchy with virtual base
classes and virtual functions winds up with a very large and complicated
constructor, even if all the constructors for all the classes have
very simple bodies.

Example 2:  User types, with code hidden in a library, may require very
complicated runtime routines.  The very simple expression
 a + b
might invoke enormous amounts of calculation, memory management, and
even file access.
--

Steve Clamage, TauMetric Corp, steve@taumet.com

Steve Clamage <steve@taumet.com> writes:
>I have to disagree with this point.  C++ hides a lot of grungy detail
>from the programmer, with the consequence that simple constructs may
>require a lot of compiler-generated code.

There's a difference between hiding a lot of grungy detail and intrinsic
inefficiency.  If the compiler filling in the grungy details is what is
causing the inefficiency, the programmer can always replace it with something
more efficient.  If it's inefficient because of something required by the
language, that's not possible.

It's curious---I posted my original article to try to start a discussion
about how something like modules or packages could be added to C++ as
seamlessly as possible, because I see that as something that the language
doesn't handle well and needs badly.  But most of the responses have been
from people who reacted to one throw-away clause as a disparagement of
nested functions, which is not what I intended at all.

Personally, I'd prefer to let those who feel passionately about nested
functions debate this point.  As it is, I'm mooting a point about which
I don't care very much.  In my thirty years of experience, including using
languages that provided them, I've only wanted nested functions a few
times---and I've _never_ wanted to take the address of one.  If I don't
use them and if they don't cause me any inefficiency, then I don't really
care if they are present or not.

On the other hand, there are literally hundreds of times I've wanted to
have a helper function that was not externally visible.  In C, a static
function provides most of the functionality I want, while in C++ it's
all but impossible.  If C++ wants to be considered a ``better'' language
than C, that's something that will have to be addressed.
--
-- Greg Noel, Unix Guru         greg@qualcomm.com  or  greg@noel.cts.com

In article <1993Jan8.192906.2342@qualcomm.com> greg@qualcom.qualcomm.com (Greg Noel) writes:
>Fergus James HENDERSON <fjh@munta.cs.mu.OZ.AU> writes:
>>Many people seem to think that the purpose of nested functions is purely
>>as encapsulation, a sort of code organization/modularization feature.
>>... the real reason that they are useful is that ... their addresses can
>>be passed to any function that just expects a function parameter.
>>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.

>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.

 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.

>
>If you look at what a compiler must do to implement this, it has to create
>a ``structure'' (the stack frame) that contains all the local variables,
>the parameters, and so forth, and arrange for the nested function to be
>able to find that structure with a sort of implicit ``this'' pointer.

 What happens on a normal call is trivial. There is a second
stack called a 'display' which maintains a pointer to each
accessible activation record. On the 386 the display is kept
on the stack, and copied each time. It is also possible
to just allocate 'n' words of memory somewhere (for 'n' levels
of nesting) and move the appropriate pointers in and out
as the level changes.

>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.
>
>On top of that, if you wish a function to retain its scope during a potentially
>recursive invocation, it means that the implicit ``this'' pointer must be
>kept as a part of the pointer, which would increase the size of _every_
>pointer, whether the feature is used or not.  That was a real killer for
>PL/I function pointers and very much against the C philosophy.

 The C memory model is bogus. It is based on the outmoded
von Neumann machine. ANY function accessing global data that
has to be re-entrant MUST be passes an instance-specific
data pointer anyhow. In other words: normal functions ALREADY
require BOTH a code address and a data pointer to be
invokable. (Pure functions dont though).

 SO: if you are using a linear address machine,
you can use trampolines and preserve function pointers
as one pointer for nested functions.

 IF you use a real machine with segments and sharable code,
you already needed two pointers ANYHOW, so you loose nothing.

>
>(BTW, I'd like to have nested functions, but I would not make pointers to
>them be compatible with a ``normal'' function pointer.

 Indeed this is an option. Can we discuss the options
for function pointers further? Seems to me this is the only
serious technical problem in writing a proposal.

 Do we require nested functions to have the same form
as ordinary ones?

 If not, how are they to be distinguished?

>Nested functions
>are handy to improve the clarity of code, but I'd want the compiler to
>have total knowledge over when they were invoked and allow it to optimize
>them as it saw fit, so that it could inline them or use special lightweight
>calling sequences if it wished.

 IF nested functions are defined as in standard Pascal
then only forward declarations will cause a problem: that is,
the compiler can inline them as it sees fit.

 IF a nested function is called through a pointer,
it isnt easy to see how much optimisation could be done:
the call could be made from a completely different module,
i.e. a separate translation unit.

>If a pointer syntax is needed, I'd make
>it similar to the C++ class pointer notation, using the function name as
>the class---after all, that's really what's going on....)

 I think .. not sure .. it is only necessary to
know whether the pointer is a nested function pointer,
a pure function pointer (special case---no environmental data),
or a rubbish C function (can access the 'global' activation
record which can be done without the data pointer if you
are prepared to give up re-entrancy)

 Come to think of it, one could easily
take the address of a object member function and execute that
indirectly too--- it is exactly the function address plus
the objects 'this' pointer.

 This is not surprising---nested functions ARE member
functions of the objects which are the activation records
of the scopes in which they are declared <pant>.
If we had garbage collection, we wouldn't need to bother with
classes, we could use closures instead.

 However, having made the observation, could we kill two
birds with one stone and all a new type of function pointer
that can execute EITHER a nested function OR a member
function of a particular object?

>
>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,

 NO the compiler does NOT have to do it expensively for
an ordinary call. On the contrary, it can be HIGHLY optimal.
As YOU pointed out yourself :-)

>by putting the
>variables you need in a structure and keeping a pointer to it where the
>helper function can find it.  I won't claim that it's fun to do it this
>way, but this is essentially what the compiler would have to generate, so
>the overhead would be the same.

 You are definitely wrong here. I as a C programmer, cannot
invoke the machine code instructions designed to manage
nested functions. But I CAN do this in Pascal. So C is
definitely slower and less efficient than Pascal here.

 And as YOU pointed out: for nested functions invoked
directly, and for which the definition has been seen,
the compiler can and often would be able to inline them.

 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.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------

greg@qualcom.qualcomm.com (Greg Noel) writes:

>If you look at what a compiler must do to implement this, it has to create
>a ``structure'' (the stack frame) that contains all the local variables,
>the parameters, and so forth, and arrange for the nested function to be
>able to find that structure with a sort of implicit ``this'' pointer.  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.

Since you always have the full text of the nested function available, and
you know exactly which variables it references, and you know exactly which
function calls might call it, this cost is borne only when it is actually
needed.

>On top of that, if you wish a function to retain its scope during a potentially
>recursive invocation, it means that the implicit ``this'' pointer must be
>kept as a part of the pointer, which would increase the size of _every_
>pointer, whether the feature is used or not.  That was a real killer for
>PL/I function pointers and very much against the C philosophy.

Only function pointers, of course.  For those who hate this cost, the
GCC approach of generating a helper function on the stack works well.  Then
you pay a slightly higher cost for the invocation, but only when it is
actually necessary.

>(BTW, I'd like to have nested functions, but I would not make pointers to
>them be compatible with a ``normal'' function pointer.  Nested functions
>are handy to improve the clarity of code, but I'd want the compiler to
>have total knowledge over when they were invoked and allow it to optimize
>them as it saw fit, so that it could inline them or use special lightweight
>calling sequences if it wished.

It's not a compiler problem.  The compiler has all of the knowledge
it needs.  It's pretty hard to inline a function through a pointer, though.

The arguments against nested functions are primarily based on compatibility
with C and on not making unnecessary changes to the language.  Implementation
costs in the generated code are quite small, and are paid only when needed.
Pointers to nested functions also add yet another area of undefined
behavour, just like pointers to local variables.

I find that my style of programming in C++ pretty much (but not entirely)
eliminates the desire for nested functions as lexical closures, so I won't
argue for them very strongly.
--
Michael S. Ball (mike@taumet.com)
TauMetric Corporation

In article <1993Jan10.023440.27522@qualcomm.com> greg@harvey.qualcomm.com (Greg Noel) writes:

>   There's a difference between hiding a lot of grungy detail and intrinsic
>   inefficiency.  If the compiler filling in the grungy details is what is
>   causing the inefficiency, the programmer can always replace it with something
>   more efficient.  If it's inefficient because of something required by the
>   language, that's not possible.

As others pointed out, nested functions requires innefficiency only when needed.
In a word : if you don't use it no cost for you. That's not the case if this
feature is not in the language. Then you must pay two times :
 - not as efficient implementation as built-in ones (even with very good code)
 - much difficulty to write your code, so NOBODY else but you can use
 libraries using non standard function calls (to emulate nested functions)

The evident consequence is that without nested functions inside the language,
I will change my programming style to be level with language inadequacies.

>   It's curious---I posted my original article to try to start a discussion
>   about how something like modules or packages could be added to C++ as
>   seamlessly as possible, because I see that as something that the language
>   doesn't handle well and needs badly.  But most of the responses have been
>   from people who reacted to one throw-away clause as a disparagement of
>   nested functions, which is not what I intended at all.

Packages would indeed be usefull. But that's not what I miss most right now.
I feel there is already many ways to achieve this with classes.
Is it not the goal of encapsulation ?

>   Personally, I'd prefer to let those who feel passionately about nested
>   functions debate this point.  As it is, I'm mooting a point about which
>   I don't care very much.  In my thirty years of experience, including using
>   languages that provided them, I've only wanted nested functions a few
>   times---and I've _never_ wanted to take the address of one.  If I don't
>   use them and if they don't cause me any inefficiency, then I don't really
>   care if they are present or not.

I only have fourteen years of programming. But what I can say is that when
I hadn't used OO languages, I never cared much about nested functions.
I won't miss them in Lisp, C, Pascal or Modula.

But I can't do without them for OO Programming. Programming in Smalltalk,
Ptitloo (lisp with an object interface) and Weird-Looking Mering IV, what
I miss most is decent containers. Let's explain.

My actual problem is making part of my local context be seen by a function.
Wich I can't call myself, cause it's called indirectly either by a system
C function (like qsort), or by a class library.

Making the context of a call seeable by a library is necessary in order
to make clean containers. What I mean by clean containers is containers
that can handle iterations internally, not externally using another class
(iterators) as it is generally done in C++.

The two approches are not equivalent. Iterators give control back to users
at each element in order to execute the user's code. Even if in much cases
it works fine, it doesn't with complex structures or heavily parallelized
archithectures.

What I'm saying is : is I don't give back the control to users at each step
 - I can do recursive calls very easily (to walk trees for instance)
 - I can make the iteration parallel in my library, may be I will have
 to hack machine code *inside* my container library, but users don't care
 this can't be done with iterator classes.

*BUT* to write a clean iterator, I need something to iterate : a function call.
This function is provided by user, so it MUST be easy to write, still its
interface is fixed by the container  (generally it takes an element of DATA),
and finally this function have generally to see external world.

You can achieve thoses three goals with nested functions. No other C++ hack
would do. The main problem is with simplicity, the other two, you can do.
What I call simplicity in my lab is, *as C as possible*. Many peoples are
eager to compile with C++ in order to reuse libraries written by others,
but not much are really wanting to learn OOP. Creating instances, they can
manage. Nested functions too (some C compilers as gnu C already has nested
functions). OO Design is to much. Nested functions would be a clean way to
write clean, efficien, perfectly encapsulated containers with iterators for
these people. I could adapt my libraries on parallel computers without
having them to change their code.

Ok, this use of nested functions is not perfectly clean in OO Design,
what should be perfect is a brand new class of functions...
functions that are really instances of a class, with a context,
an initialisation member, a return adress, etc.
If you think of it, it's nearly what a compiler would do in order to
implement nested functions.

This kind of class functions I can do in C++, but it's not simple to create
them. Terminal users won't use them... if I can't shorten their declaration.
I could do it with a better preprocessor... but preprocessor has'nt evolded.
It's still the good old C preprocessor, whose initial purposes are mostly
obsolete with C++. It's not well adapted with other purposes, as simplifying
specific class declarations. But that's another point.

>   On the other hand, there are literally hundreds of times I've wanted to
>   have a helper function that was not externally visible.  In C, a static
>   function provides most of the functionality I want, while in C++ it's
>   all but impossible.  If C++ wants to be considered a ``better'' language
>   than C, that's something that will have to be addressed.

Agreed... is it not still a problem of the number of line you have to write to
do what you want ? Efficiency is not even half of a language IMO, reusability
and clean interface (merely *short* semantic, minimalise the number of tokens
you must type to express yourself) is the other half.

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

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

In article <1993Jan11.215111.11291@qualcomm.com> greg@harvey.qualcomm.com (Greg Noel) writes:
>
>John MAX Skaller <maxtal@extro.ucc.su.OZ.AU> writes:
>
>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.

 No, you need the display for ordinary calls. However,
this is no problem.


>
>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.

 One could easily introduce a new type: the closure,
consisting of a function and a data pointer.

 Ordinary function pointers convert to closures
(by setting the data pointer to 0).

 This means you can't call qsort with a closure, but so what,
you cant do that now either.
>
>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.

 Non local goto's would be nasty. We could ban them
from nested functions, anyone?

>
>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.

 This is no problem for the 386 which ALREADY uses that
register (called the base pointer BP) to keep track of
activation records anyhow.

>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.

 No, it is well established: without pointers there are
no problems: Pascal can do it :-)
>
>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.

 As far as my limited knowledge goes: if you give
up addresses and non-local gotos, there are no great
problems with nested functions.

 Certainly on the 386, the overhead is virtually zero:
most C++ compilers generate 'enter' and sometimes 'leave'
instructions that manage the display on the stack automatically.
(Thus thread safe).

 I'd be surprised if a RISC machine couldn't emulate
these 386-hardware instructions and not be that
much slower than a 386 :-)

>> 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!)

 It would be a very strong argument if *enough* machines
had hardware GC.

 Most PC machines have hardware support for nested functions.
 Most RISC machines dont need this to emulate it easily.

 Dont know about CRAY machines?
>
>>>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.

 Same is true for any function isnt it?
 In fact, when doing a non-pointer call, nested function
 actually appear to offer optimisation *opportunities*.
>
>> 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 dont know: I want nested function even if we cant take their
addresses. If we can, and need another type, fine. I dont mind,
as long as ordinary functions convert to the 'closure' type.

>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.
>
>
>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....

 I doubt there is an argument. Adding nested function
MUST not slow down existing codes. Period. It will not
pass the committee otherwise.

--
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
 Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------