From: Martin Pomije
Subject: I would appreciate a code review
Date: 
Message-ID: <90ac4ec2.0311061901.658716ba@posting.google.com>
I've dabbled with Lisp before, and I've worked my way through most of
S&ICP, but I have decided to try a more systematic approach by working
through Paul Graham's ANSI Common Lisp book.

This is my code followed by my test cases for Exercise 3 on p. 56 of
that book.

<QOUTE>
Define a function that takes a list and returns a list indicating the
number of times each (eql) element appears, sorted from most common
element to least common.

>(occurences '(a b a d a c d c a))
((A . 4) (C . 2) (D . 2) (B . 1))
</QUOTE>

;;;; Ex. 3
;;; Takes a list of items and returns ab association list that
indicates how
;;; many times each item occured, sorted with the maximum count at the
;;; head of the association list. 
(defun occurences (list)
  (if (consp list)
    (build-occurences () list)
    nil))

;;;Steps through each item of the list and updates the alist
;;;with that item.
(defun build-occurences (alist list)
  (if (null list)
    alist  ; processed all items in list, so we're done.
    (build-occurences (update-count-alist (car list) alist) (cdr
list))))

;;; Updates the alist with the with respect to the symbol.
(defun update-count-alist (symbol alist)
  (let ((first (car alist)))
    (if (null first)
      (list (cons symbol 1)) 
      (if (eql (car first) symbol)
        ;; the first item is a match
        (cons (cons symbol (+ (cdr first) 1)) 
              (cdr alist))
        ;; first item is not a match and alist has at least one record
        (scan-count-alist symbol alist)))))


;;; Steps through alist to update symbol assoc record.
;;; Assumes that the first item of the alist does not match symbol. 
;;; Assumes alist has at least 1 assoc record.
(defun scan-count-alist (symbol alist)
  (do* ((scan-position alist (cdr scan-position))
        (second (cadr scan-position) (cadr scan-position)))
       ((null second) ; scanned through alist, no occurences of item
found
        (progn
          (setf (cdr scan-position) (cons (cons symbol 1) nil)) ; add
record to the end
          alist))
    (if (eql (car second) symbol)
      (progn
        ;; delete old record for symbol
        (setf (cdr scan-position) (cddr scan-position))
        ;; insert updated record for symbol
        (return 
         ;; alist should have at least 1 record because of the do*
exit test
         (insert-count-alist (+ (cdr second) 1) symbol alist))))))

;;; Updates alist by inserting an assoc record for symbol.
;;; Assumes alist has at least 1 item.
(defun insert-count-alist (count symbol alist)
  (if (>= count (cdar alist))
    (cons (cons symbol count) alist)
    (do* ((scan-point alist (cdr scan-point))
          (insertion-point (cdr scan-point) (cdr scan-point)))
         ((null insertion-point) ; assoc record needs to go at the end
of the list
          (progn 
            (setf (cdr scan-point) (cons (cons symbol count) nil))
            alist))
      (if (>= count (cdar insertion-point)) 
        (progn 
          (setf (cdr scan-point) 
                (cons (cons symbol count) insertion-point))
          (return alist))))))



#|
? (Occurences  (list 'A 'b 'C 'A 'B 'C 'D 'E 'F 'F 'F 'F 'F 'F 'e 'd
'a 'd 'd))
((F . 6) (D . 4) (A . 3) (E . 2) (C . 2) (B . 2))
? (occurences '(a b a d a c d c a))
((A . 4) (C . 2) (D . 2) (B . 1))
? (occurences '(a b c))
((A . 1) (B . 1) (C . 1))
? (occurences '(a b c a b c))
((C . 2) (B . 2) (A . 2))
? (occurences '(a b c a b c c c))
((C . 4) (B . 2) (A . 2))
? (occurences '(a b c a b c d d d d))
((D . 4) (C . 2) (B . 2) (A . 2))
? (occurences '(a b c a b c d e e e e e e))
((E . 6) (C . 2) (B . 2) (A . 2) (D . 1))
? (occurences '(a b c a b c d e f f f f f f))
((F . 6) (C . 2) (B . 2) (A . 2) (D . 1) (E . 1))
? (Occurences '(A B C A B C D E F F F F F F E))
((F . 6) (E . 2) (C . 2) (B . 2) (A . 2) (D . 1))
?
|#

I tried to stick with only the Common Lisp functionality that had been
presented at that point in the book.  (I cheated a bit by using do*
and return.)  I realize that a really professional solution would
probably use a hash table.

I'm pretty confident in my solution, so I'm largely looking for coding
style suggestions.  When I was coding this I couldn't think of a
purely functional solution that wouldn't generate a lot of garbage. 
Is this right?
My understanding is that imperative programming is looked on more
favorably in the CL community than in the Scheme community, so I
thought that my solution would be OK.  My solution seems to be a lot
more complicated than I thought it would be.   Does my code look
clean?
My code still generates some garbage.  If someone goes through the
hassle of creating an imperative solution like this, should they try
to eliminate the garbage collection?

From: Conrad Barski
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <a4af10cf.0311062238.7971bf3e@posting.google.com>
(BTW these next few remarks are just my personal, wacko preferences-
I'm not saying they're any better than any other solutions...)

first, here's what I would write for a slow-but-simple solution (but
it may use things in later PG chapters...)

(defun occurences (lst)
   (sort (mapcar (lambda (x)
             (cons x (count x lst)))
         (remove-duplicates lst))
         #'> 
         :key #'cdr)

(and if I used my own quirky library functions)

(defun occurences (lst)
   (sort (mapcarx (c x (count x lst)) (remdup lst) #'> :key #'d))

I see you like to do error checking (consp list), but I prefer my
errors to be "noisy" and not hidden, which CL will do for you anyway
in this case. If you do check for this, I would throw an error instead
or returning a silent nil.

I really like FP and would use it in this case, unless performance
were really critical. Then a hash table would be my choice, as you
suggested.

"if (null list)" I would flip the followup blocks and write as "if
list" instead.

nested "if" often look less clear than a "cond" to handle all cases.
This also gets rid of progns.

In Lisp, more so than most other languages, breaking duplicate
statements into local funtions or variables greatly improves
readability, such as your statement "(cdr scan-point)" that appears
numerous times.

On the other hand, I'm not a big fan of having so many small global
functions, though- Unless you can really reuse them elsewhere- In your
case they're pretty specific and might not be amenable to that.

So more local funs/vars, less globals.

I would really recommend learning a pure functional language like
Haskell as well, to break imperative habits. That's the only thing
that ever made me comfortable with FP.
From: Kent M Pitman
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <wku15gfz7g.fsf@nhplace.com>
······@MartinPomije.eiomail.com (Martin Pomije) writes:

> I've dabbled with Lisp before, and I've worked my way through most of
> S&ICP, but I have decided to try a more systematic approach by working
> through Paul Graham's ANSI Common Lisp book.
> 
> This is my code followed by my test cases for Exercise 3 on p. 56 of
> that book.
> 
> <QOUTE>
> Define a function that takes a list and returns a list indicating the
> number of times each (eql) element appears, sorted from most common
> element to least common.
> 
> >(occurences '(a b a d a c d c a))
> ((A . 4) (C . 2) (D . 2) (B . 1))
> </QUOTE>

Your code looks a little long and does a lot of raw consing for which
there are packaged operators to do this in a more refined way.

> 
> ;;;; Ex. 3
> ;;; Takes a list of items and returns ab association list that
> indicates how
> ;;; many times each item occured, sorted with the maximum count at the
> ;;; head of the association list. 
> (defun occurences (list)
>   (if (consp list)
>     (build-occurences () list)
>     nil))
> 
> ;;;Steps through each item of the list and updates the alist
> ;;;with that item.
> (defun build-occurences (alist list)
>   (if (null list)
>     alist  ; processed all items in list, so we're done.
>     (build-occurences (update-count-alist (car list) alist) (cdr
> list))))

Doing this recursively means that you'll blow out of stack 
if the list is too long.  I recommend learning some iteration tools.
Common Lisp, unlike Scheme, does not treat tail calls as something
for which there is no stack penalty.

I'll correct this individual function here, though at the end of this
message you'll see I wouldn't even bother with this function at all.

 (defun build-occurrences (list)
   (do ((list list (cdr list))
        (alist '() (update-count-alist (car list) alist)))
       ((not list) alist)))

Note also that this means you don't have to pass a stray NIL for no
other purpose than to initialize a variable that should have been 
internal to your function.

(And note that occurrences has two R's in it.)

> ;;; Updates the alist with the with respect to the symbol.
> (defun update-count-alist (symbol alist)
>   (let ((first (car alist)))
>     (if (null first)
>       (list (cons symbol 1)) 
>       (if (eql (car first) symbol)
>         ;; the first item is a match
>         (cons (cons symbol (+ (cdr first) 1)) 
>               (cdr alist))
>         ;; first item is not a match and alist has at least one record
>         (scan-count-alist symbol alist)))))

This breaks your algorithm across two functions in a way that makes
it fragile.  It's common to do stuff like this as a novice programmer,
but as you become more practiced you'll find ways to organize your data
structures so that you don't need to do this.

The primary technique applicable here is to write something that
returns an appropriate value that you can set back into the cell,
whether or not a side-effect has occurred.  You have instead separated
things into a function that definitely does not side-effect and one
that definitely does, but that's unnecessary.

Just as an example, if you'd done this, you'd have it all in one
function:

 (defun update-count-alist (symbol alist)
   (dolist (entry alist)
     (when (eql (car entry) symbol)
       (incf (cdr entry))
       (return-from update-count-alist alist)))
   ;; If we got here, we have failed to find an entry
   (acons symbol 1 alist))

But there are still simpler ways to do all of this.  Keep reading.

> ;;; Steps through alist to update symbol assoc record.
> ;;; Assumes that the first item of the alist does not match symbol. 
> ;;; Assumes alist has at least 1 assoc record.
> (defun scan-count-alist (symbol alist)
>   (do* 

Style note: Avoid DO* if you can. It's tricky to move back and forth between
DO and DO*, and, frankly, I've never found a need for DO*.  

The useful one of the two is DO because DO can be directly transliterated
to tail call procedures like Scheme programmers write.  DO* has no such
useful property.

>        ((scan-position alist (cdr scan-position))
>         (second (cadr scan-position) (cadr scan-position)))
>        ((null second) ; scanned through alist, no occurences of item
> found
>         (progn

You don't need a PROGN here.  An implicit PROGN is already in effect.

>           (setf (cdr scan-position) (cons (cons symbol 1) nil)) ; add
> record to the end

Use push here.

(push (cons symbol 1) (cdr scan-position))

>           alist))
>     (if (eql (car second) symbol)
>       (progn
>         ;; delete old record for symbol
>         (setf (cdr scan-position) (cddr scan-position))

No, no, no. Don't be deleting records once you've made them.
You can do the sorting later more straightforwardly.  Don't
try to microoptimize by interleaving these two actions.  It
will only make your code impossibly hairy.

>         ;; insert updated record for symbol
>         (return 
>          ;; alist should have at least 1 record because of the do*
> exit test
>          (insert-count-alist (+ (cdr second) 1) symbol alist))))))
> 
> ;;; Updates alist by inserting an assoc record for symbol.
> ;;; Assumes alist has at least 1 item.
> (defun insert-count-alist (count symbol alist)
>   (if (>= count (cdar alist))

I never use C...R functions that aren't either CAAR (which I use only
for alists) or CA{D*}R (which selects an nth element).  Any time you
see a D before an A in C...R, you're probably violating multiple data
abstractions at once.  In this case, you are both selecting an alist
entry and accessing the alist entry in a single action.  I find this
too hard to read.

>     (cons (cons symbol count) alist)

You can use ACONS here, btw.

>     (do* ((scan-point alist (cdr scan-point))

(DO* again.)

>           (insertion-point (cdr scan-point) (cdr scan-point)))
>          ((null insertion-point) ; assoc record needs to go at the end
> of the list
>           (progn 

You don't need PROGN here.  There is an implicit progn already in effect.

>             (setf (cdr scan-point) (cons (cons symbol count) nil))
>             alist))
>       (if (>= count (cdar insertion-point)) 

CDAR.

>         (progn 
>           (setf (cdr scan-point) 
>                 (cons (cons symbol count) insertion-point))

Because of how you've done things, you can't use PUSH here.
But you should rewrite it so that you can.  This business with
scan points and insertion points largely shouldn't need to come up
since you shouldn't ever be removing elements (IMO).  [That relies
on your agreeing with me that it's ok to sort afterward, of course.]

>           (return alist))))))
> 
> 
> 
> #|
> ? (Occurences  (list 'A 'b 'C 'A 'B 'C 'D 'E 'F 'F 'F 'F 'F 'F 'e 'd
> 'a 'd 'd))
> ((F . 6) (D . 4) (A . 3) (E . 2) (C . 2) (B . 2))
> ? (occurences '(a b a d a c d c a))
> ((A . 4) (C . 2) (D . 2) (B . 1))
> ? (occurences '(a b c))
> ((A . 1) (B . 1) (C . 1))
> ? (occurences '(a b c a b c))
> ((C . 2) (B . 2) (A . 2))
> ? (occurences '(a b c a b c c c))
> ((C . 4) (B . 2) (A . 2))
> ? (occurences '(a b c a b c d d d d))
> ((D . 4) (C . 2) (B . 2) (A . 2))
> ? (occurences '(a b c a b c d e e e e e e))
> ((E . 6) (C . 2) (B . 2) (A . 2) (D . 1))
> ? (occurences '(a b c a b c d e f f f f f f))
> ((F . 6) (C . 2) (B . 2) (A . 2) (D . 1) (E . 1))
> ? (Occurences '(A B C A B C D E F F F F F F E))
> ((F . 6) (E . 2) (C . 2) (B . 2) (A . 2) (D . 1))
> ?
> |#
> 
> I tried to stick with only the Common Lisp functionality that had been
> presented at that point in the book.

I didn't constrain my remarks this way.  My problem is that I don't think
people should teach people to program wrong unless they have a serious
commitment to retraining people later when they are going to have the
full set of operations available.  They should pick examples that naturally
cause you to use operators correctly, not examples that cause you to abuse
operators and only later to realize you should have used something else
when you finally get there...  Those operators you've gotten to so far
ARE useful for things, and they should be giving you homework that 
exemplifies intended uses.

> (I cheated a bit by using do*
> and return.)

I'm glad no one has been pushing DO*.

> I realize that a really professional solution would
> probably use a hash table.

Not necessarily, though it's possible.  It really depends on how long
you expect the list to be.  If the data is of the length you're showing,
a hash table's natural hash key overhead is perhaps such that you don't
lose anything by doing a linear search since the constant factors in that
are probably smaller. 
 
> I'm pretty confident in my solution, so I'm largely looking for coding
> style suggestions.  When I was coding this I couldn't think of a
> purely functional solution that wouldn't generate a lot of garbage. 
> Is this right?

Get out of the mode of caring about purely functional solutions.
Common Lisp allows you to program in pure functional style if that's
your personal passion, but it doesn't intend that you do that.
Most of the operators are designed to give you much more efficient
code if you don't.  Industrial strength programming is not about
pure functional programming.

> My understanding is that imperative programming is looked on more
> favorably in the CL community than in the Scheme community,

Absolutely.

> so I
> thought that my solution would be OK.

Well, it has issues for other reasons I've cited here.  I hope it
gives you some useful things to think about.

> My solution seems to be a lot
> more complicated than I thought it would be.   Does my code look
> clean?

That's the wrong question.  It looks long and cluttered.  That's ok
for where you are in the learning process--don't feel I'm beating up on
you.  But you asked for code review, and I might as well not pull punches.
I wouldn't accept this in a commercial setting.  I'd send you back and
tell you to wholly rewrite it.  This is a small problem and a solution
should be one that you can glance easily at and tell what's going on.

One cue, btw, that you have a problem is that your function names are
relatively meaningless (except at the micro level of how you implemented
things). They will not mean anything to someone who just understands the
overall problem and will not allow someone's conceptual structure to say
"ah, that's the obvious breakdown".

> My code still generates some garbage.  If someone goes through the
> hassle of creating an imperative solution like this, should they try
> to eliminate the garbage collection?

Generally don't worry about that.  Mostly that's what the GC is for.  
You can tune your programs later if it turns out to matter.

HOWEVER, in this case I'd say you are generating gratuitous garbage
not because you're generating it at all, but because it's just wasteful
to cons things up and then throw them away when it doesn't serve your
end result.  (If it did, I'd say "fine".)  If you look at my solution 
below, you'll see that a natural solution doesn't discard cons cells
needlessly...

As an aside, this is how I'd have solved the problem:

(defun occurrences (list &key (test #'eql)) ;#1
  (let ((alist '()))
    (dolist (item list)
      (incf (cdr (or (assoc item alist :test test)
                     (let ((entry (cons item 0)))
                        (push entry alist)
                        entry)))))
    (sort alist #'> :key #'cdr)))

Note that this solution lets you do 
 (occurrences '(a b a d a c d c a))
but also
 (occurrences '(a b a d "a" c d c a) :test #'string-equal)

You could also do it with a hash table, but note that the test
is more restricted  since there are only a few kinds of hash tables.

(defun occurrences (list &key (test #'eql)) ;#2
  (let ((table (make-hash-table :test test)))
    (dolist (item list) (incf (gethash item table 0)))
    (let ((alist '()))
      (maphash #'(lambda (key val) (push (cons key val) alist))
               table)
      (sort alist #'> :key #'cdr))))

I don't usually use MERGE, but I think you could use it here by
doing this, which avoids the call to SORT after, but I'm not sure
to what end...

(defun occurrences (list &key (test #'eql)) ;#3
  (let ((table (make-hash-table :test test)))
    (dolist (item list) (incf (gethash item table 0)))
    (let ((alist '()))
      (maphash #'(lambda (key val)
                   (setq alist (merge 'list
                                      (list (cons key val))
                                      alist
                                      #'>
                                      :key #'cdr)))
               table)
      alist)))

Personally, I'd use my definition #1 unless the data sets were
going to be very large, and then I'd use #2.
From: Jock Cooper
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <m3y8usxbf7.fsf@jcooper02.sagepub.com>
Kent M Pitman <······@nhplace.com> writes:
> Style note: Avoid DO* if you can. It's tricky to move back and forth between
> DO and DO*, and, frankly, I've never found a need for DO*.  
>

I don't use DO* when DO will do, but I have found uses for DO*.  However I 
just did a survey of my code and most of my use of DO* is something like
(DO* ((somecdr somelist (cdr somecdr))
      (someitem (car somecdr) (car somecdr))
       ... etc...))

which I suppose is poor style.  But how about something like this?:

(do* ((top (1- (length the-array)))
      (bottom 0)
      (middle #1=(truncate (/ (+ top bottom) 2)) #1#)
      (row #2=(funcall key-fun (aref the-array middle)) #2#)
      (eq-p #3=(funcall eq-fun look-for row) #3#)
     ((or eq-p (> bottom top))
       (if eq-p (values middle nil) (values nil top)))
   (if (funcall less-fun look-for row)
       (setq top (1- middle))
       (setq bottom (1+ middle))))))

Of course this could be coded any number of ways, but is there a 
good reason why I *shouldn't* use DO* here?

> The useful one of the two is DO because DO can be directly transliterated
> to tail call procedures like Scheme programmers write.  DO* has no such
> useful property.

Can you elaborate on this last part?
From: Sashank Varma
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <none-A74638.12171009112003@news.vanderbilt.edu>
In article <··············@jcooper02.sagepub.com>,
 Jock Cooper <·····@mail.com> wrote:

> I don't use DO* when DO will do, but I have found uses for DO*.  However I 
> just did a survey of my code and most of my use of DO* is something like
> (DO* ((somecdr somelist (cdr somecdr))
>       (someitem (car somecdr) (car somecdr))
>        ... etc...))
> 
> which I suppose is poor style.  But how about something like this?:

[Sheepishly]  I do this too.  While it's not the prettiest code
in the world, why do you consider it to be poort style?

(Is should add that I don't LOOP, so perhaps you're alluding to
a feature of this macro that makes such loops trivial to write.)
From: Jock Cooper
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <m365hq3kag.fsf@jcooper02.sagepub.com>
Sashank Varma <····@vanderbilt.edu> writes:

> In article <··············@jcooper02.sagepub.com>,
>  Jock Cooper <·····@mail.com> wrote:
> 
> > I don't use DO* when DO will do, but I have found uses for DO*.  However I 
> > just did a survey of my code and most of my use of DO* is something like
> > (DO* ((somecdr somelist (cdr somecdr))
> >       (someitem (car somecdr) (car somecdr))
> >        ... etc...))
> > 
> > which I suppose is poor style.  But how about something like this?:
> 
> [Sheepishly]  I do this too.  While it's not the prettiest code
> in the world, why do you consider it to be poort style?
 
Well actually I assumed it must be poor style, otherwise Kent would 
already consider this a good reason to use DO* ... 

> (Is should add that I don't LOOP, so perhaps you're alluding to
> a feature of this macro that makes such loops trivial to write.)

I started out always using DO and DO* because of Graham's negative
comments about LOOP in ANSI Common Lisp, but at some point I started
using ITER.. It was so useful I started using it all over the place.
Later I started thinking I might as well just use LOOP, as it is part
of the language while ITER is not; and many of the c.l.l.  Lispers
seem to accept it.  So now I am a huge LOOP fan - I just find code
much clearer when using it.
From: james anderson
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <3FAB75B9.E9A1D925@setf.de>
Kent M Pitman wrote:
> 
> ...
> HOWEVER, in this case I'd say you are generating gratuitous garbage
> not because you're generating it at all, but because it's just wasteful
> to cons things up and then throw them away when it doesn't serve your
> end result.  (If it did, I'd say "fine".)  If you look at my solution
> below, you'll see that a natural solution doesn't discard cons cells
> needlessly...
> 
> As an aside, this is how I'd have solved the problem:
> 
> (defun occurrences (list &key (test #'eql)) ;#1
>   (let ((alist '()))
>     (dolist (item list)
>       (incf (cdr (or (assoc item alist :test test)
>                      (let ((entry (cons item 0)))
>                         (push entry alist)
>                         entry)))))
>     (sort alist #'> :key #'cdr)))
> 
> Note that this solution lets you do
>  (occurrences '(a b a d a c d c a))
> but also
>  (occurrences '(a b a d "a" c d c a) :test #'string-equal)
> 
> You could also do it with a hash table, but note that the test
> is more restricted  since there are only a few kinds of hash tables.
> 
> (defun occurrences (list &key (test #'eql)) ;#2
>   (let ((table (make-hash-table :test test)))
>     (dolist (item list) (incf (gethash item table 0)))
>     (let ((alist '()))
>       (maphash #'(lambda (key val) (push (cons key val) alist))
>                table)
>       (sort alist #'> :key #'cdr))))
> 

?

other than the lack of generality, what are the arguments against using the
provided data itself for the intermediate storage?

(defun occurrences (list)
  (let ((key (gensym)))
    (dolist (item list)
      (incf (get item key 0)))
    (mapcar #'(lambda (sym) (prog1 (cons sym (get sym key))
                              (remprop sym key)))
            (sort (remove-duplicates list) #'>
                  :key #'(lambda (sym) (get sym key))))))

?
From: Kent M Pitman
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <wkk76ctdsw.fsf@nhplace.com>
james anderson <··············@setf.de> writes:

> other than the lack of generality, what are the arguments against using the
> provided data itself for the intermediate storage?

If the user is sharing this data with something else, you will be 
destroying a data structure you didn't mean to.  Never destroy a
data structure that someone hasn't given you license to destroy.

> (defun occurrences (list)
>   (let ((key (gensym)))
>     (dolist (item list)
>       (incf (get item key 0)))
>     (mapcar #'(lambda (sym) (prog1 (cons sym (get sym key))
>                               (remprop sym key)))
>             (sort (remove-duplicates list) #'>
>                   :key #'(lambda (sym) (get sym key))))))
> 
> ?

This destroys the input list by calling sort on it directly,
but I don't see to what end.  The MAPCAR just constructs a new
list.

When I read your text, I expected you to do something more like:

(defun occurrences (list)
  ;; Note that this assumes SORT will re-use the list structure
  ;; of list, which I'm not sure all implementations of SORT will
  ;; do.  They are allowed to, but not required to.
  (setq list (sort list 
	           ;; You'd need access to a system's pointer-lessp 
	           ;; here to make sure you could efficiently sort
	           ;; all eq symbols together.
                   ;; Use (defun pointer-lessp (x y) (string< x y))
                   ;; to test this on simple cases, but you won't 
                   ;; do so well if you have symbols with the same
                   ;; name in different packages (or no package at all).
	           #'pointer-lessp))
  (let ((tail list)
        (prev nil)
        (cursor (cons nil 0)))
    ;; awful kludge: trick the upcoming loop into immediately
    ;;     discarding this cursor by making sure it has a unique car.
    ;;     to save space, we just make the temporary cursor circular
    ;;     rather than wasting another cons for another unique value.
    (setf (car cursor) cursor)
    (let ((pool '()))
      (flet ((kons (x y)
               (if pool
                   (let ((new pool))
                     (pop pool)
                     (setf (car new) x)
                     (setf (cdr new) y)
                     new)
                   (cons x y))))
        (loop (unless tail (return))
          (cond ((eq (car tail) (car cursor))
                 (incf (cdr cursor))
                 (let ((old tail))
                   (pop tail)
                   (when prev (setf (cdr prev) tail))
                   (setq pool (rplacd old pool))))
                (t
                 (setf (car tail) (setq cursor (kons (car tail) 1)))
                 (setq prev tail)
                 (pop tail))))
        (sort list #'> :key #'cdr)))))

When it's all done, I don't see that this code is either perspicuous
or necessarily even (which I assume was the goal) space-efficient.
From: Kalle Olavi Niemitalo
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <87ekwia1so.fsf@Astalo.kon.iki.fi>
Kent M Pitman <······@nhplace.com> writes:

> 	           ;; You'd need access to a system's pointer-lessp 
> 	           ;; here to make sure you could efficiently sort
> 	           ;; all eq symbols together.

Do such pointer-lessp functions give consistent results if the
garbage collector runs in the middle?  If not, one could instead
lazily put an integer on the property list.
From: Kent M Pitman
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <sfw1xsigl5d.fsf@shell01.TheWorld.com>
Kalle Olavi Niemitalo <···@iki.fi> writes:

> Kent M Pitman <······@nhplace.com> writes:
> 
> > 	           ;; You'd need access to a system's pointer-lessp 
> > 	           ;; here to make sure you could efficiently sort
> > 	           ;; all eq symbols together.
> 
> Do such pointer-lessp functions give consistent results if the
> garbage collector runs in the middle?  If not, one could instead
> lazily put an integer on the property list.

Yes, but even that much consing would mostly defeat the purpose of
recycling the input structure's conses... 
From: Thomas A. Russ
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <ymid6c4vsef.fsf@sevak.isi.edu>
james anderson <··············@setf.de> writes:

> other than the lack of generality, what are the arguments against using the
> provided data itself for the intermediate storage?
> 
> (defun occurrences (list)
>   (let ((key (gensym)))
>     (dolist (item list)
>       (incf (get item key 0)))
                   ^^^^
You are assuming here that item has to be a symbol.  That would fail if
the input included things like integers as well.

>     (mapcar #'(lambda (sym) (prog1 (cons sym (get sym key))
>                               (remprop sym key)))
>             (sort (remove-duplicates list) #'>
>                   :key #'(lambda (sym) (get sym key))))))
> 
> ?

-- 
Thomas A. Russ,  USC/Information Sciences Institute
From: james anderson
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <3FAECFE2.72ACE864@setf.de>
"Thomas A. Russ" wrote:
> 
> james anderson <··············@setf.de> writes:
> 
> > other than the lack of generality, what are the arguments against using the
> > provided data itself for the intermediate storage?
> >
> > (defun occurrences (list)
> >   (let ((key (gensym)))
> >     (dolist (item list)
> >       (incf (get item key 0)))
>                    ^^^^
> You are assuming here that item has to be a symbol.
>     That would fail if
> the input included things like integers as well.
> 

thus the initial note about "lack of generality".

Kent M Pitman wrote:
> 
> This destroys the input list by calling sort on it directly,
> but I don't see to what end.  The MAPCAR just constructs a new
> list.
> 

reuse of the list argument was not the issue. read (copy-list
(remove-duplicates list)), for (remove-duplicates list)

the question concerns benefits or shortcomings of using the symbols v/s
building a data structure. 

...
From: Pascal Bourguignon
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <87vfpwcu4k.fsf@thalassa.informatimago.com>
Kent M Pitman <······@nhplace.com> writes:

> ······@MartinPomije.eiomail.com (Martin Pomije) writes:
> 
> > I've dabbled with Lisp before, and I've worked my way through most of
> > S&ICP, but I have decided to try a more systematic approach by working
> > through Paul Graham's ANSI Common Lisp book.
> > 
> > This is my code followed by my test cases for Exercise 3 on p. 56 of
> > that book.
> > 
> > <QOUTE>
> > Define a function that takes a list and returns a list indicating the
> > number of times each (eql) element appears, sorted from most common
> > element to least common.
> > 
> > >(occurences '(a b a d a c d c a))
> > ((A . 4) (C . 2) (D . 2) (B . 1))
> > </QUOTE>
> 
> Your code looks a little long and does a lot of raw consing for which
> there are packaged operators to do this in a more refined way.

What about this:

(defun occurences (list &key (test  (function eql)) 
                             (lessp (function total-order)))
  (sort (mapcar (lambda (sublis) (cons (car sublis) (length sublis)))
                (nsplit-list-on-indicator (sort (copy-seq list) lessp)
                                          (complement test)))
        (lambda (a b) (>= (cdr a) (cdr b)))))

(defun total-order (a b) (string<= (format nil "~S" a) (format nil "~S" b)))


If you don't  what to have to pass two  functions when using something
else than  eql, (which  was not asked  anyway), you could  deduce test
from lessp: test = (lambda (a b) (and (lessp a b) (lessp b a)))
(given lessp is a total order).


The following function is fetched from my toolbox, it doesn't count, does it:

(DEFUN NSPLIT-LIST-ON-INDICATOR (LIST INDICATOR)
  "
RETURN: a list of sublists of list (the conses from list are reused),
        the list is splited between items a and b for which (indicator a b).
"
  (DECLARE (TYPE (FUNCTION (T T) T) INDICATOR))
  (LET* ((RESULT NIL)
         (SUBLIST LIST)
         (CURRENT LIST)
         (NEXT    (CDR CURRENT)))
    (LOOP WHILE NEXT DO
          (IF (FUNCALL INDICATOR (CAR CURRENT) (CAR NEXT))
              (PROGN ;; split
                (SETF (CDR CURRENT) NIL)
                (PUSH SUBLIST RESULT)
                (SETQ CURRENT NEXT)
                (SETQ NEXT (CDR CURRENT))
                (SETQ SUBLIST CURRENT)
                )
            (PROGN ;; keep
              (SETQ CURRENT NEXT)
              (SETQ NEXT (CDR CURRENT))
              ))
          ) ;;while
    (PUSH SUBLIST RESULT)
    (NREVERSE RESULT))
  )


-- 
__Pascal_Bourguignon__
http://www.informatimago.com/
From: Martin Pomije
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <90ac4ec2.0311100015.45446272@posting.google.com>
Kent M Pitman <······@nhplace.com> wrote in message news:<··············@nhplace.com>...
> ······@MartinPomije.eiomail.com (Martin Pomije) writes:
(snip)
> > ;;;Steps through each item of the list and updates the alist
> > ;;;with that item.
> > (defun build-occurences (alist list)
> >   (if (null list)
> >     alist  ; processed all items in list, so we're done.
> >     (build-occurences (update-count-alist (car list) alist) (cdr
> > list))))
> 
> Doing this recursively means that you'll blow out of stack 
> if the list is too long.  I recommend learning some iteration tools.
> Common Lisp, unlike Scheme, does not treat tail calls as something
> for which there is no stack penalty.
(snip)
> 
> Style note: Avoid DO* if you can. It's tricky to move back and forth
> between DO and DO*, and, frankly, I've never found a need for DO*.  
> 
> The useful one of the two is DO because DO can be directly 
> transliterated to tail call procedures like Scheme programmers write.  
> DO* has no such useful property.
> 

I understand your stylistic objection to DO*, but I don't understand
your second objection.  You pointed out that the tail-call style is
inappropriate for Common Lisp.  Unless I plan on porting my code to
Scheme, why should it be important to be able to make that
transliteration?

(snip)
> 
> I didn't constrain my remarks this way.  My problem is that I don't think
> people should teach people to program wrong unless they have a serious
> commitment to retraining people later when they are going to have the
> full set of operations available.  They should pick examples that naturally
> cause you to use operators correctly, not examples that cause you to abuse
> operators and only later to realize you should have used something else
> when you finally get there...  Those operators you've gotten to so far
> ARE useful for things, and they should be giving you homework that 
> exemplifies intended uses.

Paul Graham probably meant a solution to the exercise that is similar
to your solution #1 below.  It wouldn't include INCF, but it would
work about the same.

(snip)

> 
> That's the wrong question.  It looks long and cluttered.  That's ok
> for where you are in the learning process--don't feel I'm beating up on
> you.  But you asked for code review, and I might as well not pull 
> punches.I wouldn't accept this in a commercial setting.  I'd send you 
> back and tell you to wholly rewrite it.  This is a small problem and a 
> solution should be one that you can glance easily at and tell what's 
> going on.
> 

Thank you for your straightforwardness.

> 
> (defun occurrences (list &key (test #'eql)) ;#1
>   (let ((alist '()))
>     (dolist (item list)
>       (incf (cdr (or (assoc item alist :test test)
>                      (let ((entry (cons item 0)))
>                         (push entry alist)
>                         entry)))))
>     (sort alist #'> :key #'cdr)))
> 
> Note that this solution lets you do 
>  (occurrences '(a b a d a c d c a))
> but also
>  (occurrences '(a b a d "a" c d c a) :test #'string-equal)
> 
> You could also do it with a hash table, but note that the test
> is more restricted  since there are only a few kinds of hash tables.
> 
> (defun occurrences (list &key (test #'eql)) ;#2
>   (let ((table (make-hash-table :test test)))
>     (dolist (item list) (incf (gethash item table 0)))
>     (let ((alist '()))
>       (maphash #'(lambda (key val) (push (cons key val) alist))
>                table)
>       (sort alist #'> :key #'cdr))))
> 
> I don't usually use MERGE, but I think you could use it here by
> doing this, which avoids the call to SORT after, but I'm not sure
> to what end...
> 
> (defun occurrences (list &key (test #'eql)) ;#3
>   (let ((table (make-hash-table :test test)))
>     (dolist (item list) (incf (gethash item table 0)))
>     (let ((alist '()))
>       (maphash #'(lambda (key val)
>                    (setq alist (merge 'list
>                                       (list (cons key val))
>                                       alist
>                                       #'>
>                                       :key #'cdr)))
>                table)
>       alist)))
> 
> Personally, I'd use my definition #1 unless the data sets were
> going to be very large, and then I'd use #2.

Some of your other points were also addressed by others, so I include
them in another post.

Thanks for putting so much effort into your reply.
From: Kent M Pitman
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <wk4qx9ba89.fsf@nhplace.com>
······@MartinPomije.eiomail.com (Martin Pomije) writes:

> > The useful one of the two is DO because DO can be directly 
> > transliterated to tail call procedures like Scheme programmers write.  
> > DO* has no such useful property.
> 
> I understand your stylistic objection to DO*, but I don't understand
> your second objection.  You pointed out that the tail-call style is
> inappropriate for Common Lisp.  Unless I plan on porting my code to
> Scheme, why should it be important to be able to make that
> transliteration?

Because you might receive or conceptualize code with tail calls in it
and then have no way to render it.  DO is important to understand as a
way of casting certain Scheme code into CL without worrying about
stack overflow.  DO* on the other hand is just a mess you have to
understand directly/primitively; its only analog is a bunch of SETQs
in a loop.
From: Sashank Varma
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <none-8ECF2A.20372212112003@news.vanderbilt.edu>
In article <··············@nhplace.com>,
 Kent M Pitman <······@nhplace.com> wrote:

> DO* on the other hand is just a mess you have to
> understand directly/primitively; its only analog is a bunch of SETQs
> in a loop.

DO* is to DO as LET* is to LET.  DO* and LET* do sequentially what
DO and LET accomplish in parallel.

Of course, this is an approximation.  You can think of LET* as
nested LETs (or LAMBDAs).  There is no comparable translation
of DO* to nested DOs.

But still, I find the analogy just close enough to be useful.
There's enough abstraction in DO* that I don't think of it
as "a bunch of SETQs in a loop."
From: Thomas F. Burdick
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <xcv1xsc6bji.fsf@famine.OCF.Berkeley.EDU>
Sashank Varma <····@vanderbilt.edu> writes:

> In article <··············@nhplace.com>,
>  Kent M Pitman <······@nhplace.com> wrote:
> 
> > DO* on the other hand is just a mess you have to
> > understand directly/primitively; its only analog is a bunch of SETQs
> > in a loop.
> 
> DO* is to DO as LET* is to LET.  DO* and LET* do sequentially what
> DO and LET accomplish in parallel.
> 
> Of course, this is an approximation.  You can think of LET* as
> nested LETs (or LAMBDAs).  There is no comparable translation
> of DO* to nested DOs.
> 
> But still, I find the analogy just close enough to be useful.
> There's enough abstraction in DO* that I don't think of it
> as "a bunch of SETQs in a loop."

Well, yeah, DO* is like DO, but with the assignments happening in a
nested/sequential fashion -- how does that differ from what Kent said?
Every DO* I've ever seen that wasn't easily expressible with DO, was
either a mess, or was begging for a new iteration macro.  If your
iteration isn't following some generally recognizable path, that's a
bad sign.  In fact, usually DO* can be better expressed as a well
structured PROG form.

-- 
           /|_     .-----------------------.                        
         ,'  .\  / | No to Imperialist war |                        
     ,--'    _,'   | Wage class war!       |                        
    /       /      `-----------------------'                        
   (   -.  |                               
   |     ) |                               
  (`-.  '--.)                              
   `. )----'                               
From: Kent M Pitman
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <sfw65ho18l7.fsf@shell01.TheWorld.com>
···@famine.OCF.Berkeley.EDU (Thomas F. Burdick) writes:

> Sashank Varma <····@vanderbilt.edu> writes:
> 
> > In article <··············@nhplace.com>,
> >  Kent M Pitman <······@nhplace.com> wrote:
> > 
> > > DO* on the other hand is just a mess you have to
> > > understand directly/primitively; its only analog is a bunch of SETQs
> > > in a loop.
> > 
> > DO* is to DO as LET* is to LET.  DO* and LET* do sequentially what
> > DO and LET accomplish in parallel.
> > 
> > Of course, this is an approximation.  You can think of LET* as
> > nested LETs (or LAMBDAs).  There is no comparable translation
> > of DO* to nested DOs.
> > 
> > But still, I find the analogy just close enough to be useful.
> > There's enough abstraction in DO* that I don't think of it
> > as "a bunch of SETQs in a loop."
> 
> Well, yeah, DO* is like DO, but with the assignments happening in a
> nested/sequential fashion -- how does that differ from what Kent said?
> Every DO* I've ever seen that wasn't easily expressible with DO, was
> either a mess, or was begging for a new iteration macro.  If your
> iteration isn't following some generally recognizable path, that's a
> bad sign.  In fact, usually DO* can be better expressed as a well
> structured PROG form.

To say what Thomas has already said more concisely in my usual more 
long-winded form:

LET* is a tool that allows one or more incoming, interdependent
dataflows to be cascaded in an unconstrained way for use within a
lexical contour.  Already by this metric, you can see that it's 
overpowerful.  Certainly, it lets you do:

 (let ((x (compute-x))
       (y (compute-y))
       (z (combine-somehow x y)))
   ...)

but in so doing, it loses the aesthetic of showing that x and y are
inputs while z is not.  It also makes it hard to spot that in

 (let ((x (compute-x))
       (y (compute-y))
       (z (combine-somehow x y k)))
   ...)

there are really three inputs: x, y, and k because the internal
computation of z makes that be harder to see.

It gets even worse if you have

 (let* ((x (compute-x))
        (y (compute-y))
        (z (combine-somehow x y k))
        (k (compute-local-k)))
   ...)

because here you're really saying that there are three inputs (x, y, k)
and one dependent value (z) but that k is badly named because you
wnat to use its outer and inner values in the same lexical contour
but are unable, so you have to grab it before it is renamed.

LET* certainly lets you save indentation space, but at quite large cost.

DO* compounds the injury by allowing you new ways to misuse k.  For example,
it might be that it really isn't even used twice--perhaps it's only used
again as an input, but you're putting the step in a strange place.  That is,
if you're doing:

 (do* ((x (compute-x) ...)
       (y (compute-y) ...)
       (z (combine-somehow x y k) ...)
       (k (step-it k) (step-it k)))
      (...)
   ...)

you are really probably meaning to do

 (do ((x (compute-x) ...)
      (y (compute-y) ...)
      (k k (step-it k)))
     (...)
  (let ((z (combine-somehow x y k)))
    ...))

which would be much more intelligible to most poeple.

Almost always, in my experience, DO* ends up in a case where someone is
not understanding the base case and both the init and the step situation
for the dependent variable is too complex.  Not always.  There are some
idiomatic cases that are not like this.  But in those cases, a great many
are better expressable using a LET in the body.  Some object that this
means the exit test for the DO isn't set up "in time" to use the inner
LET variables, but that's easily dealt with by making the loop not 
terminate and doing an explicit test in the loop body.
From: Sashank Varma
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <none-2FE63E.13084013112003@news.vanderbilt.edu>
In article <···············@shell01.TheWorld.com>,
 Kent M Pitman <······@world.std.com> wrote:

> DO* compounds the injury by allowing you new ways to misuse k.  For example,
> it might be that it really isn't even used twice--perhaps it's only used
> again as an input, but you're putting the step in a strange place.  That is,
> if you're doing:
> 
>  (do* ((x (compute-x) ...)
>        (y (compute-y) ...)
>        (z (combine-somehow x y k) ...)
>        (k (step-it k) (step-it k)))
>       (...)
>    ...)
> 
> you are really probably meaning to do
> 
>  (do ((x (compute-x) ...)
>       (y (compute-y) ...)
>       (k k (step-it k)))
>      (...)
>   (let ((z (combine-somehow x y k)))
>     ...))
> 
> which would be much more intelligible to most poeple.

I waffle on this.  Sometimes I favor the conciseness of the
DO* version -- all the variables being changed on each
iteration are gathered in one place.  Sometimes I favor the
clarity of the DO/LET version.

> Almost always, in my experience, DO* ends up in a case where someone is
> not understanding the base case and both the init and the step situation
> for the dependent variable is too complex.  Not always.  There are some
> idiomatic cases that are not like this.  But in those cases, a great many
> are better expressable using a LET in the body.  Some object that this
> means the exit test for the DO isn't set up "in time" to use the inner
> LET variables, but that's easily dealt with by making the loop not 
> terminate and doing an explicit test in the loop body.

I guess I would be one of those objecting.  I'd favor
stepping the dependent variable along with the independent
variables rather than (1) leaving the termination test
empty and (2) providing an explicit RETURN-FROM (or
something similar) in the body, all things being equal.

I saw some categorical denouncements of DO* earlier in this
thread and was looking for a definitive reason to ditch it
in favor of DO/LET.  However, it seems like this is all a
matter of style, unless I'm still missing something.
From: Kent M Pitman
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <sfw8ymjdku2.fsf@shell01.TheWorld.com>
Sashank Varma <····@vanderbilt.edu> writes:

> I saw some categorical denouncements of DO* earlier in this
> thread and was looking for a definitive reason to ditch it
> in favor of DO/LET.  However, it seems like this is all a
> matter of style, unless I'm still missing something.

There are certainly reasons to dump it entirely.  You may or may not 
believe them.

1. It doesn't offer power you don't have elsewhere.
   (Yes, true of many things.)

2. It offers many opportunities to do things wrong.

3. It forces the many other people who have sworn off DO* to cringe
   and suspect true evil when they see your loop.  They cannot assume
   you are sharp enough to have avoided problem #2.  They have to
   begin with the assumption that you are confusing yourself (and them).
   In the end, you haven't saved them any time.

As with all style rules, you may have a reason you don't want to go
this way or you may subscribe to someone else's style rule (including,
maybe, your own) that this can be used safely enough that you don't
mind the costs.  But it is my personal style rule never to use it, and
I frankly have never found myself even _thinking_ about using it.

Disclaimer: Mostly, I use LOOP in the places where it probably matters.
  And some people have style rules against that.  Such is the world.
From: Sashank Varma
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <none-23AB76.14142614112003@news.vanderbilt.edu>
In article <···············@shell01.TheWorld.com>,
 Kent M Pitman <······@world.std.com> wrote:

> There are certainly reasons to dump it entirely.  You may or may not 
> believe them.
[...]
> 3. It forces the many other people who have sworn off DO* to cringe
>    and suspect true evil when they see your loop.  They cannot assume
>    you are sharp enough to have avoided problem #2.  They have to
>    begin with the assumption that you are confusing yourself (and them).
>    In the end, you haven't saved them any time.
> 
> As with all style rules, you may have a reason you don't want to go
> this way or you may subscribe to someone else's style rule (including,
> maybe, your own) that this can be used safely enough that you don't
> mind the costs.

I never knew DO* had such a bad reputation.  I don't
read others' code much, so I have no sense of how
often it appears versus DO/LET versus LOOP in contexts
when all three will do.  And when I do read programs
written by others, they're typically in books or
tutorials or academic papers where the authors stay
away from more esoteric constructions for other
reasons.  You're comments and Thomas' echo were the
first I'd heard of this matter.
From: Thomas F. Burdick
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <xcvptfua6gm.fsf@fallingrocks.OCF.Berkeley.EDU>
Sashank Varma <····@vanderbilt.edu> writes:

> In article <···············@shell01.TheWorld.com>,
>  Kent M Pitman <······@world.std.com> wrote:
> 
> > There are certainly reasons to dump it entirely.  You may or may not 
> > believe them.
> [...]
> > 3. It forces the many other people who have sworn off DO* to cringe
> >    and suspect true evil when they see your loop.  They cannot assume
> >    you are sharp enough to have avoided problem #2.  They have to
> >    begin with the assumption that you are confusing yourself (and them).
> >    In the end, you haven't saved them any time.
> > 
> > As with all style rules, you may have a reason you don't want to go
> > this way or you may subscribe to someone else's style rule (including,
> > maybe, your own) that this can be used safely enough that you don't
> > mind the costs.
> 
> I never knew DO* had such a bad reputation.  I don't
> read others' code much, so I have no sense of how
> often it appears versus DO/LET versus LOOP in contexts
> when all three will do.  And when I do read programs
> written by others, they're typically in books or
> tutorials or academic papers where the authors stay
> away from more esoteric constructions for other
> reasons.  You're comments and Thomas' echo were the
> first I'd heard of this matter.

I think DO* is a case of the combination of two things (DO and LET*)
multiplying the bad aspects of the two.  DO is the primitive iteration
construct, and is often more primitive than what would be optimal (for
communicating with later readers).  It's powerful, but the iteration
paths aren't spelled out explicitly like with the other DO... macros,
or with LOOP paths, so it makes it more difficult to read.  When you
add in the LET*-like nested bindings, it gets too close to a
write-only language.  It's not that you can't write readable code in
such things, but if I'm reading your code, and I come across a DO*,
I'll take a deep breath, and maybe take a break first.  When I come
back, I might see a perfectly comprehensible iteration, but knowing
how easy DO* makes it to produce spaghetti code, I get instant
aprehension when I see it.

-- 
           /|_     .-----------------------.                        
         ,'  .\  / | No to Imperialist war |                        
     ,--'    _,'   | Wage class war!       |                        
    /       /      `-----------------------'                        
   (   -.  |                               
   |     ) |                               
  (`-.  '--.)                              
   `. )----'                               
From: Tayss
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <5627c6fa.0311150049.44eb6de0@posting.google.com>
Sashank Varma <····@vanderbilt.edu> wrote in message news:<··························@news.vanderbilt.edu>...
> I saw some categorical denouncements of DO* earlier in this
> thread and was looking for a definitive reason to ditch it
> in favor of DO/LET.  However, it seems like this is all a
> matter of style, unless I'm still missing something.

I think it's like the denouncement of iteration given in SICP; you
have to deal with different variables changing state at different
times, so order is important.  This supposedly leads to bugs,
especially when programmers add layer upon layer to your legacy code.

I wish there were setf and setf*.
From: Nikodemus Siivola
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <bp4pvc$28r$1@nyytiset.pp.htv.fi>
Tayss <··········@yahoo.com> wrote:

> I wish there were setf and setf*.

There are! Except that your setf* is SETF, and setf is PSETF -- if I
understood you correctly.

Cheers,

 -- Nikodemus
From: Tayss
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <5627c6fa.0311150637.7badccdc@posting.google.com>
Nikodemus Siivola <······@random-state.net> wrote in message news:<············@nyytiset.pp.htv.fi>...
> Tayss <··········@yahoo.com> wrote:
> > I wish there were setf and setf*.
> 
> There are! Except that your setf* is SETF, and setf is PSETF -- if I
> understood you correctly.

I mispoke.  I should have said that I wished psetf were called setf,
and the old setf -> setf*.  Before posting, I deleted the part where I
mentioned I was tempted to almost always use psetf, even for assigning
single variables, except people reading my code would wonder if they
were missing something.  Having setf have psetf's semantics should
take care of the problem, and people would reserve their caution for
when they encountered setf*.

(set! and set!* would work too...  Plus some portable way to tell the
system to use tail recursion, unless that series stuff takes care of
it.  Some things from scheme look worth borrowing in a cl way.)

Sorry for the misunderstanding!
From: David Golden
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <ixstb.680$nm6.1843@news.indigo.ie>
Anyway, "setf*", meaning a multiple-value setf, is conventionally used to
explain how CLIM changes setf - so the notation is "already used" for
something else (in my brain anyway), even if you don't actually type it.

http://www.stud.uni-karlsruhe.de/~unk6/clim-spec/B-4.html#_1903
From: Pascal Costanza
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <bp53af$krk$2@newsreader3.netcologne.de>
Tayss wrote:

> I wish there were setf and setf*.

Check out psetf!


Pascal
From: Paolo Amoroso
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <87ekw9okbx.fsf@plato.moon.paoloamoroso.it>
Thomas F. Burdick writes:

> Every DO* I've ever seen that wasn't easily expressible with DO, was
> either a mess, or was begging for a new iteration macro.  If your

DOH :)


Paolo
-- 
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
From: Kenny Tilton
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <S3Fqb.45994$Gq.10800453@twister.nyc.rr.com>
Martin Pomije wrote:
> I've dabbled with Lisp before, and I've worked my way through most of
> S&ICP, but I have decided to try a more systematic approach by working
> through Paul Graham's ANSI Common Lisp book.
> 
> This is my code followed by my test cases for Exercise 3 on p. 56 of
> that book.
> 
> <QOUTE>
> Define a function that takes a list and returns a list indicating the
> number of times each (eql) element appears, sorted from most common
> element to least common.
> 

Nice work!

> 
>>(occurences '(a b a d a c d c a))
> 
> ((A . 4) (C . 2) (D . 2) (B . 1))
> </QUOTE>
> 
> ;;;; Ex. 3
> ;;; Takes a list of items and returns ab association list that
> indicates how
> ;;; many times each item occured, sorted with the maximum count at the
> ;;; head of the association list. 
> (defun occurences (list)
>   (if (consp list)
>     (build-occurences () list)
>     nil))

1. You could just do:

(defun occurrences (list &optional alist)
    ...)

and avoid the helper build-occurrences.

2. You could also just do:

    (when (consp list)
       ...)

and get nil anyway if it is not consp.



> 
> ;;;Steps through each item of the list and updates the alist
> ;;;with that item.
> (defun build-occurences (alist list)
>   (if (null list)
>     alist  ; processed all items in list, so we're done.
>     (build-occurences (update-count-alist (car list) alist) (cdr
> list))))

Unlike in Scheme, you can just:

     (if list ;; nil/not-nil ok as boolean
        (occurrences ....)
        alist)
> 
> ;;; Updates the alist with the with respect to the symbol.
> (defun update-count-alist (symbol alist)
>   (let ((first (car alist)))
>     (if (null first)
>       (list (cons symbol 1)) 
>       (if (eql (car first) symbol)
>         ;; the first item is a match
>         (cons (cons symbol (+ (cdr first) 1)) 
>               (cdr alist))
>         ;; first item is not a match and alist has at least one record
>         (scan-count-alist symbol alist)))))
> 
> 
> ;;; Steps through alist to update symbol assoc record.
> ;;; Assumes that the first item of the alist does not match symbol. 
> ;;; Assumes alist has at least 1 assoc record.
> (defun scan-count-alist (symbol alist)
>   (do* ((scan-position alist (cdr scan-position))
>         (second (cadr scan-position) (cadr scan-position)))
>        ((null second) ; scanned through alist, no occurences of item
> found
>         (progn
>           (setf (cdr scan-position) (cons (cons symbol 1) nil)) ; add
> record to the end
>           alist))
>     (if (eql (car second) symbol)
>       (progn
>         ;; delete old record for symbol
>         (setf (cdr scan-position) (cddr scan-position))
>         ;; insert updated record for symbol
>         (return 
>          ;; alist should have at least 1 record because of the do*
> exit test
>          (insert-count-alist (+ (cdr second) 1) symbol alist))))))
> 
> ;;; Updates alist by inserting an assoc record for symbol.
> ;;; Assumes alist has at least 1 item.
> (defun insert-count-alist (count symbol alist)
>   (if (>= count (cdar alist))
>     (cons (cons symbol count) alist)
>     (do* ((scan-point alist (cdr scan-point))
>           (insertion-point (cdr scan-point) (cdr scan-point)))
>          ((null insertion-point) ; assoc record needs to go at the end
> of the list
>           (progn 
>             (setf (cdr scan-point) (cons (cons symbol count) nil))
>             alist))
>       (if (>= count (cdar insertion-point)) 
>         (progn 
>           (setf (cdr scan-point) 
>                 (cons (cons symbol count) insertion-point))
>           (return alist))))))

Yowza. You did some serious work/learning there. It's all good. But here 
is what I would recommend:

1. sort the list when you are done. destructively. write your own if 
SORT is mentioned after page 56.

2. don't use recursion, iterate over the occurrences building up an 
unsorted alist as you go, sort at the end by destructively relinking the 
cons cells of the alist (a neat learning exercise itself).

Don't forget, once you have the matching alist entry, you can:

     (incf (cdr entry))

But I realize you were maintaining the sort as you went by deleting the 
prior entry and inserting a new entry with an incremented count. You 
have done a lot of work here, and as long as you can write all this 
code, go ahead and work out how to:

     (let ((entry (find-entry new alist))
         (if entry
              (progn (incf (cdr entry))
                     (setf alist (maybe-move-up entry alist)))
           (cons ... alist)

where you muck about with cars and cdrs and build some cons cell fluency.


3. as with sort, OK, assoc does not come before p56, but that does not 
mean you cannot factor out the "find matching alist entry" functionality 
in a roll-your-own assoc of some ilk and simplify the mainline.

kenny

-- 
http://tilton-technology.com

Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film

Your Project Here! http://alu.cliki.net/Industry%20Application
From: Artie Gold
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <3FAB353C.70205@austin.rr.com>
Kenny Tilton wrote:
> 
> 
> Martin Pomije wrote:
> 
>> I've dabbled with Lisp before, and I've worked my way through most of
>> S&ICP, but I have decided to try a more systematic approach by working
>> through Paul Graham's ANSI Common Lisp book.
>>
>> This is my code followed by my test cases for Exercise 3 on p. 56 of
>> that book.
>>
>> <QOUTE>
>> Define a function that takes a list and returns a list indicating the
>> number of times each (eql) element appears, sorted from most common
>> element to least common.
>>
> 
> Nice work!
> 
>>
>>> (occurences '(a b a d a c d c a))
>>
>>
>> ((A . 4) (C . 2) (D . 2) (B . 1))
>> </QUOTE>
>>
>> ;;;; Ex. 3
>> ;;; Takes a list of items and returns ab association list that
>> indicates how
>> ;;; many times each item occured, sorted with the maximum count at the
>> ;;; head of the association list. (defun occurences (list)
>>   (if (consp list)
>>     (build-occurences () list)
>>     nil))
> 
> 
> 1. You could just do:
> 
> (defun occurrences (list &optional alist)
>    ...)
> 
> and avoid the helper build-occurrences.
> 
> 2. You could also just do:
> 
>    (when (consp list)
>       ...)
> 
> and get nil anyway if it is not consp.
> 
> 
> 
>>
>> ;;;Steps through each item of the list and updates the alist
>> ;;;with that item.
>> (defun build-occurences (alist list)
>>   (if (null list)
>>     alist  ; processed all items in list, so we're done.
>>     (build-occurences (update-count-alist (car list) alist) (cdr
>> list))))
> 
> 
> Unlike in Scheme, you can just:
> 
>     (if list ;; nil/not-nil ok as boolean
>        (occurrences ....)
>        alist)
> 
>>
>> ;;; Updates the alist with the with respect to the symbol.
>> (defun update-count-alist (symbol alist)
>>   (let ((first (car alist)))
>>     (if (null first)
>>       (list (cons symbol 1))       (if (eql (car first) symbol)
>>         ;; the first item is a match
>>         (cons (cons symbol (+ (cdr first) 1))               (cdr alist))
>>         ;; first item is not a match and alist has at least one record
>>         (scan-count-alist symbol alist)))))
>>
>>
>> ;;; Steps through alist to update symbol assoc record.
>> ;;; Assumes that the first item of the alist does not match symbol. 
>> ;;; Assumes alist has at least 1 assoc record.
>> (defun scan-count-alist (symbol alist)
>>   (do* ((scan-position alist (cdr scan-position))
>>         (second (cadr scan-position) (cadr scan-position)))
>>        ((null second) ; scanned through alist, no occurences of item
>> found
>>         (progn
>>           (setf (cdr scan-position) (cons (cons symbol 1) nil)) ; add
>> record to the end
>>           alist))
>>     (if (eql (car second) symbol)
>>       (progn
>>         ;; delete old record for symbol
>>         (setf (cdr scan-position) (cddr scan-position))
>>         ;; insert updated record for symbol
>>         (return          ;; alist should have at least 1 record 
>> because of the do*
>> exit test
>>          (insert-count-alist (+ (cdr second) 1) symbol alist))))))
>>
>> ;;; Updates alist by inserting an assoc record for symbol.
>> ;;; Assumes alist has at least 1 item.
>> (defun insert-count-alist (count symbol alist)
>>   (if (>= count (cdar alist))
>>     (cons (cons symbol count) alist)
>>     (do* ((scan-point alist (cdr scan-point))
>>           (insertion-point (cdr scan-point) (cdr scan-point)))
>>          ((null insertion-point) ; assoc record needs to go at the end
>> of the list
>>           (progn             (setf (cdr scan-point) (cons (cons symbol 
>> count) nil))
>>             alist))
>>       (if (>= count (cdar insertion-point))         (progn           
>> (setf (cdr scan-point)                 (cons (cons symbol count) 
>> insertion-point))
>>           (return alist))))))
> 
> 
> Yowza. You did some serious work/learning there. It's all good. But here 
> is what I would recommend:
> 
> 1. sort the list when you are done. destructively. write your own if 
> SORT is mentioned after page 56.
> 
> 2. don't use recursion, iterate over the occurrences building up an 
> unsorted alist as you go, sort at the end by destructively relinking the 
> cons cells of the alist (a neat learning exercise itself).
> 
> Don't forget, once you have the matching alist entry, you can:
> 
>     (incf (cdr entry))
> 
> But I realize you were maintaining the sort as you went by deleting the 
> prior entry and inserting a new entry with an incremented count. You 
> have done a lot of work here, and as long as you can write all this 
> code, go ahead and work out how to:
> 
>     (let ((entry (find-entry new alist))
>         (if entry
>              (progn (incf (cdr entry))
>                     (setf alist (maybe-move-up entry alist)))
>           (cons ... alist)
> 
> where you muck about with cars and cdrs and build some cons cell fluency.
> 
> 
> 3. as with sort, OK, assoc does not come before p56, but that does not 
> mean you cannot factor out the "find matching alist entry" functionality 
> in a roll-your-own assoc of some ilk and simplify the mainline.
> 
All right, I was mucking about (without SICP in front of me -- so I 
used
the documentation included in PowerLisp) and came up with the following:

(defun build-occurences-alist (the-list)
   ; the-alist is the result
   (let ((the-alist nil))
     (flet ((update-alist (key)
       ; have we dealt with this symbol already?
       (let ((pos (assoc key the-alist)))
	(if pos
           ; we have, so increment the count
           (incf (cdr pos))
           ; we haven't, so create an entry
           (push (cons key 1) the-alist)))))
       ; map across the supplied list
       (mapc #'update-alist the-list)
       ; I can't get the sort to work for some reason
       ;(sort the-alist #'> :key #'cdr)
       the-alist)))
From: Artie Gold
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <3FAB3A8F.1020402@austin.rr.com>
Kenny Tilton wrote:
 >
 >
 > Martin Pomije wrote:
 >
 >> I've dabbled with Lisp before, and I've worked my way through 
most of
 >> S&ICP, but I have decided to try a more systematic approach by 
working
 >> through Paul Graham's ANSI Common Lisp book.
 >>
 >> This is my code followed by my test cases for Exercise 3 on p. 56 of
 >> that book.
 >>
 >> <QOUTE>
 >> Define a function that takes a list and returns a list 
indicating the
 >> number of times each (eql) element appears, sorted from most common
 >> element to least common.
 >>
 >
 > Nice work!
 >
 >>
 >>> (occurences '(a b a d a c d c a))
 >>
 >>
 >> ((A . 4) (C . 2) (D . 2) (B . 1))
 >> </QUOTE>
 >>
 >> ;;;; Ex. 3
 >> ;;; Takes a list of items and returns ab association list that
 >> indicates how
 >> ;;; many times each item occured, sorted with the maximum count 
at the
 >> ;;; head of the association list. (defun occurences (list)
 >>   (if (consp list)
 >>     (build-occurences () list)
 >>     nil))
 >
 >
 > 1. You could just do:
 >
 > (defun occurrences (list &optional alist)
 >    ...)
 >
 > and avoid the helper build-occurrences.
 >
 > 2. You could also just do:
 >
 >    (when (consp list)
 >       ...)
 >
 > and get nil anyway if it is not consp.
 >
 >
 >
 >>
 >> ;;;Steps through each item of the list and updates the alist
 >> ;;;with that item.
 >> (defun build-occurences (alist list)
 >>   (if (null list)
 >>     alist  ; processed all items in list, so we're done.
 >>     (build-occurences (update-count-alist (car list) alist) (cdr
 >> list))))
 >
 >
 > Unlike in Scheme, you can just:
 >
 >     (if list ;; nil/not-nil ok as boolean
 >        (occurrences ....)
 >        alist)
 >
 >>
 >> ;;; Updates the alist with the with respect to the symbol.
 >> (defun update-count-alist (symbol alist)
 >>   (let ((first (car alist)))
 >>     (if (null first)
 >>       (list (cons symbol 1))       (if (eql (car first) symbol)
 >>         ;; the first item is a match
 >>         (cons (cons symbol (+ (cdr first) 1))               (cdr 
alist))
 >>         ;; first item is not a match and alist has at least one 
record
 >>         (scan-count-alist symbol alist)))))
 >>
 >>
 >> ;;; Steps through alist to update symbol assoc record.
 >> ;;; Assumes that the first item of the alist does not match symbol.
 >> ;;; Assumes alist has at least 1 assoc record.
 >> (defun scan-count-alist (symbol alist)
 >>   (do* ((scan-position alist (cdr scan-position))
 >>         (second (cadr scan-position) (cadr scan-position)))
 >>        ((null second) ; scanned through alist, no occurences of item
 >> found
 >>         (progn
 >>           (setf (cdr scan-position) (cons (cons symbol 1) nil)) 
; add
 >> record to the end
 >>           alist))
 >>     (if (eql (car second) symbol)
 >>       (progn
 >>         ;; delete old record for symbol
 >>         (setf (cdr scan-position) (cddr scan-position))
 >>         ;; insert updated record for symbol
 >>         (return          ;; alist should have at least 1 record
 >> because of the do*
 >> exit test
 >>          (insert-count-alist (+ (cdr second) 1) symbol alist))))))
 >>
 >> ;;; Updates alist by inserting an assoc record for symbol.
 >> ;;; Assumes alist has at least 1 item.
 >> (defun insert-count-alist (count symbol alist)
 >>   (if (>= count (cdar alist))
 >>     (cons (cons symbol count) alist)
 >>     (do* ((scan-point alist (cdr scan-point))
 >>           (insertion-point (cdr scan-point) (cdr scan-point)))
 >>          ((null insertion-point) ; assoc record needs to go at 
the end
 >> of the list
 >>           (progn             (setf (cdr scan-point) (cons (cons 
symbol
 >> count) nil))
 >>             alist))
 >>       (if (>= count (cdar insertion-point))         (progn 

 >> (setf (cdr scan-point)                 (cons (cons symbol count)
 >> insertion-point))
 >>           (return alist))))))
 >
 >
 > Yowza. You did some serious work/learning there. It's all good. 
But here
 > is what I would recommend:
 >
 > 1. sort the list when you are done. destructively. write your own if
 > SORT is mentioned after page 56.
 >
 > 2. don't use recursion, iterate over the occurrences building up an
 > unsorted alist as you go, sort at the end by destructively 
relinking the
 > cons cells of the alist (a neat learning exercise itself).
 >
 > Don't forget, once you have the matching alist entry, you can:
 >
 >     (incf (cdr entry))
 >
 > But I realize you were maintaining the sort as you went by 
deleting the
 > prior entry and inserting a new entry with an incremented count. You
 > have done a lot of work here, and as long as you can write all this
 > code, go ahead and work out how to:
 >
 >     (let ((entry (find-entry new alist))
 >         (if entry
 >              (progn (incf (cdr entry))
 >                     (setf alist (maybe-move-up entry alist)))
 >           (cons ... alist)
 >
 > where you muck about with cars and cdrs and build some cons cell 
fluency.
 >
 >
 > 3. as with sort, OK, assoc does not come before p56, but that 
does not
 > mean you cannot factor out the "find matching alist entry" 
functionality
 > in a roll-your-own assoc of some ilk and simplify the mainline.
 >

[sorry, something went wrong with my original followup]

All right, I was mucking about (without SICP in front of me -- so I
used
the documentation included in PowerLisp) and came up with the following:

(defun build-occurences-alist (the-list)
    ; the-alist is the result
    (let ((the-alist nil))
      (flet ((update-alist (key)
        ; have we dealt with this symbol already?
        (let ((pos (assoc key the-alist)))
          (if pos
            ; we have, so increment the count
            (incf (cdr pos))
            ; we haven't, so create an entry
            (push (cons key 1) the-alist)))))
        ; map across the supplied list
        (mapc #'update-alist the-list)
        ; I can't get the sort to work for some reason
        ;(sort the-alist #'> :key #'cdr)
        the-alist)))

Aside from the fact that I can't seem to get the SORT to work (any 
clues would, of course, be welcome) -- this seems pretty much short, 
simple and clear.

Flames, slings and arrows welcome!

Many thanks,
--ag

--
Artie Gold   Austin, Texas
From: Kenny Tilton
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <d4Qqb.52041$Gq.11067509@twister.nyc.rr.com>
Artie Gold wrote:

> (defun build-occurences-alist (the-list)
>    ; the-alist is the result
>    (let ((the-alist nil))
>      (flet ((update-alist (key)
>        ; have we dealt with this symbol already?
>        (let ((pos (assoc key the-alist)))
>          (if pos
>            ; we have, so increment the count
>            (incf (cdr pos))
>            ; we haven't, so create an entry
>            (push (cons key 1) the-alist)))))
>        ; map across the supplied list
>        (mapc #'update-alist the-list)
>        ; I can't get the sort to work for some reason
>        ;(sort the-alist #'> :key #'cdr)
>        the-alist)))
> 
> Aside from the fact that I can't seem to get the SORT to work (any clues 
> would, of course, be welcome) 

This is an FAQ classic: you have to capture the return value from sort. 
Remember, there is no such thing as a list. The local variable the-alist 
is bound to a cons cell (the first of the list before the sort). after 
the sort (since you do not code "(setf the-alist (sort the-alist....") 
it naturally is still bound to the same cons cell, no matter where that 
cons cell now sits in the structure which followed it until sort 
destructively rearranged things.

Of course in the example above it so happens you do not need the "(setf 
the-alist (sort..." at all since you could just return what sort returns 
(the new first cons cell).

kenny


-- 
http://tilton-technology.com

Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film

Your Project Here! http://alu.cliki.net/Industry%20Application
From: Thomas A. Russ
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <ymi4qxfx6k3.fsf@sevak.isi.edu>
······@MartinPomije.eiomail.com (Martin Pomije) writes:

> <QOUTE>
> Define a function that takes a list and returns a list indicating the
> number of times each (eql) element appears, sorted from most common
> element to least common.
> 
> >(occurences '(a b a d a c d c a))
> ((A . 4) (C . 2) (D . 2) (B . 1))
> </QUOTE>
> 
> ;;;; Ex. 3
> ;;; Takes a list of items and returns ab association list that
> indicates how
> ;;; many times each item occured, sorted with the maximum count at the
> ;;; head of the association list. 
> (defun occurences (list)
>   (if (consp list)
>     (build-occurences () list)
>     nil))
> 
> ;;;Steps through each item of the list and updates the alist
> ;;;with that item.
> (defun build-occurences (alist list)
>   (if (null list)
>     alist  ; processed all items in list, so we're done.
>     (build-occurences (update-count-alist (car list) alist) (cdr
> list))))
> 
 > ;;; Updates the alist with the with respect to the symbol.
 > (defun update-count-alist (symbol alist)
 >   (let ((first (car alist)))
 >     (if (null first)
 >       (list (cons symbol 1)) 
 >       (if (eql (car first) symbol)
 >         ;; the first item is a match
 >         (cons (cons symbol (+ (cdr first) 1)) 
 >               (cdr alist))
 >         ;; first item is not a match and alist has at least one record
 >         (scan-count-alist symbol alist)))))

Well, if you wanted a simple, recursive, consing solution you could make
the alist traversal and updating into a single function here and
dispense with the other functions.  This is also a scheme-like solution.

(defun update-count-alist (symbol alist)
  (if (null alist)   ; No matches for symbol in alist
      (list (cons symbol 1))
      (if (eql (caar alist) symbol)  ; Matching entry
	  ; Non-destructive version:
          (cons (cons symbol (+ (cdar alist) 1))
                (cdr alist))
	  ; Try next element
          (cons (first alist)
                (update-count-alist symbol (cdr alist))))))

A destructive version of this function would use
          (progn (setf (cdar alist) (+ (cdar alist) 1))
                 alist)


-- 
Thomas A. Russ,  USC/Information Sciences Institute
From: Richard Fateman
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <5tYqb.5676$Ga4.3359@newssvr25.news.prodigy.com>
the word is spelled "occurrences"  at least in English.
From: Tim Daly Jr.
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <87smkz40i1.fsf@simple.intern>
Richard Fateman <········@sbcglobal.net> writes:

> the word is spelled "occurrences"  at least in English.
> 

We also begin sentences with capital letters and offset parenthetic
expressions with commas, at least in English.

Oh, wait, you mean this isn't comp.lang.english?  Silly me.

-Tim (Who somehow expected more than spelling lessons from a professor
of computer science.)


-- 
Man must shape his tools lest they shape him. -- Arthur R. Miller
From: Nicolas Neuss
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <873cczhx3w.fsf@ortler.iwr.uni-heidelberg.de>
···@tenkan.org (Tim Daly Jr.) writes:

a criticism of

> Richard Fateman <········@sbcglobal.net> writes:
> 
> > the word is spelled "occurrences"  at least in English.


Looking at it from another point of view: as a non-native speaker, I do
like corrections of my English spelling very much (at least in such
sensitive areas as function names).

Nicolas.
From: Alexander Schmolck
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <yfsvfpufxw4.fsf@black132.ex.ac.uk>
···@tenkan.org (Tim Daly Jr.) writes:

> Oh, wait, you mean this isn't comp.lang.english?  Silly me.
> 
> -Tim (Who somehow expected more than spelling lessons from a professor
> of computer science.)

Exactly, who minds using libraries where half the names are spelled
incorrectly? ("Let me see, I want to use the occurrences function but first I
have to look up how the author spelled it again. I'd also better misspell my
own foo-occurrences function the same way, for consistencies sake.") Great.

'as
From: Kenny Tilton
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <BRcrb.56666$Gq.11705182@twister.nyc.rr.com>
Alexander Schmolck wrote:
> ···@tenkan.org (Tim Daly Jr.) writes:
> 
> 
>>Oh, wait, you mean this isn't comp.lang.english?  Silly me.
>>
>>-Tim (Who somehow expected more than spelling lessons from a professor
>>of computer science.)
> 
> 
> Exactly, who minds using libraries where half the names are spelled
> incorrectly? ("Let me see, I want to use the occurrences function but first I
> have to look up how the author spelled it again. I'd also better misspell my
> own foo-occurrences function the same way, for consistencies sake.") Great.

That's "for consistency's sake", in Englisch anyway.

-- 
http://tilton-technology.com

Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film

Your Project Here! http://alu.cliki.net/Industry%20Application
From: Curt
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <87ptg2mt1t.fsf@einstein.electron.net>
Kenny Tilton <·······@nyc.rr.com> writes:

> Alexander Schmolck wrote:

> > ···@tenkan.org (Tim Daly Jr.) writes:

> >>Oh, wait, you mean this isn't comp.lang.english?  Silly me.

> >>-Tim (Who somehow expected more than spelling lessons from a professor
> >>of computer science.)

> > Exactly, who minds using libraries where half the names are spelled
> > incorrectly? ("Let me see, I want to use the occurrences function but first I
> > have to look up how the author spelled it again. I'd also better misspell my
> > own foo-occurrences function the same way, for consistencies sake.") Great.

> That's "for consistency's sake", in Englisch anyway.

I think he was just being consistent for the sake of Miss Spelling, whoever she is.
From: Sebastian Stern
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <ad7d32de.0311100818.6e572ac8@posting.google.com>
Kenny Tilton wrote:
> Alexander Schmolck wrote:
> > own foo-occurrences function the same way, for consistencies sake.") Great.
> 
> That's "for consistency's sake", in Englisch anyway.

That 'English', in Englich anyway.

Sebastian Stern
"Freedom is the freedom to say (= (+ 2 2) 4). If that is granted, all else follows."
From: Don Geddis
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <877k2anl44.fsf@sidious.geddis.org>
Alexander Schmolck <··········@gmx.net> writes:
> Exactly, who minds using libraries where half the names are spelled
> incorrectly? ("Let me see, I want to use the occurrences function but first I
> have to look up how the author spelled it again. I'd also better misspell my
> own foo-occurrences function the same way, for consistencies sake.") Great.

The example I enjoy the most is in the HTTP protocol, part of how the World
Wide Web works.  A common header is
        Referer: http://[...]
which indicates the immediately preceding web page that the user was visiting
before arriving at the current page being requested.

The correct English spelling is "referrer", but Tim Berners-Lee (who invented
the web) made a spelling error in the first version of the protocol.  Since
this is a machine-to-machine protocol anyway, and it would have broken
backward compatibility, there wasn't any point to correcting it later, so the
misspelling sticks.

(The web has become so popular, and that's an unusual enough word, and the
mistaken spelling is logical enough, that I predict Tim's error may actually
become a force for changing the "proper" spelling of that word.  Perhaps in a
few decades the HTTP spelling will be listed in dictionaries along with the
current spelling as alternative correct usages.)

        -- Don
_______________________________________________________________________________
Don Geddis                  http://don.geddis.org/               ···@geddis.org
From: Pascal Bourguignon
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <87fzgxmlv9.fsf@thalassa.informatimago.com>
Don Geddis <···@geddis.org> writes:
> The correct English spelling is "referrer", but Tim Berners-Lee (who invented
> the web) made a spelling error in the first version of the protocol.  Since
> this is a machine-to-machine protocol anyway, and it would have broken
> backward compatibility, there wasn't any point to correcting it later, so the
> misspelling sticks.
> 
> (The web has become so popular, and that's an unusual enough word, and the
> mistaken spelling is logical enough, that I predict Tim's error may actually
> become a force for changing the "proper" spelling of that word.  Perhaps in a
> few decades the HTTP spelling will be listed in dictionaries along with the
> current spelling as alternative correct usages.)

That's already the case:

From The Free On-line Dictionary of Computing (27 SEP 03) [foldoc]:

  referer
       
          <World-Wide Web> A misspelling of "referrer" which somehow
          made it into the HTTP standard.  A given web page's
          referer (sic) is the URL of whatever web page contains the
          link that the user followed to the current page.  Most
          browsers pass this information as part of a request.
       
          (1998-10-19)
       
       

-- 
__Pascal_Bourguignon__
http://www.informatimago.com/
From: Christopher C. Stacy
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <uvfpszxe5.fsf@dtpq.com>
It's surprising to me that the latest version of HTTP does 
not specify an additional valid header that has identical
semantics to "Referer" (sets the conceptual referrer)
but which is spelled properly.  The API should accept either
spelling in both functional or name string-based interfaces.
From: Alan Crowe
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <86r80ilda2.fsf@cawtech.freeserve.co.uk>
Martin Pomije
> This is my code followed by my test cases for Exercise 3
> on p. 56 of that book.

I am enormously impressed by Martin's ingenuity.
With this code:

          (setf (cdr scan-point) 
                (cons (cons symbol count) insertion-point))

he destructively inserts an item into a list. Graham doesn't
teach how to do this until Figure 12.7 in Chapter 12,
and Martin is only on Chapter 3.

I found Figure 12.7 a real challenge. What did I do 18
months ago, when I tackled Chapter 3?

(defun one-more(name table)
  (let ((res (assoc name table)))
    (if res
        (progn
          (incf (cdr res))
          table)
      (cons (cons name 1) table))))

(defun occurrences (rep-list)
  (sort (do ((l rep-list (cdr l))
             (table nil (one-more (car l) table)))
            ((null l) table))
        #'> :key 'cdr))
                  
Graham introduces the :key argument to Member on page 44,
Sort on page 46, and Assoc on page 51, so I'm pretty sure
that the point of Exercise 3 on page 56 is to practise the
use of assoc, sort and :key. 

Exercise 3b) Try using Sort with an anonymous lambda
    expression as the test, instead of using a key function.
    Why is Graham introducing the "advanced" feature of
    keyword arguments, such as :test and :key, so early in
    his book?

Alan Crowe
From: Kenny Tilton
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <PAerb.56709$Gq.11745360@twister.nyc.rr.com>
Alan Crowe wrote:
> Martin Pomije
> 
>>This is my code followed by my test cases for Exercise 3
>>on p. 56 of that book.
> 
> 
> I am enormously impressed by Martin's ingenuity.
> With this code:
> 
>           (setf (cdr scan-point) 
>                 (cons (cons symbol count) insertion-point))

Yes, the lad shows great promise. Lots of buzz among the scouts. Should 
go early in the open software project draft. The league is looking into 
the Lexus he started driving around in this week -- that "CL-PDF" 
license plate need explaining.

:)

kenny


-- 
http://tilton-technology.com

Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film

Your Project Here! http://alu.cliki.net/Industry%20Application
From: Martin Pomije
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <90ac4ec2.0311100101.77d38d2f@posting.google.com>
······@MartinPomije.eiomail.com (Martin Pomije) wrote in message news:<····························@posting.google.com>...
(Bunch of convoluted crap)

Well, I'm amazed at everyone's generosity here.  Thanks to everyone
who wrote in.

Of course spelling the name of a library function is vitally
important.  I have let myself become dependent on automatic spelling
correction.

I realize now how awful my design was.  I went off the rails and ended
up trying to create an all-terrain locomotive instead of recognizing
that there was a problem. I have been reading Introduction to
Algorithms by Cormen, Leiseron, and Rivest which I think influenced me
to focus on the optimization of always keeping the association list in
sorted order to maximize the efficiency of searching through it.  Not
to say that it's their fault, but it put me into a mode that made
micro-optimization seem to make sense.  There might be a better way of
keeping this optimization, but it probably isn't worth it.

This reminds me of something that I saw recently.  According to 
David Moon,  "Any Bozo can write code!"  All I need now is an orange
wig, some floppy shoes, and a horn and I'll be all set for a job
interview.
(Check out 
http://www.ai.mit.edu/projects/dynlangs/dynlang-wizards-20mar01.mov
at 35 minutes into the movie.)
From: Wolfhard Buß
Subject: Re: I would appreciate a code review
Date: 
Message-ID: <m3d6bx1yzm.fsf@buss-14250.user.cis.dfn.de>
* Martin Pomije:
> working through Paul Graham's ANSI Common Lisp book.

> Define a function that takes a list and returns a list indicating the
> number of times each (eql) element appears, sorted from most common
> element to least common.
>
>>(occurences '(a b a d a c d c a))
> ((A . 4) (C . 2) (D . 2) (B . 1))

Yet another suggestion for occurrences:

 (defun occurrences (list &key (test #'eql) (key #'identity))
   (let ((alist ()))
     (dolist (item list (stable-sort (nreverse alist) #'> :key #'cdr))
       (incf (get-assoc (funcall key item) alist :test test :default 0)))))

with get-assoc and (setf get-assoc) modeled on getf and (setf getf).

Example:

 (occurrences '((L 2.0) (i 3) (s 1) (p 2) (! 6/2)) :test #'= :key #'second)
 => ((2.0 . 2) (3 . 2) (1 . 1))


-- 
"Hurry if you still want to see something. Everything is vanishing."
                                       --  Paul C�zanne (1839-1906)