Primitive Recursion et al
chris.danx
I'm curious about the difference between tail and primitive recursion. I'm
aware that tail recursion is much more efficient than primitive recursion and
that tail recursion uses limited stack space. Does it only work for FPs or can
you do it in say Ada, or Pascal? Just curious since i'll be continuing my
Haskell studies in a few days and left of around primitive recursion.
Chris Campbell
Barry Kelly
"chris.danx" <chris...@ntlworld.com> wrote:
> I'm curious about the difference between tail and primitive recursion.
> I'm aware that tail recursion is much more efficient than primitive
> recursion and that tail recursion uses limited stack space.
> Does it only work for FPs or can you do it in say Ada, or Pascal?
You can do it manually in an imperative language with the use of
'goto' or 'while', with the application of a little thought.
Essentially, with tail recursion, instead of recursing into the same
routine, you set up the current function's state in such a way as to
be able to accomplish the same effect by merely jumping to the start
of the routine.
Optimizing compilers can sometimes convert ordinary recursion into
tail recursion.
-- Barry
Jerzy Karczmarczuk
> > I'm curious about the difference between tail and primitive recursion.
> > I'm aware that tail recursion is much more efficient than primitive
> > recursion and that tail recursion uses limited stack space.
> > Does it only work for FPs or can you do it in say Ada, or Pascal?
>
> You can do it manually in an imperative language with the use of
> 'goto' or 'while', with the application of a little thought.
>
> Essentially, with tail recursion, instead of recursing into the same
> routine, you set up the current function's state in such a way as to
> be able to accomplish the same effect by merely jumping to the start
> of the routine.
>
> Optimizing compilers can sometimes convert ordinary recursion into
> tail recursion.
1. "Tail recursion" optimization is part of the *tail call* optimization,
which replaces the last "call" by "jump". This is horribly difficult
to do manually, often simply impossible. No little though will help
you. A direct recursion can be dealt with - as mentioned - by
transforming the procedure into a loop, but you have to reassign manually
all the arguments. Perhaps little thought, but a lot of chores.
(*)
2. I don't know of *any* compiler of C which does the tail call
optimization. Nor Pascal. Anybody knows more?
3. Converting depth recursion into a terminal one is always possible
in a *functional language* using the continuation passing style.
But, normally it is not what you should do, for many reasons. If
the recursion depth is not so high, stack handling is much cheaper
than developing horrible closures in your heap.
Sometimes, adding an accumulator argument permits to "iteratize"
a recursive procedure, but does anybody *really* know a compiler
which does this automatically??
==
(*) GNU C compiler has a "dynamic branching" instruction, but the variable
label cannot belong to a different procedure.
Jerzy Karczmarczuk
Caen, France
William Chesters
> 2. I don't know of *any* compiler of C which does the tail call
> optimization. Nor Pascal. Anybody knows more?
I don't understand. If you are talking about tail-call-optimizing
something like
int foo(int x, int a = 1) {
return x == 0 ? a : foo(x - 1, a * x);
}
then every C compiler I have seen at least for the last ten years has
done it??
Jerzy Karczmarczuk
> > 2. I don't know of *any* compiler of C which does the tail call
> > optimization. Nor Pascal. Anybody knows more?
>
> I don't understand. If you are talking about tail-call-optimizing
> something like
>
> int foo(int x, int a = 1) {
> return x == 0 ? a : foo(x - 1, a * x);
> }
>
> then every C compiler I have seen at least for the last ten years has
> done it??
Alright.
That's why I split - before this - the problem into the direct recursion
which can be locally handled, and general *tail call*, say
f(...)
{...
g(...);}
where g may call f again, also through a tail call. In principle this is
iterative, but do your C compilers optimize also that? It would require
a global program analysis, it seems...
Jerzy Karczmarczuk
Markus Mottl
> 2. I don't know of *any* compiler of C which does the tail call
> optimization. Nor Pascal. Anybody knows more?
gcc definitely doesn't do it, Digital's DEC C V5.8 obviously neither. But
Sun's cc (version 5.0) can do it if you turn on optimization.
This example also shows that _not_ using optimization can indeed lead
to unsafe programs in some cases.
> 3. Converting depth recursion into a terminal one is always possible
> in a *functional language* using the continuation passing style.
> But, normally it is not what you should do, for many reasons. If
> the recursion depth is not so high, stack handling is much cheaper
> than developing horrible closures in your heap.
Right. E.g. in OCaml the "@"-operator, which appends lists, is not
tail-recursive because of a slight performance bonus. You'll have to
reverse the left list and "rev_append" it if you need tail-recursiveness.
> Sometimes, adding an accumulator argument permits to "iteratize"
> a recursive procedure, but does anybody *really* know a compiler
> which does this automatically??
I recall having read a paper about automated transformations that make
non-tail-recursive programs tail-recursive by introducing accumulators.
Should be somewhere in the web... ;)
Regards,
Markus Mottl
--
Markus Mottl, mo...@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
Markus Mottl
> I don't understand. If you are talking about tail-call-optimizing
> something like
> int foo(int x, int a = 1) {
> return x == 0 ? a : foo(x - 1, a * x);
> }
> then every C compiler I have seen at least for the last ten years has
> done it??
gcc and the DEC-compiler cannot even handle this:
void f() { f(); }
Pixel
> Jerzy Karczmarczuk <kar...@info.unicaen.fr> wrote:
> > 2. I don't know of *any* compiler of C which does the tail call
> > optimization. Nor Pascal. Anybody knows more?
>
> gcc definitely doesn't do it
not true anymore since around 2.96, it now handles a lot more tail-call and
tail-recursion (with -fomit-frame-pointer, but beware, not very stable yet)
--
Posted from office.mandrakesoft.com [195.68.114.34]
via Mailgate.ORG Server - http://www.Mailgate.ORG
Pixel
[...]
> > then every C compiler I have seen at least for the last ten years has
> > done it??
>
> gcc and the DEC-compiler cannot even handle this:
>
> void f() { f(); }
.L3:
jmp .L3
> > int foo(int x, int a = 1) {
> > return x == 0 ? a : foo(x - 1, a * x);
> > }
foo__Fii:
movl 4(%esp), %edx
movl 8(%esp), %eax
.L4:
testl %edx, %edx
je .L3
imull %edx, %eax
decl %edx
jmp .L4
.p2align 4,,7
.L3:
ret
:)
PS: using gcc version 2.96 20000731
William Chesters
> Alright.
>
> That's why I split - before this - the problem into the direct recursion
> which can be locally handled, and general *tail call*, say
>
> f(...)
> {...
>
> g(...);}
> where g may call f again, also through a tail call. In principle this is
> iterative, but do your C compilers optimize also that? It would require
> a global program analysis, it seems...
>
> Jerzy Karczmarczuk
Ah, they don't do that. (NB all decent C++ compilers have inlining
and/or interprocedural analysis which does most of the things people
mean under the term "global program analysis". Mutual recursion just
isn't something the compiler authors are terribly interested in, a
shame I suppose.)
Lon Willett
> William Chesters answers my query:
>
>
> > > 2. I don't know of *any* compiler of C which does the tail call
> > > optimization. Nor Pascal. Anybody knows more?
> >
> > I don't understand. If you are talking about tail-call-optimizing
> > something like
> >
> > int foo(int x, int a = 1) {
> > return x == 0 ? a : foo(x - 1, a * x);
> > }
> >
> > then every C compiler I have seen at least for the last ten years has
> > done it??
>
[snip]
The problem in C/C++ is that lifetime issues will usually prevent a
compiler from performing the last-call optimisation. e.g.
bool f(int x, Type y, Type* out_value)
{
// Do something. Return false if done, else return true
// with some result in *OUT_VALUE
...
}
void g(int x, Type y)
{
Type z;
if (!f(x,y,&z))
return y;
return g(x+1,z);
}
The tail-recursive call on g can't be optimised without global
analysis; i.e. the compiler has to know that "f" doesn't save the
reference to "z" before it can perform last-call optimisation. In
C++, order of destruction issues make it even harder to do last-call
optimisations (e.g. imagine that "Type" has a non-trivial destructor
in the above example; then it doesn't matter even if the compiler
knows that "f" doesn't retain a reference to "z", unless it can also
manage to prove that "~Type()" doesn't care about the order of
destruction).
So one really can't rely on last-call optimisation in C/C++. It
rarely happens except for trivial examples.
/Lon
Joachim Durchholz
> [...] general *tail call*, say
>
> f(...)
> {...
>
> g(...);}
> where g may call f again, also through a tail call. In principle this
is
> iterative, but do your C compilers optimize also that? It would
require
> a global program analysis, it seems...
Not at all. Actually it's trivial and local.
Say the calling convention is this:
- Caller pushes arguments on stack
- Caller does a JSR
- Callee executes its body
- Callee pops arguments off the stack
- Callee terminates with a RET
then it's a rather straightforward optimization. The code generated for
the last call would be:
- Caller pops its own arguments
- Caller pushes arguments for the callee
- Caller does a JMP to the callee
- Callee executes body, pops arguments, does a RET
There are some intricacies related to the calling convention. The most
nasty case is if the caller pops the arguments (as is the rule in
languages such as C that allow a variable number of parameters on a
routine); there's no problem if the number of parameters stays the same
or decreases, but a parameter count increase makes tail call
optimization impossible (unless either the caller establishes a stack
frame, or the caller gets enough dummy parameters to makes its parameter
count at least as large as that of the callee - the latter technique is
indeed sort-of a global analysis).
Regards,
Joachim
--
This is not an official statement from my employer.
Markus Mottl
> PS: using gcc version 2.96 20000731
I'll try it with a new gcc some time. It definitely doesn't work with
version 2.95.2 (tried that on several platforms).
Markus Mottl
> not true anymore since around 2.96, it now handles a lot more tail-call and
> tail-recursion (with -fomit-frame-pointer, but beware, not very stable yet)
Ok, I trust you. ;)
It's about time that gcc introduces this, though there are some inherent
problems in the general case in C that can lead to unsoundness...
Wilhelm B. Kloke
Pixel <pi...@mandrakesoft.com> wrote:
>Markus Mottl <mo...@miss.wu-wien.ac.at> writes:
>
>[...]
>
>> > then every C compiler I have seen at least for the last ten years has
>PS: using gcc version 2.96 20000731
2.96 is not an official version, and will never be. The latest stable version
before 3.0 is 2.95.3.
--
Dipl.-Math. Wilhelm Bernhard Kloke
Institut fuer Arbeitsphysiologie an der Universitaet Dortmund
Ardeystrasse 67, D-44139 Dortmund, Tel. 0231-1084-257
William Chesters
> William Chesters <will...@paneris.org> wrote:
> > I don't understand. If you are talking about tail-call-optimizing
> > something like
>
> > int foo(int x, int a = 1) {
> > return x == 0 ? a : foo(x - 1, a * x);
> > }
>
> > then every C compiler I have seen at least for the last ten years has
> > done it??
>
> gcc and the DEC-compiler cannot even handle this:
>
> void f() { f(); }
I tried my example with gcc 2.7.2.3, and a fairly old Sun compiler, as
well as every other modern compiler I have access to. They do all
absolutely fine.
But: :-)
You are, strangely, right that your apparently simpler example foxes
gcc (even current versions)! Try replacing void f with int f, I think
you will find it works better ...
David Casperson
Jerzy Karczmarczuk <kar...@info.unicaen.fr> wrote:
>Barry Kelly after "chris.danx"
>
>> ...You can do it manually in an imperative language with the use of
>> 'goto' or 'while', with the application of a little thought.
>>
>> Essentially, with tail recursion, instead of recursing into the same
>> routine, you set up the current function's state in such a way as to
>> be able to accomplish the same effect by merely jumping to the start
>> of the routine.
>>
>> Optimizing compilers can sometimes convert ordinary recursion into
>> tail recursion.
>
> (*)
>
>2. I don't know of *any* compiler of C which does the tail call
> optimization. Nor Pascal. Anybody knows more?
In general this is difficult in C-like languages because ... argument
syntax leads to calling conventions where it is the caller's rather than
the callee's responsibility to clean up the stack. This means that
tail-call optimisation needs to be clever. I am not sure if I am
answering the correct question, but
gcc version 2.95.2 19991024 (release)
unrolls gcd into a loop in
//--------------------------------------------------
#include <iostream>
static int gcd(int a, int b)
{ return a==0 ? b : gcd(b%a,a) ; }
int main()
{
cout << "gcd(34,55) = " << gcd(34,55) << endl ;
return 0 ;
}
//--------------------------------------------------
(at least on a sparc).
I didn't experiment to see what would happen if gcd had external linkage.
>3. Converting depth recursion into a terminal one is always possible
> in a *functional language* using the continuation passing style.
> But, normally it is not what you should do, for many reasons. If
> the recursion depth is not so high, stack handling is much cheaper
> than developing horrible closures in your heap.
> Sometimes, adding an accumulator argument permits to "iteratize"
> a recursive procedure, but does anybody *really* know a compiler
> which does this automatically??
I am sure that Jerzy is aware of this, but
val rec fact1 = (fn 0 => 1 | n => n * fact1 (n-1))
is only equivalent to
val rec fact2 = (fn x => fact2(x,1))
and fact2a = (fn (0,a) => a | (n,a) => fact2a(n-1,n*a))
if multiplication is associative, and so it is very unlikely for a
compiler to find such a transformation. I have no idea about the state
of compiler technology for things like list reversal.
>Jerzy Karczmarczuk
>Caen, France
David Casperson
Prince George, Canada
--
Dr. David Casperson | cas...@unbc.ca
Department of Mathematics & Computer Science | (250) 960-6672
Faculty of Science |
College of Science and Management |
ol...@pobox.com
> > [...] general *tail call*, say
> >
> > f(...)
> > {...
> >
> > g(...);}
> > where g may call f again, also through a tail call. In principle this is
> > iterative, but do your C compilers optimize also that? It would require
> > a global program analysis, it seems...
> Not at all. Actually it's trivial and local.
I'm afraid Jerzy is right. There are certain features in C that make
tail-call optimizations generally impossible.
Let's consider the following snippet:
static jmp_buf handler;
static int bar(int x);
static int foo(int x)
{
if( setjmp(handler) == 0 )
return bar(x);
return x+1;
}
static int bar(int x)
{
x++;
if( x > 42 )
longjmp(handler,5);
return x;
}
The call to bar() in foo() is a tail call -- syntactically. If foo()
drops its frame from the stack before invoking bar(), longjmp() will
return to a destroyed frame. A statement "return x+1" in foo() can't
then be executed correctly as the automatic variable x, a part of
foo's frame, will be gone.
The following -- a more realistic -- snippet is another example where
the tail-call optimization will break the code:
FILE * open_png(char * file_name_stem)
{
char file_name[256];
if( strlen(file_name_stem) + 1 + 4 >= sizeof(file_name) )
return (FILE*)0;
sprintf(file_name,"%s.png",file_name_stem);
return fopen(file_name,"rb");
}
The call to fopen() is a tail-call. If open_png() destroys its own
frame before passing the control to fopen(), the name of the file to
open will be destroyed as well.
In Scheme and other functional and non-functional languages (Java),
only bindings are allocated on stack while non-primitive values go on
heap. When a frame is dropped and the bindings are destroyed, the
values are unaffected (and will survive the collection if, e.g.,
another binding points to them). In C not only the bindings are
allocated on stack but the values (e.g., structures, strings and other
arrays) as well. Dropping a frame has more consequences then.
William Chesters
> I'm afraid Jerzy is right. There are certain features in C that make
> tail-call optimizations generally impossible.
>
> Let's consider the following snippet:
>
> static jmp_buf handler;
What people often forget is that C/C++ compilers do whole program
analysis, or a fair approximation thereto, at the intermediate-code
level, because of inlining. That is why Oleg's cases---which are
knockdown arguments even against self-tail-calls, if they are knockdown
arguments against mutual tail-calls---do not prevent compilers from
tailifying recursive x! or fibonacci functions.
George Neuner
>
>Let's consider the following snippet:
>
>static jmp_buf handler;
>
>static int bar(int x);
>
>static int foo(int x)
>{
> if( setjmp(handler) == 0 )
> return bar(x);
> return x+1;
>}
>
>static int bar(int x)
>{
> x++;
> if( x > 42 )
> longjmp(handler,5);
> return x;
>}
>
Every language that allows continuation capture, even benign downward
forms like exception handlers, will have the same problem.
In Scheme the compiler has to verify that *any* (arbitrarily deeply
nested) function reachable from the position of setjmp() [in the
example] did not save its continuation.
George
George Neuner
wrote:
>
>What people often forget is that C/C++ compilers do whole program
>analysis, or a fair approximation thereto, at the intermediate-code
>level, because of inlining.
>
The "global" optimization offered by most C/C++ compilers is limited
to functions in the same source file. Separate compilation all but
guarantees that intra-module is the best that will be done.
I've heard lots of talk about whole program optimizing C/C++
compilers, but I've only ever seen it actually done in some
(expensive) DSP cross-compilers.
George
William Chesters
The standard compiler that comes with IRIX does "inter-procedural
analysis" between modules, and it's not the only one. More
importantly, any decent C++ compiler does serious inlining, and
precompiles the headers in which you define the inline
functions---much of the advantage of separate compilation without the
restrictions.
C++ compiler technology at its best (and I don't mean g++ or VC++) is
pretty mature. Right now it is possible to use quasi-functional
idioms in your inner loops with very little cost, and you just can't
with any functional language, even ocaml. (Maybe scheme with this
stalin compiler we have heard about, I don't know.)
It's a bit like RISC versus Pentia. With enough money and time and
second chances, the warts are not as show-stopping as they appear.
[Disclaimer---I don't like C++, but it is indisputably the only
language in which you can write fast, abstract code.]
Joachim Durchholz
> "Joachim Durchholz" <joac...@gmx.de> wrote:
> > > [...] general *tail call*, say
> > >
> > > f(...)
> > > {...
> > >
> > > g(...);}
> > > where g may call f again, also through a tail call. In principle
> > > this is iterative, but do your C compilers optimize also that?
> > > It would require a global program analysis, it seems...
>
> > Not at all. Actually it's trivial and local.
>
> I'm afraid Jerzy is right. There are certain features in C that make
> tail-call optimizations generally impossible.
>
> Let's consider the following snippet:
>
OK, I take that back that tail-call optimization is trivial. C offers
enough irregularities to make it an "interesting" problem.
I still stand by my position that it's a local problem.
Fergus Henderson
I missed the earlier parts of this thread, but doing good tail-call
optimization in C often requires non-local program analysis.
For example:
void foo() {
int x;
bar(&x);
baz(x); // safe to use tail-call here?
}
Whether or not it is safe to replace the call to baz() with a jump
to baz() depends on whether or not bar() saved the address of x
in a global variable which is later referenced by some function
called from baz(). Figuring that out in general requires some kind of
non-local program analysis. The only other alternative is to make
overly-conservative approximations which would prevent tail-call
optimization in cases like this one.
--
Fergus Henderson <f...@cs.mu.oz.au> | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
Joachim Durchholz
> "Joachim Durchholz" <joac...@gmx.de> writes:
> >I still stand by my position that it's a local problem.
>
> I missed the earlier parts of this thread, but doing good tail-call
> optimization in C often requires non-local program analysis.
>
> For example:
>
> void foo() {
> int x;
> bar(&x);
> baz(x); // safe to use tail-call here?
> }
>
> Whether or not it is safe to replace the call to baz() with a jump
> to baz() depends on whether or not bar() saved the address of x
> in a global variable which is later referenced by some function
> called from baz().
I stand corrected.