Style, or lack thereof in Graham's ANSI CL
ccc31807
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.
Zach Beane
> 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
fortunatus
> 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.
Pillsy
> 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
Rainer Joswig
<60400ac0-f2c3-4fa6...@r1g2000vbp.googlegroups.com>,
ccc31807 <cart...@gmail.com> wrote:
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.
Unknown
a = %w(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
35 37 39 41).map{|s| s.to_i}
def bin_search obj, array
len = array.size
len > 0 and finder( obj, array, 0, len.pred )
end
def finder obj, array, first, last
span = last - first
if span.zero?
obj == array[first] ? obj : nil
else
mid = first + (span / 2.0).round
case obj <=> array[mid]
when -1
finder obj, array, first, mid.pred
when 0
obj
when 1
finder obj, array, mid.succ, last
end
end
end
--
Rahul Jain
> I have noticed this about CL in general and in Graham's book in
> particular
Huh? how is that a sensible phrase? Graham is opposed to CL in general.
--
Rahul Jain
rj...@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Paul Donnelly
> ccc31807 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.
>
> a = %w(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
> 35 37 39 41).map{|s| s.to_i}
>
> def bin_search obj, array
> len = array.size
> len > 0 and finder( obj, array, 0, len.pred )
> end
>
> def finder obj, array, first, last
> span = last - first
> if span.zero?
> obj == array[first] ? obj : nil
> else
> mid = first + (span / 2.0).round
> case obj <=> array[mid]
> when -1
> finder obj, array, first, mid.pred
> when 0
> obj
> when 1
> finder obj, array, mid.succ, last
> end
> end
> end
I'm glad we can count on you to remind us how much worse things could
be.
Alain Picard
>
>
> a = %w(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
> 35 37 39 41).map{|s| s.to_i}
>
> def bin_search obj, array
> len = array.size
> len > 0 and finder( obj, array, 0, len.pred )
> end
[SNIP]
I thought this was comp.lang.lisp. Did I stray into
comp.lang.python by mistake? If so, good, I have quite
a few complaints I'd like to get off my chest...
--ap
jos...@lisp.de
Is that Commune Ruby?
http://ruby-std.netlab.jp/
>
> a = %w(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
> 35 37 39 41).map{|s| s.to_i}
wait, in Ruby you can't write a vector of numbers???
Nice!
>
> def bin_search obj, array
> len = array.size
> len > 0 and finder( obj, array, 0, len.pred )
> end
>
> def finder obj, array, first, last
> span = last - first
> if span.zero?
> obj == array[first] ? obj : nil
> else
> mid = first + (span / 2.0).round
Wait, you need floating point division and rounding
to get the middle integer index???
> case obj <=> array[mid]
> when -1
> finder obj, array, first, mid.pred
> when 0
> obj
> when 1
> finder obj, array, mid.succ, last
> end
> end
> end
Why so long?
(defun bin-search (obj vec &aux (las (1- (length vec))))
(labels ((finder (s e &aux (r (- e s)) (mid (+ s (truncate r 2))))
(when (<= 0 s e las)
(let ((m (aref vec mid)))
(cond ((= obj m) obj)
((< obj m) (finder s (1- mid)))
(t (finder (1+ mid) e)))))))
(finder 0 las)))
Look, no floating point calculations.
He, and we can write vectors of numbers.
? (bin-search 25 #(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37
39 41))
25
>
> --
Tamas K Papp
> ccc31807 <cart...@gmail.com> writes:
>
>> I have noticed this about CL in general and in Graham's book in
>> particular
>
> Huh? how is that a sensible phrase? Graham is opposed to CL in general.
Where did you hear that?
Tamas
jos...@lisp.de
From Paul Graham... For example his talk at the ILC in New York a few
years ago was mostly about how much he dislikes CL (the audience loved
that ;-) ).
I guess there was a bit 'rebel' attitude, but he was explaining lots
of language design that was opposed to CL. From long identifiers vs.
short identifiers, no CLOS, ... etc.etc. - think On Lisp applied to
design a language -> Arc.
You can see what kind of code he wants to write when you look at the
arc example source code.
Tamas K Papp
Maybe that's what he says to market Arc to people who don't know
anything about Lisp except that they dislike it for some vague reason
("So you don't like CL? Me neither! That's why I created Arc, which
is so totally different that it would take maybe a whole lunchbreak to
implement as a thin layer on top if CL. We are on the same side!
Come try my new language!").
But he wrote 2 books about CL, which is pretty weird if he hates it.
One can of course argue that he started hating it later on, but that
doesn't compute either: writing even a single book should be enough to
realize that you hate something.
So I still consider it as a pose. And I don't think that CL-bashing
gets him very far: I wouldn't be surprised if the Arc fans ended up
using CL in the long run.
Tamas
Raffael Cavallaro
> Where did you hear that?
straight from the horse's mouth:
"I think we may have made a mistake in thinking that hackers are turned
off by Lisp's strangeness. This comforting illusion may have prevented
us from seeing the real problem with Lisp, or at least Common Lisp,
which is that it sucks for doing what hackers want to do. A hacker's
language needs powerful libraries and something to hack. Common Lisp
has neither. A hacker's language is terse and hackable. Common Lisp is
not.
The good news is, it's not Lisp that sucks, but Common Lisp. If we can
develop a new Lisp that is a real hacker's language, I think hackers
will use it."
from:
"http://www.paulgraham.com/popular.html"
Not that I agree with him about these supposed faults; I don't.
--
Raffael Cavallaro
w_a_x_man
I believe that fans of COBOL-LISP have IQs lower than that
of the average programmer. And they have a mindless, emotional
attachment to it.
Here's what the experts say about Commune Lisp:
"an unwieldy, overweight beast"
"A monstrosity"
"sucks"
"an aberration"
"incomprehensible"
"a nightmare"
"no future"
"a significantly ugly language"
"hacks"
"bad"
In context:
Brooks and Gabriel 1984, "A Critique of Common Lisp":
Every decision of the committee can be locally rationalized
as the right thing. We believe that the sum of these
decisions, however, has produced something greater than its
parts; an unwieldy, overweight beast, with significant costs
(especially on other than micro-codable personal Lisp
engines) in compiler size and speed, in runtime performance,
in programmer overhead needed to produce efficient programs,
and in intellectual overload for a programmer wishing to be
a proficient COMMON LISP programmer.
-----
Bernard Lang:
Common Lisp did kill Lisp. Period. (just languages take a
long time dying ...) It is to Lisp what C++ is to C. A
monstrosity that totally ignores the basics of language
design, simplicity and orthogonality to begin with.
-----
Gilles Kahn:
To this day I have not forgotten that Common Lisp killed
Lisp, and forced us to abandon a perfectly good system,
LeLisp.
-----
Paul Graham, May 2001:
A hacker's language is terse and hackable. Common Lisp is not.
The good news is, it's not Lisp that sucks, but Common Lisp.
Historically, Lisp has been good at letting hackers have their
way. The political correctness of Common Lisp is an aberration.
Early Lisps let you get your hands on everything.
A really good language should be both clean and dirty:
cleanly designed, with a small core of well understood and
highly orthogonal operators, but dirty in the sense that it
lets hackers have their way with it. C is like this. So were
the early Lisps. A real hacker's language will always have a
slightly raffish character.
Organic growth seems to yield better technology and richer
founders than the big bang method. If you look at the
dominant technologies today, you'll find that most of them
grew organically. This pattern doesn't only apply to
companies. You see it in sponsored research too. Multics and
Common Lisp were big-bang projects, and Unix and MacLisp
were organic growth projects.
-----
Jeffrey M. Jacobs:
Common LISP is the PL/I of Lisps. Too big and too
incomprehensible, with no examination of the real world of
software engineering.
... The CL effort resembles a bunch of spoiled children,
each insisting "include my feature or I'll pull out, and
then we'll all go down the tubes". Everybody had vested
interests, both financial and emotional.
CL is a nightmare; it has effectively killed LISP
development in this country. It is not commercially viable
and has virtually no future outside of the traditional
academic/defense/research arena.
-----
Dick Gabriel:
Common Lisp is a significantly ugly language. If Guy and I
had been locked in a room, you can bet it wouldn't have
turned out like that.
-----
Paul Graham:
Do you really think people in 1000 years want to be
constrained by hacks that got put into the foundations of
Common Lisp because a lot of code at Symbolics depended on
it in 1988?
-----
Daniel Weinreb, 24 Feb 2003:
Having separate "value cells" and "function cells" (to use
the "street language" way of saying it) was one of the most
unfortuanate issues. We did not want to break pre-existing
programs that had a global variable named "foo" and a global
function named "foo" that were distinct. We at Symbolics
were forced to insist on this, in the face of everyone's
knowing that it was not what we would have done absent
compatibility constraints. It's hard for me to remember all
the specific things like this, but if we had had fewer
compatibility issues, I think it would have come out looking
more like Scheme in general.
-----
Daniel Weinreb, 28 Feb 2003:
Lisp2 means that all kinds of language primitives have to
exist in two versions, or be parameterizable as to whether
they are talking about the value cell or function cell. It
makes the language bigger, and that's bad in and of itself.
-----
Guy L. Steele, Jr., July 1989:
I think we may usefully compare the approximate number of pages
in the defining standard or draft standard for several
programming languages:
Common Lisp 1000 or more
COBOL 810
ATLAS 790
Fortran 77 430
PL/I 420
BASIC 360
ADA 340
Fortran 8x 300
C 220
Pascal 120
DIBOL 90
Scheme 50
Kenneth Tilton
Nice compendium!
I had to laugh at the idea of good languages coming out of Steele and
one other person locked in a room since that is exactly where Java came
from. All the death notices are nice but CL seems to have outlived them,
no deader than usual. It is great fun to see Lisp Gods completely wrong
about Lisp, like Weinreb preferring Scheme and all the folks lamenting
CL's size when I think the only thing I have never used is series.
In the meantime we have jokes like Python and Ruby aspiring to CL's
power (at runtime and while programming) while copying badly as many
features as they can, cocking them all up along the way. Imitation,
flattery, and all that.
Thx for the quotes, and keep 'em coming. You might find some gems here:
http://wiki.alu.org/RtL%20Highlight%20Film
kt
--
http://thelaughingstockatpngs.com/
http://www.facebook.com/pages/The-Laughingstock/115923141782?ref=nf
Pascal J. Bourguignon
> On 16 Dez., 22:12, "William James" <> wrote:
>> a = %w(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
>> � � � �35 37 39 41).map{|s| s.to_i}
>
> wait, in Ruby you can't write a vector of numbers???
> Nice!
You can. But you cannot expect William to know how to.
Besides, it's harder to write vectors of numbers in Ruby than in Lisp,
you have to use brackets with sharp corners instead of the smooth
parenthesis, and to spread it with a lot of thorny commas.
Passing thru such a string allows him to get closer to lisp syntax, to
the price of Greenspunning some parsing.
--
__Pascal Bourguignon__
Rahul Jain
> But he wrote 2 books about CL, which is pretty weird if he hates it.
> One can of course argue that he started hating it later on, but that
> doesn't compute either: writing even a single book should be enough to
> realize that you hate something.
He never liked it. You can tell clearly from what he chooses to ignore.
He didn't write books about CL. He wrote books about Arc, and then
realized what he was writing about. :)
Barry Margolin
<404e1698-289b-441e...@a21g2000yqc.googlegroups.com>,
w_a_x_man <w_a_...@yahoo.com> wrote:
> Guy L. Steele, Jr., July 1989:
>
> I think we may usefully compare the approximate number of pages
> in the defining standard or draft standard for several
> programming languages:
>
> Common Lisp 1000 or more
> COBOL 810
> ATLAS 790
> Fortran 77 430
> PL/I 420
> BASIC 360
> ADA 340
> Fortran 8x 300
> C 220
> Pascal 120
> DIBOL 90
> Scheme 50
This is a little unfair, because the Common Lisp base language includes
lots of things that would be in libraries in most other languages, e.g.
hash tables, sequences, association lists, and portable pathnames. In
fact, even types that are basic primitives in Lisp, such as linked
lists, imaginary numbers, and symbols, would generally be in libraries
in traditional languages.
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Kenneth Tilton
Indeed, and since all that functionality is Way Useful(tm) what moron
Schemers do not realize is that the arrow points in the other direction:
less is less. The Commune Lisper (why didn't we think of that name?!!)
has 20x standardized and reliable no matter what library we use. The
Schemer? Oh, 50 pages of primitives. Anything a library delivers using
anything outside that snippet is implementation-dependent.
Nice work, Guys! Super puristic and educational!! 50pp!!! Woohoo! Take a
bow!!
Pascal Costanza
I think there is a change in perspective now. Younger generations
nowadays consider that these things should be part of a language, and
that Common Lisp is actually too small and should have even more.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
George Neuner
wrote:
>On 18/12/2009 03:51, Barry Margolin wrote:
>
>> This is a little unfair, because the Common Lisp base language includes
>> lots of things that would be in libraries in most other languages, e.g.
>> hash tables, sequences, association lists, and portable pathnames. In
>> fact, even types that are basic primitives in Lisp, such as linked
>> lists, imaginary numbers, and symbols, would generally be in libraries
>> in traditional languages.
>
>I think there is a change in perspective now. Younger generations
>nowadays consider that these things should be part of a language, and
>that Common Lisp is actually too small and should have even more.
I find many members of the "younger generations" to be unacceptably
ignorant in too many areas. IMO, much of what they "consider" is not
worth the concern of a reasonable person. Now, if politicians were
reasonable ...
I don't have any problem with proscribed standard libraries. I do
have a problem with people who should know better deliberately
pandering to ignorance by conflating the notions of language and
library. (I'm not saying you are doing so, btw, but only that the
practice is widespread and annoys me whenever I encounter it).
George
Barry Margolin
Kenneth Tilton <kent...@gmail.com> wrote:
I always remember the days when I dabbled in Prolog. It seemed like
every Prolog program started with its own definition of member(), or
some other simple function like this. Sure, it's only 2 or 3 lines,
just a trivial copy-and-paste, but I always felt that there was
something wrong if every programmer had to do this. It would be like if
Lisp programmers had to write their own LIST, using CONS, instead of
having it as a built-in.
Thierry Pirot
> 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.
[...]
> ;;; ---------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))))
>
The parentheses in that copy of bin-search are wrong.
Is this genuinely Graham's ? I don't own the book to check.
> (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)))))))
>
I doubt that such a code might be understandable or correct ;
indeed it is not : just evaluate (bin-search 0 #(1 2)) and blow the stack.
What is the origin of this bug and the way to correct it ?
The bug is about fiddling with indices and splitting their range.
Other posts in this thread have emphasised
the advantage to separate functionalities amongst functions.
finder is a step in that direction, however it still dangerously mixes
the job of finding with the job of dichotomy,
which can be handled in the following quick and dirty protocol
to deal with ranges --- as conses --- and their splitting.
(defun range (start end) ;end inclusive
(if (<= start end)
(cons start end)
(error "Invalid range ~s ~s. " start end)))
(defmethod range_of ((v vector))
(unless (equalp #() v) (range 0 (1- (length v)))))
(defun range_len (range)
(if range (1+ (- (cdr range) (car range))) 0))
(defun range_mid (range)
(when (and range (< (car range) (cdr range)))
(+ (car range) (floor (range_len range) 2))))
(defmethod range_splits (range)
"The cons of two complementary 'even' subranges of the range range. "
(let ((mid (range_mid range)))
(when mid ;is_splittable
(cons (range (car range) (1- mid))
(range mid (cdr range))))))
Now, one should wonder about this protocol,
is it reliable --- anyway it is easy to unit-test ---,
is it handy --- more than start and end parameters --- to use ?
Let's see,
(defun bin-search (obj vec)
(format t "bin-search' ~a ~a~%" obj vec)
(unless (equalp #() vec)
(labels ((finder (range)
(format t "range:~a~%" range)
(format t " ~a~%" (subseq vec (car range) (1+ (cdr range))))
(let ((splits (range_splits range)))
(if splits
(if (< obj (aref vec (cadr splits)))
(finder (car splits))
(finder (cdr splits)))
(when (= obj (aref vec (car range))) obj)))))
(finder (range_of vec)))))
The original finder was rather self contained and used a lot of variables,
now it involves a lot of functions,
although it's essentially only range_splits.
It also performs a slightly different algorithm [1], using no pivot :
if the range is splittable
then search in the appropriate split,
else --- the range stands for a singleton ---
check if the element of the singleton is the searched 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 simply don't need it, it is always 0.
So your function can be written like
(defun bin-search (obj vec &key (cmp #'cmp))
(format t "bin-search''' obj: ~a vec: ~a ~%" obj vec)
(let* ((len (length vec))
(mid (floor len 2)))
(when (/= 0 len)
(case (funcall cmp obj (aref vec mid))
(0 obj)
(-1 (bin-search obj (subseq vec 0 mid)))
(+1 (bin-search obj (subseq vec (1+ mid))))))))
where I added
(defgeneric cmp (x y)
(:documentation "+1, 0, -1 according to x being after, with, before y. "))
(defmethod cmp ((x integer) (y integer)) (signum (- x y)))
To cope with the problem of the consing of subseq, maybe using
(defun subvec (a_vector start &optional (end (length a_vector)))
(make-array (- end start)
:displaced-to a_vector
:displaced-index-offset start
:element-type (array-element-type a_vector)))
instead of subseq can help, but I know little about displaced arrays
and a quick profiling shows only slight differences in Clisp.
I guess it should be different for bitvectors or vectors or big elements.
I hope someone will clear this.
[1] This algorithm exhibits a nice pattern, for processing by dichotomy,
that can be translated, without further explanations, as
(defun spliterator (rektor f_atom &optional (splitter #'split))
(labels ((f (x)
(let ((splits (funcall splitter x)))
(if splits
(funcall rektor (f (car splits)) (f (cdr splits)) splits)
(funcall f_atom x)))))
#'f))
(defun bin-search (obj vec)
(unless (equalp #() vec)
(funcall
(spliterator
(lambda (x y splits) (if (< obj (aref vec (cadr splits))) x y))
(lambda (x) (when (= obj (aref vec (car x))) obj))
'range_splits)
(range_of vec))))
--
Take it Easy Don't Hurry Be Happy
Thierry
((LAMBDA (LAMBDA) `(,LAMBDA ',LAMBDA)) '(LAMBDA (LAMBDA) `(,LAMBDA ',LAMBDA)))
W. James
v = 1.step(41,2).to_a
def bin_search obj, array
len = array.size
len > 0 and finder( obj, array, 0 ... len )
end
def split_range range
first, last = range.min, range.max
mid = first + ((last - first) / 2.0).round
[(first .. [first,mid.pred].max), mid, ([mid.succ,last].min .. last)]
end
def finder obj, array, range
return (obj == array[range.first] ? obj : nil) if range.one?
left, mid, right = split_range range
case obj <=> array[mid]
when -1
finder obj, array, left
when 0
obj
when 1
finder obj, array, right
end
end
--
W. James
> def bin_search obj, array
> len = array.size
> len > 0 and finder( obj, array, 0 ... len )
> end
>
> def split_range range
> first, last = range.min, range.max
> mid = first + ((last - first) / 2.0).round
> [(first .. [first,mid.pred].max), mid, ([mid.succ,last].min ..
> last)] end
Faster:
def bin_search obj, array
len = array.size
len > 0 and finder( obj, array, 0 .. len.pred )
end
def split_range range
first, last = range.first, range.last
mid = first + ((last - first) / 2.0).round
[(first .. [first,mid.pred].max), mid, ([mid.succ,last].min .. last)]
end
--
Paul Donnelly
Kenneth Tilton
I always got a kick out of the two-page implementation of something that
was 2 or 3 lines in a language that could stomach something other than
logic programming.
> just a trivial copy-and-paste, but I always felt that there was
> something wrong if every programmer had to do this. It would be like if
> Lisp programmers had to write their own LIST, using CONS, instead of
> having it as a built-in.
>
LIST? I missed that! It's a big language, hard to know it all.
gavino
> 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.
>
> 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.
>
> (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))))
>
> (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)))))))
>
> (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.
amen brother I find reading my copy is ansi common lips is liek
drinking a pan galatic gargle blaster!
Chris Barts
Which is why we have Clojure (for which there is another little troll in
this very group), which brings all of Java into Lisp without actually
making Lispers write in Java. The fundamental problem with that is it
doesn't bring in any well-designed class libraries along with it.
Pascal Costanza
Unfortunately it brings a little bit too much Java into Lisp, for my
taste...
W. James
Bigloo Scheme:
(module binsearch)
(define *vec* (list->vector (iota 21 1 2)))
(define (finder num vec start end)
(if (= start end)
(and (= num (vector-ref vec end)) num)
(let* [ (mid (flonum->fixnum (/ (+ start end) 2.0)))
(found (vector-ref vec mid)) ]
(if (= found num)
num
(if (< num found)
(finder num vec start (max start (- mid 1)))
(finder num vec (+ mid 1) end))))))
(define (bin-search num vec)
(let [ (len (vector-length vec)) ]
(and (> len 0)
(finder num vec 0 (- len 1)))))
--
jos...@lisp.de
This looks even relevant to the newsgroup. I'm surprised
by your progress.
> (module binsearch)
>
> (define *vec* (list->vector (iota 21 1 2)))
>
> (define (finder num vec start end)
> (if (= start end)
> (and (= num (vector-ref vec end)) num)
> (let* [ (mid (flonum->fixnum (/ (+ start end) 2.0)))
Still no integer division?
game_designer
> On page 61 of Graham's ANSI Common Lisp, he defines bin-search and
> finder, which I have copied below.
>
>
> 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
Graham writes nice essays which have helped Lisp a lot. I am thankful
for that. The reference flavor aspect of ANSI Common Lisp is quite OK
but for people writing modern applications especially when including
OOP this is a book that needs to be avoided. It is not clear if Graham
only hates object oriented programming - there is quite some evidence
for that elsewhere - or actually does not understand it. In the end it
does not matter. Common Lisp has a very powerful object system (CLOS).
If you are planing to write a modern application making use of OO and
are not just planning to walk down memory lane then look elsewhere.
Alexander Repenning, University of Colorado
ccc31807
> Graham writes nice essays which have helped Lisp a lot. I am thankful
> for that. The reference flavor aspect of ANSI Common Lisp is quite OK
> but for people writing modern applications especially when including
> OOP this is a book that needs to be avoided. It is not clear if Graham
> only hates object oriented programming - there is quite some evidence
> for that elsewhere - or actually does not understand it. In the end it
> does not matter. Common Lisp has a very powerful object system (CLOS).
> If you are planing to write a modern application making use of OO and
> are not just planning to walk down memory lane then look elsewhere.
Thank you for your helpful remarks. Two points:
(1) There's no such thing as a perfect student, and there's no such
thing as a perfect text -- sometimes I think that the match between
the student and the text is simply a matter of sheer, dumb luck.
Graham's book is strong in many ways, for example I like the way he
serves up 'real' programs from the very beginning, and it's probably
essential for the development of a mature Lisper, but it's certainly
not good for the beginner. For my money, Wilensky and Winston & Horn
are probably the best in that regard.
(2) I received Norvig's 'Paradigms' for Christmas, and have read
through the first three chapters. I've now read about 100 pages each
of Graham and Norvig, comparing them. Each adds much, but I suspect
that Norvig will have a lot more staying power than Graham.
CC.
Rahul Jain
> Unfortunately it [Clojure] brings a little bit too much Java into Lisp, for my
> taste...
And a bit too much scheme for most of my existing code to be portable to it.
gavino
> Barry Margolin wrote:
> > In article
so common lisp includes so much that the avg new user would have 100
times what she needs to get the job done.
Where scheme has basic and then one must hope the scheme RFI cover
what you want.
This begs the question: are the lisp functionalities modern or perhaps
old? or does common lisp evolve the standard to meet new fast/better
techniques as they appear?
gavino
AWESOME
GOOD SHOW!
hardcore!
gavino
gavino
> On 27/12/2009 13:30, Chris Barts wrote:
>
>
>
> > Pascal Costanza<p...@p-cos.net> writes:
>
> >> On 18/12/2009 03:51, Barry Margolin wrote:
> >>> In article
I am with pascal.
Please no java!
gavino
Also keep in mind Paul Graham is a lisper who sold his Lisp company
for ~us$50,000,000 to yahoo.
I am not sure CLOS using company did.
http://harmful.cat-v.org/software/OO_programming/
gavino
I was told incidentally that lamkins successful lisp and gentro intro
by touretsky are great for the beginner. I own the Winston/horn book
and found it not much better than graham in that he starts to go into
global vs local assignments before simply stating what set and setf
etc are and how they differ so you are trying to absorb bot at once.
I wish the book would simply define it terms. Then what they main
concept groupss are, and then code some examples.
tryign to absorb 2 or even 3 to 4 sets of things at same time with
them being separated out can lead to student [eg me I can't speak for
all] getting prehaps a wrong idea about 1 of the concepts. Then the
following chapter builds on the before so confusion gets worse. Math
book are suprisingly good at giving the concepts layed out before
going into execution.
WJ
> 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.
Clojure:
(def v (vector 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
35 37 39 41))
(defn _bin-search_ [obj coll start end]
(if (= start end)
(if (= obj (nth coll start)) obj nil)
(let [mid (int (/ (+ start end) 2))
val (nth coll mid) ]
(if (= obj val)
obj
(if (< obj val)
(_bin-search_ obj coll start (max (dec mid) start))
(_bin-search_ obj coll (inc mid) end))))))
(defn bin-search [obj coll]
(let [length (count coll)]
(and (not= 0 length)
(_bin-search_ obj coll 0 (dec length)))))
Marco Antoniotti
In Common Lisp
(find obj coll)
Cheers
--
MA