Software bugs aren't inevitable

S

Steven D'Aprano

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.
 
J

Jerzy Karczmarczuk

Steven said:
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
 
P

phil hunt

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?
 
P

Paddy

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.
 
T

Terry Reedy

Steven D'Aprano said:
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
 
S

Steven D'Aprano

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.
 
S

Steven D'Aprano

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.
 
A

Aahz

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.
 
M

Mike Meyer

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
 
?

=?iso-8859-1?Q?Fran=E7ois?= Pinard

[Jerzy Karczmarczuk]
Steven D'Aprano recommends iteration over recursion:
[...] 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.
 
M

Mike Meyer

François Pinard said:
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
 
P

Paul Rubin

François Pinard said:
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.
 
T

Terry Reedy

Mike Meyer said:
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
 
M

Michael Sparks

Paddy said:
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.
--
(e-mail address removed), 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.
 
J

Jerzy Karczmarczuk

Terry Reedy cites:
"Mike Meyer" who fights with:


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
 
S

Steven D'Aprano

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?
 
P

Paul Rubin

Steven D'Aprano said:
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.
 
M

Michael Sparks

Steven said:
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.
 
G

Giles Brown

Michael said:
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*.
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
 
T

Terry Hancock

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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top