Re: Open Source Quality

From: Douglas W. Jones <jones_at_cs_dot_uiowa_dot_edu>
Date: Sun May 09 2004 - 13:58:58 CDT

On May 9, 2004, at 12:49 PM, David Mertz wrote:

>> The presence of these errors argues (minimally) for garbage-collected
>> languages and fulltime array bounds checking to help a sloppy
>> programmer detect these problems.
>
> I.e. Python is the *right* language to write OVC's reference in.

Well, the same could be said for Java, LISP, Simula 67 and a number of
other languages. This merely demonstrates that Python is a member of
a class of relatively safer languages.

> Overall, it's quite striking how much more reliable GNU utilities are
> than commercial equivalents.

This is indeed striking evidence that open source leads to higher
quality standards than is normal in the industry.

> However, the paper made a peculiar error in its description. It
> described the bugs detected as including "infinite loops." Well,
> there's this little thing called the Halting Problem that says you
> don't know in the general case if a program will ever end.

I'll lay odds that most of the hangs detected by the Fuzz test suite
are indeed infinite loops.

I have, however, made this mistake once in my career, when I assigned
students the job of writing a sort program in LISP (limited to the
functional programming subset) and tested them with a list of 10 random
digits. Most solutions produced results faster than you could blink
your eyes, but one solution had "obviously" hung. We gave that student
a zero, and the student complained. "You didn't give it long enough"
he said. "How long is enough?" I asked. "several hours," he replied.
It turned out that, while most students had sort algorithms that took
O(n log n) time and a few had O(n**2) algorithms, his was at least
O(n**4). We never did figure out how he'd done this, but part of the
trick was to do array indexing suing an O(n**2) algorithm to pick the
n'th item out of a list. (This story happened 20 years ago, but the
relative improvement of computer speed since then is pretty much
irrelevant.)

                        Doug Jones
                        jones@cs.uiowa.edu
==================================================================
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
==================================================================
Received on Mon May 31 23:17:27 2004

This archive was generated by hypermail 2.1.8 : Mon May 31 2004 - 23:18:16 CDT