why does this work ?

[Micah Cowan]

No it can't. Only for some particular forms of recursive
functions. Where are you going to put the local storage for that
recursive function? Conversion of recursive arbitrary functions
requires an auxiliary stack.

Nothing in your statement above contradicts what I said. If
you'll read the whole message, you'll note that I actually say
this. Except for the "auxiliary" part: not sure what you mean by
that, but I don't see why it would have to be "auxiliary".

I said all recursive algorithms can be converted to an iterative
one. This is trivially true; but some only have iterative
algorithms which must make use of some sort of stack.

-Micah

 

[Micah Cowan]

Hi Micah,

Only a C implementation for a genuine Turing machine could handle
infinite recursion.
The above statement isn't actually *quite* true. According to
the
as-if rule, an implementation could rewrite recursive code to be
iterative; and since all recursive algorithms are equivalent to
at least one iterative algorithm, this could be done for all
recursive calls. [...]

Memory serving, this is true only for so-called 'primitive
recursive' functions; a counterexample is the Ackermann function:

int ackermann(int x, int y)
{
return (x==0) ? y+1 : (y==0) ? ackermann(x-1,1) :
ackermann(x-1,ackermann(x,y-1));
}

Nope. I never said it could be done without a stack. Read the
rest of my previous message. I never said all such conversions
would be useful for our purposes, I merely said that such a
conversion was always possible.

----------

#include <stdlib.h>
#include <stdio.h>

struct stack {
int x;
struct stack *next;
};

struct stack * stack_push(struct stack **, int);
void stack_pop (struct stack **, int *);
void stack_destroy(struct stack **);

/* In this function, *result is the equivalent of your return
value; a 1 is returned for error; zero for
successful completion. */
int ackermann(int x, int y, int *result)
{
int intermed_result;
int error = 0;
struct stack *stk = NULL;

for (; {
while (x != 0) {
if (y==0) {
/* Your return ackermann(x-1,1) */
x--;
y = 1;
}
else {
/* Your return ackermann(x-1,ackermann(x,y-1)) */
struct stack *tmpstk;
tmpstk = stack_push(&stk, x-1);
if (!tmpstk) {
stack_destroy(&stk);
error = 1;
}
y--;
}
}
/* Your return y+1 */
intermed_result = y+1;

/* Loop test: */ if (stk == NULL) break;

/* Continue... pop stack and reprocess. */
y = intermed_result;
stack_pop(&stk,&x);
}

*result = intermed_result;
return error;
}

struct stack *stack_push(struct stack **stk, int x)
{
struct stack *new_node = malloc(sizeof *new_node);

if (new_node) {
new_node->x = x;
new_node->next = *stk;
*stk = new_node;
}
return new_node;
}

void stack_pop(struct stack **stk, int *x)
{
struct stack *next_node = (*stk)->next;
*x = (*stk)->x;
free (*stk);
*stk = next_node;
}

void stack_destroy(struct stack **stk)
{
struct stack *next_node;

while (*stk != NULL) {
next_node = (*stk)->next;
free (*stk);
*stk = next_node;
}
}

----------

The above is (obviously) completely without recursion. It can
fail, but so can yours: it's just a question of how long it takes
to hit the limit of your system (for both versions).

HAND,
Micah

 

[Glen Herrmannsfeldt]

(snip)

This is in fact the method used
on early IBM 370 C compilers. (I imagine it is still used on S/370
architectures, since there is no dedicated "frame pointer" register,
though as I recall R14 is somewhat conventional.)

R14 is usually the return address register. R13 is usually the save area
(linked list) register.

As for the original subject, the traditional function return value register
is R0, or for floating point values, F0.

(snip)

I have never found one. The "Translation limits" section (at or
near 5.2.4.1) is the logical place for something like "at least N
function activations down from the initial call to main()", but
there is no such wording. On the other hand, that section is not
a good weapon against Evil Compilers, as it requires only that an
implementation "translate and execute ... one program" that tests
those limits.

The MSDOS linker had a parameter to set the stack size for the EXE file,
which I believe defaulted to 2K if not specified. I remember when I first
started using OS/2 2.0, with virtual memory, and trying different (virtual)
stack sizes. It would take many megabytes, and not actually try to allocate
the space until needed, yet the default was still 2K.

-- glen

 

[Sidney Cadot]

Hi Micah,

the as-if rule, an implementation could rewrite recursive code to be
iterative; and since all recursive algorithms are equivalent to
at least one iterative algorithm, this could be done for all
recursive calls. [...]

Memory serving, this is true only for so-called 'primitive
recursive' functions; a counterexample is the Ackermann function:

int ackermann(int x, int y)
{
return (x==0) ? y+1 : (y==0) ? ackermann(x-1,1) :
ackermann(x-1,ackermann(x,y-1));
}

Nope. I never said it could be done without a stack. Read the
rest of my previous message. I never said all such conversions
would be useful for our purposes, I merely said that such a
conversion was always possible.

Well, if you mean it like that, you're obviously right. It becomes sort
of a tautology - it is a fact so trivially true that there is not much
sense in stating it.

However, given the meaning of your statement as you just explained it,
the following line of your original post doesn't make sense:

It would actually be completely trivial. All that is required is for the
runtime system to maintain it's own stack, instead of using the stack
provided by the hardware (if any). So I was reading too much in your
post because of this.

Best regards,

Sidney Cadot

 

[Micah Cowan]

Hi Micah,

the as-if rule, an implementation could rewrite recursive code to be
iterative; and since all recursive algorithms are equivalent to
at least one iterative algorithm, this could be done for all
recursive calls. [...]

Memory serving, this is true only for so-called 'primitive
recursive' functions; a counterexample is the Ackermann function:

int ackermann(int x, int y)
{
return (x==0) ? y+1 : (y==0) ? ackermann(x-1,1) :
ackermann(x-1,ackermann(x,y-1));
}

Nope. I never said it could be done without a stack. Read the
rest of my previous message. I never said all such conversions
would be useful for our purposes, I merely said that such a
conversion was always possible.

Well, if you mean it like that, you're obviously right. It
becomes sort of a tautology - it is a fact so trivially true that
there is not much sense in stating it.

However, given the meaning of your statement as you just
explained it, the following line of your original post doesn't
make sense:

It would actually be completely trivial. All that is required is
for the runtime system to maintain it's own stack, instead of
using the stack provided by the hardware (if any). So I was
reading too much in your post because of this.

Yeah, okay, I see the confusion. I meant that it would require a
very intelligent implementation to always determine whether
recursive code (including indirectly recursive code) is in fact
primitive and can be implemented as iterative code *without* a
stack (which I didn't meant to suggest as always, or even
usually, being possible), but that's not what I said.

-Micah

 

[Bamber]

Why does f get returned ? (compiled with gcc).

#include<stdio.h>

int func(int a);

main()
{ int f;
f=func(7);
printf("f=%d",f);

}
int func(int a)
{
int f,d = 100;
if (a<10){
f = d;
}
}

Ta,

Bamber.

Found out later that day ...

This was compiled on a pc ...

It works because function results are stored in the same register as
the
results of arithmetic operations (ax/eax).

On a SPARC, you would get the value of the first parameter.

Lucky for the lad who's test was being marked he didn't sit at a Sun
(the program he was doing was longer but the above gives the jist of
it).

Thanks for info.


Bamber.