Just a check on my comprehension: (nconc x y) should be an ok
substitute for append in functional code if x is freshly cons'd. e.g.
(nconc (list 'a 'b 'c) y)?
Also is it an error (according to ansi) to use a literal with nconc:
(nconc '(a b c) y)?
Matt
On Tue, 13 Jan 2009 12:23:35 -0800, Matthew D. Swank wrote:
> Just a check on my comprehension: (nconc x y) should be an ok substitute
> for append in functional code if x is freshly cons'd. e.g. (nconc (list
> 'a 'b 'c) y)?
yes, but make sure that all conses are freshly-created. non-destructive
functions may return lists that share some conses with their arguments:
"The result of remove may share with sequence; the result may be
identical to the input sequence if no elements need to be removed."
> Also is it an error (according to ansi) to use a literal with nconc:
> (nconc '(a b c) y)?
modifying a literal value is illegal, so (nconc '(a b c) y) is bad, but
(nconc y '(a b c)) is good but still inadvisable.
From: Tobias C. Rittweiler
Subject: Re: nconc and functional code
Date:
Message-ID: <877i4zx7xs.fsf@freebits.de>
"Matthew D. Swank" <··················@gmail.com> writes:
> Just a check on my comprehension: (nconc x y) should be an ok
> substitute for append in functional code if x is freshly cons'd. e.g.
> (nconc (list 'a 'b 'c) y)?
NCONC allows for dotted lists.
> Also is it an error (according to ansi) to use a literal with nconc:
> (nconc '(a b c) y)?
It is not an error but it results in undefined behaviour.
-T.
Matthew D. Swank wrote:
> Just a check on my comprehension: (nconc x y) should be an ok
> substitute for append in functional code if x is freshly cons'd. e.g.
> (nconc (list 'a 'b 'c) y)?
(nconc x y) is ok if you know for sure that nobody is going to refer to
whatever x referred to anymore. (nconc (list 'a 'b 'c) y) is a special
case because there it is trivial to know that. But it can also be used
in other circumstances, for example as in:
(setq *x* (nconc *x* y))
If you know that nobody keeps a reference to what *x* referred to, you
are also safe. It may be harder to convince yourself of the truth of
this fact, though.
(And there are even situations where _some_ kinds of reference to what
*x* referred are also ok.)
When in doubt, opt for append instead. nconc is only necessary for
optimization, and the general rules for optimization apply: Don't do it
unless you're sure that it actually gains something - which you can only
know for sure after profiling your program.
Furthermore, the real optimization comes from avoiding append and nconc
altogether: They have to traverse all input lists but the last ones, and
that is potentially very costly. Instead, try to reformulate your
algorithms in such a way that you keep on pushing something to the front
of the list, and possibly eventually reverse or nreverse the result.
Other solutions to look out for for avoiding append and nconc are: LOOP
with COLLECT and APPEND and NCONC clauses (which can be implemented more
efficiently than their functional counterparts), and NRECONC. Also
collecting results into an array and eventually coercing it to a list
can be a good solution.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza wrote:
> (nconc x y) is ok if you know for sure that nobody is going to refer to
> whatever x referred to anymore. (nconc (list 'a 'b 'c) y) is a special
> case because there it is trivial to know that. But it can also be used
> in other circumstances, for example as in:
>
> (setq *x* (nconc *x* y))
>
> If you know that nobody keeps a reference to what *x* referred to, you
> are also safe. It may be harder to convince yourself of the truth of
> this fact, though.
Sorry, friend Pascal, your interpretation is incorrect. It doesn't
conform with the ANS.
The intention of the "never modify a constant" restriction in the ANS is
that the implementation (often incorrectly known as the "compiler") is
allowed to place constant objects in read-only space. The theory is
that this might allow better paging behavior, in that objects that could
never be mutated would live on immutable read-only pages, while objects
that might be modified would be collected together in potentially
modifiable heap pages.
So you are not safe, and you code might still trigger exception, even if
you can prove that no one else keeps a reference to the constant.
> When in doubt, opt for append instead. nconc is only necessary for
> optimization, and the general rules for optimization apply: Don't do it
> unless you're sure that it actually gains something - which you can only
> know for sure after profiling your program.
This is also incorrect. While we usually call nconc as a slightly less
consy version of append, the behavior of nconc on the last cons of a
list is well defined by the ANS, and it is quite reasonable to call it
with that side effect in mind. This is very different from the
delete/remove distinction, where delete allows the implementation to
provide either behavior depending on its convenience.
Steven M. Haflich wrote:
> Pascal Costanza wrote:
>
>> (nconc x y) is ok if you know for sure that nobody is going to refer
>> to whatever x referred to anymore. (nconc (list 'a 'b 'c) y) is a
>> special case because there it is trivial to know that. But it can also
>> be used in other circumstances, for example as in:
>>
>> (setq *x* (nconc *x* y))
>>
>> If you know that nobody keeps a reference to what *x* referred to, you
>> are also safe. It may be harder to convince yourself of the truth of
>> this fact, though.
>
> Sorry, friend Pascal, your interpretation is incorrect. It doesn't
> conform with the ANS.
>
> The intention of the "never modify a constant" restriction in the ANS is
> that the implementation (often incorrectly known as the "compiler") is
> allowed to place constant objects in read-only space. The theory is
> that this might allow better paging behavior, in that objects that could
> never be mutated would live on immutable read-only pages, while objects
> that might be modified would be collected together in potentially
> modifiable heap pages.
>
> So you are not safe, and you code might still trigger exception, even if
> you can prove that no one else keeps a reference to the constant.
I was taking the fact that you shouldn't side-effect constant for
granted. But it's good that you stress this again. Thanks.
>> When in doubt, opt for append instead. nconc is only necessary for
>> optimization, and the general rules for optimization apply: Don't do
>> it unless you're sure that it actually gains something - which you can
>> only know for sure after profiling your program.
>
> This is also incorrect. While we usually call nconc as a slightly less
> consy version of append, the behavior of nconc on the last cons of a
> list is well defined by the ANS, and it is quite reasonable to call it
> with that side effect in mind. This is very different from the
> delete/remove distinction, where delete allows the implementation to
> provide either behavior depending on its convenience.
Not quite:
(defvar *x* '())
(nconc *x* '(1 2 3))
*x* => '()
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Thu, 15 Jan 2009 13:00:46 +0100, Pascal Costanza wrote:
>Steven M. Haflich wrote:
>>> When in doubt, opt for append instead. nconc is only necessary for
>>> optimization, and the general rules for optimization apply: Don't do
>>> it unless you're sure that it actually gains something - which you can
>>> only know for sure after profiling your program.
>>
>> This is also incorrect. While we usually call nconc as a slightly less
>> consy version of append, the behavior of nconc on the last cons of a
>> list is well defined by the ANS, and it is quite reasonable to call it
>> with that side effect in mind. This is very different from the
>> delete/remove distinction, where delete allows the implementation to
>> provide either behavior depending on its convenience.
>
> Not quite:
>
> (defvar *x* '())
>
> (nconc *x* '(1 2 3))
>
> *x* => '()
>
>
> Pascal
This example doesn't negate Steven's assertion: *x* does not refer to a
cons.
Matt
--
Q: What's the difference between the 1950's and the 1980's?
A: In the 80's, a man walks into a drugstore and states loudly, "I'd
like some condoms," and then, leaning over the counter, whispers,
"and some cigarettes."
Matthew D Swank wrote:
> On Thu, 15 Jan 2009 13:00:46 +0100, Pascal Costanza wrote:
>> Steven M. Haflich wrote:
>>>> When in doubt, opt for append instead. nconc is only necessary for
>>>> optimization, and the general rules for optimization apply: Don't do
>>>> it unless you're sure that it actually gains something - which you can
>>>> only know for sure after profiling your program.
>>> This is also incorrect. While we usually call nconc as a slightly less
>>> consy version of append, the behavior of nconc on the last cons of a
>>> list is well defined by the ANS, and it is quite reasonable to call it
>>> with that side effect in mind. This is very different from the
>>> delete/remove distinction, where delete allows the implementation to
>>> provide either behavior depending on its convenience.
>> Not quite:
>>
>> (defvar *x* '())
>>
>> (nconc *x* '(1 2 3))
>>
>> *x* => '()
>>
>>
>> Pascal
>
> This example doesn't negate Steven's assertion: *x* does not refer to a
> cons.
Nitpicker! ;)
Allow me to nitpick myself: Steven said "the last cons of a list". NIL
is also a list, but nconc doesn't modify the last cons of NIL.
Or something... ;)
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/