By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,148 Members | 779 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,148 IT Pros & Developers. It's quick & easy.

why does this work ?

P: n/a
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.
Nov 13 '05 #1
Share this Question
Share on Google+
44 Replies


P: n/a
Bamber <ba******************@yahoo.co.uk> scribbled the following:
Why does f get returned ? (compiled with gcc).
It doesn't. You're mistaking implementation-dependent behaviour for
normal operation.
#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;
}
}


When control reaches the end of func(), the returned value is
indeterminate. When the assignment f=func(7) is done in main(), the C
implementation tries to get a value from where there isn't any. On
some implementations, this is the last value put on a stack before
the assignment happens, but there is no requirement that implementations
should do this. There is no requirement for implementations to *have* a
stack in the first place.
Generally, you just got (un)lucky.

--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ---------------------------\
| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.helsinki.fi/~palaste W++ B OP+ |
\----------------------------------------- Finland rules! ------------/
"Ice cream sales somehow cause drownings: both happen in summer."
- Antti Voipio & Arto Wikla
Nov 13 '05 #2

P: n/a
Greetings.

In article <37**************************@posting.google.com >, Bamber wrote:
Why does f get returned ?


It doesn't. In fact, nothing gets returned, since there is no return
statement to be found anywhere in your program.

Regards,
Tristan

--
_
_V.-o Tristan Miller [en,(fr,de,ia)] >< Space is limited
/ |`-' -=-=-=-=-=-=-=-=-=-=-=-=-=-=-= <> In a haiku, so it's hard
(7_\\ http://www.nothingisreal.com/ >< To finish what you
Nov 13 '05 #3

P: n/a
In <37**************************@posting.google.com > ba******************@yahoo.co.uk (Bamber) writes:
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);
There is a newline character missing in this format string.

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


By pure accident. Your code invokes undefined behaviour, by using the
value returned by a function that doesn't actually return anything, so
*anything* can happen.

Compiled with the same compiler, on a diferent platform, the output is
different:

mentor:~/tmp 11> uname -a
SunOS mentor 5.8 Generic_108528-11 sun4u sparc
mentor:~/tmp 12> cat test.c
#include<stdio.h>

int func(int a);

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

}
int func(int a)
{
int f,d = 100;
if (a<10){
f = d;
}
}
mentor:~/tmp 13> gcc test.c
mentor:~/tmp 14> ./a.out
f=7

This doesn't look like f's value before func() returns, does it?
By your logic, I should start asking myself: why does func() return the
value of its parameter? ;-)

Moral: it is a pure waste of time to try to understand why a piece of
broken code behaves the way it does.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 13 '05 #4

P: n/a
Joona I Palaste wrote:
<snip>
There is no requirement for implementations to *have* a stack in the first place.


This is the second time I see this posted over the last couple of days,
and you're surely right. But it does beg the following question:

----

#include <stdio.h>

/* returns n! modulo 2^(number of bits in an unsigned long) */
unsigned long f(unsigned long n)
{
return (n==0) ? 1 : f(n-1)*n;
}

int main(void)
{
unsigned long z;
for(z=1;z!=0;z*=2)
{
printf("%lu %lu\n", z, f(z));
fflush(stdout);
}
return 0;
}

----

As far as I can see, this is a perfectly valid C program that should
reach the 'return 0' statement always, were it not for the fact that in
all compilers I tried (one, actually) it terminates with a segmentation
fault of some sort, due to limited stack size.

Is this 'incorrect behavior' of all these compilers, or is there some
wording in the Standard that covers for machines with a finite stack
(much to my dismay, this covers all machines I have access to)?

If so, 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 :-)
Best regards,

Sidney
Nov 13 '05 #5

P: n/a
In article <bm**********@news.tudelft.nl>,
Sidney Cadot <si****@jigsaw.nl> wrote:
#include <stdio.h>

/* returns n! modulo 2^(number of bits in an unsigned long) */
unsigned long f(unsigned long n)
{
return (n==0) ? 1 : f(n-1)*n;
}

int main(void)
{
unsigned long z;
for(z=1;z!=0;z*=2)
{
printf("%lu %lu\n", z, f(z));
fflush(stdout);
}
return 0;
}

----

As far as I can see, this is a perfectly valid C program that should
reach the 'return 0' statement always, were it not for the fact that in
all compilers I tried (one, actually) it terminates with a segmentation
fault of some sort, due to limited stack size.

Is this 'incorrect behavior' of all these compilers, or is there some
wording in the Standard that covers for machines with a finite stack
(much to my dismay, this covers all machines I have access to)?

If so, 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 suggest you start saving your money for a POWER4 with 64 GB of memory
or so, which IBM will happily sell you for some six digit dollar number.
Make sure that unsigned long is not more than 32 bit, though.
Nov 13 '05 #6

P: n/a
>Joona I Palaste wrote:
There is no requirement for implementations to *have* a stack
in the first place.

In article <bm**********@news.tudelft.nl>
Sidney Cadot <si****@jigsaw.nl> writes:This is the second time I see this posted over the last couple of days,
and you're surely right.
In a technical sense, at least, and it *does* matter sometimes.

The constraints in the standard force "stack-like behavior" for
local variables inside functions (including any parameters), and
I think it is not out of line to call this "a stack". But one
should remember that this "stack" may well be implemented as,
e.g., a linked list of frames:

struct stackframe {
struct stackframe *inner;
unsigned char mem[]; /* C99 "flexible array member" syntax */
};

and the memory for each stack frame allocated out of a general
storage pool, so that there is no fixed addressing relationship
between any pair of stack frames. 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.)

Other hardware that runs C code may have two or more hardware
stacks, and/or multiple software stacks. Consider Moore's "Forth
on a chip" systems, which have a call/return stack separate from
their "value" stack on which one would pass parameters. Or look
at the Pyramid, which had separate "control" and "data" stacks,
although the control stack held register values which were often
(probably "usually") data.
... 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.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.
Nov 13 '05 #7

P: n/a
Hi Chris,
[[does the Standard require a stack?]]
The constraints in the standard force "stack-like behavior" for
local variables inside functions (including any parameters), and
I think it is not out of line to call this "a stack". [...]


As for me: If it walks like a stack and talks like a stack, so to say -
I'd prefer to call it a stack.

If I understand what you're saying correctly, the standard does not (of
course!) force the underlying hardware to support anything stack-like,
but the runtime model implies something that can in good faith only be
called a stack (albeit perhaps one that implemented in software, as your
IBM 370 and other examples show). Interesting.
... 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.


That's interesting... Based on a literal reading of the standard at
least, I'd say my sample program is fully compliant and there's no
reason for it ever to not reach the 'return 0' statement.

Now the actual behavior, segfaulting, is usually classified as a
manifestation of 'undefined behavior' in other contexts. Moreover, it is
obvious that one cannot sensibly expect arbitrarily deep function calls
to work (although the standard doesn't give limits).

To me, perhapse naively, this seems then like a point where the standard
is not complete. Anybody care to comment on that point of view?

Best regards,

Sidney Cadot
The Netherlands

Nov 13 '05 #8

P: n/a
On Sat, 11 Oct 2003 12:53:07 +0200, in comp.lang.c , Sidney Cadot
<si****@jigsaw.nl> wrote:
snip prog that runs out of stack space
Is this 'incorrect behavior' of all these compilers, or is there some
wording in the Standard that covers for machines with a finite stack
(much to my dismay, this covers all machines I have access to)?


The C standard sets limits on the size, number and so forth of objects
that an implementation is required to provide. Infinite recursion, or
even relatively deep recursion, tends to break them. See 5.2.4 of the
Standard.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 13 '05 #9

P: n/a

On Sun, 12 Oct 2003, Sidney Cadot wrote:
[[does the Standard require a stack?]]
The constraints in the standard force "stack-like behavior" for
local variables inside functions (including any parameters), and
I think it is not out of line to call this "a stack". [...]


As for me: If it walks like a stack and talks like a stack, so to say -
I'd prefer to call it a stack.


But lots of non-pedants like to say things like, "automatic variables
are declared on the stack," or "the function parameters are pushed on
the stack in reverse order," or things like that -- which are blatantly
false, given some of the "stack-like" models that [whomever you were
quoting] demonstrated.
If I understand what you're saying correctly, the standard does not (of
course!) force the underlying hardware to support anything stack-like,
but the runtime model implies something that can in good faith only be
called a stack
....or two stacks, or three. Or one three-element "stack" per function
(giving a maximum recursion depth of 3 calls). Or whatever else the
implementor comes up with...
(albeit perhaps one that implemented in software, as your
IBM 370 and other examples show). Interesting.
... 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.


That's interesting... Based on a literal reading of the standard at
least, I'd say my sample program is fully compliant and there's no
reason for it ever to not reach the 'return 0' statement.


Correct. The only reason the program doesn't work is because we
live in the pesky physical world.
Now the actual behavior, segfaulting, is usually classified as a
manifestation of 'undefined behavior' in other contexts. Moreover, it is
obvious that one cannot sensibly expect arbitrarily deep function calls
to work (although the standard doesn't give limits).

To me, perhapse naively, this seems then like a point where the standard
is not complete. Anybody care to comment on that point of view?


Yup. The Standard doesn't give any hint of a min-max recursion depth.
In practice, I think most compiler systems use sensible recursion
strategies, limited only by the amount of RAM available. But yes, in
theory, all C compilers are non-conforming in this regard.

You might be interested in this old thread:
http://groups.google.com/groups?
th********************************************@uni x47.andrew.cmu.edu

which is also continued under different subject lines here:
http://groups.google.com/groups?
threadm=Pine.LNX.4.53L-031.0304251302260.9612%40unix44.andrew.cmu.edu
th******************@news.meganetnews.com
and several other places. [I hate the way Google Groups handles
threads with changing subject lines!] Search for "C turing-complete"
in comp.programming and comp.lang.c, and see what pops up, if you're
still interested. (Bottom line: An infinite stack can't simulate an
infinite tape.)

-Arthur
Nov 13 '05 #10

P: n/a
On Sun, 12 Oct 2003 00:12:38 +0200, in comp.lang.c , Sidney Cadot
<si****@jigsaw.nl> wrote:
Hi Chris,
[[does the Standard require a stack?]]

The constraints in the standard force "stack-like behavior" for
local variables inside functions (including any parameters), and
I think it is not out of line to call this "a stack". [...]


As for me: If it walks like a stack and talks like a stack, so to say -
I'd prefer to call it a stack.


Except that its not. The standard doesn't require, or even force,
implementations to put variables into a stack. I don't think thats
what Chris was saying. For example all parameters could be (and even
on stack based machines generally are) passed via registers. All
automatics could be created in reserved memory, in no particular
order.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 13 '05 #11

P: n/a
Hi Barry,
[snip program]
As far as I can see, this is a perfectly valid C program that should
reach the 'return 0' statement always, were it not for the fact that in
It is valid in the theoretical sense but it executes in the real
world.
Of course I agree, but this being comp.lang.c, I think it's valid to
look at the ill-lit corners of the language as it is specified.

I mean, people here sometimes insist that code like:

#include <stdio.h>
int main(void)
{
int a[1];
printf("%d", a[1]);
return 0;
}

....could cause nuclear detonation or even (perish the thought!)
harddrive formatting, so I think there's a bit of a tradition with
regard to projecting theoretical issues onto practice.
All systems have limited resources. Even virtual memory is backed up
in some kind of file. I could not find in the standard a minimum for
the number of recursive function calls an implementation was required
to support. It does state that a function can be recursively called
at least once.
Of course you're right. I would be already half satisfied if there would
be a statement in the standard to the effect that "function calls are
allowed to consume an unspecified amount of an unspecified type of one
or more unspecified types of resources, which the function will release
upon completion of execution. Undefined behavior can occur when the
amount of said resources in use at any one time exceeds an unspecified
threshold."

The downside of such a statement of course would be that any program
performing function calls could cause undefined behavior. But right now
that seems to be an accurate representation of the state of affairs
anyway, so the question is: which one of the two evils is the most evil?

Please realize that I'm playing the devil's advocate here... I'm just
curious if I'm either missing something crucial in the Standard, or that
perhaps a wording could be found to mend the situation to the effect
that something real we sometimes observe in practice (stack overflows)
is covered by the Standard.
[[ some numbers on estimate of memory usage in the sample program ]]
The sample program was of course devised exactly to trigger a stack
overflow on any (or at least most) practical implementations.

An interesting point is that by recognizing tail recursion, a very smart
compiler could even come up with a translation that does, indeed,
eventually reach the 'return 0' statement.
Would you be asking your question if your program simply issued malloc
requests until no more memory was available? The only difference is
that malloc fails "politely" by returning NULL.
That's a good homologous case, yes, with the exception (as you point
out) that there is a perfectly good provision within the Standard to
handle it.
There doesn't seem to be any way for a recursion failure to be "polite." Both fail for
exactly the same reason. Only the symptoms of that failure are
different.
I beg to differ on your first statement, I think there is a way, but it
would require an amendment to the standard.

A function invocation could check if it would exceed the stack resource,
and (if so) abort execution, for example. This would require a change of
the standard, and would have performance ramifications. But it would be
possible.
Welcome to the limitations of practicality.


That's all good and dandy, but we still seem to be stuck in a situation
where a fully compliant program invokes a segmentation fault, which can
only signify undefined behavior (as the Standard doesn't talk about
segmentation faults). If that situation could be improved (and the point
of this discussion, for me at least, is to see if it can), I for one
would welcome it!

Best regards,

Sidney Cadot
The Netherlands

Nov 13 '05 #12

P: n/a
Hi Mark,
Is this 'incorrect behavior' of all these compilers, or is there some
wording in the Standard that covers for machines with a finite stack
(much to my dismay, this covers all machines I have access to)?
The C standard sets limits on the size, number and so forth of objects
that an implementation is required to provide. Infinite recursion, or
even relatively deep recursion, tends to break them. See 5.2.4 of the
Standard.


I've just browsed 5.2.4 of the Committee Draft dated August 3, 1998
(it's Saturday night after all - what else to do?).

5.2.4.1 gives some lower bounds on compile-time constructs a compiler
should be able to handle, and the other subsections give numeric
constraints that should be met.

I honestly see nothing in there that a program using infinite or
relatively deep recursion (such as my example) violates.

Best regards,

Sidney Cadot

Nov 13 '05 #13

P: n/a
Hi Arthur,
As for me: If it walks like a stack and talks like a stack, so to say -
I'd prefer to call it a stack.
But lots of non-pedants like to say things like, "automatic variables
are declared on the stack," or "the function parameters are pushed on
the stack in reverse order," or things like that -- which are blatantly
false, given some of the "stack-like" models that [whomever you were
quoting] demonstrated.
Ok. To clarify my understanding of this: the Standard sets forth a
number of constraints that amount to implementing an (abstract) stack,
that can be /though of/ as something on which things are pushed or
popped. The implementor is free to devise a way to implement this
abstract mechanism any way (s)he chooses.
If I understand what you're saying correctly, the standard does not (of
course!) force the underlying hardware to support anything stack-like,
but the runtime model implies something that can in good faith only be
called a stack ...or two stacks, or three. Or one three-element "stack" per function
(giving a maximum recursion depth of 3 calls). Or whatever else the
implementor comes up with...
Yes. I'm just not happy that the concept of a 'maximum recursion depth'
is brought in without any backing from the Standard.
[snip] That's interesting... Based on a literal reading of the standard at
least, I'd say my sample program is fully compliant and there's no
reason for it ever to not reach the 'return 0' statement. Correct. The only reason the program doesn't work is because we
live in the pesky physical world.
It's a drag, isn't it? :-) I would be happy to see this reflected in the
Standard.
To me, perhapse naively, this seems then like a point where the standard
is not complete. Anybody care to comment on that point of view?

Yup. The Standard doesn't give any hint of a min-max recursion depth.
In practice, I think most compiler systems use sensible recursion
strategies, limited only by the amount of RAM available. But yes, in
theory, all C compilers are non-conforming in this regard.
Surely the founding fathers of C99 have considered this issue(?) I
wonder if they couldn't come up with a good formulation, or decided it
was just not worth the effort.
You might be interested in this old thread: [...]


Thanks, I will go and read this. I used to toy with issues of Turing
completeness of different formal systems so this will make an
interesting read I'm sure.

Best regards,

Sidney Cadot

Nov 13 '05 #14

P: n/a
Hi Mark,
>[[does the Standard require a stack?]]
The constraints in the standard force "stack-like behavior" for
local variables inside functions (including any parameters), and
I think it is not out of line to call this "a stack". [...]


As for me: If it walks like a stack and talks like a stack, so to say -
I'd prefer to call it a stack.

Except that its not. The standard doesn't require, or even force,
implementations to put variables into a stack. I don't think thats
what Chris was saying. For example all parameters could be (and even
on stack based machines generally are) passed via registers. All
automatics could be created in reserved memory, in no particular
order.


I think the issue here is to distinguish between something that
/logically/ behaves like a stack, and something that is a classical
stack implementation as supported by many hardware platforms.

Reading Chris' reply I feel that his statement amounted to the effect
that, given the constraints in the Standard, it follows that an
implementation must support something that behaves like a /logical/ stack.

Your example of register based parameter passing hits home for me, as I
did some assembly coding on the PowerPC RISC architecture; parameter
passing by register is the preferred way of working there. However, when
doing recursive function calls where each invocation manages a local
state (dare I say: stack-frame), one is in effect emulating a /logical/
stack.

I'm curious about Chris' opinion on the matter, whether I did correctly
understand his reply.

Best regards,

Sidney Cadot

Nov 13 '05 #15

P: n/a
On Sun, 12 Oct 2003 01:09:01 +0200, in comp.lang.c , Sidney Cadot
<si****@jigsaw.nl> wrote:
5.2.4.1 gives some lower bounds on compile-time constructs a compiler
should be able to handle, and the other subsections give numeric
constraints that should be met.

I honestly see nothing in there that a program using infinite or
relatively deep recursion (such as my example) violates.


There are other min and max requirements scattered throughout the
standard as well, but, indeed, its probable that there's nothing to
specifically outlaw infinite recursion. Remember tho the standard is
notionally implemented in a theoretical machine. We live in the Real
World (tm) where infinite memory is not available.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 13 '05 #16

P: n/a
On Sun, 12 Oct 2003 01:21:39 +0200, in comp.lang.c , Sidney Cadot
<si****@jigsaw.nl> wrote:
But lots of non-pedants like to say things like, "automatic variables
are declared on the stack," or "the function parameters are pushed on
the stack in reverse order," or things like that -- which are blatantly
false, given some of the "stack-like" models that [whomever you were
quoting] demonstrated.


Ok. To clarify my understanding of this: the Standard sets forth a
number of constraints that amount to implementing an (abstract) stack,
that can be /though of/ as something on which things are pushed or
popped.


AFAIK No, the standard sets out no constraints that /require/ anything
to be pushed or popped from a stack, or even to amount to doing that.
Thats merely one way to represent what the standard requires which is
that for example copies of the values of the parameters to a function
be made available in the function, or that array members shall appear
to be adjacent in memory.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 13 '05 #17

P: n/a
On Sun, 12 Oct 2003 01:31:51 +0200, in comp.lang.c , Sidney Cadot
<si****@jigsaw.nl> wrote:
I think the issue here is to distinguish between something that
/logically/ behaves like a stack,


In what way does the standard /REQUIRE/ the logical behaviour of a
stack.

Thats as opposed to "S Cabot needs an internal mental picture of how
function calls etc work, and he finds the idea of a stack easy to
visualise and operate with". No offense intended.

For myself I don't need this mental picture. I think of function
calls, recurnsion and automatics as involving the computer storing
different data in various places, and remembering where it is at the
relevant time.

A bit like me working on something, and using various books from my
bookshelf. I feel no compulsion to make a "stack" of hte ones I need,
pushing the most recently used one to the top, and then popping it off
again when I'm done. I merely pull them off the shelf when needed, and
put 'em back afterwards, generally in much the same place but a few
books to the left or right doesn't matter, I'm no Dewey obsessive.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 13 '05 #18

P: n/a
Hi Mark,
I think the issue here is to distinguish between something that
/logically/ behaves like a stack,
In what way does the standard /REQUIRE/ the logical behaviour of a
stack.
Well, in a very obvious way really. Actual parameters and local
variables are accessible during execution of a function; they become
inaccessible during a recursive call as the same formal parameters and
local variables now refer to new, independent variables, which cease to
exist upon return from the secondary call to the same function. I think
you will agree that this behavior is prescribed by the standard.

To me at least, this seems equivalent to viewing the set of parameters
and local variables as a tuple; the ordered list of these tuples
associated with recursive invocations of a function, of which only the
current one is accessible, has all the hallmark properties of a stack of
which only the top-most element is accessible at any given time.
Thats as opposed to "S Cabot needs an internal mental picture of how
function calls etc work, and he finds the idea of a stack easy to
visualise and operate with". No offense intended.
None taken, not even for misspelling my name ;-)
For myself I don't need this mental picture. I think of function
calls, recurnsion and automatics as involving the computer storing
different data in various places, and remembering where it is at the
relevant time.
My main argument in this thread is not whether C prescribes a logical
stack or not; for me that's a useful model (so good, in fact, that I
would be interested to see where this model falls apart), and for you it
isn't. That's A-ok by me.

On the risk of committing speculation, I think you would be hard-pressed
to find a compiler implementor who doesn't use the stack as a very
useful model while implementing a C (or any other) compiler.

What I /would/ like to get to is the phenomenon that a seemingly
standard-compliant program can exhibit undefined behavior. There's a
number of explanations (perhaps there are more):

* the standard does in fact cover this case through a specific limit
exceeded (for example) by my small program, and nobody mentioned
it so far in this thread.
* the standard does in fact cover this case, as it presumes an
idealized machine where certain practical constraints do not
hold (I'd welcome a clear reference).
* the standard does not cover this case.

Presuming for the moment that the third case is what's going on, I think
it is a worthwile exercise to ponder if/how the standard could be
amended in such a way as to cover this case. Stack overflow (perhaps
'resource depletion due to many nested function calls' is a better, but
clumsier term), in my opinion, is a phenomenon that is important enough
to deserve mention in the standard. I would be interested to know if
people disagree with this.
A bit like me working on something, and using various books from my
bookshelf. I feel no compulsion to make a "stack" of hte ones I need,
pushing the most recently used one to the top, and then popping it off
again when I'm done. I merely pull them off the shelf when needed, and
put 'em back afterwards, generally in much the same place but a few
books to the left or right doesn't matter, I'm no Dewey obsessive.


But then, you're not a running C program which, I hope, exhibits a level
of neurotic-obsessive behavior that would make a clinical psychiatrist
dance with joy.

Best regards,

Sidney Cadot

Nov 13 '05 #19

P: n/a
Chris Torek wrote:
Sidney Cadot <si****@jigsaw.nl> writes:
Joona I Palaste wrote:

There is no requirement for implementations to *have* a stack
in the first place.

This is the second time I see this posted over the last couple
of days, and you're surely right.


In a technical sense, at least, and it *does* matter sometimes.

The constraints in the standard force "stack-like behavior" for
local variables inside functions (including any parameters), and
I think it is not out of line to call this "a stack". But one
should remember that this "stack" may well be implemented as,
e.g., a linked list of frames:


I just came up with a new system that can confuse many programs
that take liberties. :-)

Assuming that byte, short, int, long are all an increasing size,
i.e. 1,2,4,8, and that we can fit float and double in there, lets
have a machine with 4 separate stacks, separated by size.

We can also have an assortment of sized registers, each of which
represents the top of a stack of items of its own size.

I think it would be a feasible machine. Might be a good basis for
the DS9000.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 13 '05 #20

P: n/a
In article <bm**********@news.tudelft.nl>
Sidney Cadot <si****@jigsaw.nl> writes:
I think the issue here is to distinguish between something that
/logically/ behaves like a stack, and something that is a classical
stack implementation as supported by many hardware platforms.

Reading Chris' reply I feel that his statement amounted to the effect
that, given the constraints in the Standard, it follows that an
implementation must support something that behaves like a /logical/ stack.


Yes. Any queue data structure with last-in-first-out and "top
entry is visible" can be called a "stack", and the values of
variables within a function activation fit this description.

The main problem with saying that local variables are "on the
stack", or even "on a stack", is that people may -- and do in
practice -- draw invalid (in the general case, at least) conclusions
from this wording. We might safely say "local variables participate
in a stack discipline" or "behave in a stack-like manner", but at
that point the meaning may no longer be clear to the reader.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.
Nov 13 '05 #21

P: n/a
On Sun, 12 Oct 2003 03:16:36 +0200, Sidney Cadot <si****@jigsaw.nl> wrote:
Message-ID: <bm**********@news.tudelft.nl>
Subject: Re: why does this work ?
From: Sidney Cadot <si****@jigsaw.nl>
Newsgroups: comp.lang.c
Date: Sun, 12 Oct 2003 03:16:36 +0200

Hi Mark,
I think the issue here is to distinguish between something that
/logically/ behaves like a stack,

In what way does the standard /REQUIRE/ the logical behaviour of a
stack.


Well, in a very obvious way really. Actual parameters and local
variables are accessible during execution of a function; they become
inaccessible during a recursive call as the same formal parameters and
local variables now refer to new, independent variables, which cease to
exist upon return from the secondary call to the same function. I think
you will agree that this behavior is prescribed by the standard.

To me at least, this seems equivalent to viewing the set of parameters
and local variables as a tuple; the ordered list of these tuples
associated with recursive invocations of a function, of which only the
current one is accessible, has all the hallmark properties of a stack of
which only the top-most element is accessible at any given time.
Thats as opposed to "S Cabot needs an internal mental picture of how
function calls etc work, and he finds the idea of a stack easy to
visualise and operate with". No offense intended.


None taken, not even for misspelling my name ;-)
For myself I don't need this mental picture. I think of function
calls, recurnsion and automatics as involving the computer storing
different data in various places, and remembering where it is at the
relevant time.


My main argument in this thread is not whether C prescribes a logical
stack or not; for me that's a useful model (so good, in fact, that I
would be interested to see where this model falls apart), and for you it
isn't. That's A-ok by me.

On the risk of committing speculation, I think you would be hard-pressed
to find a compiler implementor who doesn't use the stack as a very
useful model while implementing a C (or any other) compiler.

What I /would/ like to get to is the phenomenon that a seemingly
standard-compliant program can exhibit undefined behavior. There's a
number of explanations (perhaps there are more):

* the standard does in fact cover this case through a specific limit
exceeded (for example) by my small program, and nobody mentioned
it so far in this thread.
* the standard does in fact cover this case, as it presumes an
idealized machine where certain practical constraints do not
hold (I'd welcome a clear reference).
* the standard does not cover this case.

Presuming for the moment that the third case is what's going on, I think
it is a worthwile exercise to ponder if/how the standard could be
amended in such a way as to cover this case. Stack overflow (perhaps
'resource depletion due to many nested function calls' is a better, but
clumsier term), in my opinion, is a phenomenon that is important enough
to deserve mention in the standard. I would be interested to know if
people disagree with this.
A bit like me working on something, and using various books from my
bookshelf. I feel no compulsion to make a "stack" of hte ones I need,
pushing the most recently used one to the top, and then popping it off
again when I'm done. I merely pull them off the shelf when needed, and
put 'em back afterwards, generally in much the same place but a few
books to the left or right doesn't matter, I'm no Dewey obsessive.


But then, you're not a running C program which, I hope, exhibits a level
of neurotic-obsessive behavior that would make a clinical psychiatrist
dance with joy.

Best regards,

Sidney Cadot


---------------------------------------
Posted with JOC News Finder
Download at http://www.jocsoft.com/jnf/

Nov 13 '05 #22

P: n/a
Sidney Cadot <si****@jigsaw.nl> writes:


* the standard does in fact cover this case through a specific limit
exceeded (for example) by my small program, and nobody mentioned
it so far in this thread.
* the standard does in fact cover this case, as it presumes an
idealized machine where certain practical constraints do not
hold (I'd welcome a clear reference).


I would vote for this one, as you are exceeding the required minimum
number of objects with your recursive calls ( you have one auto
variable per call, where the lifetime ends on return of the function.)
Björn

--
Bjoern Pedersen Lichtenbergstr.1
Technische Universitaet Muenchen D-85747 Garching
ZWE Instrumentierung FRM-II
Tel. + 49 89 289-14707 Fax -14666
Nov 13 '05 #23

P: n/a
On Sun, 12 Oct 2003 03:16:36 +0200, in comp.lang.c , Sidney Cadot
<si****@jigsaw.nl> wrote:
Hi Mark,
I think the issue here is to distinguish between something that
/logically/ behaves like a stack,
In what way does the standard /REQUIRE/ the logical behaviour of a
stack.


Well, in a very obvious way really. Actual parameters and local
variables are accessible during execution of a function; they become
inaccessible during a recursive call as the same formal parameters and
local variables now refer to new, independent variables, which cease to
exist upon return from the secondary call to the same function. I think
you will agree that this behavior is prescribed by the standard.


it is, but its not necessary for a stack to be used either literally
or logically to achieve this. I have a ladder to access the top shelf
of my books. When I'm pulling down Sci Fi books, I can't access my C
books, and vice versa. But I still don't have a stack of books with
LIFO type behaviour.
To me at least, this seems equivalent to viewing the set of parameters
and local variables as a tuple;
sure, you can regard it that way, its your mindset. I'm just trying to
make clear that the standard doesn't require you to think of it like
that, or implementors to implement it thus
My main argument in this thread is not whether C prescribes a logical
stack or not;
IMHO it does not.
for me that's a useful model
Thats ok with me. I don't feel the need to have it.
On the risk of committing speculation, I think you would be hard-pressed
to find a compiler implementor who doesn't use the stack as a very
useful model while implementing a C (or any other) compiler.


I suspect this discussion is now well into the realm of
comp.compilers. Perhaps you should continue it over there?
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 13 '05 #24

P: n/a
Hi Mark,
[snip]

My main argument in this thread is not whether C prescribes a logical
stack or not;


IMHO it does not.
for me that's a useful model


Thats ok with me. I don't feel the need to have it.
On the risk of committing speculation, I think you would be hard-pressed
to find a compiler implementor who doesn't use the stack as a very
useful model while implementing a C (or any other) compiler.


I suspect this discussion is now well into the realm of
comp.compilers. Perhaps you should continue it over there?


:-)

As stated, my main argument in this thread is not whether C prescribes a
logical stack or not; rather, it is to find out if stack overflows are
covered by the standard, one way or another.

We differ on whether we feel the need to internalize the C runtime model
as a stack; I'm comfortable with that, as are you. Let's just keep it at
that and move on to more interesting matters.

Best regards,

Sidney Cadot

Nov 13 '05 #25

P: n/a
Hi Björn,
* the standard does in fact cover this case, as it presumes an
idealized machine where certain practical constraints do not
hold (I'd welcome a clear reference).
I would vote for this one, as you are exceeding the required minimum
number of objects with your recursive calls ( you have one auto
variable per call, where the lifetime ends on return of the function.)


I am not aware of a requirement in the Standard that prescribes a
minimum number of active objects that an implementation must support
(where 'object' includes things like parameters and automatic
variables). Do you have a reference?

For sure, if there is one, the sample program may well exceed it at some
point. I, for one, would be quite satisfied if you are right.

Best regards,

Sidney Cadot

Nov 13 '05 #26

P: n/a
Sidney Cadot <si****@jigsaw.nl> writes:
I would vote for this one, as you are exceeding the required minimum
number of objects with your recursive calls ( you have one auto
variable per call, where the lifetime ends on return of the function.)


I am not aware of a requirement in the Standard that prescribes a
minimum number of active objects that an implementation must support
(where 'object' includes things like parameters and automatic
variables). Do you have a reference?

That's the Translation Limits section. I don't have the standard at
hand, but it should be around 5.2.4.1 (see post from C. Torek
upthread). Maybe some of the language lawyers here can give a better
reference.

Björn


--
Bjoern Pedersen Lichtenbergstr.1
Technische Universitaet Muenchen D-85747 Garching
ZWE Instrumentierung FRM-II
Tel. + 49 89 289-14707 Fax -14666
Nov 13 '05 #27

P: n/a
Bjoern Pedersen <bj*************@frm2.tum.de> wrote:
Sidney Cadot <si****@jigsaw.nl> writes:

I am not aware of a requirement in the Standard that prescribes a
minimum number of active objects that an implementation must support
(where 'object' includes things like parameters and automatic
variables). Do you have a reference?
That's the Translation Limits section. I don't have the standard at
hand, but it should be around 5.2.4.1 (see post from C. Torek
upthread).


I cannot find anything in or around ISO/IEC 9899:1999 5.2.4.1 that
addressess the mentioned problem. This is the part from Chris Torek's
post you are probably referring to:

SC: ... is there a minimum depth of function calls that I can rely on
SC: to be executed properly? ...

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


Regards
--
Irrwahn
(ir*******@freenet.de)
Nov 13 '05 #28

P: n/a
Irrwahn Grausewitz <ir*******@freenet.de> writes:
Bjoern Pedersen <bj*************@frm2.tum.de> wrote:
Sidney Cadot <si****@jigsaw.nl> writes:

I am not aware of a requirement in the Standard that prescribes a
minimum number of active objects that an implementation must support
(where 'object' includes things like parameters and automatic
variables). Do you have a reference?
SC: ... is there a minimum depth of function calls that I can rely on
SC: to be executed properly? ...

The problem I addressed was the number of objects allocated by the
example ( it had a local auto variable). This is covered by the normal
allocation limits. A function not allocating anything (i.e. no locals,
no parameters) colud probabaly be called indefinitly.

Björn
--
Bjoern Pedersen Lichtenbergstr.1
Technische Universitaet Muenchen D-85747 Garching
ZWE Instrumentierung FRM-II
Tel. + 49 89 289-14707 Fax -14666
Nov 13 '05 #29

P: n/a
Bjoern Pedersen <bj*************@frm2.tum.de> wrote:
Irrwahn Grausewitz <ir*******@freenet.de> writes:
Bjoern Pedersen <bj*************@frm2.tum.de> wrote:
>Sidney Cadot <si****@jigsaw.nl> writes:
>>
>> I am not aware of a requirement in the Standard that prescribes a
>> minimum number of active objects that an implementation must support
>> (where 'object' includes things like parameters and automatic
>> variables). Do you have a reference?
>>
SC: ... is there a minimum depth of function calls that I can rely on
SC: to be executed properly? ...

The problem I addressed was the number of objects allocated by the
example ( it had a local auto variable). This is covered by the normal
allocation limits.


Ah, I see, but still I can't find anything in the standard that imposes
such a limit; but of course I'm neither a C expert nor a "language
lawyer".
A function not allocating anything (i.e. no locals,
no parameters) colud probabaly be called indefinitly.

[ ITYM infinitely ^^^^^^^^^^^ ]

I don't think so, because even with a function not containing automatic
variables at least the return address has to be stored somewhere (in
RealWorld[tm] implementations without magic).

Hm, thinking further, I imagine a compiler that completely optimizes
away such code, but then actually no calls take place at all .....
well, it's of no pratical use anyway.

Regards
--
Irrwahn
(ir*******@freenet.de)
Nov 13 '05 #30

P: n/a
On Sun, 12 Oct 2003 12:57:22 +0200, in comp.lang.c , Sidney Cadot
<si****@jigsaw.nl> wrote:
As stated, my main argument in this thread is not whether C prescribes a
logical stack or not; rather, it is to find out if stack overflows are
covered by the standard, one way or another.


fair enough. In that case, the answer is probably "no".
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 13 '05 #31

P: n/a
Irrwahn Grausewitz wrote:
Bjoern Pedersen <bj*************@frm2.tum.de> wrote:
.... snip ...
A function not allocating anything (i.e. no locals,
no parameters) colud probabaly be called indefinitly.

[ ITYM infinitely ^^^^^^^^^^^ ]

I think he meant indefinitely. It's idiomatic for as many times
as you like. Just a minor spelling error.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 13 '05 #32

P: n/a
CBFalconer <cb********@yahoo.com> wrote:
Irrwahn Grausewitz wrote:
Bjoern Pedersen <bj*************@frm2.tum.de> wrote:

... snip ...
> A function not allocating anything (i.e. no locals,
>no parameters) colud probabaly be called indefinitly.

[ ITYM infinitely ^^^^^^^^^^^ ]

I think he meant indefinitely. It's idiomatic for as many times
as you like. Just a minor spelling error.


Hm, maybe I have to update my English dictionary.

From Oxford Advanced Learner's, 3rd edition (1974!):

in-defi-nite /adj/ vague; not clearly defined or stated [...]
the ~ article, /a or an/. ~-ly /adv/

in-fi-nite /adj/ endless; without limits; that cannot be
measured, calculated or imagined [...] ~-ly /adv/

Maybe I get something totally wrong here, or my English is just
too bad. Dunno.

Regards
--
Irrwahn
(ir*******@freenet.de)
Nov 13 '05 #33

P: n/a
Mark McIntyre <ma**********@spamcop.net> writes:
On Sun, 12 Oct 2003 01:09:01 +0200, in comp.lang.c , Sidney Cadot
<si****@jigsaw.nl> wrote:
5.2.4.1 gives some lower bounds on compile-time constructs a compiler
should be able to handle, and the other subsections give numeric
constraints that should be met.

I honestly see nothing in there that a program using infinite or
relatively deep recursion (such as my example) violates.


There are other min and max requirements scattered throughout the
standard as well, but, indeed, its probable that there's nothing to
specifically outlaw infinite recursion. Remember tho the standard is
notionally implemented in a theoretical machine. We live in the Real
World (tm) where infinite memory is not available.


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*
intelligent implementation; and, in the case of indirect
recursion between functions defined in separate translation
units, might require that the actual *object* code (assuming its
a compiler or whatnot) be rewritten. Even then, there are
certainly many examples of recursive functions which cannot be
implemented without some sort of stack that grows to some degree
with each new call, so still not all infinite recursions could be
handled.

-Micah

Nov 13 '05 #34

P: n/a

On Sun, 12 Oct 2003, Irrwahn Grausewitz wrote:

CBFalconer <cb********@yahoo.com> wrote:
Irrwahn Grausewitz wrote:
Bjoern Pedersen <bj*************@frm2.tum.de> wrote:

> A function not allocating anything (i.e. no locals,
>no parameters) colud probabaly be called indefinitly.

[ ITYM infinitely ^^^^^^^^^^^ ]

I think he meant indefinitely. It's idiomatic for as many times
as you like. Just a minor spelling error.


Hm, maybe I have to update my English dictionary.


Not really; but remember that English (and other languages, too)
can leave out a lot of non-essential words. For "indefinitely,"
read "an indefinite number of times" -- i.e., a number of times
which could be indefinitely (arbitrarily) large.

-Arthur
Nov 13 '05 #35

P: n/a

On Sun, 12 Oct 2003, Bjoern Pedersen wrote:

Sidney Cadot <si****@jigsaw.nl> writes:
I would vote for this one, as you are exceeding the required minimum
number of objects with your recursive calls ( you have one auto
variable per call, where the lifetime ends on return of the function.)


I am not aware of a requirement in the Standard that prescribes a
minimum number of active objects that an implementation must support
(where 'object' includes things like parameters and automatic
variables). Do you have a reference?


That's the Translation Limits section. I don't have the standard at
hand, but it should be around 5.2.4.1 (see post from C. Torek
upthread). Maybe some of the language lawyers here can give a better
reference.


Nope, because there is no such reference. :-)
The closest 5.2.4 comes is saying that an implementation
must support at least one 65535-byte object; but nothing is
said about supporting (or not supporting) millions of 1-byte
objects -- especially, as in this case, millions of objects
of which only one is accessible at any one time.

(Again, this has been done to death in the early stages of
the threads I posted earlier.)

-Arthur
Nov 13 '05 #36

P: n/a
"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote:

On Sun, 12 Oct 2003, Irrwahn Grausewitz wrote:

CBFalconer <cb********@yahoo.com> wrote:
>Irrwahn Grausewitz wrote:
>> Bjoern Pedersen <bj*************@frm2.tum.de> wrote:
>>
>> > A function not allocating anything (i.e. no locals,
>> >no parameters) colud probabaly be called indefinitly.
> [ ITYM infinitely ^^^^^^^^^^^ ]
>
>I think he meant indefinitely. It's idiomatic for as many times
>as you like. Just a minor spelling error.


Hm, maybe I have to update my English dictionary.


Not really; but remember that English (and other languages, too)
can leave out a lot of non-essential words. For "indefinitely,"
read "an indefinite number of times" -- i.e., a number of times
which could be indefinitely (arbitrarily) large.


Thanks. C.l.c seems to be a good place to brush up both
one's C and English knowledge. :)

Irrwahn
--
Three is no spimle sbtsuuttie for cearful, cercrot,
wtlirtew-len Esglinh. Tehre is no slveir beullt.

- Rhacrid Hfiaehlted in comp.programming, 2003-09-25
Nov 13 '05 #37

P: n/a
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.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 13 '05 #38

P: n/a
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));
}

Best regards, Sidney Cadot
Nov 13 '05 #39

P: n/a
CBFalconer <cb********@yahoo.com> 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
Nov 13 '05 #40

P: n/a
Sidney Cadot <si****@jigsaw.nl> 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
Nov 13 '05 #41

P: n/a

"Chris Torek" <no****@elf.eng.bsdi.com> wrote in message
news:bm**********@elf.eng.bsdi.com...
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
Nov 13 '05 #42

P: n/a
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

Nov 13 '05 #43

P: n/a
Sidney Cadot <si****@jigsaw.nl> 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
Nov 13 '05 #44

P: n/a
ba******************@yahoo.co.uk (Bamber) wrote in message news:<37**************************@posting.google. 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.
Nov 13 '05 #45

This discussion thread is closed

Replies have been disabled for this discussion.