http://qs321.pair.com?node_id=492476

I was reading the passage below from Larry Wall second state of the onion's speech (98) :

You need a certain amount of complexity to do any particular job. A Saturn V rocket is said to have had seven million parts, all of which had to work. But that's not entirely true. Many of those parts were redundant. But that redundancy was absolutely necessary to achieve the goal of putting someone on the moon in 1969. So if some of those rocket parts had the job of being redundant, then each of those parts still had to do their part. So to speak. They also serve who only stand and wait.

We betray ourselves when we say "That's redundant", meaning "That's useless." Redundancy is not always "redundant", whether you're talking about rockets or human languages or computer languages. In short, simplicity is often the enemy of success.

Suppose I want to take over the world. laughter Not hard to imagine, eh? Simplicity says I should just take over the world by myself. But the reality of the situation is that I need your help to take over the world, and you're all very complex. I actually consider that a feature. Your relationships are even more complex. I usually think of those as features. But sometimes they're bugs. We can debug relationships, but it's always good policy to consider the people themselves to be features. People get annoyed when you try to debug them. "

and the question that came to (my) mind was:

Suppose I implement a faulty algorithm (faulty defined as: -any program in any programming language written as a perfect syntactic representation of the algorithm could be faulted using at least one test case consistent across all implementations) in Perl.

Suppose my Perl implementation happens to also be a faulty implementation of my faulty algorithm (for example, I don't use strict and make a case syntax error, or I switch a $ for a @), but a perfectly valid Perl program. Suppose also that my faulty implementation of my faulty algorithm will give the proper output on all input.

Question:
Does my program have a bug ?

Replies are listed 'Best First'.
Re: Feature or Bug ?
by pg (Canon) on Sep 16, 2005 at 02:16 UTC

    Couple of things:

    • Whether your program has bug is not a fixed or constant truth, but rather a conclusion made based on the way of observation. If our way of observation is black box testing, obviously we will say that your program has no bug as far as we tested. But if part of our observation is a code review, someone may quickly realize that you are not implementing the algorithm, regardless whether the algorithm is correct, your program has a bug. Or someone might realize that the algorithm is faulty, thus regardless of your implementation, your program is faulty.
    • Secondly, to say that the algorithm or the implementation is/are faulty is meaningless, unless such claim is supported by facts. If the only fact is your seemingly successful testing, no suggestion can be made that the implementation or algorithm is/are faulty. There might be some hidden truth, but you cannot claim it until it is proved so. For example, we can make that conclusion if there is a correct implementation of the faulty algorithm, or vice versa, and subsequently fail the testing, and lead to the realization of such truth.

      On the other hand, human understanding of the natural or so called truth is never complete, thus it can only be considered as true under a complex set of assumptions, or to be more straight "always faulty", but as time goes, you are getting more and more close to the never reaching truth, and sometime you could even go backwards. In the world of computer science, all programs with a certain level (this level can be easily exceeded, much easier than you thought) of complexity are buggy, and it is just a timing issue for you to find the next bug in a perfect program.

Re: Feature or Bug ?
by dragonchild (Archbishop) on Sep 16, 2005 at 01:03 UTC
    Let's say I have a subroutine that looks something like:
    sub dummy { no strict; no warnings; ${"$_[0]"} = $_[1]; }
    Is that code buggy? Maybe ... maybe not. That code is unsafe, but unsafe is not necessary incorrect. You cannot evaluate a piece of code outside of its context.

    Now, most of us are in the habit of evaluating a piece of code within a global context, because any piece of code may be used anywhere, but that's not always reasonable. The rules in my sig are ordered as they are for a reason. Good software follows rule #1. Great software needs rule #2, but the perfect is the enemy of the good.


    My criteria for good software:
    1. Does it work?
    2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

      "My criteria for good software: ..
      2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?"

      (2) depends also somewhat on the person who comes in.

        I may not necessarily have the same criteria for good software as dragonchild, but no, it shouldn't depend on the person who comes in. I think that's (part of) dragonchild's point.

        Anyone should be able to come in, make a change to some small part of the program, and be reasonably certain that everything else continues to work as before, with this modification. I do think this ideal is a wee bit lofty for any set of requirements that approach moderate complexity, but I think I see where he's coming from.

        Absolutely. One of the hallmarks of the master programmer is that s/he programs with the intended maintenance programmer's level in mind. For example, the code I write for my CPAN modules is very different from the code I write when doing maintenance on a contract. In the first case, the only people I expect to even read it are programmers of my skill level, so I can use more advanced constructs (soft references and closures) and my code can be more compact. I also make extensive use of direct access into @_, where I would never do that in application code.

        My criteria for good software:
        1. Does it work?
        2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
Re: Feature or Bug ?
by chas (Priest) on Sep 16, 2005 at 00:57 UTC
    Well, a "faulty implementation of my faulty algorithm" could happen to be a correct implementation of the "correct" algorithm, so in that case no. And, generally, if a program gives proper (i.e. desired) output on all input, then how can it be considered to have a bug? A program is a function mapping inputs to outputs, and if it does this "correctly", then it is correct, isn't it?
    chas
Re: Feature or Bug ?
by chester (Hermit) on Sep 16, 2005 at 01:05 UTC
    It doesn't have a bug so long as no one ever has to edit or update or maintain or read your program or do anything that relies upon your understading of what you intended to do. So, yes, I think it has a bug. If only that the documentation (which of course was written extensively!) will be inconsistent with what the program is doing, or at least with how it's doing it.

      "So, yes, I think it has a bug. If only that the documentation (which of course was written extensively!) will be inconsistent with what the program is doing, "

      Sure, but while the program is a faulty implementation of a faulty algorithm to compute X, it's also a correct implementation of a correct algorithm to compute X.

      Would we really want to fix that bug ? And if not, is it still a bug ?

Re: Feature or Bug ?
by spiritway (Vicar) on Sep 16, 2005 at 05:55 UTC

    Since your premise states that you have incorrectly implemented a faulty algorithm, it seems to me that you have two bugs.

    Whether the bugs are ever discovered seems to me to be irrelevant.

Re: Feature or Bug ?
by jepri (Parson) on Sep 16, 2005 at 05:58 UTC
    If it works, it is correct.

    If you're presenting an theory of a higher truth for programming, and an idea of perfect code, then I'm not swayed by your current argument :)

    ___________________
    Jeremy
    I didn't believe in evil until I dated it.

Re: Feature or Bug ?
by radiantmatrix (Parson) on Sep 16, 2005 at 17:18 UTC

    This is largely symantics. A bug is a problem that is observable erroneous behavior - if the correct output is always generated, there is no bug in the system.

    So you only have one bug, in one component: your algorithm has a bug. If you've implemented it outside the specification (faulty implementation), even by accident, what you have isn't a bug but a workaround for the bug in the algorithm.

    Your overall system, then, has no bugs. However, there is a vast difference between not buggy and provably correct. The hypothetical system here is not buggy, but neither is it provably correct. Which matters more largely depends on whether you're labor or management. ;-)

    <-radiant.matrix->
    Larry Wall is Yoda: there is no try{} (ok, except in Perl6; way to ruin a joke, Larry! ;P)
    The Code that can be seen is not the true Code
    "In any sufficiently large group of people, most are idiots" - Kaa's Law
Re: Feature or Bug ?
by ady (Deacon) on Sep 17, 2005 at 08:16 UTC
    Question: Suppose also that my faulty implementation of my faulty algorithm will give the proper output on all input. -- Does my program have a bug ?

    The input/output function (the mapping from one set of values to another) is the mathematical definition of behavioural correctness of a program transformation. If your implementation (as stated) performs the transformation as specified, it is correct from a black box perspective.

    Example:
    A program with following i/O behaviour (i=>o mapping) performs a doubling finction on the integer range 1..4:
    1=>2 2=>4 3=>6 4=>8
    The following program performs the i/o transformation as specified; It is "black box correct".
    # Faulty Algorithm: double int's in range [1..4] my %hDouble = (1=>'2', 2=>'4', 3=>'7', 4=>'8'); # Kinky Perl computation: assert (&& thus fix) algorithm for my $i (1..4) { my $o = $hDouble{$i}; $o-- if ($o%2 != 0); print $i . "=>" . $o . "\n"; }
    Opening the box we can observe that the doubling algorithm (a lookup table) is flawed and the Perl code is unnecessarily complex and shaky. From a white box perspective the implementation is of poor quality : the bugs cancel out each other (from the black box perspective), but the code should definitely be cleaned up for better maintainability, robustness and efficiency.

    That in a way brings us back to your Larry Wall quote: ...redundancy was absolutely necessary to achieve the goal of putting someone on the moon. Use pair programming, technical walkthroughs, reviews... any and all human redundancy to assure "white box quality" of the implementation (ie. to catch - among other things - bugs cancelling out each other as seen from a pure interface/black box view. And for certain systems (as rocket science): use hardware redundancy as well, because only relatively small applications can be mathematically proven to be even black box (I/O transformation) correct, much less white box so.

    Allan

    If a tree falls in a forest with no one to hear it, then does it make a sound?
Re: Feature or Bug ?
by gargle (Chaplain) on Sep 18, 2005 at 11:51 UTC

    Hi,

    UPDATE: Sorry for the non working link. I corrected the href!

    No, for as long as you know all the valid inputs to give to your program. Once you start giving invalid inputs (in the sense that you know you'll trigger the error) your program is incorrect.

    I once read Program Construction and Verification in which Dijkstra got paraphrased: program testing can be used very effectively to show the presence of bugs but never to show their absence. On this site you can read more.

    --
    if ( 1 ) { $postman->ring() for (1..2); }
Re: Feature or Bug ?
by ambrus (Abbot) on Sep 18, 2005 at 22:35 UTC

    I call that an obfuscation.

Re: Feature or Bug ?
by sauoq (Abbot) on Sep 19, 2005 at 01:17 UTC

    Suppose also that my faulty implementation of my faulty algorithm will give the proper output on all input.

    Question:
    Does my program have a bug ?

    Strike outs are mine, of course.

    My answer: No (with a caveat.)

    Your Perl error has simply resulted in a correct algorithm. Since you've stipulated it is valid Perl then, no, there is no bug. Someone else could come along, read the code, and explain how it works.

    It is possible that you've created an obfuscated solution but it is not necessarily so. It might be perfectly obvious that your algorithm works and how.

    The caveat: by "valid Perl program" I assume that also means that you have not introduced any undefined behavior. Something like $b = ++$a - $a++; is valid syntax but is undefined. If your implementation contains anything of the sort, then it does have a bug. And a nasty (but latent) one at that. Upgrade Perl or change platforms and it might bite you.

    Otherwise though, you've got a perfectly fine algorithm and a confused programmer... A relatively common situation, I might add! :-)

    -sauoq
    "My two cents aren't worth a dime.";