From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Subject: Re: Use of nested functions (Was: Proposal for default scope)
Organization: MAXTAL P/L C/- University Computing Centre, Sydney
Date: Sat, 9 Jan 1993 18:29:38 GMT

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 ------------------
Newsgroups: comp.std.c++