Subject: Re: Request for comments on CLOS code
From: (Rob Warnock)
Date: Tue, 31 Aug 2004 22:50:26 -0500
Newsgroups: comp.lang.lisp
Message-ID: <>
Peter Lewerin <> wrote:
| (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.


[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! */
	    tmp->next = NIL;	/* required if *not* done in enqueue */
	return tmp;

Rob Warnock			<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607