[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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
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.
;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.
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))
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.
- Collecting items
- From: kddlab!atr-la.atr.co.jp!myers@uunet.UU.NET (John K. Myers)