Collecting items

[barmar@Think.COM (Barry Margolin)]

    Date: Thu, 8 Aug 1991 08:09 EDT
    From: kddlab!atr-la.atr.co.jp!myers@uunet.UU.NET (John K. Myers)

    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?

Yes, Common Lisp requires that arguments be evaluated left-to-right (or,
as I like to put it, car-to-cdr).  But don't try using that idiom if you
port your code to Scheme, which has no such requirement.

      One of the main problems with building a collection routine is
    that RPLACD does not work on a variable whose contents are ().

That's why the Symbolics code uses a locative.

    It thus seems necessary, in the general case, to start the 
    program out with a real list to build upon.

That's right.  Locatives were invented for the Lisp Machine precisely to
obviate these gratuitous initial conses, but you can frequently interchange
locatives and conses (that's why the CDR instruction is used to
dereference both of them).

      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.

What it's saying, in a convoluted way, is that you tried to modify a
constant; see p.115 of CLtL 2nd Edition for a description of this
restriction.  The "structure" that the list is embedded in is the
compiled function object.

If it worked, it would have actually modified the original
constant in the code, which could affect future invocations.  In this
particular case, the logic of the program is such that these
modifications don't affect the behavior, but try interpreting the
following definition, and then calling it twice:

(defun broken (x)
  (let ((temp '(junk)))
    (nconc (last temp) (list x))
    temp))

I didn't know that Genera detected this.  Unfortunately, it only detects
it for lists, as a side effect of other checks (it notices that the list
is allocated in a structure region rather than a list region).  It
doesn't detect attempts to modify constant arrays.

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

Instead of '(junk), use (list 'junk).  This is guaranteed to make a new
cons each time through.

                                                barmar