[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Collecting items

The task for this week is to write an extremely fast piece of code
that pulls items onto the back of a list, and then returns the list,
similar to the "collecting" feature in the LOOP macro.
The code has to run not only on a Symbolics but also under Common Lisp
on a Sun and under Franz's Allegro CL on a Sequent, so Symbolics-specific
functions such as SYS:VARIABLE-LOCATION are out.  The code should be
reentrant.  LOOP can't be used because of a convoluted control flow.

The Symbolics LOOP solution hinges on three magic statements:
  (setq #G-accum-1 NIL)
  (setq pointer (SYS:VARIABLE-LOCATION #G-accum-1))
  (rplacd pointer (setq pointer (ncons 'Item-1)))
  (rplacd pointer (setq pointer (ncons 'Item-2)))
where #G-accum-1 is a gensym that has somehow been inserted into the
code twice, presumably using a macro.  Pointer is also a gensym'd
symbol in the original code, but I don't see why; it seems better
to leave it as a local var, which presumably gets allocated on the stack
and then deallocated later when the enclosing routine exits.
For that matter, I don't see why the accumulator should be a gensym
either, since the value of the accumulator is returned at last,
not the accum itself.  As far as I can see.
  The RPLACD idiom is subtle but I think it should work.  It seems
to base its behavior on the assumption that the first argument
[pointer] gets evaluated before the second arguement [the setq]
does.  Is this a valid assumption in general, or at least for the
machines listed?

  One of the main problems with building a collection routine is
that RPLACD does not work on a variable whose contents are ().
It thus seems necessary, in the general case, to start the 
program out with a real list to build upon.
  The first-pass solution is the following:
(defun collect-and-do-stuff (item1 item2)
  (let* ((accum  '(junk))      ;This is sloppy but it avoids too much Symbolics magic.
	 (point  accum)
    ;Do stuff.

    ;Copy item1 onto accum stack.
    (rplacd point (setq point (ncons item1)))
    ;Do more stuff.

    ;Copy item2 onto accum stack.
    (rplacd point (setq point (ncons item2)))
    ;Return the results.
    (cdr accum)

This routine does the proper thing.  When it's interpreted.
When it's compiled, it breaks with the following error message:

Error: Attempt to RPLACD a list that is embedded in a structure and
       therefore cannot be RPLACD'ed.  The list is (JUNK)

This is just plain WEIRD.  I can't understand how a list can be
"embedded" in a structure, and how that could possibly prevent me
from replacing its CDR cell.  I don't understand what structure
it is talking about, and why this could possibly work differently
when it's interpreted vs. when it's compiled.

How do I make pieces of portable code that perform collecting behavior?

John Myers      myers@atr-la.atr.co.jp