Coming from assembler background, it didn't take very long for me to recognize the fallacy of recursion -- problems can be solved "elegantly", but, apart from designing a special harness to "babysit" the recursion loop, the whole thing can overflow the stack, which makes it inherently unreliable.

Elegance of code is more than just beauty: it need not necessarily be short/small code, but it should be as simple as possible, because, as I often teach, simple is robust; and only when one has robust building blocks as foundations, can one hope to build more complex robust solutions. Recursion, alas, does not belong into that category because of its conventional implementation.

Finally, I'll leave with quoting a famous programmer:

"Programming perfection is not when there's nothing more to add to a program, but when there is nothing left to take away."

Posted by UX-admin on July 11, 2007 at 02:27 AM PDT #

Posted by Rafael de F. Ferreira on July 12, 2007 at 08:22 PM PDT #

Posted by Bryan Cantrill on July 13, 2007 at 12:01 PM PDT #

Posted by Michael Feathers on July 16, 2007 at 11:00 PM PDT #

Posted by josh on July 17, 2007 at 07:14 AM PDT #

Michael, as Geoff mentioned, if input is not checked (and I hasten to add that the length-of-death is much lower than 300K -- as low as 37K) this is a potential security problem. Now, as I believe Josh is trying to say, this does not constitute a buffer overflow attack -- an attacker could not use this vector to execute arbitrary code on the stack. But contrary to Josh's assertion that there is "no security problem", this does allow for a potential DoS attack.

That said, to me the issue is less about security and more about failure mode. Michael, while your assertion about tolerances is interesting, the physical world is ultimately a poor analogy for software: this is not physical failure, it is logical failure -- and there's quite a difference. To me, the better analogy is with mathematics: if you prove a theorem for all n less than 38,821, is that proof correct? It depends, of course, on how that proof is labelled: if one asserts that one has proved the theorem for all n when, in fact, it's only proved for n less than 38,821, than the proof is incorrect. If, however, one accurately claims that one has only proved the theorem for n less than 38,821, then the proof is correct -- but it is also clearly a proof of limited consequence, and certainly not one for Erdös's Book. My argument is that it is better to correctly solve a smaller problem (i.e. limited input) than to incorrectly solve a more ambitious problem (i.e. arbitrary input).

Finally, as for the assertion that we "get ourselves in trouble when we assume that functions have to work across all inputs", I could not disagree more -- indeed, I believe that we get ourselves into trouble when we make implicit assumptions that our input will fit some (ill-defined) notion of "reasonable." In my experience, software that makes such implicit assumptions becomes especially problematic as its used as foundation software, introducing new, cascading failure modes into the system. Certainly if one fancies writing software that will itself be used by higher layers of software, one must be paranoid about input and explicit about failure modes.

Posted by Bryan Cantrill on July 17, 2007 at 08:56 AM PDT #

Bryan, we can go back and forth about whether it's a logical or a physical problem.. but those are just labels. To me, the crux of this is the fact that the algorithm has certain computational characteristics that place constraints on the environment. If the environment doesn't meet them, we probably shouldn't run it.

You're proof analogy is fine as it stands, but I think we have to question the assumption. Nobody is making the assertion that the algorithm is correct for all N input sequences. We might be able to construct a proof, but that proof would say something about the algorithm on an ideal machine (infinite stack). It wouldn't say anything about what you can expect in the face of physical (whoops, I said it) resource constraints.

I think that the biggest beef I have with your position is that I feel that there is no single standard for correctness or appropriateness of coding style in the industry. What you do in software that you release to thousands of users can be different from what you do in software you use in a tool for a small workgroup. Safety critical is another area, so is teaching software. As well, not all software is in the middle of an application stack. Not all software is distributed either. Some has trusted users.

FIT is a good example. It's heavily recursive, and I imagine it could overflow the stack if the size of the tables it processes are too large. I don't think it's a serious problem, though. FIT is used in work groups where developers are always present. If it happened, the size of tables would be the obvious culprit. Would I want flight control software to be that trusting? No, but that's a completely different domain. There is no "one size fits all" standard for code.

Posted by Michael Feathers on July 17, 2007 at 01:12 PM PDT #

Posted by PJW on July 17, 2007 at 07:40 PM PDT #

I think a lot of people are missing the point. This is a very concise and elegant solution to a simple pattern matcher. It will work on all practical examples. If you want to treat some arbitrary input from an untrusted user as a match pattern, it's your own fault if you don't verify and place limits on that input first.

A robust regexp library would compile simple patterns like this to a DFA. Or, more likely, include more features such as alternations and remembering submatches, and compile some or all patterns to NFA's. This will be a lot more complicated. For something as commonly used as regexps it may be worth having such a full library, but on small and embedded systems, or for less common tasks for which there isn't likely to be a pre-existing library, it's a great advantage to be able to quickly put together simple, clean code like this.

Regarding tail-call optimization, the reason the example has non-tail calls is because it's using backtracking, and it needs somewhere to store that information. The stack is the easiest place to do this, but you can always move the data into the heap (a technique Scheme programmers are used to).

Below is a straightforward translation of the same code to use the heap instead of the stack, and thus never blows out the stack when compiled with gcc -O2. It's basically the same thing, except you pass around an extra "stack" parameter. matchstar is made simpler by just pushing a backtrack point onto the stack and recursing (and could just as easily do greedy matching).

For technical reasons, matchhere needs an unused extra "int c" parameter to force tail-call optimizations. See http://www.ddj.com/dept/cpp/184401756 for the explanation. This and explicit malloc/free make the code a lot more clumsy than the equivalent in Scheme, where you have GC and tail-calls are guaranteed to be optimized.

-- Alex

typedef struct _matchstack {
  int c;
  char *regexp;
  char *text;
  struct _matchstack *next;
} *matchstack;

int matchhere(int, char *, char *, matchstack);
int matchstar(int, char *, char *, matchstack);
int matchfail(matchstack);
matchstack matchpushstack(int, char *, char *, matchstack);

int
match(char *regexp, char *text)
{
        if (regexp[0] == '^') 
          return (matchhere('\0', regexp + 1, text, NULL));
        else
          return (matchstar('.', regexp, text, NULL));
}

int
matchhere(int c, char *regexp, char *text, matchstack stack)
{
        if (regexp[0] == '\0')
                return (1);

        if (regexp[1] == '*')
                return (matchstar(regexp[0], regexp + 2, text, stack));

        if (regexp[0] == '$' && regexp[1] == '\0')
                return (*text == '\0');

        if (*text != '\0' && (regexp[0] == '.' || regexp[0] == *text))
                return (matchhere(c, regexp + 1, text + 1, stack));

        return (0);
}

int
matchstar(int c, char *regexp, char *text, matchstack stack)
{
        if (*text != '\0' && (*text == c || c == '.'))
              stack = matchpushstack(c, regexp, text+1, stack);
        return matchhere(c, regexp, text, stack);
}

int
matchfail(matchstack stack)
{
        int c;
        char *regexp, *text;
        matchstack next;
        if (stack) {
               c = stack->c;
               regexp = stack->regexp;
               text = stack->text;
               next = stack->next;
               free(stack);
               return matchstar(c, regexp, text, next);
        } else {
               return (0);
        }
}

matchstack
matchpushstack(int c, char *regexp, char *text, matchstack stack)
{
        matchstack newstack = (matchstack) malloc(sizeof(struct _matchstack));
        newstack->c = c;
        newstack->regexp = regexp;
        newstack->text = text;
        newstack->next = stack;
        return newstack;
}

Posted by Alex Shinn on July 18, 2007 at 09:00 PM PDT #

This all brings to mind a conversation that Bill Moore once relayed to me: he was talking to a friend of his who is a professional drummer. The friend said that the primary difference between the amateur drummer and the professional drummer is that the professional can recover when things go wrong. In short, the difference between the amateur and the professional is error handling -- and I think this holds true for software as well.

Posted by Bryan Cantrill on July 19, 2007 at 12:33 PM PDT #

Posted by Alex Shinn on July 19, 2007 at 04:00 PM PDT #

Posted by sri on July 20, 2007 at 05:31 PM PDT #