Style, or lack thereof in Graham's ANSI CL
in [Lisp]
|
Prev: Question from a non-user: Garbage Collection
Next: Loading a file into a running image with Swank
From: ccc31807 on 16 Dec 2009 10:42 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 16 Dec 2009 10:52 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 16 Dec 2009 10:58 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 16 Dec 2009 11:15 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 16 Dec 2009 11:51
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/ |