why does this work ?

Discussion in 'C Programming' started by Bamber, Oct 10, 2003.

  1. Bamber

    Bamber Guest

    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.
     
    Bamber, Oct 10, 2003
    #1
    1. Advertising

  2. Bamber <> 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 () ---------------------------\
    | 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
     
    Joona I Palaste, Oct 10, 2003
    #2
    1. Advertising

  3. Greetings.

    In article <>, 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
     
    Tristan Miller, Oct 10, 2003
    #3
  4. Bamber

    Dan Pop Guest

    In <> (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:
     
    Dan Pop, Oct 10, 2003
    #4
  5. Bamber

    Sidney Cadot Guest

    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
     
    Sidney Cadot, Oct 11, 2003
    #5
  6. In article <bm8ne5$hf3$>,
    Sidney Cadot <> 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.
     
    Christian Bau, Oct 11, 2003
    #6
  7. Bamber

    Chris Torek Guest

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


    In article <bm8ne5$hf3$>
    Sidney Cadot <> 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.
     
    Chris Torek, Oct 11, 2003
    #7
  8. On Sat, 11 Oct 2003 12:53:07 +0200, Sidney Cadot <>
    wrote:

    >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


    It is valid in the theoretical sense but it executes in the real
    world.

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


    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.

    Do you know how much data your system must save when a function is
    re-called? Usually, this includes information about the state of your
    task (such as the address to return to) and all automatic variables
    (those defined in your code and any generated by the compiler to hold
    intermediate results). There is probably more that I cannot think of
    at the moment. What would you accept as a reasonable estimate? 100
    bytes just to make the arithmetic easier?

    ULONG_MAX is required to be greater than 4,000,000,000 (that's billion
    on my side of the pond but perhaps milliard on yours, 4*10^9 in any
    case). What will happen when z is 10,000,000 (a mere 10 million)? f
    will be recursively called 10 million times, requiring 1 gigabyte of
    storage. Is your task authorized to consume that much of your system
    resources? Does your system even have that much available? Even if
    you can support this, can you support z at 100 million requiring 10
    gigabtyes? At 4 billion (milliard) requiring 400 gigabytes? What
    happens if long is 64 bits on your system?

    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. 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.

    Welcome to the limitations of practicality.


    <<Remove the del for email>>
     
    Barry Schwarz, Oct 11, 2003
    #8
  9. Bamber

    Sidney Cadot Guest

    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
     
    Sidney Cadot, Oct 11, 2003
    #9
  10. On Sat, 11 Oct 2003 12:53:07 +0200, in comp.lang.c , Sidney Cadot
    <> 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 =---
     
    Mark McIntyre, Oct 11, 2003
    #10
  11. 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?
    threadm=

    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
    threadm=3eb1049b$
    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
     
    Arthur J. O'Dwyer, Oct 11, 2003
    #11
  12. On Sun, 12 Oct 2003 00:12:38 +0200, in comp.lang.c , Sidney Cadot
    <> 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 =---
     
    Mark McIntyre, Oct 11, 2003
    #12
  13. Bamber

    Sidney Cadot Guest

    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
     
    Sidney Cadot, Oct 11, 2003
    #13
  14. Bamber

    Sidney Cadot Guest

    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
     
    Sidney Cadot, Oct 12, 2003
    #14
  15. Bamber

    Sidney Cadot Guest

    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
     
    Sidney Cadot, Oct 12, 2003
    #15
  16. Bamber

    Sidney Cadot Guest

    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
     
    Sidney Cadot, Oct 12, 2003
    #16
  17. On Sun, 12 Oct 2003 01:09:01 +0200, in comp.lang.c , Sidney Cadot
    <> 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 =---
     
    Mark McIntyre, Oct 12, 2003
    #17
  18. On Sun, 12 Oct 2003 01:21:39 +0200, in comp.lang.c , Sidney Cadot
    <> 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 =---
     
    Mark McIntyre, Oct 12, 2003
    #18
  19. On Sun, 12 Oct 2003 01:31:51 +0200, in comp.lang.c , Sidney Cadot
    <> 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 =---
     
    Mark McIntyre, Oct 12, 2003
    #19
  20. Bamber

    Sidney Cadot Guest

    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
     
    Sidney Cadot, Oct 12, 2003
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jblazi
    Replies:
    5
    Views:
    458
    jblazi
    Aug 16, 2004
  2. Horace Nunley

    why why why does function not work

    Horace Nunley, Sep 27, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    500
    =?Utf-8?B?UGV0ZXIgQnJvbWJlcmcgW0MjIE1WUF0=?=
    Sep 27, 2006
  3. Mr. SweatyFinger

    why why why why why

    Mr. SweatyFinger, Nov 28, 2006, in forum: ASP .Net
    Replies:
    4
    Views:
    979
    Mark Rae
    Dec 21, 2006
  4. Mr. SweatyFinger
    Replies:
    2
    Views:
    2,226
    Smokey Grindel
    Dec 2, 2006
  5. Tarun
    Replies:
    5
    Views:
    418
    Tarun
    Jul 14, 2005
Loading...

Share This Page