«

CBFalconer <> writes:

> Micah Cowan wrote:
> >
> ... snip ...
> >
> > 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. However, this would require an *extremely*
>
> 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

Sidney Cadot <> writes:

> 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

"Chris Torek" <> wrote in message
news:bm9bug$7ep$...
> >Joona I Palaste wrote:
> >>There is no requirement for implementations to *have* a stack
> >>in the first place.

(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)

> >... is there a minimum depth of function calls that I can rely on to
> >be executed properly? I would hate to rewrite all my programs to do
> >everything within main() without function calls, for the ultimate
> >portability
>
> 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

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:

>>> However, this would require an *extremely* intelligent
>>> implementation;

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

Sidney Cadot <> writes:

> 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:
>
> >>> However, this would require an *extremely* intelligent
> >>> implementation;
>
> 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) wrote in message news:<. com>...
> 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.