Strange bug

Discussion in 'C Programming' started by Super Ted, Nov 19, 2010.

  1. Super Ted

    Super Ted Guest

    Hi I am trying to write a function to trim white-space from the beginning
    and end of a string. I have decided to capitalize on the recursive nature
    of this task and also to subdivide it into two simpler functions (trim
    left, trim right).

    Here is my code with a test-harness:

    #include <stdio.h>

    static int TrimWSpaceL(char *s)
    {
    if(isspace(*s)) {
    strcpy(s,s+1);
    return 1+TrimWSpaceL(s);
    }
    else
    return 0;
    }

    static int TrimWSpaceR(char *s)
    {
    if(isspace(*(s+strlen(s)-1))) {
    *(s+strlen(s)-1)='\0';
    return 1+TrimWSpaceR(s);
    }
    else
    return 0;
    }

    /* trims white-space, returning #spaces trimmed */
    int TrimWSpace(char *s)
    {
    return TrimWSpaceL(s) + TrimWSpaceR(s);
    }

    int main()
    {
    char s[] = " \t *Hello world* \n ";
    int i = TrimWSpace(s);
    printf("%s\n(deleted %d spaces)\n", s,i);
    return 0;
    }

    However I get an unexpected output:

    *Hello world
    (deleted 11 spaces)

    Both lines are wrong! In the first line, a * has disappeared. In the 2nd
    line, 11 spaces are reported, not 10!

    Can anyone help?

    Cheers.
     
    Super Ted, Nov 19, 2010
    #1
    1. Advertising

  2. Super Ted

    Ian Collins Guest

    On 11/20/10 09:10 AM, Super Ted wrote:
    > #include<stdio.h>


    You haven't included <ctype.h> or <string.h>, so you don't have
    prototypes for strcpy, strlen or isspace.

    --
    Ian Collins
     
    Ian Collins, Nov 19, 2010
    #2
    1. Advertising

  3. Super Ted

    Super Ted Guest

    Ian Collins writes:

    > On 11/20/10 09:10 AM, Super Ted wrote:
    >> #include<stdio.h>

    >
    > You haven't included <ctype.h> or <string.h>, so you don't have
    > prototypes for strcpy, strlen or isspace.


    Sorry, but adding those includes does not fix the problem!
     
    Super Ted, Nov 19, 2010
    #3
  4. Super Ted

    Ian Collins Guest

    On 11/20/10 10:31 AM, Super Ted wrote:
    > Ian Collins writes:
    >
    >> On 11/20/10 09:10 AM, Super Ted wrote:
    >>> #include<stdio.h>

    >>
    >> You haven't included<ctype.h> or<string.h>, so you don't have
    >> prototypes for strcpy, strlen or isspace.

    >
    > Sorry, but adding those includes does not fix the problem!


    It should, the code appears fine (and works for me).

    ../a.out
    *Hello world*
    (deleted 10 spaces)

    --
    Ian Collins
     
    Ian Collins, Nov 19, 2010
    #4
  5. Ian Collins <> writes:
    > On 11/20/10 10:31 AM, Super Ted wrote:
    >> Ian Collins writes:
    >>
    >>> On 11/20/10 09:10 AM, Super Ted wrote:
    >>>> #include<stdio.h>
    >>>
    >>> You haven't included<ctype.h> or<string.h>, so you don't have
    >>> prototypes for strcpy, strlen or isspace.

    >>
    >> Sorry, but adding those includes does not fix the problem!

    >
    > It should, the code appears fine (and works for me).
    >
    > ./a.out
    > *Hello world*
    > (deleted 10 spaces)


    strcpy(s,s+1);

    C99 7.21.2.3:

    The strcpy function copies the string pointed to by s2 (including
    the terminating null character) into the array pointed to by
    s1. If copying takes place between objects that overlap, the
    behavior is undefined.

    If you really wanted to do it this way, you could use memmove(),
    which works for overlapping arguments. But the approach
    is quite inefficient; each character is copied multiple times.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Nov 19, 2010
    #5
  6. Super Ted

    Ian Collins Guest

    On 11/20/10 10:47 AM, Keith Thompson wrote:
    > Ian Collins<> writes:
    >> On 11/20/10 10:31 AM, Super Ted wrote:
    >>> Ian Collins writes:
    >>>
    >>>> On 11/20/10 09:10 AM, Super Ted wrote:
    >>>>> #include<stdio.h>
    >>>>
    >>>> You haven't included<ctype.h> or<string.h>, so you don't have
    >>>> prototypes for strcpy, strlen or isspace.
    >>>
    >>> Sorry, but adding those includes does not fix the problem!

    >>
    >> It should, the code appears fine (and works for me).
    >>
    >> ./a.out
    >> *Hello world*
    >> (deleted 10 spaces)

    >
    > strcpy(s,s+1);
    >
    > C99 7.21.2.3:
    >
    > The strcpy function copies the string pointed to by s2 (including
    > the terminating null character) into the array pointed to by
    > s1. If copying takes place between objects that overlap, the
    > behavior is undefined.
    >
    > If you really wanted to do it this way, you could use memmove(),
    > which works for overlapping arguments. But the approach
    > is quite inefficient; each character is copied multiple times.


    Silly me - the prototype should have given that away:

    char *strcpy(char *restrict s1, const char *restrict s2);

    --
    Ian Collins
     
    Ian Collins, Nov 19, 2010
    #6
  7. Super Ted

    Mark Wooding Guest

    Super Ted <> writes:

    > #include <stdio.h>


    The `strcpy' and `strlen' functions you use are declared in <string.h>.
    The `isspace' function is declared in <ctype.h>. You should include
    these headers if you use the functions. I believe that the implicit
    declaration of `isspace' if you omit <ctype.h> is sufficient to be able
    to call it in a well-defined way; but this is not the case for `strcpy'
    or `strlen', neither of which return `int' -- the former returns a
    `char *' and the latter a `size_t'.

    My compiler gives me warnings about the above. You should probably turn
    on your compiler's warnings.

    #include <ctype.h>
    #include <string.h>

    > static int TrimWSpaceL(char *s)
    > {
    > if(isspace(*s)) {


    The ismumble functions from <ctype.h> expect to receive their argument
    in a rather peculiar form: an `unsigned char' converted to an `int'. If
    the `char' type is signed on your system (as it is in many), and the
    first character of the string is negative (and not EOF, a special
    exemption) then the behaviour is undefined.

    > strcpy(s,s+1);


    The source and destination arguments for `strcpy' mustn't overlap. This
    has undefined behaviour. Also, you do this copy for every leading
    whitespace character you find: if the string consists entirely of
    n whitespace then you move a total of n (n + 1)/2 characters, taking
    quadratic time to solve a linear-time problem.

    > return 1+TrimWSpaceL(s);


    This is not a tail position. You have potentially unbounded non-tail
    recursion, and therefore run the risk of exhausting the stack. There is
    no reason to use more than a constant amount of memory to solve this
    problem.

    Also, the type `int' may be too small to store the number of whitespace
    characters removed from the string. I'd use `size_t' instead.

    > }
    > else
    > return 0;
    > }


    static size_t trimspace_l(char *p)
    {
    const char *q;

    for (q = p; *q && isspace((unsigned char)*q); q++);
    if (q > p) memmove(p, q, strlen(q) + 1);
    return (q - p);
    }

    > static int TrimWSpaceR(char *s)
    > {
    > if(isspace(*(s+strlen(s)-1))) {


    Same remarks about isspace again. Many people would find
    `s[strlen(s) - 1]' clearer, though the two are entirely equivalent.

    More seriously, this has a bug if the string is empty: strlen(s) is
    zero, so this is s[-1], probably outside the bounds of the string, and
    undefined behaviour.

    > *(s+strlen(s)-1)='\0';


    The `strlen' function has to scan the entire string trying to find a
    zero byte. For long strings, this takes a fair amount of time. You
    call it twice for each trailing whitespace character. Again, this leads
    to quadratic running time for ought to be a linear-time operation.

    > return 1+TrimWSpaceR(s);


    And again the unbounded recursion, using linear space for what ought to
    be a constant-space operation. And again, `int' may not be large
    enough.

    > }
    > else
    > return 0;
    > }


    static size_t trimspace_r(char *p)
    {
    char *q = p + strlen(p);
    const char *r = q;

    while (q > p && isspace((unsigned char)q[-1])) *--q = 0;
    return (r - q);
    }

    > /* trims white-space, returning #spaces trimmed */
    > int TrimWSpace(char *s)
    > {
    > return TrimWSpaceL(s) + TrimWSpaceR(s);


    This performs the two trimmings in an arbitrary order. Either order is
    correct, but it's slightly (negligibly!) more efficient to trim the
    right hand side first (why?).

    > }


    static size_t trimspace(char *p)
    {
    size_t n = 0;

    n += trimspace_r(p);
    n += trimspace_l(p);
    return (n);
    }

    > int main()


    It's more usual nowadays to write `int main(void)' in C. The above
    doesn't provide a `prototype', which probably doesn't matter for `main'
    because calling `main' is usually only done in IOCCC submissions.

    > {
    > char s[] = " \t *Hello world* \n ";
    > int i = TrimWSpace(s);
    > printf("%s\n(deleted %d spaces)\n", s,i);
    > return 0;
    > }


    This seems OK.

    > However I get an unexpected output:
    >
    > *Hello world
    > (deleted 11 spaces)
    >
    > Both lines are wrong! In the first line, a * has disappeared. In the 2nd
    > line, 11 spaces are reported, not 10!


    I don't know which of the mistakes I've pointed above causes this. (On
    my system, I get the expected output for your program. That doesn't
    mean that the mistakes aren't serious -- only that they don't cause
    observable failures on one particular machine with one particular
    compiler version using one particular collection of compiler options.

    -- [mdw]
     
    Mark Wooding, Nov 20, 2010
    #7
  8. Super Ted

    Super Ted Guest

    Keith Thompson writes:

    > Ian Collins <> writes:
    >> On 11/20/10 10:31 AM, Super Ted wrote:
    >>> Ian Collins writes:
    >>>
    >>>> On 11/20/10 09:10 AM, Super Ted wrote:
    >>>>> #include<stdio.h>
    >>>>
    >>>> You haven't included<ctype.h> or<string.h>, so you don't have
    >>>> prototypes for strcpy, strlen or isspace.
    >>>
    >>> Sorry, but adding those includes does not fix the problem!

    >>
    >> It should, the code appears fine (and works for me).
    >>
    >> ./a.out
    >> *Hello world*
    >> (deleted 10 spaces)

    >
    > strcpy(s,s+1);
    >
    > C99 7.21.2.3:
    >
    > The strcpy function copies the string pointed to by s2 (including
    > the terminating null character) into the array pointed to by s1. If
    > copying takes place between objects that overlap, the behavior is
    > undefined.
    >
    > If you really wanted to do it this way, you could use memmove(), which
    > works for overlapping arguments. But the approach is quite inefficient;
    > each character is copied multiple times.


    This is a truely stupid restriction. I have now written a strcpy_safe
    function by hand, where all string copies are valid, and from now on I
    will use only that in all my future code.
     
    Super Ted, Nov 20, 2010
    #8
  9. Super Ted

    Super Ted Guest


    > More seriously, this has a bug if the string is empty: strlen(s) is
    > zero, so this is s[-1], probably outside the bounds of the string, and
    > undefined behaviour.


    I do not check argument validity for efficiency reasons. Like with
    standard functions eg strlen, the caller of my function is responsible
    for ensuring it doesn't pass a null string.
     
    Super Ted, Nov 20, 2010
    #9
  10. Super Ted

    Seebs Guest

    On 2010-11-20, Super Ted <> wrote:
    > Keith Thompson writes:
    >> The strcpy function copies the string pointed to by s2 (including
    >> the terminating null character) into the array pointed to by s1. If
    >> copying takes place between objects that overlap, the behavior is
    >> undefined.


    > This is a truely stupid restriction.


    Is it?

    Because it seems to me that if it were all that stupid, surely someone
    would have pointed this out and it wouldn't be there.

    Is it possible that there is a reason for it which you don't understand?

    > I have now written a strcpy_safe
    > function by hand, where all string copies are valid, and from now on I
    > will use only that in all my future code.


    All string copies? That's an accomplishment.

    -s
    --
    Copyright 2010, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
     
    Seebs, Nov 20, 2010
    #10
  11. Super Ted <> writes:
    >> More seriously, this has a bug if the string is empty: strlen(s) is
    >> zero, so this is s[-1], probably outside the bounds of the string, and
    >> undefined behaviour.

    >
    > I do not check argument validity for efficiency reasons. Like with
    > standard functions eg strlen, the caller of my function is responsible
    > for ensuring it doesn't pass a null string.


    By "null string", you mean a string with a length of zero, right?
    The usual term for that is "empty string", which avoids confusion
    with null pointers. (Pointers are not strings, of course, but
    passing a string is usually accomplished by passing a pointer to
    the first character.)

    Note that strlen is perfectly happy with an empty string (it
    returns 0).

    Does the documentation for your function state that its behavior is
    undefined when it's given an empty string? If so, then passing an
    empty string is caller's fault; if not, failing to handle an emtpy
    string gracefully is your fault.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Nov 20, 2010
    #11
  12. Super Ted

    Seebs Guest

    On 2010-11-20, Super Ted <> wrote:
    >> More seriously, this has a bug if the string is empty: strlen(s) is
    >> zero, so this is s[-1], probably outside the bounds of the string, and
    >> undefined behaviour.


    > I do not check argument validity for efficiency reasons. Like with
    > standard functions eg strlen, the caller of my function is responsible
    > for ensuring it doesn't pass a null string.


    You are confused. An empty string is not the same as a null string.

    You should absolutely handle empty strings correctly.

    -s
    --
    Copyright 2010, all wrongs reversed. Peter Seebach /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
    I am not speaking for my employer, although they do rent some of my opinions.
     
    Seebs, Nov 20, 2010
    #12
  13. Super Ted <> writes:
    > Keith Thompson writes:

    [...]
    >> C99 7.21.2.3:
    >>
    >> The strcpy function copies the string pointed to by s2 (including
    >> the terminating null character) into the array pointed to by s1. If
    >> copying takes place between objects that overlap, the behavior is
    >> undefined.
    >>
    >> If you really wanted to do it this way, you could use memmove(), which
    >> works for overlapping arguments. But the approach is quite inefficient;
    >> each character is copied multiple times.

    >
    > This is a truely stupid restriction. I have now written a strcpy_safe
    > function by hand, where all string copies are valid, and from now on I
    > will use only that in all my future code.


    Note that the name "strcpy_safe", like any identifier starting with
    "str" and a lowercase letter, is reserved.

    The point of the restriction is that the vast majority of string
    copies take place between non-overlapping objects. strcpy() can be
    made just a little faster by not having to check for an overlap.
    We give up defined behavior in 0.1% of cases for greater speed in
    99.9% of cases (yes, I pulled those numbers of thin air).

    You might be giving up even more performance if the implementation's
    strcpy() uses compiler-specific tricks to get better speed, tricks
    that you can't use in portable code.

    Your strcpy_safe function might still be useful. If it were in the
    standard, strmove() would probably be a good name for it (by analogy
    with memcpy() vs. memmove()).

    A suggestion: don't call a language feature or restriction "truly
    stupid" until you understand why it's there. Sometimes you might
    be right, but I think you'll often find there are good reasons you
    haven't yet thought about.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Nov 20, 2010
    #13
  14. Super Ted

    Ian Collins Guest

    On 11/21/10 10:35 AM, Super Ted wrote:
    > Keith Thompson writes:
    >
    >> Ian Collins<> writes:
    >>> On 11/20/10 10:31 AM, Super Ted wrote:
    >>>> Ian Collins writes:
    >>>>
    >>>>> On 11/20/10 09:10 AM, Super Ted wrote:
    >>>>>> #include<stdio.h>
    >>>>>
    >>>>> You haven't included<ctype.h> or<string.h>, so you don't have
    >>>>> prototypes for strcpy, strlen or isspace.
    >>>>
    >>>> Sorry, but adding those includes does not fix the problem!
    >>>
    >>> It should, the code appears fine (and works for me).
    >>>
    >>> ./a.out
    >>> *Hello world*
    >>> (deleted 10 spaces)

    >>
    >> strcpy(s,s+1);
    >>
    >> C99 7.21.2.3:
    >>
    >> The strcpy function copies the string pointed to by s2 (including
    >> the terminating null character) into the array pointed to by s1. If
    >> copying takes place between objects that overlap, the behavior is
    >> undefined.
    >>
    >> If you really wanted to do it this way, you could use memmove(), which
    >> works for overlapping arguments. But the approach is quite inefficient;
    >> each character is copied multiple times.

    >
    > This is a truely stupid restriction.


    Er, no, it isn't. Study the prototype again, then read up on restrict
    and the optimisations it permits.

    --
    Ian Collins
     
    Ian Collins, Nov 20, 2010
    #14
  15. Super Ted wrote:
    >> More seriously, this has a bug if the string is empty: strlen(s) is
    >> zero, so this is s[-1], probably outside the bounds of the string, and
    >> undefined behaviour.

    >
    > I do not check argument validity for efficiency reasons. Like with
    > standard functions eg strlen, the caller of my function is responsible
    > for ensuring it doesn't pass a null string.


    I'm assuming that by "null string" you mean what's usually called an
    empty string, or a zero-length string, the type of string Mark was
    talking about. That's a perfectly valid string; you're wrong about the
    standard functions, they're required to handle such a string correctly.
     
    J. J. Farrell, Nov 20, 2010
    #15
  16. On 19/11/2010 21:10, Super Ted wrote:
    > Hi I am trying to write a function to trim white-space from the beginning
    > and end of a string. I have decided to capitalize on the recursive nature
    > of this task and also to subdivide it into two simpler functions (trim
    > left, trim right).


    The reasons I know to use C rather than (insert other language) are
    - fast executable code.
    - source code understandable by a wide human audience.
    - source code portable to many platforms.

    The approach used
    - resulted in inherently slow code (execution time is proportional
    to the square of the length of the input for a string consisting
    of spaces and final char).
    - resulted in verbose code, that is thus harder to check than
    a straight non-recursive version.
    - gave code that was not portable (non-conformant use of strcpy;
    missing headers;then use of a reserved name for a strcpy substitute).

    I conclude the decision "to capitalize on the recursive nature of
    this task" and to do it in C are inconsistent, except perhaps as a
    learning exercise
    - on how to code recursive tasks in C.
    - on why NOT to code thing recursively when they can be coded more
    simply without recursion.

    Also, all four embedded C compilers I use have two modes: one that
    supports recursion, and another that generates much faster and
    compact code by analyzing the call tree and assigning static addresses
    to all automatic variables. Guess which one is used, and the resulting
    practical portability of recursive code.

    I note that the archetypal learning use case for recursion are
    factorials and the "Tower of Hanoi", although both happen to have
    a non-recursive solution which is much simpler:
    http://en.wikipedia.org/wiki/Tower_of_Hanoi#Non-recursive_solution
    This should be a giveaway that recursion is seldom useful, since
    instructors fail to find a good use case for it.

    Francois Grieu
     
    Francois Grieu, Nov 21, 2010
    #16
  17. Super Ted

    BartC Guest

    "Francois Grieu" <> wrote in message
    news:4ce90002$0$8129$...
    > On 19/11/2010 21:10, Super Ted wrote:
    >> Hi I am trying to write a function to trim white-space from the beginning
    >> and end of a string. I have decided to capitalize on the recursive nature
    >> of this task and also to subdivide it into two simpler functions (trim
    >> left, trim right).

    >
    > The reasons I know to use C rather than (insert other language) are
    > - fast executable code.


    > - source code understandable by a wide human audience.
    > - source code portable to many platforms.


    (Which is also a bit of myth (from what I've seen). Ignoring the mess of
    conditional macros that seem to be needed to make this happen, 'portability'
    also seems to depend on using, for example, the right compiler, the exact
    sequence of compiler options, and the right makefile syntax. And a lot of
    luck)

    >
    > The approach used
    > - resulted in inherently slow code (execution time is proportional
    > to the square of the length of the input for a string consisting
    > of spaces and final char).
    > - resulted in verbose code, that is thus harder to check than
    > a straight non-recursive version.
    > - gave code that was not portable (non-conformant use of strcpy;
    > missing headers;then use of a reserved name for a strcpy substitute).


    I think this exercise was just an experiment, rather than a serious
    implementation.

    > I note that the archetypal learning use case for recursion are
    > factorials and the "Tower of Hanoi", although both happen to have
    > a non-recursive solution which is much simpler:
    > http://en.wikipedia.org/wiki/Tower_of_Hanoi#Non-recursive_solution
    > This should be a giveaway that recursion is seldom useful, since
    > instructors fail to find a good use case for it.


    It tends to be useful when the problem itself, or the data, has a recursive
    nature...

    --
    Bartc
     
    BartC, Nov 21, 2010
    #17
  18. Super Ted

    Eric Sosman Guest

    On 11/20/2010 4:35 PM, Super Ted wrote:
    > Keith Thompson writes:
    >[...]
    >> C99 7.21.2.3:
    >>
    >> The strcpy function copies the string pointed to by s2 (including
    >> the terminating null character) into the array pointed to by s1. If
    >> copying takes place between objects that overlap, the behavior is
    >> undefined.
    >> [...]

    > This is a truely stupid restriction. I have now written a strcpy_safe
    > function by hand, where all string copies are valid, and from now on I
    > will use only that in all my future code.


    Super Ted, we all owe you a tremendous debt of gratitude for
    pointing out the stupidity of a restriction that has plagued the C
    library for more than two decades. In all that time, you're the
    first to have seen that the restriction is pointless and could be
    removed easily. Thank you, thank you, thank you for being so much
    smarter than all the C practitioners that have gone before.

    Just a few minor matters: (1) using strcpy_safe as the name of
    your function isn't a good idea, since all external names beginning
    with str... are reserved, (2) there's a faint chance that the preceding
    paragraph might be insincere, and that there's something you haven't
    realized yet, and (3) there's no "e" in "truly."

    --
    Eric Sosman
    lid
     
    Eric Sosman, Nov 21, 2010
    #18
  19. Super Ted

    BartC Guest

    "Eric Sosman" <> wrote in message
    news:icbb4q$41t$-september.org...
    > On 11/20/2010 4:35 PM, Super Ted wrote:
    >> Keith Thompson writes:
    >>[...]
    >>> C99 7.21.2.3:
    >>>
    >>> The strcpy function copies the string pointed to by s2 (including
    >>> the terminating null character) into the array pointed to by s1. If
    >>> copying takes place between objects that overlap, the behavior is
    >>> undefined.
    >>> [...]

    >> This is a truely stupid restriction. I have now written a strcpy_safe
    >> function by hand, where all string copies are valid, and from now on I
    >> will use only that in all my future code.


    > realized yet, and (3) there's no "e" in "truly."


    No, but there is one in "truely".

    --
    Bartc
     
    BartC, Nov 21, 2010
    #19
  20. Super Ted

    Eric Sosman Guest

    On 11/21/2010 9:05 AM, BartC wrote:
    >
    > "Francois Grieu" <> wrote in message
    > news:4ce90002$0$8129$...
    >> On 19/11/2010 21:10, Super Ted wrote:
    >>> Hi I am trying to write a function to trim white-space from the
    >>> beginning
    >>> and end of a string. I have decided to capitalize on the recursive
    >>> nature
    >>> of this task and also to subdivide it into two simpler functions (trim
    >>> left, trim right).

    >>
    >> The reasons I know to use C rather than (insert other language) are
    >> - fast executable code.

    >
    >> - source code understandable by a wide human audience.
    >> - source code portable to many platforms.

    >
    > (Which is also a bit of myth (from what I've seen). Ignoring the mess of
    > conditional macros that seem to be needed to make this happen,
    > 'portability'
    > also seems to depend on using, for example, the right compiler, the exact
    > sequence of compiler options, and the right makefile syntax. And a lot
    > of luck)


    Topic drift: It used to be said that "C combines the power of
    assembly language with the portability of assembly language," and
    this was (sort of) true twenty-odd years ago. Prior to the ANSI
    standard, C code had to be larded up with all manner of #ifdef's
    and the like if it was to be ported at all. C wasn't portable; it
    was luggable.

    But the ANSI standard improved matters vastly, which I think
    was the main reason for its rapid uptake (contrast the reluctant
    adoption of C99). With ANSI, it became not only possible but
    practical to write portable code, with few or even no "feature test"
    macros lying around. Read some C from a quarter-century ago and
    contrast it with more recent C, and the improvement will be obvious.

    Unfortunately, a C Standard can only legislate C itself, not the
    environments in which C runs. Programs that use networking or window
    systems or shared memory or ... still need to indulge in feature-
    testing -- but it's for the beyond-C stuff, not for C per se. (Indeed,
    some parts of POSIX are devoted to standardizing feature tests!) You
    no longer see #ifdef's governing whether <string.h> or <strings.h> is
    included, you see #ifdef's governing whether to use fork() or spawn().

    ... except, of course, when you run across C code written by
    people who have not learned how to write portably. It remains possible
    to write non-portable C (indeed, the Rationale treats the possibility
    as an objective), and there are lots of bad examples to lead beginners
    astray. Perhaps that's why this group attaches so much importance to
    describing what is and isn't portable: It's not about prohibiting code
    that is intentionally and constructively non-portable, but about raising
    consciousness so that code isn't non-portable out of carelessness.

    As for Makefiles, compiler options, and the like: Again, you're
    talking about things outside the realm of the C language. It is, I
    guess, conceivable that the C Standard might have tried to specify the
    nature and form of the tools used with C, but I doubt the effort would
    have been successful; we might still be waiting for the first Standard
    if it had tried to specify all the linker options for Unix, Windows,
    OpenVMS, MVS, ...

    >> The approach used
    >> - resulted in inherently slow code (execution time is proportional
    >> to the square of the length of the input for a string consisting
    >> of spaces and final char).
    >> - resulted in verbose code, that is thus harder to check than
    >> a straight non-recursive version.
    >> - gave code that was not portable (non-conformant use of strcpy;
    >> missing headers;then use of a reserved name for a strcpy substitute).

    >
    > I think this exercise was just an experiment, rather than a serious
    > implementation.


    Probably. In which case it's odd that the O.P. uses "efficiency"
    as his excuse for not validating function arguments. (It's also odd
    that he prates of "efficiency" while using an inherently inefficient
    algorithm.)

    >> I note that the archetypal learning use case for recursion are
    >> factorials and the "Tower of Hanoi", although both happen to have
    >> a non-recursive solution which is much simpler:
    >> http://en.wikipedia.org/wiki/Tower_of_Hanoi#Non-recursive_solution
    >> This should be a giveaway that recursion is seldom useful, since
    >> instructors fail to find a good use case for it.

    >
    > It tends to be useful when the problem itself, or the data, has a recursive
    > nature...


    Francois' point remains, though: If such problems are commonplace,
    why do the teachers always assign exercises about Fibonacci numbers?
    Can't they think of a problem for which recursion is useful, and not
    just possible? I'd have thought Quicksort would make a good vehicle,
    both for teaching the idea of recursion and for illustrating some of
    its pitfalls -- but no, we keep seeing Fibonacci computations that
    are described as "elegant" and take exponential running time. Pfui!

    --
    Eric Sosman
    lid
     
    Eric Sosman, Nov 21, 2010
    #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. S. Justin Gengo
    Replies:
    0
    Views:
    537
    S. Justin Gengo
    Jul 16, 2003
  2. Philipp Schumann
    Replies:
    2
    Views:
    1,387
  3. Shawn

    Very very strange. Major bug?

    Shawn, Feb 3, 2004, in forum: ASP .Net
    Replies:
    4
    Views:
    348
    Shawn
    Feb 4, 2004
  4. Bruno Jouhier [MVP]
    Replies:
    5
    Views:
    416
    Steven Cheng[MSFT]
    Apr 7, 2004
  5. Harvey Twyman
    Replies:
    8
    Views:
    569
    August Derleth
    Oct 25, 2003
Loading...

Share This Page