By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,222 Members | 2,416 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,222 IT Pros & Developers. It's quick & easy.

Software bugs aren't inevitable

P: n/a
A work colleague circulated this interesting article about reducing
software bugs by orders of magnitude:
http://www.spectrum.ieee.org/WEBONLY...5/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...905extsb1.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.

Sep 12 '05 #1
Share this Question
Share on Google+
56 Replies


P: n/a
"Paddy" <pa*******@netscape.net> writes:
A work colleague circulated this interesting article about reducing
software bugs by orders of magnitude:
http://www.spectrum.ieee.org/WEBONLY...5/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).
Sep 14 '05 #2

P: n/a
On Wed, 14 Sep 2005 01:05:55 -0700, Paul Rubin wrote:
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.)
--
Steven.
Sep 14 '05 #3

P: n/a
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
Sep 14 '05 #4

P: n/a
Paddy wrote:
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


Cheers, Paddy.


Sep 14 '05 #5

P: n/a

"Steven D'Aprano" <st***@REMOVETHIScyber.com.au> wrote in message
news:pa****************************@REMOVETHIScybe r.com.au...
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

Sep 14 '05 #6

P: n/a
Terry Reedy wrote:
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.
Sep 14 '05 #7

P: n/a
On Wed, 14 Sep 2005 11:28:02 -0400, Terry Reedy wrote:

"Steven D'Aprano" <st***@REMOVETHIScyber.com.au> wrote in message
news:pa****************************@REMOVETHIScybe r.com.au...
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.


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.

Sep 14 '05 #8

P: n/a
On Wed, 14 Sep 2005 14:32:17 +0200, Jerzy Karczmarczuk wrote:
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.
--
Steven.

Sep 14 '05 #9

P: n/a
Steven D'Aprano <st***@REMOVETHIScyber.com.au> writes:
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.
Sep 14 '05 #10

P: n/a
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.

Sep 14 '05 #11

P: n/a
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.

Sep 14 '05 #12

P: n/a
On Wednesday 14 September 2005 02:23 pm, Paul Rubin wrote:
Steven D'Aprano <st***@REMOVETHIScyber.com.au> writes:
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.


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 Hancock ( hancock at anansispaceworks.com )
Anansi Spaceworks http://www.anansispaceworks.com

Sep 14 '05 #13

P: n/a

"Rocco Moretti" <ro**********@hotpop.com> wrote in message
news:dg**********@news.doit.wisc.edu...
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

Sep 15 '05 #14

P: n/a

"Steven D'Aprano" <st***@REMOVETHIScyber.com.au> wrote in message
news:pa****************************@REMOVETHIScybe r.com.au...
On Wed, 14 Sep 2005 11:28:02 -0400, Terry Reedy wrote: 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.
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).
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.
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.


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 ;-).
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.


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

Sep 15 '05 #15

P: n/a

"Steven D'Aprano" <st***@REMOVETHIScyber.com.au> wrote in message
news:pa****************************@REMOVETHIScybe r.com.au...
On Wed, 14 Sep 2005 14:32:17 +0200, Jerzy Karczmarczuk wrote:
Here you are a recursive version linear in n; it
returns the two last Fibonacci numbers of the sequence
The minor problem is that for n = 0, there are no two last numbers.
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.


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


Sep 15 '05 #16

P: n/a
"Paddy" <pa*******@netscape.net> writes:
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.
Sep 15 '05 #17

P: n/a
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
Sep 15 '05 #18

P: n/a
On Wed, 14 Sep 2005 12:23:00 -0700, Paul Rubin wrote:
Steven D'Aprano <st***@REMOVETHIScyber.com.au> writes:
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.


Are you saying that the recursion done by "serious" languages is a fake?
That it is actually implemented behind the scenes by iteration?

It seems to me that if recursion and iteration produce "the exact same
machine code", the argument for preferring recursion over iteration is
gutted.
--
Steven.

Sep 15 '05 #19

P: n/a
Paddy wrote:
A work colleague circulated this interesting article about reducing
software bugs by orders of magnitude:
http://www.spectrum.ieee.org/WEBONLY...5/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...905extsb1.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
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.pycon.org

Sep 15 '05 #20

P: n/a
Hi!

2005/9/15, Jerzy Karczmarczuk <ka*****@info.unicaen.fr>:

[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
--
http://mail.python.org/mailman/listinfo/python-list


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
Sep 15 '05 #21

P: n/a
Steven D'Aprano wrote:
On Wed, 14 Sep 2005 12:23:00 -0700, Paul Rubin wrote:

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.

Are you saying that the recursion done by "serious" languages is a fake?
That it is actually implemented behind the scenes by iteration?

It seems to me that if recursion and iteration produce "the exact same
machine code", the argument for preferring recursion over iteration is
gutted.


Well, in such a way we can discuss for eternity...
Please, distinguish between the high-level algorithm formulation, and what
computer does under the carpet.

The recursion - as put forward by functionalists is a conceptual way of
thinking. With passing of new parameters without explicitly updating the
variables to which the old ones are assigned. Without loop control
variables, nor looping constructs.
You don't reassign your variables, you avoid the side-effects. The
programs are often clearer and safer, less error-prone.

Now, the ugly world of basic computing at the assembly level is imperative,
not functional (within standard architectures). The registers ARE
reassigned. The stack must be explicitly handled, etc. You *SEE* explicitly
the iterative structures.

The point of functionalists is that one should avoid that, and leave those
nasty things to the compiler. That's all. Your final conclusion is for me
rather inacceptable. It is not the machine code which matters, but
human effort [provided you spent sufficient time to be fluent in *good*
recursive programming of complex tasks.]
Jerzy Karczmarczuk
Sep 15 '05 #22

P: n/a
Surely, (don't call me Shirley), one of the goals pf Python is to make
the Programmer more productive.
It is obvious that we can tolerate some bugs in programs, but, after
reading the article, I thought that we might have a change to here from
'the other side'.
I get the fealing that the proponents of flows such as Extreme
Programming are decreasing the bug rate compared to their previous
flows, where Praxis might be able to suggest Python methodology that
would be an increase in bug-rate compared to their internal flow, but
maybe be better than current workflows.

P.S. I like your suggestion about pycon, but I have no reply from
anyone at Praxis after emailing them yesterday.

- Cheers, Paddy.

Sep 15 '05 #23

P: n/a
On Thu, 15 Sep 2005 21:56:06 +1000, Steven D'Aprano <st***@REMOVETHIScyber.com.au> wrote:

Are you saying that the recursion done by "serious" languages is a fake?
That it is actually implemented behind the scenes by iteration?

It seems to me that if recursion and iteration produce "the exact same
machine code", the argument for preferring recursion over iteration is
gutted.


It seems to me that if a high level language and assembler produce
"the exact same machine code", the argument for preferring high
level languages is gutted.

Do you see the fallacy in your statement now?

--
Email: zen19725 at zen dot co dot uk
Sep 15 '05 #24

P: n/a

"Steven D'Aprano" <st***@REMOVETHIScyber.com.au> wrote in message
news:pa****************************@REMOVETHIScybe r.com.au...
Are you saying that the recursion done by "serious" languages is a fake?
That it is actually implemented behind the scenes by iteration?


Although easy to confuse, we should separate expressive syntax, whether
recursive or iterative, from computation implementation. (The expressive
question would remain even if computation were replaced by a magic
answer-oracle.) What you call iterative implementation can also be called
within-frame recursion. The function parameters are bound to new values or
objects and control jumps to the first line of code. The only thing 'fake'
about this as a function call is the reuse of the same execution frame
instead of allocation a new frame when a new frame is not needed.

Terry J. Reedy

Sep 15 '05 #25

P: n/a
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.

Sep 15 '05 #26

P: n/a
On Thu, 15 Sep 2005 11:38:57 +0200, Jerzy Karczmarczuk wrote:
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."


Yes, in an ideal world, there would be some way for Python to magically
work out what the rest of the recursion would have calculated without
actually needing to calculate it recursively. Maybe all the fans of
Functional Programming will suggest patches to Python that will optimize
recursion so there will be no need for the maximum recursion depth
exception. But until then, it is better to explicitly fail than to return
an incorrect answer.

Either way, unless somebody redoes the Python language, it is a limit we
are stuck with in the real world of Python programming.
I do not feel guilty for proposing a function which fails for n>1000.
That's a curious attitude to have. I always feel guilty when I write a
program that fails for some legitimate input.

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...
But that is precisely my point. Ideas that work well in theory can fail
badly when put into practice because of limitations of the language used.
Algorithms that work poorly in one language can work wonderfully in
another.

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].
Yes, good point. In hindsight, I should have reworded my post to be more
clear. I am not opposed to recursion itself, just overly broad advice that
recursion is always good and modifying variables is always bad.

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


Which is a pity, because they are a powerful technique.
--
Steven.

Sep 15 '05 #27

P: n/a
In article <7x************@ruckus.brouhaha.com>,
Paul Rubin <http://ph****@NOSPAM.invalid> wrote:

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.


While that's true, one of the reasons Guido has historically rejected
this optimization is because there are plenty of recursive algorithms
not amenable to tail-call optimization.
--
Aahz (aa**@pythoncraft.com) <*> http://www.pythoncraft.com/

The way to build large Python applications is to componentize and
loosely-couple the hell out of everything.
Sep 16 '05 #28

P: n/a
aa**@pythoncraft.com (Aahz) writes:
In article <7x************@ruckus.brouhaha.com>,
Paul Rubin <http://ph****@NOSPAM.invalid> wrote:
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.

While that's true, one of the reasons Guido has historically rejected
this optimization is because there are plenty of recursive algorithms
not amenable to tail-call optimization.


That seems amazingly silly. Sort of like refusing to hoist function
definitions because not all function definitions can be hoisted. Or
choose your favorite "sometimes-I-can-sometimes-I-can't" optimization.

Since the BDFL is *not* known for doing even mildly silly things when
it comes to Python's design and implementation, I suspect there's more
to the story than that.

<mike
--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.
Sep 16 '05 #29

P: n/a
[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)

[...] 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. [...]


I did not look recently, but many introductory texts to computer
science, and many, many "serious" teachers as well, introduce recursion
using Fibonacci numbers and Towers of Hanoi. So, there is no need to be
harsh on your correspondent, unless you feel like being harsh on a whole
generation of teachers as well! :-)

This being said, for one, I always found _insane_ presenting recursion
to new programmers using such examples, which are both very easily,
and much better written non-recursively. It does not help beginners
at taking recursion any seriously. This is handicapping somehow, as
recursion could be so useful when properly understood and applied.

--
François Pinard http://pinard.progiciels-bpi.ca
Sep 16 '05 #30

P: n/a
François Pinard <pi****@iro.umontreal.ca> writes:
This being said, for one, I always found _insane_ presenting recursion
to new programmers using such examples, which are both very easily,
and much better written non-recursively. It does not help beginners
at taking recursion any seriously. This is handicapping somehow, as
recursion could be so useful when properly understood and applied.


Yup. I was lucky enough to stumble onto a book titled "Recursvie
Techniques in Programming" by D.W. Barron while still a relative
newcomer to programming. It makes an excellent introduction to the
topic.

Surprisingly, it's apparently still in print. At least Amazon claims
you can order new copies of it.

<mike
--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.
Sep 16 '05 #31

P: n/a
François Pinard <pi****@iro.umontreal.ca> writes:
This being said, for one, I always found _insane_ presenting recursion
to new programmers using such examples, which are both very easily,
and much better written non-recursively. It does not help beginners
at taking recursion any seriously.


I dunno whether functional programming is a suitable topic for
beginners, but I do know that there are some kinds of programs that
beginners shouldn't be writing. I'm more interested in how well these
techniques work for experts, than in how well they work for beginners.
Sep 16 '05 #32

P: n/a

"Mike Meyer" <mw*@mired.org> wrote in message
news:86************@bhuda.mired.org...
aa**@pythoncraft.com (Aahz) writes:
While that's true, one of the reasons Guido has historically rejected
this optimization is because there are plenty of recursive algorithms
not amenable to tail-call optimization.


That seems amazingly silly. Sort of like refusing to hoist function
definitions because not all function definitions can be hoisted. Or
choose your favorite "sometimes-I-can-sometimes-I-can't" optimization.

Since the BDFL is *not* known for doing even mildly silly things when
it comes to Python's design and implementation, I suspect there's more
to the story than that.


Yes. The reason Guido rejected tail-call optimization the last time it was
suggested is because it is semanticly incorrect for Python. Python's name
bindings are dynamic, not static, and the optimization (and the discussion
here) assumes static bindings. In Python, runtime recursiveness (defined
as a function *object* calling itself directly or indirectly), is
dynamically determined. You cannot tell whether a function object will act
recursive or not just by looking at its code body. Trivial examples:

def f(): return f() # looks recursive
g = f
def f(): return 1 # now the function formerly named f and now g is not

def f(): return g() # looks not recursive
g = f # now it is

Someone, I believe Raymond H., wrote and posted and maybe added to the
Cookbook a CPython-specific bytecode hack to change 'load global named 'f'
(or whatever) to 'load constant <function object f>' to eliminate the
dynamic name lookup. This could be written as a decorator if it is not
now.

Terry J. Reedy

Sep 16 '05 #33

P: n/a
Terry Reedy cites:
"Mike Meyer" who fights with:
While that's true, one of the reasons Guido has historically rejected
this optimization is because there are plenty of recursive algorithms
not amenable to tail-call optimization.
Since the BDFL is *not* known for doing even mildly silly things when
it comes to Python's design and implementation, I suspect there's more
to the story than that.

Yes. The reason Guido rejected tail-call optimization the last time it was
suggested is because it is semanticly incorrect for Python. Python's name
bindings are dynamic, not static, and the optimization (and the discussion
here) assumes static bindings. In Python, runtime recursiveness (defined
as a function *object* calling itself directly or indirectly), is
dynamically determined. You cannot tell whether a function object will act
recursive or not just by looking at its code body.


Hmmmmmm.....

The question is to optimize the TAIL CALLS, not just the recursivity.
Mind you, Scheme has also a dynamical name binding, yet it does this
optimization. This is for me more a question of policy than of
semantics [with the *true* meaning of the word "semantics"].

The situation is a bit different in, say, Prolog, where the tail calls
cannot - typically - be optimized for *serious* reasons, the indeterminism.
Prolog has to keep/stack the choice points in recursive generators.
In Python not so.

Hm.
Now I began to scratch my head. I will have to translate some Prolog
algorithms to Python generators...

Jerzy Karczmarczuk
Sep 16 '05 #34

P: n/a
On Thu, 15 Sep 2005 18:07:28 +0100, phil hunt wrote:
On Thu, 15 Sep 2005 21:56:06 +1000, Steven D'Aprano <st***@REMOVETHIScyber.com.au> wrote:

Are you saying that the recursion done by "serious" languages is a fake?
That it is actually implemented behind the scenes by iteration?

It seems to me that if recursion and iteration produce "the exact same
machine code", the argument for preferring recursion over iteration is
gutted.


It seems to me that if a high level language and assembler produce
"the exact same machine code", the argument for preferring high
level languages is gutted.

Do you see the fallacy in your statement now?


Ah, yes, you got me on that one.

But there is a difference: writing assembly is *hard*, which is why we
prefer not to do it. Are you suggesting that functional programming is
significantly easier to do than declarative?

--
Steven.

Sep 16 '05 #35

P: n/a
Paddy wrote:
A work colleague circulated this interesting article about reducing
software bugs by orders of magnitude:


The problem that these sorts of approaches don't address is the simple
fact that simple creating a formal spec and implementing it, even if
you manage to create a way of automating the test suite from the spec
*doesn't guarantee that it will do the right thing*.

The hidden assumption is that the formal spec will be correct. If it
isn't then you have the same problems as before. Sure you might be able
to reduce the number of bugs, but you can be certain of one thing,
given:
* Customer has a need
* Customer communicates this to Supplier
* Supplier translates needs to spec
* Supplier translates spec back to english
* Customer agrees spec

This involves human communication, and misunderstandings happen all
the time then. Sure it can be easier to detect errors at this stage,
but you can't guarantee that it will do so. You can almost guarantee
though that people will misunderstand each other from time to time.
A purely engineering approach to dealing with correctness cannot
guarantee that misunderstandings won't occur. Those misunderstandings
translate into bugs, no matter what approach you use.

It's why I find XP and agile approaches interesting, they're often more
than just engineering.

As a result I'd say that the subject "Software bugs aren't inevitable"
is not true.

Regards,
Michael.
--
Mi************@rd.bbc.co.uk, http://kamaelia.sourceforge.net/
British Broadcasting Corporation, Research and Development
Kingswood Warren, Surrey KT20 6NP

This message (and any attachments) may contain personal views
which are not the views of the BBC unless specifically stated.

Sep 16 '05 #36

P: n/a
Steven D'Aprano <st***@REMOVETHIScyber.com.au> writes:
But there is a difference: writing assembly is *hard*, which is why we
prefer not to do it. Are you suggesting that functional programming is
significantly easier to do than declarative?


I think you mean imperative. Yes, there is a community that believes
that writing bug-free programs in functional style is easier than
writing them in imperative style. Writing buggy programs might be
easier in imperative style, but in some application areas, that's not
good enough.

Why don't you read the Hughes paper I cited instead of taking cheap
shots at it without reading it, if you want to understand the issues
better.
Sep 16 '05 #37

P: n/a
Steven D'Aprano wrote:
On Thu, 15 Sep 2005 18:07:28 +0100, phil hunt wrote:
On Thu, 15 Sep 2005 21:56:06 +1000, Steven D'Aprano
<st***@REMOVETHIScyber.com.au> wrote:

Are you saying that the recursion done by "serious" languages is a fake?
That it is actually implemented behind the scenes by iteration?

It seems to me that if recursion and iteration produce "the exact same
machine code", the argument for preferring recursion over iteration is
gutted.


It seems to me that if a high level language and assembler produce
"the exact same machine code", the argument for preferring high
level languages is gutted.

Do you see the fallacy in your statement now?


Ah, yes, you got me on that one.

But there is a difference: writing assembly is *hard*, which is why we
prefer not to do it. Are you suggesting that functional programming is
significantly easier to do than declarative?


But there is a difference: writing assembly is *hard*, which is why we
prefer not to do it. Are you suggesting that object oriented programming is
significantly easier to do than old style imperative?

(sorry, couldn't resist)

FWIW, IMO once you've learnt functional programming's idioms it certainly
can be easier and more natural. The problem is the tools that make things
like recursion efficient aren't available normally in mainstream languages
meaning that most people simply don't get the practice.

Essentially it's about expressiveness.

Think of it this way - we normally write left to write, however some
languages read up and down. Neither is inherently better or easier
than the other, but for some things *may* be more expressive.

If you think about it being about choosing the most clear/expressive way to
describe an algorithm, the argument may become clearer. After all, the
recursive definition of some things is clearer than the non-recursive.
Michael.

Sep 16 '05 #38

P: n/a

Michael Sparks wrote:
The problem that these sorts of approaches don't address is the simple
fact that simple creating a formal spec and implementing it, even if
you manage to create a way of automating the test suite from the spec
*doesn't guarantee that it will do the right thing*. <snip> As a result I'd say that the subject "Software bugs aren't inevitable"
is not true.


I think you can argue (I would) that any behaviour that is in the
specification this "isn't right" is not a software bug, but a
specification error. This obviously puts the focus on specification
errors, but standard development processes don't guarantee the absence
of specification errors either.

Btw, I'm not arguing that this type of approach is widely applicable,
but the "you'll always face specification errors" argument isn't well
reasoned I think.

Cheers,
Giles

Sep 16 '05 #39

P: n/a
On Thursday 15 September 2005 04:38 am, Jerzy Karczmarczuk wrote:
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.
This is ludicrous sophistry. The technical reason for having ANY high
level languages is "psychological". Computers are happier with binary
code, over ANY language that must be interpreted. So, presumeably, would
some perfect intellectual being not limited by "mere psychology".

Programming languages are an interface to Human minds, so the argument
that one system of representation is easier to understand is an argument
that that system is *better* in that it is a better interface.
(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...)


Clearly Jerry here believes that arrogance and intelligence must go hand
in hand: just for your education, there is a difference between *being*
intelligent and feeling like you have to *prove* it to everyone you meet.
I learned a long time ago, that there are plenty of *unavoidably* complex
problems out there, so that there's so need to make simple ones complex,
just to prove how clever you are. You're darned right I avoid wasting
time on problems that don't require it.

As for the education claim, you are just *so* out of your depth ...
Humans learn to program about as early now as they can handle the subject.
Many working programmers today started learning to program in grade school,
most of the ones under 30 or so started in high school at the latest.

As a matter of observable fact, people tend to solve problems in certain
ways more naturally than others (and not necessarily the same way as
other people). There's nothing "more natural" about functional
programming than procedural. In fact, it would appear that some
problems are more intuitive to solve one way or the other.

The FP camp (apparently) wants to advance the claim that FP will *always*
reduce bugs. I find that very hard to believe. It seems to me that programmers
will always have an easier time reducing bugs in programs they *understand*
well. While cleverness in algorithm design is always respected for the
intellectual prowess it demonstrates, it is almost always bad engineering.

"Keep It Simple Stupid" is just as good a rule in computer science
as in any other area of engineering -- and given the natural complexity
of CS, it clearly needs such admonitions more.

I don't avoid complex code because I *can't* understand it. I avoid it,
because complex code gets in the way of solving problems. You might argue
that FP code is simpler because it is shorter or encodes fewer conceptual
steps (within the FP framework), but this is just as false a measure, IMHO,
as Perl (or C) advocates' tendency to measure complexity in keystrokes
or lines of code.

Just because something involves fewer symbols doesn't necessarily make it
simpler. There's a correlation -- but other factors, like the amount of
time the reader is going to have to spend visualizing or stepping through
the process are just as important.

Rules like estimating project complexity in lines of code rely on
assumptions that the average level of understanding required to deal
with average lines of code are about the same. It would seem that in
practice this is true.

But that is tangential to this argument: if you insist on a difficult
methodology, then you are violating the assumption of the LOC estimation
model, and it will no longer be accurate. To the degree that FP makes
each LOC harder to understand, it is cancelling out any LOC savings it
makes.

So, when FP is intuitive AND reduces code complexity AND is reasonably
efficient, it's a good buy, and I'll use it -- but to argue that it
will *always* do so seems insane.

--
Terry Hancock ( hancock at anansispaceworks.com )
Anansi Spaceworks http://www.anansispaceworks.com

Sep 16 '05 #40

P: n/a
Terry Hancock enlightened us with:
This is ludicrous sophistry. The technical reason for having ANY high
level languages is "psychological". Computers are happier with binary
code, over ANY language that must be interpreted.
Computers aren't happy. They couldn't care less about the programming
language.
Programming languages are an interface to Human minds, so the
argument that one system of representation is easier to understand
is an argument that that system is *better* in that it is a better
interface.


Well said! I'm going to remember that one :)

Sybren
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa
Sep 16 '05 #41

P: n/a
On Friday 16 September 2005 08:35 am, Michael Sparks wrote:
Steven D'Aprano wrote:
But there is a difference: writing assembly is *hard*, which is why we
prefer not to do it. Are you suggesting that functional programming is
significantly easier to do than declarative?
But there is a difference: writing assembly is *hard*, which is why we
prefer not to do it. Are you suggesting that object oriented programming is
significantly easier to do than old style imperative?


The answer in both cases, is that it depends very much on what you're
trying to write.
FWIW, IMO once you've learnt functional programming's idioms it certainly
can be easier and more natural.
In particular domains of problem-solving, yes.
The problem is the tools that make things
like recursion efficient aren't available normally in mainstream languages
meaning that most people simply don't get the practice.
There's also an assumption here (which I regard as a fallacy), that different
models of programming are equally intuitive. Some models, like OOP, draw
heavily on experience *outside* the realm of programming (in many cases,
you can successfully apply machine-shop experience to a programming problem
if the program is object-oriented -- in fact, ISTM, this is the *primary*
power of OOP, that it allows you to provide experience from the problem
domain to the process of writing a software program to work with that domain).

Functional programming (and I am no expert here), seems to me to draw
heavily on the problem domain *of* computer science. So naturally,
computer scientists think it's brilliant and intuitive.

But for those of us who primarily regard computers as tools for solving
problems in other domains -- such as image-processing, web-application,
handling business transactions, or simulating supernovae -- FP just doesn't
seem very natural at all. In fact it seems completely backwards, perverse,
and twisted, as if the designer were simply trying to confuse and
obfuscate the problem instead of solving it.

Or at least, it frequently does.
Essentially it's about expressiveness.
Yes, and expressiveness means keeping vocabulary and grammar for
different applications, not throwing one out on the basis that it
is somehow superior. If you *are* making the latter claim, then
the burden is on you to prove that your method is really that much
better.
Think of it this way - we normally write left to write, however some
languages read up and down. Neither is inherently better or easier
than the other, but for some things *may* be more expressive.
I *really* doubt that, actually. ;-)
But I heard what you meant.
If you think about it being about choosing the most clear/expressive way to
describe an algorithm, the argument may become clearer. After all, the
recursive definition of some things is clearer than the non-recursive.


Yes. I think all we're claiming is that the reverse is equally true.

In addition to this kind of elegance argument, there is also a pragmatic
argument that, with existing technology, it is sometimes much more efficient
to write an iterative solution than to insist on recursion. Even if it can
then be shown for particular cases that a recursive solution that is also
efficient exists, and even if it can be proven that, in general, all such
efficient iterative solutions have equivalent recursive solutions, it does
not defeat the simple point that the obvious iterative solution is faster
and more efficient than the obvious recursive solution.

Let's not forget that this started with an example of the Fibonacci series.

Who in their right mind would *actually* be trying to solve the Fibonacci
series for a practical programming application? It's a toy, like the
"hello world" program. I have no doubt that I can handle the extra burden
of understanding the cleverly structured "efficient recursive" algorithm,
versus the alternatives. But I can also see that it *is* more of a burden
to understand it -- it causes confusion.

Now what happens when the complexity goes up ten-fold, and we add extra
bells and whistles to it that theoretical programs usually skip over, and
real world programs have in abundance?

At that point, I *really* want that core problem to be simple to understand.
Ideally, as simple as it can possibly be.

--
Terry Hancock ( hancock at anansispaceworks.com )
Anansi Spaceworks http://www.anansispaceworks.com

Sep 16 '05 #42

P: n/a
On Friday 16 September 2005 09:41 am, Terry Hancock wrote:
(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...)


Clearly Jerry here believes that arrogance and intelligence must go hand
in hand: just for your education, there is a difference between *being*
intelligent and feeling like you have to *prove* it to everyone you meet.
I learned a long time ago, that there are plenty of *unavoidably* complex
problems out there, so that there's so need to make simple ones complex,
just to prove how clever you are. You're darned right I avoid wasting
time on problems that don't require it.


I *probably* should've used a little more restraint here. ;-)

I *definitely* should've spelled Jerzy's name correctly.
Sorry, no offense intended.

--
Terry Hancock ( hancock at anansispaceworks.com )
Anansi Spaceworks http://www.anansispaceworks.com

Sep 16 '05 #43

P: n/a
Paul Rubin wrote:
Steven D'Aprano <st***@REMOVETHIScyber.com.au> writes:
But there is a difference: writing assembly is *hard*, which is why we
prefer not to do it. Are you suggesting that functional programming is
significantly easier to do than declarative?

I think you mean imperative. Yes, there is a community that believes
that writing bug-free programs in functional style is easier than
writing them in imperative style. Writing buggy programs might be
easier in imperative style, but in some application areas, that's not
good enough.

Why don't you read the Hughes paper I cited instead of taking cheap
shots at it without reading it, if you want to understand the issues
better.

Just some comments from my own experiences concerning bugs and writing
dependable software. It pretty much depends on a number of things and
isn't just a matter of good design or what language is used.

* The dependability of the hardware
* The dependability of the OS
* The stability of the language used
* The programmers knowledge of the language used
* Program design
* How many programmers are working on the same project
* How many extensions are used and written by other people
* The stability of those extensions
* Rate of change of the program design, and all underlying parts.

A small program with no external modules and written by a single person
can be fairly dependable, or as dependable as the underlying language,
OS, and hardware.

But as soon as the softwares complexity increases and/or multiple
programmers are used, either directly or indirectly through third party
extensions, then the probability of bugs increases substantially.

Given *enough* time, effort, and testing, without changing the design,
even a large program can be nearly as dependable as the least dependable
part of the platform it is running on. ("enough" could be a long time
here.)

To increase reliability to nearly 100%, you need to run different
versions of a program on several different platforms simultaneously and
use only the results that have a majority agreement.

Or to put it another way; risk management by ... "keep it simple",
"don't have too many cooks", "get second opinions", and "don't put all
your eggs in one basket".

Cheers,
Ron

Sep 16 '05 #44

P: n/a
Terry Reedy wrote:
You cannot tell whether a function object will act
recursive or not just by looking at its code body. Trivial examples:


I was thinking last night that maybe it would be useful to be able to
define a function explicitly as a recursive object where it's frame is
reused on successive calls, but then I realized that it's nearly
identical to a loop in that context, so why not just write it as a loop
to start with.

Cheers,
Ron
Sep 16 '05 #45

P: n/a
On Fri, 16 Sep 2005 20:36:02 +1000, Steven D'Aprano <st***@REMOVETHIScyber.com.au> wrote:
On Thu, 15 Sep 2005 18:07:28 +0100, phil hunt wrote:
On Thu, 15 Sep 2005 21:56:06 +1000, Steven D'Aprano <st***@REMOVETHIScyber.com.au> wrote:

Are you saying that the recursion done by "serious" languages is a fake?
That it is actually implemented behind the scenes by iteration?

It seems to me that if recursion and iteration produce "the exact same
machine code", the argument for preferring recursion over iteration is
gutted.


It seems to me that if a high level language and assembler produce
"the exact same machine code", the argument for preferring high
level languages is gutted.

Do you see the fallacy in your statement now?


Ah, yes, you got me on that one.

But there is a difference: writing assembly is *hard*, which is why we
prefer not to do it. Are you suggesting that functional programming is
significantly easier to do than declarative?


No. I'm saying that under some circumstances it might be easier to
write code as a recursive routine than a loop. In those
circumstances, why should I care if the compiler then re-encodes my
recursive routine as a loop, so long as the program gives the
correct answer.

Compilers/interpreters/runtimes are black boxes: we don't (or
shouldn't) care how they do their work as long as they run correctly
and aren't too heavy on system resources like CPU time and memory.
--
Email: zen19725 at zen dot co dot uk
Sep 16 '05 #46

P: n/a
The article states that their method calls for them to have much more
than normal access to many more people in the clients organisation than
is normal; from the CEO to the receptionist.
The specification stage can take a year without the customer seeing a
line of code.
And they deliberately "write one to throw away".

In short, they *are* aware of the human element .

- Pad.

Sep 16 '05 #47

P: n/a
ze******@zen.co.uk (phil hunt) writes:
Compilers/interpreters/runtimes are black boxes: we don't (or
shouldn't) care how they do their work as long as they run correctly
and aren't too heavy on system resources like CPU time and memory.


Maybe in academia. Not in the real world. Or maybe you just phrased
that last clause poorly. In the real world, programs have performance
constraints. Some of them are seriously inflexible - in which case we
call what we're doing "real-time" or "embedded" or words to that
effect. Others are softer, but in the end they matter *very much*. I
would have phrased that last clause to make reasonableness a
requirement, rather than making "not unreasonable" the requirement.

Because of that, you have to care about how your implementation
works. If you don't know how strings work in Python, you tend to write
O(n^2) algorithms instead of O(n) ones for fundamental
operations. Things like that make a difference.

<mike
--
Mike Meyer <mw*@mired.org> http://www.mired.org/home/mwm/
Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information.
Sep 17 '05 #48

P: n/a
On Fri, 16 Sep 2005 20:05:04 -0400, Mike Meyer <mw*@mired.org> wrote:
ze******@zen.co.uk (phil hunt) writes:
Compilers/interpreters/runtimes are black boxes: we don't (or
shouldn't) care how they do their work as long as they run correctly
and aren't too heavy on system resources like CPU time and memory.
Maybe in academia. Not in the real world. Or maybe you just phrased
that last clause poorly.


I think perhaps I did.
In the real world, programs have performance
constraints.
Yes i know, that's why I said "aren't too heavy on system resources
like CPU time and memory".
Some of them are seriously inflexible - in which case we
call what we're doing "real-time" or "embedded" or words to that
effect.
If a program is too slow to respond isn't that about "system time"?
Others are softer, but in the end they matter *very much*. I
would have phrased that last clause to make reasonableness a
requirement, rather than making "not unreasonable" the requirement.

Because of that, you have to care about how your implementation
works. If you don't know how strings work in Python, you tend to write
O(n^2) algorithms instead of O(n) ones for fundamental
operations.


What does "CPU time" mean again?

--
Email: zen19725 at zen dot co dot uk
Sep 17 '05 #49

P: n/a
phil hunt enlightened us with:
If a program is too slow to respond isn't that about "system time"?
Not by definition. Could be anything. If it's slow to respond due to a
slow harddisk, then you're right. If it's slow to respond due to not
putting the I/O and the GUI main loop in different threads, then it's
not about "system time".
What does "CPU time" mean again?


The time the CPU takes to run (part of) a program. And this means the
time the CPU actually spends on running that program, and not some
other piece of software.

Sybren
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa
Sep 17 '05 #50

56 Replies

This discussion thread is closed

Replies have been disabled for this discussion.