From: Enrico `Trippo' Porreca
Subject: Request for comments on CLOS code
Date:
Message-ID: <412FB387.6050202@people.it>
The following is one of my first experiments with the Common Lisp Object
System: the implementation of a FIFO queue. I'd like to hear your
comments (of any kind) about my code.
(defclass queue ()
((head :initform nil
:accessor head)
(tail :initform nil
:accessor tail)))
(defmethod emptyp ((queue queue))
(null (head queue)))
(defmethod enqueue (object (queue queue))
(let ((new-tail (list object)))
(if (emptyp queue)
(setf (head queue) new-tail)
(rplacd (tail queue) new-tail))
(setf (tail queue) new-tail)))
(defmethod dequeue ((queue queue))
(pop (head queue)))
Thanks in advance.
--
Enrico `Trippo' Porreca
In article <·····················@clgrps12>,
Wade Humeniuk <····································@telus.net> wrote:
> Enrico `Trippo' Porreca wrote:
>
> > (defclass queue ()
> > ((head :initform nil
> > :accessor head)
> > (tail :initform nil
> > :accessor tail)))
> >
> > (defmethod emptyp ((queue queue))
> > (null (head queue)))
> >
> > (defmethod enqueue (object (queue queue))
> > (let ((new-tail (list object)))
> > (if (emptyp queue)
> > (setf (head queue) new-tail)
> > (rplacd (tail queue) new-tail))
> > (setf (tail queue) new-tail)))
> >
> > (defmethod dequeue ((queue queue))
> > (pop (head queue)))
>
> My Mods:
>
> ;; Remove accessors, users shouldn't be calling them, so I would
> ;; remove them
>
> (defclass queue ()
> ((head :initform nil)
> (tail :initform nil)))
>
> ;; Changed because of a lack of accessor
> (defmethod emptyp ((queue queue))
> (null (slot-value queue 'head)))
I disagree. The point of accessors is that they're generic functions,
so they can be overridden or augmented in subclasses, which is an
important feature of OO programming. Otherwise, you might as well be
using DEFSTRUCT rather than DEFCLASS.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Enrico `Trippo' Porreca
Subject: Re: Request for comments on CLOS code
Date:
Message-ID: <412FCC9B.5090204@people.it>
Wade Humeniuk wrote:
> Enrico `Trippo' Porreca wrote:
>
>> (defclass queue ()
>> ((head :initform nil
>> :accessor head)
>> (tail :initform nil
>> :accessor tail)))
>>
>> (defmethod emptyp ((queue queue))
>> (null (head queue)))
>>
>> (defmethod enqueue (object (queue queue))
>> (let ((new-tail (list object)))
>> (if (emptyp queue)
>> (setf (head queue) new-tail)
>> (rplacd (tail queue) new-tail))
>> (setf (tail queue) new-tail)))
>>
>> (defmethod dequeue ((queue queue))
>> (pop (head queue)))
>
>
> My Mods:
>
> ;; Remove accessors, users shouldn't be calling them, so I would
> ;; remove them
It isn't clear from the snippet I posted, but the code is encapsulated
in a package and the accessor names are not exported, so I think the
user won't normally use them anyway.
> (defclass queue ()
> ((head :initform nil)
> (tail :initform nil)))
>
> ;; Changed because of a lack of accessor
> (defmethod emptyp ((queue queue))
> (null (slot-value queue 'head)))
>
> ;; Changed enqueue to build up queue by cons. (for efficiency)
> ;; Enqueue to return obj, this is tends to be useful.
> ;; Use with-slots to make up for lack of accessors.
> (defmethod enqueue (obj (queue queue))
> (with-slots (head tail) queue
> (let ((new-tail (cons obj nil)))
> (if (null head)
> (setf head (setf tail new-tail))
> (setf (cdr tail) new-tail
> tail new-tail)))
> obj))
One question: won't an efficient compiler produce the same code for
(cons obj nil) and for list with a single argument?
> ;; Fixed error in dequeuing, tail must be nulled when last obj
> ;; removed from queue.
Thanks, I missed that. It is a matter of useless references kept around,
right?
> (defmethod dequeue ((queue queue))
> (with-slots (head tail) queue
> (when head
> (prog1 (pop head)
> (unless head (setf tail nil))))))
Thanks a lot for your suggestions.
--
Enrico `Trippo' Porreca
Enrico `Trippo' Porreca <········@people.it> wrote
> System: the implementation of a FIFO queue. I'd like to hear your
> comments (of any kind) about my code.
I think it's a bit awkward with the two slots. As a counter-example:
;; A fifo queue is a container, so it will have contents
;; (initially nil). I don't care about heads or tails yet,
;; and possibly never will.
(defclass fifo ()
((contents :initform nil)))
;; I do want to be able to tell whether the queue is
;; empty or not. When the contents are nil, it is empty.
;; Need head slot? No.
(defmethod emptyp ((q fifo))
(null (slot-value q 'contents)))
;; I also want to be able to add an element. No problem,
;; just NCONC it to the current contents.
;; Need tail slot? No.
(defmethod enqueue (new-value (q fifo))
(with-slots (contents) q
(setf contents (nconc contents (list new-value))))
new-value)
;; Finally, I want to be able to add read-and-discard an
;; element. No problem, just POP the contents.
;; Need head slot? No.
(defmethod dequeue ((q fifo))
(pop (slot-value q 'contents)))
Defined this way, the FIFO becomes a thin wrapper around a standard
list. This is OK, because *behavior* counts here, not representation.
Because if this, I can use standard functions (NCONC, POP) to do
*all* the footwork.
In your implementation you made up your own special representation[1],
so you also needed to make your own access functions. You used an
approximation of NCONC (the (rplacd (tail queue) new-tail) bit) and
standard POP (which turned out to be in error); in the end the
head/tail structure made it *harder* to get the work done, not easier.
[1] implicitly using a list, but without the convenience of a list.
·············@swipnet.se (Peter Lewerin) writes:
> Enrico `Trippo' Porreca <········@people.it> wrote
>> [about] the implementation of a FIFO queue
> [...]
> ;; I also want to be able to add an element. No problem,
> ;; just NCONC it to the current contents.
> ;; Need tail slot? No.
Unless, of course, it is required that the time it takes to add an
element is not proportional to the length of the queue. The
original formulation of the problem didn't say anything about that,
but it should at least be noted.
---Vassil.
--
Vassil Nikolov <········@poboxes.com>
Hollerith's Law of Docstrings: Everything can be summarized in 72 bytes.
Vassil Nikolov <········@poboxes.com> wrote
> Unless, of course, it is required that the time it takes to add an
> element is not proportional to the length of the queue.
Of course. With this added requirement, a tail slot makes sense:
(defclass constant-time-fifo (fifo)
((tail :initform nil)))
;; code due to Wade Humeniuk
(defmethod enqueue (new-value (q constant-time-fifo))
(with-slots (contents tail) q
(let ((new-tail (list new-value)))
(if contents
(setf (cdr tail) new-tail
tail new-tail)
(setf contents (setf tail (list new-value)))))))
·············@swipnet.se (Peter Lewerin) wrote
> Of course. With this added requirement, a tail slot makes sense:
Ooops. Forgot to null the tail slot when the last element is
dequeued. (Actually, it doesn't matter, but anyway.)
(defmethod dequeue :after ((q constant-time-fifo))
(with-slots (contents tail) q
(unless contents
(setf tail nil))))
Peter Lewerin <·············@swipnet.se> wrote:
+---------------
| ·············@swipnet.se (Peter Lewerin) wrote
| > Of course. With this added requirement, a tail slot makes sense:
|
| Ooops. Forgot to null the tail slot when the last element is
| dequeued. (Actually, it doesn't matter, but anyway.)
|
| (defmethod dequeue :after ((q constant-time-fifo))
| (with-slots (contents tail) q
| (unless contents
| (setf tail nil))))
+---------------
Alternatively, you could just as easily do that right
in the primary method itself:
(defmethod dequeue ((q constant-time-fifo))
(with-slots (contents tail) q
(prog1
(pop contents)
(unless contents
(setf tail nil)))))
That way, somebody reading your code doesn't have to
go looking for the :AFTER method. [Plus, it's likely
to be somewhat faster as well.]
Note: I don't have anything against :AFTER methods in
general, but it seems a bit excessive in this case.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) wrote
> Alternatively, you could just as easily do that right
> in the primary method itself:
<snip>
> That way, somebody reading your code doesn't have to
> go looking for the :AFTER method.
You're probably right, but still: isn't that rather contrary to the OO
idea? The added slot doesn't change the way dequeueing is done, it
merely adds a cleanup operation. What if the dequeueing code for
class fifo had been 200 lines? Or if it might change later on,
forcing me to synchronize changes in two classes?
I'd say that by using an :AFTER method (or a specialized primary that
CALL-NEXT-METHODs the original primary), someone reading my code
doesn't have to look at all of the code for dequeueing, just the code
that is directly relevant to the constant-time-fifo class.
Peter Lewerin <·············@swipnet.se> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) wrote
| > Alternatively, you could just as easily do that right
| > in the primary method itself: ...
| > That way, somebody reading your code doesn't have to
| > go looking for the :AFTER method.
|
| You're probably right, but still: isn't that rather contrary to the OO
| idea? The added slot doesn't change the way dequeueing is done, it
| merely adds a cleanup operation.
+---------------
Aha! I think I see the fundamental point on which we disagree.
Having written the classic head/tail singly-linked list algorithm
in everything from assembly language (on a dozen different architectures)
to FORTRAN to SNOBOL to C and now Lisp, I consider the nulling[1]
of the tail pointer when the queue empties to be an integral part
of the correct implementation of the basic dequeue algorithm. It's
*not* some optional "cleanup" -- without it, it's just *broken*!
As such, it belongs with the main code, not stuck off somewhere
where it could be overlooked.
+---------------
| I'd say that by using an :AFTER method (or a specialized primary that
| CALL-NEXT-METHODs the original primary), someone reading my code
| doesn't have to look at all of the code for dequeueing, just the code
| that is directly relevant to the constant-time-fifo class.
+---------------
Since the nulling[1] of the tail pointer *is* "directly relevant
to the constant-time-fifo class" -- and in fact, is what makes it
different at all than its superclass! -- it belongs in the primary
method for that class.
-Rob
[1] In many languages (assembler, C) in which "pointer" has more
dangerous properties than my colloquial usage of the term above
implies in a Lisp context, the tail pointer *is* an actual
pointer, and a variant of the singly-linked list algorithm
is often used in which the empty state of the list has the
head pointer null but has the tail pointer pointing AT THE
HEAD POINTER (or at that offset from it which, when treated
as a pointer to a list element, will cause the head pointer
to be treated as a "next" cell in a list element). In such
variants, enqueueing is done by storing the location of the
new list element *indirectly* through the tail pointer, then
storing the same thing again into the tail pointer -- it is
not necessary to touch the head pointer explicitly at all!!
That is, in C [details of types omitted]:
tail->next = new;
tail = new;
tail->next = NIL; /* optional if guaranteed by make_new */
However, in those same variants, the "nulling" of the tail pointer
when the list becomes empty must be replaced by setting the tail
pointer to point to (or near) the head pointer, e.g. [again ignoring
some of the required coersions]:
tmp = head;
head = tmp->next;
if (NULLP(head))
tail = &head - (long)&(((CELL*)0)->next); /* MUST do this! */
else
tmp->next = NIL; /* required if *not* done in enqueue */
return tmp;
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) wrote
> Aha! I think I see the fundamental point on which we disagree.
That's good, because now *I'm* mystified ;-)
> I consider the nulling[1]
> of the tail pointer when the queue empties to be an integral part
> of the correct implementation of the basic dequeue algorithm.
Yes, if you use a tail pointer in your implementation. In the fifo
class I _don't_, so naturally I don't adjust it. In the
constant-time-fifo class I _do_, and accordingly I adjust it[1]. This
a point of agreement, I think.
> It's *not* some optional "cleanup" -- without it, it's just *broken*!
For me, cleanup doesn't imply being optional at all. Cleanup is just
as vital as any other part of the code, otherwise it wouldn't be
there[2]. As you say, without proper cleanup, the code is broken.
> As such, it belongs with the main code, not stuck off somewhere
> where it could be overlooked.
Important parts of the code should be made easy to find, one more
point of agreement. However: which coding style makes it more likely
to be overlooked:
* putting it in a method of its own.
* creating a new primary method by copying N[3] lines from the
super-primary and sticking it onto those lines.
I believe my code makes the action of nulling the pointer more
explicit, and your code makes it less explicit.
> Since the nulling[1] of the tail pointer *is* "directly relevant
> to the constant-time-fifo class" -- and in fact, is what makes it
> different at all than its superclass! -- it belongs in the primary
> method for that class.
Looking at my code, I read the lack of a primary dequeue and the
addition of an :AFTER dequeue as telling me "dequeueing in
constant-time-fifo is just like in fifo except that something more
needs to be done afterwards, let's see... ah, the tail pointer is
nulled if the queue is emptied."
To you, that may be obfuscation, but to me it's self-documenting code
:-)
The alternative, creating one primary each for enqueue and dequeue
tells me "OK, both enqueue and dequeue use different algorithms than
in fifo, I'd better read both carefully to catch differences". More
confusing.
[1] In an auxiliary method, not "integrally", but the end result is
the same: the :AFTER method will always be called after the primary.
[2] In this particular case, actually nulling the tail pointer is
necessary only for educational purposes, since it's never used without
first being adjusted. In general I totally agree that pointers should
never be allowed to go "bad": I'm the kind of guy who would wrap a
free() call in C in a macro that sets the pointer to NULL.
[3] In this case, N = 1, but what if N = 200? Arguably, it's sinful
to copy even one line if you don't really need to, as you create one
more point of potential need for synchronization.
> The following is one of my first experiments with the Common Lisp Object
> System: the implementation of a FIFO queue. I'd like to hear your
> comments (of any kind) about my code.
>
> (defclass queue ()
> ((head :initform nil
> :accessor head)
> (tail :initform nil
> :accessor tail)))
>
> (defmethod emptyp ((queue queue))
> (null (head queue)))
>
> (defmethod enqueue (object (queue queue))
> (let ((new-tail (list object)))
> (if (emptyp queue)
> (setf (head queue) new-tail)
> (rplacd (tail queue) new-tail))
> (setf (tail queue) new-tail)))
>
> (defmethod dequeue ((queue queue))
> (pop (head queue)))
>
> Thanks in advance.
>
Is there an abstract type compiler in lisp which generates implementation details from the abstract type definition ?
It should have give you the answer.
Christophe Turle.