From: ccc31807 on
On page 61 of Graham's ANSI Common Lisp, he defines bin-search and
finder, which I have copied below.

I have struggled with this for days, and still don't understand these
definitions completely. This morning, I wrote bin-search-2, which took
about ten minutes to write (and about thirty minutes to debug), but I
understand it thoroughly -- and I am just the merest beginner, barely
a toe in the water.

I have noticed this about CL in general and in Graham's book in
particular -- Lispers seem to go to great lengths to make their code
obtuse, obscurantist, obscure, and difficult to understand. For
example, in the example below, Why the nested ifs? Why the nested
lets? I've been reading Miller and Benson 'Lisp: Style and Design' and
I simply don't understand why tutorials (like ANSI CL -- which I think
on the whole is a very good book) want to throw up walls to
understanding. Seems to me that materials targeted toward beginners
would be written to be clear and understandable.

CC.

;;; ---------ch_04.lisp-----------------------
(defparameter v (vector 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
35 37 39 41))

(defun bin-search (obj vec)
(format t "bin-search ~a ~a~%" obj vec)
(let ((len (length vec)))
(and (not (zerop len)))
(finder obj vec 0 (- len 1))))

(defun finder (obj vec start end)
(format t "finder obj: ~a, vec: ~a, start: ~a, end: ~a~%" obj vec
start end)
(format t " ~a~%" (subseq vec start (+ end 1)))
(let ((range (- end start)))
(if (zerop range) ; outer if test
(if (eql obj (aref vec start)) ; inner if test
obj ; the return obj
nil) ; else return nil
(let ((mid (+ start (round (/ range 2))))) ; outer then
(let ((obj2 (aref vec mid)))
(if (< obj obj2)
(finder obj vec start (- mid 1))
(if (> obj obj2)
(finder obj vec (+ mid 1) end)
obj)))))))

(defun bin-search-2 (obj vec &optional (start 0))
(let*((len (length vec))
(mid (floor (/ len 2))))
(format t "bin-search-2 obj: ~a, vec: ~a, start ~a, end: ~a, mid: ~a~
%" obj vec start len mid)
(cond ((zerop len) nil)
((= obj (svref vec mid)) obj)
((< obj (svref vec mid)) (bin-search-2 obj (subseq vec start
mid)))
((> obj (svref vec mid)) (bin-search-2 obj (subseq vec (+ mid
1) len))))))

;; I don't know how to set 'start' to 0 by default, other than by
making it optional.
;; I would appreciate help with this.
From: Zach Beane on
ccc31807 <cartercc(a)gmail.com> writes:

> I have noticed this about CL in general and in Graham's book in
> particular -- Lispers seem to go to great lengths to make their code
> obtuse, obscurantist, obscure, and difficult to understand.

Gee, thanks.

http://www.cs.northwestern.edu/academics/courses/325/readings/graham/graham-notes.html
has some notes on Graham's style.

Zach
From: fortunatus on
On Dec 16, 10:42 am, ccc31807 <carte...(a)gmail.com> wrote:
> On page 61 of Graham's ANSI Common Lisp, he defines bin-search and
> finder, which I have copied below.
....
> Seems to me that materials targeted toward beginners
> would be written to be clear and understandable.

Targeted towards beginners? Why does Graham write books? Why does
Graham write essays?


> ;; I don't know how to set 'start' to 0 by default, other than by
> making it optional.

That's a great way!! I never thought of that - really good idea.


> ;; I would appreciate help with this.

Your code is better, you don't need help.

I might only suggest avoid re-writing (SVREF ...) in the COND. Since
you have a LET* anyway, just put another variable after the (MID ...)
binding.
From: Pillsy on
On Dec 16, 10:42 am, ccc31807 <carte...(a)gmail.com> wrote:
[...]
> I have noticed this about CL in general and in Graham's book in
> particular -- Lispers seem to go to great lengths to make their code
> obtuse, obscurantist, obscure, and difficult to understand. For
> example, in the example below, Why the nested ifs? Why the nested
> lets?

You're not the first person to have some complaints about Graham's
style in ANSI CL; it's a bit idiosyncratic. See

http://www.cs.northwestern.edu/academics/courses/325/readings/graham/graham-notes.html

for some more examples. One of the issues mentioned in the website is
his aversion to COND. I agree that Graham's FINDER function is harder
to to read because he doesn't use COND and LET*.

> I've been reading Miller and Benson 'Lisp: Style and Design' and
> I simply don't understand why tutorials (like ANSI CL -- which I think
> on the whole is a very good book) want to throw up walls to
> understanding.

There's a degree of idiosyncracy to what different people find "clear"
or "easy to understand". I'm virtually certain Graham wasn't writing
his code in a deliberately obscure way, and to be fair to him, I find
his code to be quite clear in this instance, despite the fact that it
would be even clearer with the use of of COND and LET*.

Perhaps you'd be happier starting with a different book?

Now on to your code.
[...]
> (defun bin-search-2 (obj vec &optional (start 0))
>   (let*((len (length vec))
>         (mid (floor (/ len 2))))
>   (format t "bin-search-2 obj: ~a, vec: ~a, start ~a, end: ~a, mid: ~a~
> %" obj vec start len mid)
>   (cond ((zerop len) nil)
>         ((= obj (svref vec mid)) obj)
>         ((< obj (svref vec mid)) (bin-search-2 obj (subseq vec start
> mid)))
>         ((> obj (svref vec mid)) (bin-search-2 obj (subseq vec (+ mid
> 1) len))))))

OK, this is not a good way to go about this. The problem is your use
of SUBSEQ, because it makes a whole new vector every time you call it.
This is very wasteful. There are a number of ways around this, but
frankly Graham's solution, with the auxiliary function FINDER which
takes starting and ending indices, is the best approach, being simple
and efficient, while allowing BIN-SEARCH to provide a very simple
interface to the user.

In general, the approach of wrapping a helper function with a function
that provides a more friendly interface is a very common approach in
Lisp, and it's a good coding practice. Doing a good job decomposing
functions into smaller, simpler functions provides tremendous gains in
clarity, modifiability and ease of testing and debugging, especially
when working with Lisp, which provides such good support for
interactivity. You can test the individual functions at the REPL,
provide doc strings for each one if needed, and STEP, TRACE and the
debugger will all be more useful.

You should also probably follow Graham's lead and use AREF instead of
SVREF, since not every one-dimensional array is a SIMPLE-VECTOR.

> ;; I don't know how to set 'start' to 0 by default, other than by
> making it optional.
> ;; I would appreciate help with this.

Look up "keyword" arguments. It's very common for standard Lisp
functions that deal with sequences to take both :START and :END
keyword arguments.

Cheers,
Pillsy
From: Rainer Joswig on
In article
<60400ac0-f2c3-4fa6-8706-23e53ab1eb2d(a)r1g2000vbp.googlegroups.com>,
ccc31807 <cartercc(a)gmail.com> wrote:

> On page 61 of Graham's ANSI Common Lisp, he defines bin-search and
> finder, which I have copied below.
>
> I have struggled with this for days, and still don't understand these
> definitions completely. This morning, I wrote bin-search-2, which took
> about ten minutes to write (and about thirty minutes to debug), but I
> understand it thoroughly -- and I am just the merest beginner, barely
> a toe in the water.
>
> I have noticed this about CL in general and in Graham's book in
> particular -- Lispers seem to go to great lengths to make their code
> obtuse, obscurantist, obscure, and difficult to understand. For
> example, in the example below, Why the nested ifs? Why the nested
> lets? I've been reading Miller and Benson 'Lisp: Style and Design' and
> I simply don't understand why tutorials (like ANSI CL -- which I think
> on the whole is a very good book) want to throw up walls to
> understanding. Seems to me that materials targeted toward beginners
> would be written to be clear and understandable.
>
> CC.
>
> ;;; ---------ch_04.lisp-----------------------
> (defparameter v (vector 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
> 35 37 39 41))
>
> (defun bin-search (obj vec)
> (format t "bin-search ~a ~a~%" obj vec)
> (let ((len (length vec)))
> (and (not (zerop len)))
> (finder obj vec 0 (- len 1))))
>
> (defun finder (obj vec start end)
> (format t "finder obj: ~a, vec: ~a, start: ~a, end: ~a~%" obj vec
> start end)
> (format t " ~a~%" (subseq vec start (+ end 1)))
> (let ((range (- end start)))
> (if (zerop range) ; outer if test
> (if (eql obj (aref vec start)) ; inner if test
> obj ; the return obj
> nil) ; else return nil
> (let ((mid (+ start (round (/ range 2))))) ; outer then
> (let ((obj2 (aref vec mid)))
> (if (< obj obj2)
> (finder obj vec start (- mid 1))
> (if (> obj obj2)
> (finder obj vec (+ mid 1) end)
> obj)))))))
>
> (defun bin-search-2 (obj vec &optional (start 0))
> (let*((len (length vec))
> (mid (floor (/ len 2))))
> (format t "bin-search-2 obj: ~a, vec: ~a, start ~a, end: ~a, mid: ~a~
> %" obj vec start len mid)
> (cond ((zerop len) nil)
> ((= obj (svref vec mid)) obj)
> ((< obj (svref vec mid)) (bin-search-2 obj (subseq vec start
> mid)))
> ((> obj (svref vec mid)) (bin-search-2 obj (subseq vec (+ mid
> 1) len))))))
>
> ;; I don't know how to set 'start' to 0 by default, other than by
> making it optional.
> ;; I would appreciate help with this.


You might want to use code like the one from Graham
as 'training' that helps you understanding more
complicated code. A usual way to study those
functions is to trace or step them - and then
study the trace or step log. The FORMAT might
be enough. Sometimes I do the following:
I define a variable, say *trace-data*
and push lists with trace data to that list:
(push (list :finder :vector vec :start start)
*trace-data*)
Later I can inspect or print that list.


A few remarks:

* it might be useful to put LETs precisely at the smallest
possible enclosing form - so that code that needs
the variables have access to them and code that doesn't
need them has no access.

* keeping the vector constant and recursing over
start/end or positions is a common 'pattern'

* subseq is a 'code smell' : wasteful consing

* having a function that provides the public interface
and another function that does the internal
work with possible additional variables
is also a common 'pattern'. Some primitive checks
(like on empty vectors) can be done in the
first functions.

--
http://lispm.dyndns.org/