Software bugs aren't inevitable

[Steven D'Aprano]

On Wed, 14 Sep 2005 23:44:18 -0400, Terry Reedy wrote:

>> Yes. There are lots of algorithms that could be done, and they all have
>> their pros and cons. Biset's formula, for example, is mathematically
>> correct, but for large enough n, the "mere implementation detail" that
>> floats have a finite precision will cause that algorithm to give 
>> incorrect answers. For "large enough", on my system I mean n=71.
> 
> I am assuming you mean the Fib formula?  No matter.  With finite precision 
> ints, typically 32 bits, fib(n) by addition overflows sooner than that.  If 
> you allow extended precision ints, then allow extended precision floats 
> also.

Except for the mere implementation detail that Python doesn't have
extended precision floats, but it does have transparent conversion between
32 bit ints and longints. So in the real world of Python language
programming, the mathematically elegant, fast, efficient algorithm using
Biset's formula is only usable for n up to about 70.

That illustrates my original point that a programming strategy that seems
like a good idea in the ivory tower of academia can be a bad idea in real
world program development.

Ivory towers are important. If not for academics and their clever ideas,
we'd still be programming in assembly language. But developers should be
aware of the dangers of adapting ideas from the ivory tower too quickly,
in the sense that an algorithm that runs optimally using one compiler may
run pessimally using a language that doesn't have all those optimizations
built into it.

For instance, naively translating Lisp-style (head, tail) lists into
Python data structures give you something like this:

[0, [1, [2, [3, [4]]]]]

Operating on such a list in Python is not as efficient as it is in Lisp,
and your code will generally run significantly slower than if you had
written code to operate on the Python-style list [0, 1, 2, 3, 4].

This is obvious, but not obvious enough -- programmers frequently "code
in X", blindly translating code or algorithms that worked well in some
other language into whichever language they are using at the time. The
original advice to always avoid iteration in favour of recursion falls
into the same category. Not all languages have the optimizations to make
that work, and more importantly, it is often easier to come up with
inefficient recursive algorithms than inefficient iterative algorithms.

I have learnt a lot about the state of the art of functional programming
from this discussion, thank you to all the folks who took the time to
respond. Will that make me a better Python programmer? Doubtful, at least
not while Python is mostly an imperative language.


> To compare iteration versus recursion, one should use the same algorithm or 
> same set of algorithms, with an iterative and recursive version of each. 
> To compare algorithms, one should use the same implementation form or forms 
> on each.  Varying one factor at a time, when possible, is basic good 
> science.

That is good science, but the majority of programmers are not scientists.
Most professional, non-academic programmers don't have the foggiest clue
what "tail-recursion" means, whether that implies that "head-recursion"
exists or not, or how to tell them apart, let alone how to convert an
iterative algorithm into a recursive one or vice versa. That's not meant
as a slight against the programmers -- many of them are extremely
competent, intelligent folks, but for them programming is a combination of
art and engineering, and not a science.

That is where advice like "use recursion, not iteration" falls down.
Most of the common languages in use outside of academia (C/C++, Perl,
Python, PHP, Javascript, Java) aren't functional programming languages
that optimize your recursion, and most programmers don't have the
skills to do it themselves. That is a skill, and not one that is taught in
terribly many "Python in a Nutshell" style books.


-- 
Steven.