On Sun, 04 Jun 2000, Khimenko Victor wrote:
>On Sun, 4 Jun 2000, Jesse Pollard wrote:
>
>> On Sun, 04 Jun 2000, Khimenko Victor wrote:
>> >In <200006041042.MAA12176@oboe.it.uc3m.es> Peter T. Breuer (ptb@it.uc3m.es) wrote:
>> >> "A month of sundays ago Florian Weimer wrote:"
>> >>> The C and C++ frontends only generate trampolines if you use a GNU
>> >>> extension (nested functions).
>> >
>> >> And I have no idea why they should want to: nesting is purely a
>> >> question of namespaces and syntactic scoping. It should impact
>> >> the implementation semantics not at all.
>> >
>> >Oh, yeah ? I eagerly wait your implementation of draw_table for sample
>> >below without trampolines (just remember: you can not alter for_each or
>> >use any information about it's implementation - there are exist sparate
>> >compilation units, you know). Oh, and of course such implementation
>> >should work in multi-threaded environment as well...
>>
>> Only piece I haven't covered is the multi-threaded indirect... Though that
>> could be done by addressing an array via the thread id...
>>
>Yeah ? How ? How well it'll work if I'll pass pointer to function from one
>thread to another (where for_each will create new thread and pass pointer
>in it) ?
See below, and it is already handled for the case of errno.
>What about recursion call of draw_table from one_step ?
Already handled - the y = y1 and y1 = y in "one_step" provides a stack of
pointers.
>Yeah, you
>can do this with some tables (for example you can keep address of for_each
>call in hash table and use this to find out "right" y), but it's just
>plain ugly: kludge over kludge.
1. So is the trampoline code.
2. Only without a good optimizer. The old lisp compilers used to do this as
part of "function elimination". (along with tail-recursion elimination, jump
optimization, ...)
After all, this is already handled for the case of errno. Nested functions
could be implemented by the compiler by including the storage needed for
"*y1" in the thread specific data structure, as is errno. I believe some of
the lisp compilers used thread specific arrays to allow all modules with
thread specific data to be appended to the end of the array. (sometimes got
long), but occasionally, the optimizer could even eliminate the storage.
>Good as prof that "it's possible".
That was all that it was intended for.
>Non-usable as general compiler technique.
I didn't claim it was opimal in this particular instantiation. THIS code
could be opimized by eliminated the "one_step_a" function entirely. Most
such code can be done that way. All the trampoline call does is what is included
with the "static int *y1" combined with the function "one_step".
I have manually translated a number of nested procedures from Algol W (and
modula) into C using this technique. It works quite well, and with the
function elimination it ends up quite clean, and fast.
One of the reasons nested functions were dropped from the original C definition
(K&R) was a proof that any nested function could be implemented without the
nesting and with no significant increase in generated code. Unfortunately I
don't have a reference to that proof (done somewhere beween 1971 and 1975 I
think, I was still in school at the time).
>
>>
>> /* example without tramploine */
>>
>> #include <stdio.h>
>>
>> /*
>> procedure for_each(_from,_to:integer;procedure _do(x:integer));
>> var
>> i:integer;
>> begin
>> for i:=_from to _to do
>> _do(i);
>> end;
>>
>> procedure draw_table;
>> var
>> y:integer;
>> procedure one_step(x:integer);
>> begin
>> write(x*y:4);
>> end;
>> begin
>> for y:=1 to 10 do begin
>> for_each(1,10,one_step);
>> writeln;
>> end;
>> end;
>> begin
>> draw_table;
>> end.
>> */
>>
>> void for_each( int from, int to, void _do( int))
>> {
>> int i;
>>
>> for (i = from; i <= to; i++) {
>> _do(i);
>> }
>> }
>>
>> void one_step_a(int *y, int x)
>> {
>> printf("%4d",x * *y);
>> }
>>
>> static int *y1; /* pointer to data of function */
>> void one_step (int x) /* substitution for trampoline */
>> {
>> int *y;
>>
>> y = y1;
>> one_step_a(y,x);
>> y1 = y;
>> }
>>
>> void draw_table(void)
>> {
>> int y;
>>
>> y1 = & y; /* new */
>> for (y = 1; y <= 10; y++) {
>> for_each(1,10,one_step);
>> printf("\n");
>> }
>> }
>>
>> int main(void)
>> {
>> draw_table();
>> return(0);
>> }
>>
>> output is:
>>
>> tabby$ ./a.out
>> 1 2 3 4 5 6 7 8 9 10
>> 2 4 6 8 10 12 14 16 18 20
>> 3 6 9 12 15 18 21 24 27 30
>> 4 8 12 16 20 24 28 32 36 40
>> 5 10 15 20 25 30 35 40 45 50
>> 6 12 18 24 30 36 42 48 54 60
>> 7 14 21 28 35 42 49 56 63 70
>> 8 16 24 32 40 48 56 64 72 80
>> 9 18 27 36 45 54 63 72 81 90
>> 10 20 30 40 50 60 70 80 90 100
>>
>> This goes back many years to the original "how is recursion implemented in
>> pascal". There ARE compilers that don't use trampoline code, just as there
>> are processors that don't have a hardware stack. Take a look at some of
>> the old lisp interpreters.
>>
>> --
>> -------------------------------------------------------------------------
>> Jesse I Pollard, II
>> Email: pollard@cats-chateau.net
>>
>> Any opinions expressed are solely my own.
>>
-- ------------------------------------------------------------------------- Jesse I Pollard, II Email: pollard@cats-chateau.netAny opinions expressed are solely my own.
- 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:19 EST