Python less error-prone than Java

[Christoph Zwerschke]

You will often hear that for reasons of fault minimization, you should
use a programming language with strict typing:

http://turing.une.edu.au/~comp284/Lectures/Lecture_18/lecture/node1.html

I just came across a funny example in which the opposite is the case.

The following is a binary search algorithm in Java. It searches a value
in an ordered array a of ints:

public static int binarySearch(in t[] a, int key) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}

Now the same thing, directly converted to Python:

def binarySearch(a, key):
low = 0
high = len(a) - 1
while low <= high:
mid = (low + high) / 2
midVal = a[mid]
if midVal < key:
low = mid + 1
elif midVal > key:
high = mid - 1;
else:
return mid # key found
return -(low + 1) # key not found.

What's better about the Python version? First, it will operate on *any*
sorted array, no matter which type the values have.

But second, there is a hidden error in the Java version that the Python
version does not have.

See the following web page if you dont find it ;-)

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

-- Christoph

[Simon Percivall]

Re: Python less error-prone than Java

Actually, you're wrong on all levels.

First: It's perfectly simple in Java to create a binary sort that sorts
all arrays that contain objects; so wrong there.

Secondly: The bug has nothing to do with static typing (I'm guessing
that's what you meant. Both Python and Java are strongly typed). The
problem is that ints are bounded in Java. They could easily have been
ints and then automatically coerced to (equivalent to) longs when they
got bigger; that they aren't is more a design fault than anything to do
with static typing. The equivalent in Python would have been if an
overflow exception was raised when the int got too big. It might have
been that way, typing or no typing.

Christoph Zwerschke wrote:[color=blue]
> You will often hear that for reasons of fault minimization, you should
> use a programming language with strict typing:
> http://turing.une.edu.au/~comp284/Le...ure/node1.html
>
> I just came across a funny example in which the opposite is the case.
>
> The following is a binary search algorithm in Java. It searches a value
> in an ordered array a of ints:
>
> public static int binarySearch(in t[] a, int key) {
> int low = 0;
> int high = a.length - 1;
> while (low <= high) {
> int mid = (low + high) / 2;
> int midVal = a[mid];
> if (midVal < key)
> low = mid + 1;
> else if (midVal > key)
> high = mid - 1;
> else
> return mid; // key found
> }
> return -(low + 1); // key not found.
> }
>
> Now the same thing, directly converted to Python:
>
> def binarySearch(a, key):
> low = 0
> high = len(a) - 1
> while low <= high:
> mid = (low + high) / 2
> midVal = a[mid]
> if midVal < key:
> low = mid + 1
> elif midVal > key:
> high = mid - 1;
> else:
> return mid # key found
> return -(low + 1) # key not found.
>
> What's better about the Python version? First, it will operate on *any*
> sorted array, no matter which type the values have.
>
> But second, there is a hidden error in the Java version that the Python
> version does not have.
>
> See the following web page if you dont find it ;-)
> http://googleresearch.blogspot.com/2...it-nearly.html
>
> -- Christoph[/color]

[Alex Martelli]

Re: Python less error-prone than Java

Simon Percivall <percivall@gmai l.com> wrote:
...[color=blue]
> with static typing. The equivalent in Python would have been if an
> overflow exception was raised when the int got too big. It might have
> been that way, typing or no typing.[/color]

Indeed, it _used_ to be that way --
<http://docs.python.org/lib/module-exceptions.html > STILL says...:

exception OverflowError

Raised when the result of an arithmetic operation is too large to be
represented. This cannot occur for long integers (which would rather
raise MemoryError than give up). Because of the lack of standardization
of floating point exception handling in C, most floating point
operations also aren't checked. For plain integers, all operations that
can overflow are checked except left shift, where typical applications
prefer to drop bits than raise an exception.


Actually, the docs are obsolete on this point, and an int becomes a long
when that's necessary:
[color=blue][color=green][color=darkred]
>>> sys.maxint+1[/color][/color][/color]
2147483648L

but, this operation _would_ have raised OverflowError in old-enough
versions of Python (not sure exactly when the switch happened...).


Alex

[Cameron Laird]

Re: Python less error-prone than Java

In article <e5sukk$ei4$1@o nline.de>,
Christoph Zwerschke <cito@online.de > wrote:[color=blue]
>You will often hear that for reasons of fault minimization, you should
>use a programming language with strict typing:
>http://turing.une.edu.au/~comp284/Le...ure/node1.html
>
>I just came across a funny example in which the opposite is the case.[/color]

[Christoph Zwerschke]

Re: Python less error-prone than Java

Simon Percivall wrote:[color=blue]
> First: It's perfectly simple in Java to create a binary sort that
> sorts all arrays that contain objects; so wrong there.[/color]

My point was that the *same* Java source example, directly converted to
Python would *automatically* accept all kinds of arrays. No need to make
any extra efforts. By the way, how would you do it in Java? With
function overloading? I would not call that perfectly simple.
[color=blue]
> Secondly: The bug has nothing to do with static typing (I'm guessing
> that's what you meant. Both Python and Java are strongly typed). The
> problem is that ints are bounded in Java. They could easily have been
> ints and then automatically coerced to (equivalent to) longs when they
> got bigger; that they aren't is more a design fault than anything to
> do with static typing. The equivalent in Python would have been if an
> overflow exception was raised when the int got too big. It might have
> been that way, typing or no typing.[/color]

Yes, sorry, I meant static typing, not strict typing. But I still do
think that the bug has to do with static typing. You're right, the
direct cause is that ints are bounded in Java, and not bounded in
Python, and that it could well be the other way round. However, doing it
the other way round would not be so clever and appropriate for the
respective language due to the difference in static typing.

Java could coerce the result to long, but then it would still crash when
the result is stored back to the statically typed variable. So that
would not be very clever.

And Python could produce an overflow error (and did in the past), but
taking advantage of the possibilities of dynamic typing and
automatically producing longs is a cleverer solution for Python, and
that's why it was proposed and accepted in PEP237.

So the difference in static typing is actually the deeper reason why
ints were made to behave differently in the two languages.

-- Christoph

[Christoph Zwerschke]

Re: Python less error-prone than Java

Cameron Laird wrote:[color=blue]
> So, here's my summary: Python's a nice language--a very nice one.
> It's safer to use than Java in many ways. Python's typing is
> STRICTER than Java's, but it's also dynamic, so people get to argue
> for decades about which is a better model. Anyone who thinks typing
> is a first-order determinant of code quality is making a big mistake
> though, anyway.[/color]

Yes, sorry. It has nothing to do with strict, but with static typing.
And I should not have chosen such a general subject line (I just meant
to be funny, but sounded more like a troll). I had just noticed that the
direct translation of that Java program to Python would not have that
subtle bug and found that this was worth mentioning.

-- Christoph

[Alan Morgan]

Re: Python less error-prone than Java

In article <e5tdfh$3s3$1@o nline.de>,
Christoph Zwerschke <cito@online.de > wrote:[color=blue]
>Simon Percivall wrote:[color=green]
> > First: It's perfectly simple in Java to create a binary sort that
> > sorts all arrays that contain objects; so wrong there.[/color]
>
>My point was that the *same* Java source example, directly converted to
>Python would *automatically* accept all kinds of arrays.[/color]

And the same code converted to SML would automatically work on all
kinds of arrays and SML is statically typed. It's a language issue,
not a typing issue.
[color=blue]
>No need to make any extra efforts.
>By the way, how would you do it in Java? With
>function overloading? I would not call that perfectly simple.[/color]

Since Java doesn't allow function overloading that clearly can't be
the way. J2SE 5.0 allows generic classes and functions that operate
on generic containers. There are some gotchas, but it's not drastically
more complex than the original int-only java code.

Alan
--
Defendit numerus

[Neil Hodgson]

Re: Python less error-prone than Java

Alan Morgan wrote:
[color=blue]
> Since Java doesn't allow function overloading that clearly can't be
> the way. J2SE 5.0 allows generic classes and functions that operate
> on generic containers. There are some gotchas, but it's not drastically
> more complex than the original int-only java code.[/color]

Doesn't Java restrict generics to only operate on reference types so
you can't produce a generic binary search that operates on arrays where
the item type may be int?

Neil

[Alan Morgan]

Re: Python less error-prone than Java

In article <3Vtgg.2967$ap3 .12@news-server.bigpond. net.au>,
Neil Hodgson <nyamatongwe+th under@gmail.com > wrote:[color=blue]
>Alan Morgan wrote:
>[color=green]
>> Since Java doesn't allow function overloading that clearly can't be
>> the way. J2SE 5.0 allows generic classes and functions that operate
>> on generic containers. There are some gotchas, but it's not drastically
>> more complex than the original int-only java code.[/color]
>
> Doesn't Java restrict generics to only operate on reference types so
>you can't produce a generic binary search that operates on arrays where
>the item type may be int?[/color]

Yup, you have to wrap int (and double and float and...). Blame type
erasure.

Alan
--
Defendit numerus

[Ilpo Nyyssönen]

Re: Python less error-prone than Java

Christoph Zwerschke <cito@online.de > writes:
[color=blue]
> What's better about the Python version? First, it will operate on
> *any* sorted array, no matter which type the values have.
>
> But second, there is a hidden error in the Java version that the
> Python version does not have.[/color]

While I can see your point, I'd say you are totally in the wrong level
here.

With Java generics you can sort a list and still keeping the type of
the contents defined. This is makes the code less error-prone. But why
would you implement binary search as the standard library already has
it for both arrays and lists? This is one big thing that makes code
less error-prone: using existing well made libraries. You can find
binary search from python standard library too (but actually the API
in Java is a bit better, see the return values).

Well, you can say that the binary search is a good example and in real
code you would use the stuff from the libraries. I'd say it is not
good example: How often will you write such algorithms? Very rarely.

Integer overflows generally are not those errors you run into in
programs. The errors happening most often are from my point of view:

1. null pointer errors
2. wrong type (class cast in Java, some weird missing attribute in python)
3. array/list index out of bounds

First and third ones are the same in about every language. The second
one is one where the typing can make a difference. If in the code
level you know the type all the way, there is much less changes of it
being wrong. (The sad thing in the Java generics is that it is a
compile time only thing and that causes some really weird stuff, but
that is too off topic to here.)

In python passing sequences for a function and also from a function is
very easy. You can very easily pass a sequence as argument list. You
can also very easily return a sequence from the function and even
split it to variables directly. This is very powerful tool, but it has
a problem too: How can you change what you return without breaking the
callers? There are many cases where passing an object instead of a
sequence makes the code much easier to develop further.

What's the point? The point is that neither with Java or Python you
want to be doing things in the low level. You really want to be doing
stuff with objects and using existing libraries as much as possible.
And in that level Java might be less error-prone as it does restrict
the ways you can shoot yourself more.

--
Ilpo Nyyssönen # biny # /* :-) */

[Kaz Kylheku]

Re: Python less error-prone than Java

Christoph Zwerschke wrote:[color=blue]
> You will often hear that for reasons of fault minimization, you should
> use a programming language with strict typing:
> http://turing.une.edu.au/~comp284/Le...ure/node1.html[/color]

Quoting from that web page:

"A programming language with strict typing and run-time checking should
be used."

This doesn't prescribe latent or manifest typing, only that there be
type checking.

There is no question that for reliability, it is necessary to have type
checking, whether at run time or earlier.

You can have statically typed languages with inadequate type safety,
and you can have dynamically typed languages with inadequate type
safety.
[color=blue]
> Now the same thing, directly converted to Python:
>
> def binarySearch(a, key):
> low = 0
> high = len(a) - 1
> while low <= high:
> mid = (low + high) / 2
> midVal = a[mid]
> if midVal < key:
> low = mid + 1
> elif midVal > key:
> high = mid - 1;
> else:
> return mid # key found
> return -(low + 1) # key not found.
>
> What's better about the Python version? First, it will operate on *any*
> sorted array, no matter which type the values have.[/color]

Uh huh! With hard-coded < and = operators, how stupid. What if you want
to use it on strings?

Would that be a case-insensitive lexicographic comparison, or
case-insensitive? How do you specify what kind of less-than and equal
you want to do?

-1 to indicate not found? Why copy Java braindamage induced by an
antiquated form of static typing? The Java version has to do that
because the return value is necessarily declared to be of type integer.


;; Common Lisp
;; Binary search any sorted sequence SEQ for ITEM, returning
;; the position (starting from zero) if the item is found,
;; otherwise returns NIL.
;;
;; :REF specifies positional accessing function, default is ELT
;; :LEN specifies function for retrieving sequence length
;; :LESS specifies function for less-than item comparison
;; :SAME specifies function for equality comparison

(defun binary-search (seq item
&key (ref #'elt) (len #'length)
(less #'<) (same #'=))
(loop with low = 0
and high = (funcall len seq)
while (<= low high)
do
(let* ((mid (truncate (+ low high) 2))
(mid-val (funcall ref seq mid)))
(cond
((funcall less mid-val item)
(setf low (1+ mid)))
((funcall same mid-val item)
(return mid))
(t (setf high (1- mid)))))))

Common Lisp integers are "mathematic al", so the overflow problem
described in your referenced article doesn't exist here.

[Peter Otten]

Re: Python less error-prone than Java

Kaz Kylheku wrote:
[color=blue]
> Would that be a case-insensitive lexicographic comparison, or
> case-insensitive? How do you specify what kind of less-than and equal
> you want to do?[/color]

class Key(object):
def __init__(self, value, key):
self.keyval = key(value)
self.key = key
def __lt__(self, other):
return self.keyval < self.key(other)
def __gt__(self, other):
return self.keyval > self.key(other)

items = ["Alpha", "Beta", "Delta", "Gamma"]
print binarySearch(it ems, Key("DELTA", str.lower)) # 2

You /can/ teach an old duck new tricks :-)

Peter

[Kaz Kylheku]

Re: Python less error-prone than Java

Ilpo Nyyssönen wrote:[color=blue]
> This is one big thing that makes code
> less error-prone: using existing well made libraries.
> You can find binary search from python standard library too (but actuallythe API
> in Java is a bit better, see the return values).
> Well, you can say that the binary search is a good example and in real
> code you would use the stuff from the libraries.[/color]

The trouble with your point is that Christoph's original posting refers
to an article, which, in turn, at the bottom, refers to a bug database
which shows that the very same defect had been found in Sun's Java
library!

Buggy library code is what prompted that article.
[color=blue]
> I'd say it is not
> good example: How often will you write such algorithms? Very rarely.
>
> Integer overflows generally are not those errors you run into in
> programs.[/color]

Except when you feed those programs inputs which are converted to
integers which are then fed as domain values into some operation that
doesn't fit into the range type.

Other than that, you are okay!

Like when would that happen, right?
[color=blue]
> The errors happening most often are from my point of view:
>
> 1. null pointer errors
> 2. wrong type (class cast in Java, some weird missing attribute in python)
> 3. array/list index out of bounds
>
> First and third ones are the same in about every language.[/color]

.... other than C and C++, where their equivalents just crash or stomp
over memory, but never mind; who uses those? ;)
[color=blue]
> The second
> one is one where the typing can make a difference.[/color]

Actually, the first one is also where typing can make a difference.
Instead of this stupid idea of pointers or references having a null
value, you can make a null value which has its own type, and banish
null pointers.

So null pointer errors are transformed into type errors: the special
value NIL was fed into an operation where some other type was expected.
And by means of type polymorphism, an operation can be extended to
handle the case of NIL.

[Christoph Zwerschke]

Re: Python less error-prone than Java

>> Simon Percivall wrote:[color=blue][color=green][color=darkred]
>>> First: It's perfectly simple in Java to create a binary sort that
>>> sorts all arrays that contain objects; so wrong there.[/color]
>> My point was that the *same* Java source example, directly converted to
>> Python would *automatically* accept all kinds of arrays.[/color]
>
> And the same code converted to SML would automatically work on all
> kinds of arrays and SML is statically typed. It's a language issue,
> not a typing issue.[/color]

Ok, here the point was that Java has *explicit* static typing. SML is
not a procedural language and uses *implicit* static typing. Therefore
it shares some of the benefits of dynamically typed languages such as
Python. However, an SML version of the program would probably still have
the same bug as the Java version, right?
[color=blue][color=green]
>> No need to make any extra efforts.
>> By the way, how would you do it in Java? With
>> function overloading? I would not call that perfectly simple.[/color]
>
> Since Java doesn't allow function overloading that clearly can't be
> the way. J2SE 5.0 allows generic classes and functions that operate
> on generic containers. There are some gotchas, but it's not drastically
> more complex than the original int-only java code.[/color]

Java doesn't allow function overloading? That would be new to me. Or did
you just want to nitpick that it should be more properly called
"method overloading" in Java? And as you already said, there are some
gotchas and you would have to wrap int and long etc. I still would not
call that perfectly simple, as it is in Python.

-- Christoph

[Fredrik Lundh]

Re: Python less error-prone than Java

Kaz Kylheku wrote:
[color=blue]
> The trouble with your point is that Christoph's original posting refers
> to an article, which, in turn, at the bottom, refers to a bug database
> which shows that the very same defect had been found in Sun's Java
> library![/color]

and as he points out at the top, it was the article author himself who
wrote that library code:

/.../ let me tell you how I discovered the bug: The version
of binary search that I wrote for the JDK contained the same
bug. It was reported to Sun recently when it broke someone's
program, after lying in wait for nine years or so.

</F>