In <200006050248.e552mdE08945@sleipnir.valparaiso.cl> Horst von Brand (vonbrand@sleipnir.valparaiso.cl) wrote:
HB> "Khimenko Victor" <khim@sch57.msk.ru> said:
>> Jesse Pollard (pollard@cats-chateau.net) wrote:
HB> [...]
>> 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).
HB> Probably proof that what can be done with nested functions can also be done
HB> without (by hand). And that is truly trivial.
Oh, yeah. When you have access to full source code that is :-)
HB> Algol (and descendants) use nesting for localizing (hiding) stuff, C uses
HB> files + static for that.
Extended Pascal and Ada supports C style as well (modules).
HB> C's model is much simpler to understand, much more flexible (you can't have
HB> function foo() or integer oof visible to just bar() and baz(), which are in
HB> turn visible to the main program in Algol/Pascal, in C it's trivial to do).
Just put baz() in bar () and foo in the same bar() before baz() ... :-)
>> 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
>> :-))
HB> Algol/Pascal don't have separate compilation anyway. Not standard, in any
HB> case.
Extended Pascal have. Ada have. Yes, there are exist addition interface part,
but it will not help you much: it's INTERFACE part - compiler can not put
there information about internal details of function since it just have no
access to it while compiling interface.
HB> Take a look at a book on compiler building, where they discuss Algol-like
HB> languages. There are two major ways of implementing globals (variables in
HB> surrounding blocks):
HB> - A static link in each activation record that points to the parent's
HB> activation record. When accessing a global variable, you walk the static
HB> links until reaching the correct stack frame. Here a function (pointer)
HB> is passed as a static link value plus a pointer to the code to run. This
HB> is slow, but simple.
It's slow even for non-nested functions.
HB> - A display, i.e., an array of pointers to the active stack frames for each
HB> level. The function is passed as a pointer to the code plus its display
HB> (part of it, really; not all has to be replaced). This is more efficient
HB> for global access, but hairy to implement (and probably impossible with
HB> separate compilation, which can create displays of different depths in
HB> different source files).
And once again you can not do this without affection call of "normal"
(non-nested) function.
HB> C does away with this hair or inefficiency by having two levels only:
HB> Globals (includes file-level objects and local statics) and automatic
HB> objects. This mapped nicely to CISC CPUs with hardware stacks for handling
HB> recursion, which where the primary class of machines at the time. Plus in C
HB> a function pointer is just the address where the function starts. I suspect
HB> this is the real reason for not having nested functions in C, and the fact
HB> that what can be done with them can be done without with no great extra
HB> cost was just frosting on the cake.
Perhaps.
HB> So, it _can_ be done without trampolines, but the result doesn't mesh with
HB> C at all, and is rather inefficient in the general case.
Exactly :-) It was the point. We talked not about ANY replacement (obviously
it's trivial: after all you can just emulate IA32 in software emulator without
any trampolines and then execute all needed code there :-) but about EFFECTIVE
replacement.
-
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