"Khimenko Victor" <khim@sch57.msk.ru> said:
> Jesse Pollard (pollard@cats-chateau.net) wrote:
[...]
> JP> One of the reasons nested functions were dropped from the original C
> JP> definition (K&R) was a proof that any nested function could be
> JP> implemented without the nesting and with no significant increase in
> JP> generated code. Unfortunately I don't have a reference to that proof
> JP> (done somewhere beween 1971 and 1975 I think, I was still in school
> JP> at the time).
Probably proof that what can be done with nested functions can also be done
without (by hand). And that is truly trivial. Algol (and descendants) use
nesting for localizing (hiding) stuff, C uses files + static for that. C's
model is much simpler to understand, much more flexible (you can't have
function foo() or integer oof visible to just bar() and baz(), which are in
turn visible to the main program in Algol/Pascal, in C it's trivial to do).
> I'm not sure that such proof is still valid when functions without
> available sources are involved - impossigble for human translation in
> open source world, typical for compiler. And I'm pretty sure such
> compilers without trampolines worked wrong for some weird examples as
> well: when logically bound information is artifactually splitted and sent
> via separate channels usual end result is wrong delivery in some cases
> :-))
Algol/Pascal don't have separate compilation anyway. Not standard, in any
case.
Take a look at a book on compiler building, where they discuss Algol-like
languages. There are two major ways of implementing globals (variables in
surrounding blocks):
- A static link in each activation record that points to the parent's
activation record. When accessing a global variable, you walk the static
links until reaching the correct stack frame. Here a function (pointer)
is passed as a static link value plus a pointer to the code to run. This
is slow, but simple.
- A display, i.e., an array of pointers to the active stack frames for each
level. The function is passed as a pointer to the code plus its display
(part of it, really; not all has to be replaced). This is more efficient
for global access, but hairy to implement (and probably impossible with
separate compilation, which can create displays of different depths in
different source files).
C does away with this hair or inefficiency by having two levels only:
Globals (includes file-level objects and local statics) and automatic
objects. This mapped nicely to CISC CPUs with hardware stacks for handling
recursion, which where the primary class of machines at the time. Plus in C
a function pointer is just the address where the function starts. I suspect
this is the real reason for not having nested functions in C, and the fact
that what can be done with them can be done without with no great extra
cost was just frosting on the cake.
So, it _can_ be done without trampolines, but the result doesn't mesh with
C at all, and is rather inefficient in the general case.
-- Horst von Brand vonbrand@sleipnir.valparaiso.cl Casilla 9G, Viņa del Mar, Chile +56 32 672616- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Wed Jun 07 2000 - 21:00:20 EST