Software bugs aren't inevitable

Discussion in 'Python' started by Paddy, Sep 12, 2005.

  1. Paddy

    Paddy Guest

    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.
    Paddy, Sep 12, 2005
    #1
    1. Advertising

  2. Paddy

    Paul Rubin Guest

    "Paddy" <> writes:
    > 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).
    Paul Rubin, Sep 14, 2005
    #2
    1. Advertising

  3. 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.
    Steven D'Aprano, Sep 14, 2005
    #3
  4. 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
    Jerzy Karczmarczuk, Sep 14, 2005
    #4
  5. Paddy

    Giles Brown Guest

    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.
    Giles Brown, Sep 14, 2005
    #5
  6. Paddy

    Terry Reedy Guest

    "Steven D'Aprano" <> wrote in message
    news:p...
    > 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
    Terry Reedy, Sep 14, 2005
    #6
  7. 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.
    Rocco Moretti, Sep 14, 2005
    #7
  8. On Wed, 14 Sep 2005 11:28:02 -0400, Terry Reedy wrote:

    >
    > "Steven D'Aprano" <> wrote in message
    > news:p...
    >> 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.
    Steven D'Aprano, Sep 14, 2005
    #8
  9. 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.
    Steven D'Aprano, Sep 14, 2005
    #9
  10. Paddy

    Paul Rubin Guest

    Steven D'Aprano <> 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.
    Paul Rubin, Sep 14, 2005
    #10
  11. Paddy

    Paddy Guest

    Paddy, Sep 14, 2005
    #11
  12. Paddy

    Paddy Guest

    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.
    Paddy, Sep 14, 2005
    #12
  13. On Wednesday 14 September 2005 02:23 pm, Paul Rubin wrote:
    > Steven D'Aprano <> 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
    Terry Hancock, Sep 15, 2005
    #13
  14. Paddy

    Terry Reedy Guest

    "Rocco Moretti" <> wrote in message
    news:dg9jh7$on1$...
    > 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, Sep 15, 2005
    #14
  15. Paddy

    Terry Reedy Guest

    "Steven D'Aprano" <> wrote in message
    news:p...
    > 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
    Terry Reedy, Sep 15, 2005
    #15
  16. Paddy

    Terry Reedy Guest

    "Steven D'Aprano" <> wrote in message
    news:p...
    > 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
    Terry Reedy, Sep 15, 2005
    #16
  17. Paddy

    Paul Rubin Guest

    "Paddy" <> 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.
    Paul Rubin, Sep 15, 2005
    #17
  18. 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
    Jerzy Karczmarczuk, Sep 15, 2005
    #18
  19. Paddy

    Steve Holden Guest

    Oh Yes, They Are [was: Re: Software bugs aren't inevitable]

    Paddy wrote:
    > 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
    --
    Steve Holden +44 150 684 7255 +1 800 494 3119
    Holden Web LLC www.holdenweb.com
    PyCon TX 2006 www.pycon.org
    Steve Holden, Sep 15, 2005
    #19
  20. Hi!

    2005/9/15, Jerzy Karczmarczuk <>:

    [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
    Carl Friedrich Bolz, Sep 15, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?VHlzb24gQnJvd24=?=

    SetAuthCookie works, but our cookies aren't being written - HELP

    =?Utf-8?B?VHlzb24gQnJvd24=?=, May 3, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    422
  2. John
    Replies:
    0
    Views:
    991
  3. John
    Replies:
    0
    Views:
    1,020
  4. M.Caggiano

    Software anti-bugs

    M.Caggiano, Dec 15, 2008, in forum: C Programming
    Replies:
    11
    Views:
    1,739
    Andrew Smallshaw
    Dec 16, 2008
  5. Josef 'Jupp' Schugt

    Still use 'ruby-bugs' for Ruby bugs?

    Josef 'Jupp' Schugt, Nov 4, 2004, in forum: Ruby
    Replies:
    2
    Views:
    160
    Tom Copeland
    Nov 4, 2004
Loading...

Share This Page