Software bugs aren't inevitable

[Paddy]

A work colleague circulated this interesting article about reducing
software bugs by orders of magnitude:
http://www.spectrum.ieee.org/WEBONLY/publicfeature/sep05/0905ext.html

Some methods they talk about include removing error prone and ambiguous
expressions from their ADA based language Sparc - The example they give
is on why they removed the increment operators x++, x-- .

A bit of googling shows that they have, in the past mentioned Python in
Job specs, but only as one of many languages.

I was wondering what Praxis thought of Python, and how good it would be
if a Praxis engineer gave a critique of Python as a part of a flow for
producing low bug-count software.

In this sidebar to the main article:

http://www.spectrum.ieee.org/WEBONLY/publicfeature/sep05/0905extsb1.html

It seems that they use one equation from the Z notation model and add
it as a comment to their main programming languages function definition
as a comment, then have a means of automatically testing the comment
against the function body.

This is rather like how doctest can check the test and expected result
given in a doc-string against the implementation given in the function;
indeed I wrote up such an example at work and circulated it amongst the
resident perl mongers. - Gosh it fealt good

So, How do I get feedback from Praxis, Do they already read
comp.lang.py?

Cheers, Paddy.

 

[Paul Rubin]

A work colleague circulated this interesting article about reducing
software bugs by orders of magnitude:
http://www.spectrum.ieee.org/WEBONLY/publicfeature/sep05/0905ext.html

This gets a not found error. Got a different link?

Some methods they talk about include removing error prone and ambiguous
expressions from their ADA based language Sparc - The example they give
is on why they removed the increment operators x++, x-- .

There's a famous paper by John Hughes called "Why Functional
Programming Matters" that (cheap oversimplification) says you should
never modify the value of any variable. So, no increments, not even
for loops (use recursion instead).

 

[Steven D'Aprano]

There's a famous paper by John Hughes called "Why Functional
Programming Matters" that (cheap oversimplification) says you should
never modify the value of any variable. So, no increments, not even
for loops (use recursion instead).

Which works wonderfully as an academic exercise, but doesn't tend to work
so terribly well in the real world where the performance and
resource-requirement differences between iteration and recursion can be
significant.

For instance, try these two simple functions for the nth number
in the Fibonacci sequence:

def fibr(n):
"Recursive version of Fibonacci sequence."
if n == 0: return 0
elif n == 1: return 1
else: return fibr(n-1) + fibr(n-2)

def fibi(n):
"Simple iterative version of Fibonacci sequence."
if n == 0: return 0
elif n == 1: return 1
else:
Fn2 = 0
Fn1 = 1
for _ in range(2, n+1):
s = Fn2 + Fn1
Fn2, Fn1 = Fn1, s
return s

Try timing how long it takes to generate the 30th Fibonacci number
(832040) using both of those algorithms. Now try the 50th. (Warning: the
amount of work done by the recursive version increases at the same rate as
the Fibonacci sequence itself increases. That's not quite exponentially,
but it is fast enough to be very painful.)

 

[Jerzy Karczmarczuk]

Steven D'Aprano recommends iteration over recursion:

For instance, try these two simple functions for the nth number
in the Fibonacci sequence:

def fibr(n):
"Recursive version of Fibonacci sequence."
if n == 0: return 0
elif n == 1: return 1
else: return fibr(n-1) + fibr(n-2)

def fibi(n):
"Simple iterative version of Fibonacci sequence."
if n == 0: return 0
etc.
Try timing how long it takes to generate the 30th Fibonacci number
(832040) using both of those algorithms. Now try the 50th. (Warning: the
amount of work done by the recursive version increases at the same rate as
the Fibonacci sequence itself increases. That's not quite exponentially,
but it is fast enough to be very painful.)

First of all, the recursive version of Fibonacci IS EXPONENTIAL in complexity,
don't say such not-quite-truth as "not quite". But, what is more important:

If you don't know too much about the way the functional programming is
used nowadays, please refrain from giving nonsensical examples, since
NOBODY serious programs something in the style of your recursive version.
Such anti-advertizing of recursion says less about the recursion
than about yourself. Here you are a recursive version linear in n; it
returns the two last Fibonacci numbers of the sequence

def fibo(n):
if n<2:
return (n-1,n)
else:
(a,b)=fibo(n-1)
return (b,a+b)

The exponential complexity, cascading version is a nice test case how to
use memoization, though, so it is not entirely senseless to learn it.

Jerzy Karczmarczuk

 

[Giles Brown]

I was wondering what Praxis thought of Python, and how good it would be
if a Praxis engineer gave a critique of Python as a part of a flow for
producing low bug-count software.

I used to work at Praxis about 4 years ago and Perl was their scripting
language of choice at that time as I recall

This is rather like how doctest can check the test and expected result
given in a doc-string against the implementation given in the function;
indeed I wrote up such an example at work and circulated it amongst the
resident perl mongers. - Gosh it fealt good

I am probably a bit out of date with this and never used it in anger,
but there are basically two levels of annotation.

The first is data flow and is used to specify what variables affect
what. That is, you may specify for a function that the resulting
variable z is affected by the values of variable x and y (thats the
basic idea, there is a bit more to it of course). The toolset checks
that your code matches your annotations. It relies on not having the
different names for the same variable (not something you can guarantee
in Python really .

The next level of annotations is for proving your code matches a
specification in Z. So your annotations are part of that proof and can
again be checked automatically.

So, How do I get feedback from Praxis, Do they already read
comp.lang.py?

Are there no email links on: http://www.praxis-his.com/sparkada/ ?

Hth,
Giles Brown

 

[Terry Reedy]

Which works wonderfully as an academic exercise, but doesn't tend to work
so terribly well in the real world where the performance and
resource-requirement differences between iteration and recursion can be
significant.

I think your comparison is incomplete.

Recursion and iteration are two syntaxes for the same operation: repetition
with variation. Indeed, iteration can be viewed as within-frame tail
recursion. Recursion usually takes more space for a stack of call
frames -- unless the particular system optimizes the stack away for
particular functions (by recursing within a frame!). For a given
algorithm -- defined by what actually gets computed -- the time difference
is a small constant. For Python, recursion is probably slower relative to
iteration than for other languages because of the flexibility and slowness
of function calls.

For instance, try these two simple functions for the nth number
in the Fibonacci sequence:

Abstractly, these are two algorithms for the same function. One runs in
exponential time because it wastefully calculates and tosses away an
exponential number of subvalues. The other runs in linear time because it
calculates each subvalue once. When one only wants Fib(n), and not the
sequence leading up to it, even this is wasteful, for large enough n, since
there is a third algorithm that caluculates Fib(n) directly by a simple
formula (something like the interger part of the golden ratio to the nth
power).

Now: I could (and probably someday will) write an iterative version of the
exponential algorithm (using an explicit stack) that calculates each
subvalue exactly as many times as the recursive version of that same
algorithm. And I could compare it to a recursive version of the more
efficient linear algorithm (such as posted by Jerzy Karczmarczuk). And I
could claim that this shows hows iteration can waste time compared to
recursion.

But that, I admit, would be an invalid conclusion. And that, I claim, is
also invalid when 'iteration' and 'recursion' are reversed, no matter how
often repeated in texts and articles. The difference is between the
algorithms, not the differing syntactic expressions thereof.

Terry J. Reedy

 

[Rocco Moretti]

But that, I admit, would be an invalid conclusion. And that, I claim, is
also invalid when 'iteration' and 'recursion' are reversed, no matter how
often repeated in texts and articles. The difference is between the
algorithms, not the differing syntactic expressions thereof.

There is a comparison in there about iteration vs. recursion, but it's
probably not the one intended.

The algorithm one uses sometimes depends quite heavily on which mindset
you're using. Some algorithms require much more mental effort to
understand when in their recursive form versus the iterative form, and
vice versa. If you're stuck thinking in only one form, you might miss
the better algorithm because it is not as "simple" in that form.

The ideal case would be a programming language that allows you to write
the algorithm in whatever form is simplest/most comfortable, and then
automagically transforms it to the form that works the fastest under the
hood.

 

[Steven D'Aprano]

I think your comparison is incomplete.

Yes, it is incomplete.

It seems that I've given the mistaken impression that I am opposed to
recursion in principle. I am not. Perhaps I should have qualified my
remarks by stating that sometimes recursion can be easier to comprehend
than iteration, more efficient and all those other goodies that developers
like their programs to be. A good example of a task that is frequently
better solved with recursion than with iteration is walking a binary tree.

But in the context of my response, I was replying to a paraphrased quote
from somebody who apparently believes that recursion is *always* better
than iteration. That is clearly not the case.

It is a "mere implementation detail" that (for most computer systems, and
most programming languages) stack space is at a premium and a deeply
recursive function can run out of stack space while the heap still has
lots of free memory. But those implementation details in the real world
make the difference between an elegant solution that runs like a lame duck
and an practical solution that has nothing going for it except the fact
that it works.

(And then there are the elegant solutions that are also practical. It is a
good day when you find yourself writing one of those.)

Recursion is frequently extravagant in its use of resources: if nothing
else, it takes resources to call a function, and recursion means you call
the same function over and over again. There is a reason why functional
programming never really took off.

Extravagance is not necessarily a bad thing -- if I thought it were, I
wouldn't be using a high-level object-oriented language like Python. But
it is important to be aware of those factors.

Recursion and iteration are two syntaxes for the same operation: repetition
with variation.

Yes, in general anything that can be solved recursively can be solved
iteratively. Some classes of problems lend themselves naturally to one or
the other solution, but it is always possible (in principle at least) to
use either.

Abstractly, these are two algorithms for the same function. One runs in
exponential time because it wastefully calculates and tosses away an
exponential number of subvalues. The other runs in linear time because it
calculates each subvalue once. When one only wants Fib(n), and not the
sequence leading up to it, even this is wasteful, for large enough n, since
there is a third algorithm that caluculates Fib(n) directly by a simple
formula (something like the interger part of the golden ratio to the nth
power).

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.

Now: I could (and probably someday will) write an iterative version of the
exponential algorithm (using an explicit stack) that calculates each
subvalue exactly as many times as the recursive version of that same
algorithm. And I could compare it to a recursive version of the more
efficient linear algorithm (such as posted by Jerzy Karczmarczuk). And I
could claim that this shows hows iteration can waste time compared to
recursion.

Of course it can. But you have to really *work* at getting the iterative
version to be as wasteful as the obvious recursive version.

But that, I admit, would be an invalid conclusion. And that, I claim,
is also invalid when 'iteration' and 'recursion' are reversed, no matter
how often repeated in texts and articles. The difference is between the
algorithms, not the differing syntactic expressions thereof.

Now you go too far. You are right that a change of algorithm will often
make a much bigger difference to performance than merely swapping from one
form of repetition to another. But you ignore those "mere implementation
details" that lead to exceptions like this one:

RuntimeError: maximum recursion depth exceeded

(eg calling Jerzy Karczmarczuk's efficiently recursive function with
n=1000, while my iterative version works for at least values of n an order
of magnitude larger.)

Yes, the maximum recursion depth in Python is an artificial limit. But
that artificial limit is built into Python specifically to protect you
from running into a real recursion limit based on the hardware and
architecture of your PC, with painful consequences.

 

[Steven D'Aprano]

First of all, the recursive version of Fibonacci IS EXPONENTIAL in complexity,
don't say such not-quite-truth as "not quite".

Your correction is noted. I had compared the work done with 2**n, but of
course any constant greater than one can exhibit exponential growth.

Out of interest, the number of recursive calls (including the first
function call) made when calculating the nth Fibonacci number are
themselves part of a Fibonacci-like sequence. Look at the 1st order
differences:

n Fib(n) Calls 1st Diff
0: 0 1 N/A
1: 1 1 0
2: 1 3 2
3: 2 5 2
4: 3 9 4
5: 5 15 6
6: 8 25 10
7: 13 41 16
8: 21 67 26
9: 34 109 42
10: 55 177 68
11: 89 287 110
12: 144 465 178

Notice the pattern?

But, what is more important:

If you don't know too much about the way the functional programming is
used nowadays, please refrain from giving nonsensical examples, since
NOBODY serious programs something in the style of your recursive version.

I never said that my recursive version was a practical implementation.
But it is a very common algorithm -- I have four or five textbooks at home
that give it. In many textbooks and programming courses, the first
algorithm given to introduce the principle of recursion is either
factorial or the Fibonacci sequence. For example:

http://www.math.pitt.edu/~wjl/nm99.html

gives the same naive recursive implementation in Fortran.

If you google for Fibonacci sequences, you will find dozens,
possibly hundreds, of implementations virtually identical to the one I
gave. Also significant numbers of Java apps that run slow for values of n
larger than 30 or 40 -- a good sign that they are using the naive
algorithm.

It is a rare under-graduate or secondary school textbook that suggests
that the naive algorithm is anything but a poor idea.

Such anti-advertizing of recursion says less about the recursion
than about yourself.

Yeah, whatever.

Here you are a recursive version linear in n; it
returns the two last Fibonacci numbers of the sequence

def fibo(n):
if n<2:
return (n-1,n)
else:
(a,b)=fibo(n-1)
return (b,a+b)

Ah, I like this algorithm! I'll add it to my collection. Thank you.

 

[Paul Rubin]

It is a "mere implementation detail" that (for most computer systems, and
most programming languages) stack space is at a premium and a deeply
recursive function can run out of stack space while the heap still has
lots of free memory.

Every serious FP language implementation optimizes tail calls and thus
using recursion instead of iteration doesn't cost any stack space and
it probably generates the exact same machine code.

 

[Paddy]

Hmm, They seem to have reorganised things.
As I write, the main article starts here:
http://www.spectrum.ieee.org/sep05/2164
With the sidebar here:
http://www.spectrum.ieee.org/sep05/2164/extsb1

- Paddy.

 

[Paddy]

Thanks Giles,
I was hoping for a reply from someone close to Praxis like yourself,
but, I'm shocked when you said they use Perl as their scripting
language of choice, because I thought that with such an emphasis on
correctness and maintainability, that it would spill over into other
aspects of their flow.

Maybe they don't see scripting as part of their flow, but as merely
occasional 'duct tape'?

I did find an email address on the page you specified and have invited
Praxis to join in on this thread, or comment on Python in general.

- Paddy.

 

[Terry Hancock]

Every serious FP language implementation optimizes tail calls and thus
using recursion instead of iteration doesn't cost any stack space and
it probably generates the exact same machine code.

I understood both the iterative version (which was efficient)
and the "naive" recursive version MUCH better than the "efficient"
recursive version.

Being able to write the efficient recursive version proves you're
smart, which is very important to some people. Being able to
write the efficient iterative version proves you don't have to be.

Since I write code to solve problems, not prove my intellectual
prowess, my vote goes for the "dumb" solution. Probably this
is why I use Python.

Sorry. ;-)

 

[Terry Reedy]

The algorithm one uses sometimes depends quite heavily on which mindset
you're using. Some algorithms require much more mental effort to
understand when in their recursive form versus the iterative form, and
vice versa. If you're stuck thinking in only one form, you might miss
the better algorithm because it is not as "simple" in that form.

This is why I disagree with the extreme recursionist and iterationist camps
that both argue that since both forms cover the same ground, one only needs
to learn one.

The ideal case would be a programming language that allows you to write
the algorithm in whatever form is simplest/most comfortable, and then
automagically transforms it to the form that works the fastest under the
hood.

I suspect that recursion can be always be sped up by doing it within one
frame. Some languages/compilers do this for the particular form of linear
recursion called tail recursion. In general, recursion to iteration
requires two stacks and two loops nested within a third, but there are
several special cases which are simpler in one way or another. I think
making the right choice will generally require extra input from the
programmer. But with the extra info and some restraint in formatting, I
think the rest could be automated.

A separate tranformation issue is how to reduce double recursion to single
recursion, when possible, and even to no recursion, as one can with the
Fibonacci example. For functions which produce a set or sequence of
structures, a related sort of transformatiom is from all-at-once production
to one-at-a-time generation.

Terry J. Reedy

 

[Terry Reedy]

But in the context of my response, I was replying to a paraphrased quote
from somebody who apparently believes that recursion is *always* better
than iteration. That is clearly not the case.

We agree here. In fact, I suggested that for a given algorithm implemented
in Python, iteration should always be faster by a small factor.

It is a "mere implementation detail" that (for most computer systems, and
most programming languages) stack space is at a premium and a deeply
recursive function can run out of stack space while the heap still has
lots of free memory. But those implementation details in the real world
make the difference between an elegant solution that runs like a lame
duck
and an practical solution that has nothing going for it except the fact
that it works.

Which is why, in the part you snipped, I said that recursion (unlike
iteration) piles up stack frames unless optimized not to and that Python
is *not* so optimized. I will add that when an function or algorithm does
require or use a stack, the iterative form will use heap memory instead of
call stack memory and will put less on the stack with each repetition. But
your example was about time and my point then and now is about time, not
space.

Yes, in general anything that can be solved recursively can be solved
iteratively. Some classes of problems lend themselves naturally to one or
the other solution, but it is always possible (in principle at least) to
use either.

To expand on this a bit: seeing the problem as 'recalculating tossed-away
subvalues' suggests the fruitful question "how do I not do that?". The
generic answer is memoization. A specific answer applicable to Fib() is
linearization or even formulaization. This is an extreme example of
wasteful calculation, but squeezing out waste is a common theme in
algorithm improvement. See below for another example.

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.

Of course it can. But you have to really *work* at getting the iterative
version to be as wasteful as the obvious recursive version.

For someone who does not know how to write the iterative version, the
'extravagent' recursive version would be infinitely faster. But, as I
said, I do and I would *not* have to work very hard. I have a 10-15 line
template (in C) sitting in a book 10 feet away. Filling it in would be
easy and straightforward. If I had the template in Python on my machine,
maybe 5 minutes. I hope someday to write a set of such templates, with
explanations, so that you could potentially do the same ;-).

Now you go too far.

Not at all. I was in my first response and here am talking specifically
about exponential time wastage and the bogus claim that it is due to
recursion or, in my reversal, iteration. It is due to the algorithm
difference. The problem with this example, which I know you have read
elsewhere, perhaps more than once, is that two factors are changed
together, making an incomplete experimental design (see below) and the
large observable difference is usually ascribed to the wrong factor.

Space is a different issue, which we seem to agree on.

Now for the other time wastage example promised above. In math, a standard
set definition method is filtration of a master set by an element predicate
to produce a subset: a set comprehension. In Python, we have the list
comprehension and generator expression forms. One can do the same with the
powerset of a set to get a set of subsets that is a subset of the set of
all subsets as defined by a set predicate.

Assume that powset(someset) produces an iterative powerset generator. Then
sops = (s for s in powset(someset) if setpred(s))
is an iterative restricted subset generator, easily passed to set() or
list().
A specific example is
ksubsets = (s for s in powset(someset) if len(s)==k).
As n = len(someset) increases, this (naive) algorithm gets increasingly
inefficient.

Alternatively, we can generate ksubsets with the standard double recursion
that generates exactly and only the size k subsets. So what can we
conclude from this example about the relative time usage of 'extravagent
naive interation' versus 'elegant recursion'. My main point here and
previously is just this: nothing (or certainly not much).

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.

To compare two factors simultaneously, one should, if possible (and here it
is) vary each independently in a balanced design with a minimun of 2x2 = 4
experimental setups.

Terry J. Reedy

 

[Terry Reedy]

The minor problem is that for n = 0, there are no two last numbers.

Ah, I like this algorithm! I'll add it to my collection. Thank you.

The above is what I call the 'body recursive' form. Others have other
names.
Here is a version of the 'tail recursive' form (without negative input
check).

def fibt(n):
if n < 2: return n
def _fib(i, a, b):
if i < n:
return _fib(i+1, b, a+b)
return b
return _fib(2, 1, 1)

The inner function does not have to be wrapped; for n >=2, the outer
function simply passes on its final return. However, the wrapping masks
the accumulator parameters from the user and correctly sets their initial
values. It also handles the base cases more efficiently by checking for n
< 2 just once instead of every inner loop.

Here is the direct iterative equivalent:

def fibi(n):
if n < 2: return n # same as before
i, a, b = 2, 1, 1 # corresponds to initial _fib call
while i < n: # repeated ('recursive') if
i, a, b = i+1, b, a+b # corresponds to args of recursive _fib call
return b # same as before

The transformation is mechanical and is done internally by some language
interpreters. (Although some might require the inner condition reversed
and the returns switched.)

Terry J. Reedy

 

[Paul Rubin]

As I write, the main article starts here:
http://www.spectrum.ieee.org/sep05/2164
With the sidebar here:
http://www.spectrum.ieee.org/sep05/2164/extsb1

Thanks, the article is slightly interesting but it doesn't say much.
I'm sure a lot more is going on than the article describes. And if
they're so sure their Z specifications are correct, why can't they
generate code from them automatically? I've heard stories like that
told about Haskell. People have seen Haskell programs and thought
they were simply formal specifications of some kind, and been
surprised to find out that they were actual runnable programs.

 

[Jerzy Karczmarczuk]

Steven D'Aprano is still unhappy with the linear complexity
recursive Fibonacci I proposed as as an alternative to the cascading
recursion which for some people is "standard" or "obvious" or other
similar attribution which is not valid anymore.

RuntimeError: maximum recursion depth exceeded

(eg calling Jerzy Karczmarczuk's efficiently recursive function with
n=1000, while my iterative version works for at least values of n an order
of magnitude larger.)

Yes, the maximum recursion depth in Python is an artificial limit. But
that artificial limit is built into Python specifically to protect you
from running into a real recursion limit based on the hardware and
architecture of your PC, with painful consequences.

Oh, I LOVE technical solutions like that:

"Everybody knows that you should not exceed some speed in your car.
So, our new technology is such that if you reach 160 km per hour,
your engine breaks.
Surely it is an artificial limit, but it is there to protect you from
worse problems with painful consequences."

I do not feel guilty for proposing a function which fails for n>1000.

This solution, in Haskell works for ANY n, and doesn't fill the stack
at all (provided it is strictified, i.e. the laziness does not produce
some thunk accumulation)

fib n = fibo n 0 1 where
fibo 0 a _ = a
fibo 1 _ b = b
fibo n a b = fibo (n-1) b (a+b)

But tail recursion is NOT iteration in Python. So, this version:

def fib1(n,a=0,b=1):
if n==0: return a
elif n==1: return b
return fib1(n-1,b,a+b)

which in a 'decent' language (no offense meant, just thinking what will
be considered scandalous in 40 years...) would run for any n, in Python
breaks for n>1000 again. [[Terry Reedy proposed another variant; mine
is a bit shorter, perhaps a bit more elegant]].

I am sorry, but Python, as every other programming language is full of
decisions ad hoc, not always universally appreciated. Recursion can be
and IS often optimised, and tail recursion in functional languages is
entirely removed (no stack filling.) Stacks can be and are sometimes
allocated on heap, so the comment of somebody who discussed the
dichotomy stack/heap, pointing out the difference in size, may be
altogether irrelevant. Again, we, the users are not responsible for the
memory allocation policy in Python...

So, this paragraph

Recursion is frequently extravagant in its use of resources: if nothing
else, it takes resources to call a function, and recursion means you call
the same function over and over again. There is a reason why functional
programming never really took off.

is for me a biased view of the problem. Justified only by the fact that
at the beginning of functional programming (sixties) nobody cared about
the efficiency. Now, such languages as Clean, or good implementations of
Scheme are very well optimized. OCaml as well, and Haskell is improving
every 3 months. Functional languages did take off, but since a pure
functionalism requires particular, quite sophisticated techniques in
GOOD algorithm design and implementation, they are less adapted to the
brutal world than C or Python. The reasons of relatively small popularity
are much less technical than psychological, and this is KNOWN.

(Terry Hancock formulated this plainly, he prefers dumb ways because
he wants to solve problems, and he doesn't like to perform gymnastics
with his brain. We have to accept those attitudes. But I believe that
this is the effect of teaching standards; people don't learn high-level
algorithm design when they are young enough...)

====================

If you google for Fibonacci sequences, you will find dozens,
possibly hundreds, of implementations virtually identical to the one I
gave. Also significant numbers of Java apps that run slow for values of n
larger than 30 or 40 -- a good sign that they are using the naive
algorithm.

It is a rare under-graduate or secondary school textbook that suggests
that the naive algorithm is anything but a poor idea.

If you Google for anything, you will find hundreds of stupidities, since
nowadays the proliferation of amateurish "tutorials" etc. on the Web is
simply terrible... I WILL NOT assume the responsibility for all the bad
solutions. On the other hand, I suspect that there will be people who will
not follow this thread, who will just remember your first posting on the
subject, and they will remain convinced that recursion /per se/ is lousy,
and that your cascading algorithm is *THE* standard recursive solution.
Yes, YOU are in the state of sin! [Optional smiley here].

But, I have used myself the cascading version. It was done on purpose, in
order to get to the following solution.
[[I preferred to use a global dict, but other ways of doing it are also
possible]].

fibdic={0:0,1:1}
def fibd(n):
if not fibdic.has_key(n):
r=fibd(n-1)+fibd(n-2)
fibdic[n]=r
return fibdic[n]

And here the recursion limit won't get you!!
But the memoization techniques are rarely taught nowadays...

=====

And the story doesn't end here. There are backtracking solutions, which
in functional (lazy) languages can be emulated through co-recursion, and
in Python by the use of generators.

Jerzy Karczmarczuk

 

[Steve Holden]

A work colleague circulated this interesting article about reducing
software bugs by orders of magnitude:
http://www.spectrum.ieee.org/WEBONLY/publicfeature/sep05/0905ext.html

Some methods they talk about include removing error prone and ambiguous
expressions from their ADA based language Sparc - The example they give
is on why they removed the increment operators x++, x-- .

A bit of googling shows that they have, in the past mentioned Python in
Job specs, but only as one of many languages.

I was wondering what Praxis thought of Python, and how good it would be
if a Praxis engineer gave a critique of Python as a part of a flow for
producing low bug-count software.

In this sidebar to the main article:

http://www.spectrum.ieee.org/WEBONLY/publicfeature/sep05/0905extsb1.html

It seems that they use one equation from the Z notation model and add
it as a comment to their main programming languages function definition
as a comment, then have a means of automatically testing the comment
against the function body.

This is rather like how doctest can check the test and expected result
given in a doc-string against the implementation given in the function;
indeed I wrote up such an example at work and circulated it amongst the
resident perl mongers. - Gosh it fealt good

So, How do I get feedback from Praxis, Do they already read
comp.lang.py?

Cheers, Paddy.

As far as I can see the advantage of this kind of rigor is best kept for
the projects where it really matters (e.g. safety-critical monitoring
and control systems). Programming is a growing human activity, and I
would suggest that one of Python's designed-in advantages is the ease
with which comprehensible implementations of known algorithms can be
constructed. Given Guido's expressed interest in "Computer Programming
for Everyone" this comes as no surprise to more.

Nonetheless we have to remember that the vast majority of Python
programmers wouldn't care about differences between implementation
techniques, being happy that they've found *any* way to get the computer
to do what they want.

I'm sure that a Praxis evaluation of Python would make a very good
presentation at PyCon, whose Call for Proposals recently came out.

Yes folks, next time around it's PyCon TX 2006, see

http://www.python.org/pycon/2006/cfp

regards
Steve

 

[Carl Friedrich Bolz]

Hi!

2005/9/15, Jerzy Karczmarczuk <[email protected]>:

[snip]

But, I have used myself the cascading version. It was done on purpose, in
order to get to the following solution.
[[I preferred to use a global dict, but other ways of doing it are also
possible]].

fibdic={0:0,1:1}
def fibd(n):
if not fibdic.has_key(n):
r=fibd(n-1)+fibd(n-2)
fibdic[n]=r
return fibdic[n]

And here the recursion limit won't get you!!
But the memoization techniques are rarely taught nowadays...

=====

And the story doesn't end here. There are backtracking solutions, which
in functional (lazy) languages can be emulated through co-recursion, and
in Python by the use of generators.

Jerzy Karczmarczuk

It is also possible to do a version that scales logarithmically with
n. It relies on the observation that calculation of the fibonacci
series can be done by taking the upper left entry of the following
matrix exponentiation:

n
/1 1\
\1 0/

Since exponentiation can be done logarithmically this can be used to
calculate fibonacci series faster (at least for big values of n):

def mul(m1, m2):
((a, b), (c, d)) = m1
((e, f), (g, h)) = m2
return [[a*e + b*g, a*f + b*h],
[c*e + d*g, c*f + d*h]]

def expo(m, n):
if n == 0:
return [[1, 0], [0, 1]]
if n % 2 == 0:
r = expo(m, n//2)
return mul(r, r)
else:
return mul(m, expo(m, n - 1))

def fib(n):
return expo([[1, 1], [1, 0]], n)[0][0]

With this you can calculate really big fibonacci numbers without
increasing the recursion depth, even though the expo function is
recursively written.

Cheers,

Carl Friedrich Bolz