Christoph Zwerschke wrote:
> 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
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.
> 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.
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 "mathematical", so the overflow problem
described in your referenced article doesn't exist here.
--
http://mail.python.org/mailman/listinfo/python-list
