🚀 go-pugleaf

In article <BxyLs4.Hn5@sci.kun.nl> marcok@cs.kun.nl (Marco Kesseler) writes:
>In article <1992Nov18.130407.12799@titan.inmos.co.uk> Stephen Doyle,
>steved@lion.inmos.co.uk writes:
>>INMOS' soon to be shipping new
>optimising C 
>>compiler has a specific optimisation for tail call recursion i.e.
>>
>>void p (int q)
>>{
>>  ...
>>  return(p(...));
>>}
>>
>>in this case the workspace of p is reused as the function recurses,
>also, 
>>nested returns are omitted so that only one return is needed no matter
>how many 
>>levels of recursion take place.
>
>The compatibility issues mentioned above make me wonder if such
>an 'optimisation' is conform ANSI standards. Forgive me my ignorance,
>but would such a procedure work in any implementation of ANSI C?
>It guess this is a new feature of C.

Provided that you check that certain enabling conditions are satisfied
(eg. you haven't put the addresses of local variables in global data),
then tail-call optimisation is perfectly legal according to the ANSI
standard for C, and a very large number of C compilers (including gcc)
implement this optimisation.  It is not a new feature of C, just an
optimisation technique.

(Incidentally, none of the optimisations performed in INMOS' C compiler
violates the ANSI standard for C.)

>Perhaps a rather superfluous
>thing to do as well. C has loops.

Although you can express tail-recursion in terms of loops in C, you cannot
express the more general case of tail-calling at source level in C.

As an example of the effect of tail-call optimisation, when compiling the
SPEC  benchmark 'li' for the transputer, tail call optimisation reduces
stack usage from 4700 bytes to 4000 bytes, meaning you can fit the entire
stack in on-chip memory, this alone provides a 12% speed-up.

'li' is written in C and it was chosen to be part of the SPEC benchmark
suite because it is typical of a certain type of application: I don't
think that this speed-up on a 'typical' application is superfluous.

('li' is an xlisp interpreter executing a lisp program to solve the
8-queens problem, so it is about as recursive as they come.
You wouldn't generally expect this kind of speed-up from tail-call
optimisation (though I have seen speed-ups of 20% for a simple coding
of the Ackermann function), but for all those heavily recursive
applications, tail-call optimisation is definitely worthwhile.)

>Marco

Cheers,
Steve.

---
Stephen Clarke      INMOS Ltd, Bristol | EMail(UK) stevec@inmos.co.uk
The opinions above are my personal     | Internet: stevec@inmos.com
views and do not reflect INMOS policy. |