Hi, I am new to LISP, so I apologize if this is a silly question!
I am wondering if there are any general patterns on when the list
returned by the union function will share substructure with its
arguments. Also, will it be eq to one of them iff the other is nil?
Cltl and the spec don't seem to say anything about this :(
(If it's of interest, the context is this. I am parsing logical
formulas. At each syntax node I have (among other things) a list of
variables free for that subformula. This will be the union of those
in its children. IF I KNEW that the union would preserve the
pointers, I could implement a simple binding mechanism by only
(rplac)ing the leafs in the tree. Alternatively, I could do
substitution explicitly, but then I wanna know what happens to those
lists of variables!)
Thanks in advance for any help!
From: Ken Tilton
Subject: Re: substructure sharing in #'union result
Date:
Message-ID: <HcA0j.7$bQ2.0@newsfe08.lga>
···············@gmail.com wrote:
> Hi, I am new to LISP, so I apologize if this is a silly question!
>
> I am wondering if there are any general patterns on when the list
> returned by the union function will share substructure with its
> arguments. Also, will it be eq to one of them iff the other is nil?
> Cltl and the spec don't seem to say anything about this :(
14.2.49 of the CLHS (on union and nunion) does not help? Seems to cover
it, including:
"The result list may be eq to either list-1 or list-2 if appropriate. "
and:
"nunion is permitted to modify any part, car or cdr, of the list
structure of list-1 or list-2. "
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
In article <·············@newsfe08.lga>,
Ken Tilton <···········@optonline.net> wrote:
> ···············@gmail.com wrote:
> > Hi, I am new to LISP, so I apologize if this is a silly question!
> >
> > I am wondering if there are any general patterns on when the list
> > returned by the union function will share substructure with its
> > arguments. Also, will it be eq to one of them iff the other is nil?
> > Cltl and the spec don't seem to say anything about this :(
>
> 14.2.49 of the CLHS (on union and nunion) does not help? Seems to cover
> it, including:
>
> "The result list may be eq to either list-1 or list-2 if appropriate. "
>
> and:
>
> "nunion is permitted to modify any part, car or cdr, of the list
> structure of list-1 or list-2. "
Note that it says "may" and "is permitted to". The OP wanted to know
what he could count on, and the answer is "almost nothing." The
standard gives implementors extreme flexibility in deciding how to share
structure in UNION.
The point of these clauses is to warn programmers not to assume that
UNION returns a fresh result, as such an assumption may result in
problems if you then modify the inputs or the result destructively.
It's not intended as any kind of guarantee of sharing, though.
I think the number of functions whose sharing behavior is specified this
precisely can be counted on one hand. Off the top of my head I can only
think of APPEND (ir always shares the last argument, and copies the
rest) and NCONC (it shares all of them, modifying the cdr of the last
cons in each). Most other functions are specified in the permissive
style above, rather than a prescriptive fashion.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin wrote:
> In article <·············@newsfe08.lga>,
> Ken Tilton <···········@optonline.net> wrote:
>
>
>>···············@gmail.com wrote:
>>
>>>Hi, I am new to LISP, so I apologize if this is a silly question!
>>>
>>>I am wondering if there are any general patterns on when the list
>>>returned by the union function will share substructure with its
>>>arguments. Also, will it be eq to one of them iff the other is nil?
>>>Cltl and the spec don't seem to say anything about this :(
>>
>>14.2.49 of the CLHS (on union and nunion) does not help? Seems to cover
>>it, including:
>>
>>"The result list may be eq to either list-1 or list-2 if appropriate. "
>>
>>and:
>>
>>"nunion is permitted to modify any part, car or cdr, of the list
>>structure of list-1 or list-2. "
>
>
> Note that it says "may" and "is permitted to".
Note that I drew no conclusions and simply threw back on the OP his
assertion that the spec was silent.
> The OP wanted to know
> what he could count on, and the answer is "almost nothing." The
> standard gives implementors extreme flexibility in deciding how to share
> structure in UNION.
And NUNION. I liked that one should not count on the destruction, an
implementation might cons up a whole new structure! I'd be checking all
my code had I known either UNION or NUNION existed (I guess I should be
checking my code for (delete-duplicates (append...))
Fortunately the OP shared with us a snippet description of what he was
up to (effectively, IIUC, an interpreter in which he wanted to bind
values to variables once for all to see) and IIUC then I am a tad
confused as to how union could ever help.
If the children have "lists" (they do not really exist) of variables and
we take the union, then perforce the union (where anything appears but
once) cannot be the same structure (cons cell) as two children might
have. So WTF was the OP thinking. IMNHAUC.
>
> The point of these clauses is to warn programmers not to assume that
> UNION returns a fresh result, as such an assumption may result in
> problems if you then modify the inputs or the result destructively.
> It's not intended as any kind of guarantee of sharing, though.
>
> I think the number of functions whose sharing behavior is specified this
> precisely can be counted on one hand. Off the top of my head I can only
> think of APPEND (ir always shares the last argument, and copies the
> rest) and NCONC (it shares all of them, modifying the cdr of the last
> cons in each). Most other functions are specified in the permissive
> style above, rather than a prescriptive fashion.
>
Word. I think I always consumed that non-destructive functions copied
and that destructives did not. If I cannot get something this basic
straight, maybe I should give up now!
kxo
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
OK, thanks all.
So the answer is NO.
I suspected this much, but I also thought that this situation arose
often enough in LISP for someone to point out "Hey, here is the right
way to do this". I guess I was wrong...
(For those who are still interested:
Seriously though! Haven't you ever had to deal with a structure
(list, tree, network, etc.) of objects where there was a uniform
dependency on a set of entities that were to be bound dynamically, in
any order, to any extent (i.e. some could remain unbound at the end of
computation)? It would be nice if there was an efficient (O(1)) way
to update this dependency, s.t. all of the objects which reference a
particular entity get their "type" updated from, say, A->B->bool to A-
>bool whenever the entity of type B gets bound.
Of course, one could always "just do it somehow", but I really
believed that for this situation there would be "the LISP way"! )
Cheers,
Andrew
On Nov 21, 2:20 pm, Ken Tilton <···········@optonline.net> wrote:
> Barry Margolin wrote:
> > In article <·············@newsfe08.lga>,
> > Ken Tilton <···········@optonline.net> wrote:
>
> >>···············@gmail.com wrote:
>
> >>>Hi, I am new to LISP, so I apologize if this is a silly question!
>
> >>>I am wondering if there are any general patterns on when the list
> >>>returned by the union function will share substructure with its
> >>>arguments. Also, will it be eq to one of them iff the other is nil?
> >>>Cltl and the spec don't seem to say anything about this :(
>
> >>14.2.49 of the CLHS (on union and nunion) does not help? Seems to cover
> >>it, including:
>
> >>"The result list may be eq to either list-1 or list-2 if appropriate. "
>
> >>and:
>
> >>"nunion is permitted to modify any part, car or cdr, of the list
> >>structure of list-1 or list-2. "
>
> > Note that it says "may" and "is permitted to".
>
> Note that I drew no conclusions and simply threw back on the OP his
> assertion that the spec was silent.
>
> > The OP wanted to know
> > what he could count on, and the answer is "almost nothing." The
> > standard gives implementors extreme flexibility in deciding how to share
> > structure in UNION.
>
> And NUNION. I liked that one should not count on the destruction, an
> implementation might cons up a whole new structure! I'd be checking all
> my code had I known either UNION or NUNION existed (I guess I should be
> checking my code for (delete-duplicates (append...))
>
> Fortunately the OP shared with us a snippet description of what he was
> up to (effectively, IIUC, an interpreter in which he wanted to bind
> values to variables once for all to see) and IIUC then I am a tad
> confused as to how union could ever help.
>
> If the children have "lists" (they do not really exist) of variables and
> we take the union, then perforce the union (where anything appears but
> once) cannot be the same structure (cons cell) as two children might
> have. So WTF was the OP thinking. IMNHAUC.
>
>
>
> > The point of these clauses is to warn programmers not to assume that
> > UNION returns a fresh result, as such an assumption may result in
> > problems if you then modify the inputs or the result destructively.
> > It's not intended as any kind of guarantee of sharing, though.
>
> > I think the number of functions whose sharing behavior is specified this
> > precisely can be counted on one hand. Off the top of my head I can only
> > think of APPEND (ir always shares the last argument, and copies the
> > rest) and NCONC (it shares all of them, modifying the cdr of the last
> > cons in each). Most other functions are specified in the permissive
> > style above, rather than a prescriptive fashion.
>
> Word. I think I always consumed that non-destructive functions copied
> and that destructives did not. If I cannot get something this basic
> straight, maybe I should give up now!
>
> kxo
>
> --http://www.theoryyalgebra.com/
>
> "In the morning, hear the Way;
> in the evening, die content!"
> -- Confucius
> particular entity get their "type" updated from, say, A->B->bool to A->bool whenever the entity of type B gets bound.
I meant:
"A -> B -> bool"
becomes
"A -> bool"
···············@gmail.com wrote:
> OK, thanks all.
>
> So the answer is NO.
>
> I suspected this much, but I also thought that this situation arose
> often enough in LISP for someone to point out "Hey, here is the right
> way to do this". I guess I was wrong...
No, the problem is that you asked a different question about union and
shared structure and then parenthetically described really badly your
problem on which it now seems you were looking for help.
>
> (For those who are still interested:
>
> Seriously though! Haven't you ever had to deal with a structure
> (list, tree, network, etc.) of objects where there was a uniform
> dependency on a set of entities that were to be bound dynamically, in
> any order, to any extent (i.e. some could remain unbound at the end of
> computation)? It would be nice if there was an efficient (O(1)) way
> to update this dependency, s.t. all of the objects which reference a
> particular entity get their "type" updated from, say, A->B->bool to A-
>
>>bool whenever the entity of type B gets bound.
>
> Of course, one could always "just do it somehow", but I really
> believed that for this situation there would be "the LISP way"! )
Heavens no, Lisp is a snowflake language, no two programmers or
solutions are ever the same. This is partly thru determined NIHism and
partly from the fact that the language is so big that the odds of any
two bits of code being the same is effectively zero.
The bad news is that your desire for the right way is terribly common in
noobs and is a pretty good sign you should go back to Java.
hth, kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
P� Wed, 21 Nov 2007 15:53:54 +0100, skrev <···············@gmail.com>:
>
> Seriously though! Haven't you ever had to deal with a structure
> (list, tree, network, etc.) of objects where there was a uniform
> dependency on a set of entities that were to be bound dynamically, in
> any order, to any extent (i.e. some could remain unbound at the end of
> computation)? It would be nice if there was an efficient (O(1)) way
> to update this dependency, s.t. all of the objects which reference a
> particular entity get their "type" updated from, say, A->B->bool to A-
>> bool whenever the entity of type B gets bound.
> Of course, one could always "just do it somehow", but I really
> believed that for this situation there would be "the LISP way"! )
>
If you are thinking of a order n way to do a union you will have to write
your own. The problem seems to be that the function as defined in the
hyper-spec is to general to allow a order n algorithms. This has come up
before. You have to roll your own. There seems to be two ways about it.
Hash a sequence and then compare the other to it. This is of order n. Or
alternately keep the set elements for both sequences in a sorted order.
This allows the set's to be merged (removing duplicates) in a order n
algorithm.
(If you have a binary tree A* or such this works as well.)
I haven't really been following this thread so sorry if this seems off
topic.
--------------
John Thingstad
In article
<····································@p69g2000hsa.googlegroups.com>,
···············@gmail.com wrote:
> Seriously though! Haven't you ever had to deal with a structure
> (list, tree, network, etc.) of objects where there was a uniform
> dependency on a set of entities that were to be bound dynamically, in
> any order, to any extent (i.e. some could remain unbound at the end of
> computation)? It would be nice if there was an efficient (O(1)) way
> to update this dependency, s.t. all of the objects which reference a
> particular entity get their "type" updated from, say, A->B->bool to A-
> >bool whenever the entity of type B gets bound.
> Of course, one could always "just do it somehow", but I really
> believed that for this situation there would be "the LISP way"! )
I'm still not sure how reliable sharing would help with this. The
common solution for binding is simply to push the new binding onto the
front of the list; all the references to the original state will not
include this new binding, and it can be popped to revert everything at
the end of the computation.
But in your case you say you want to be able to unbind in a non-LIFO
order. This is where sharing is likely to get you into trouble, because
you need to pull items out of the middle.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
> But in your case you say you want to be able to unbind in a non-LIFO
> order. This is where sharing is likely to get you into trouble, because
> you need to pull items out of the middle.
Exactly. There has GOT to be a way to pull the items out of the
middle efficiently.
So if you have a network of objects, and some of them have a reference
to X in a list, I want to make X disappear from each of those lists
whenever X gets bound.
MAYBE the ONLY way to do it is to have X carry around the list of
those cons cells which have it as their cadr (the positions within
those lists preceding X), and then run
(dolist (i (cdr X)) (rplacd i (cddr i)))
whenever X gets bound. However, I sincerely hoped that there would be
a quicker way of doing it. Substructure sharing for example.
Cheers!
Andrew
P� Thu, 22 Nov 2007 16:19:42 +0100, skrev <···············@gmail.com>:
>> But in your case you say you want to be able to unbind in a non-LIFO
>> order. This is where sharing is likely to get you into trouble, because
>> you need to pull items out of the middle.
>
> Exactly. There has GOT to be a way to pull the items out of the
> middle efficiently.
> So if you have a network of objects, and some of them have a reference
> to X in a list, I want to make X disappear from each of those lists
> whenever X gets bound.
> MAYBE the ONLY way to do it is to have X carry around the list of
> those cons cells which have it as their cadr (the positions within
> those lists preceding X), and then run
> (dolist (i (cdr X)) (rplacd i (cddr i)))
> whenever X gets bound. However, I sincerely hoped that there would be
> a quicker way of doing it. Substructure sharing for example.
>
> Cheers!
> Andrew
Are you refering to weak pointers. They are usually used in caching etc.
Some implementations have them. (Like LispWorks)
--------------
John Thingstad
John Thingstad wrote:
> P� Thu, 22 Nov 2007 16:19:42 +0100, skrev <···············@gmail.com>:
>
>>> But in your case you say you want to be able to unbind in a non-LIFO
>>> order. This is where sharing is likely to get you into trouble, because
>>> you need to pull items out of the middle.
>>
>> Exactly. There has GOT to be a way to pull the items out of the
>> middle efficiently.
>> So if you have a network of objects, and some of them have a reference
>> to X in a list, I want to make X disappear from each of those lists
>> whenever X gets bound.
>> MAYBE the ONLY way to do it is to have X carry around the list of
>> those cons cells which have it as their cadr (the positions within
>> those lists preceding X), and then run
>> (dolist (i (cdr X)) (rplacd i (cddr i)))
>> whenever X gets bound. However, I sincerely hoped that there would be
>> a quicker way of doing it. Substructure sharing for example.
>>
>> Cheers!
>> Andrew
>
> Are you refering to weak pointers. They are usually used in caching etc.
> Some implementations have them. (Like LispWorks)
Actually, most implementations have them.
See also http://www.cliki.net/trivial-garbage
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/
In article <···············@newsfe10.lga>,
Ken Tilton <···········@optonline.net> wrote:
> Word. I think I always consumed that non-destructive functions copied
> and that destructives did not.
When you CONSUME, you make a CONS out of U and ME. Is that a Lispian
slip?
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin wrote:
> In article <···············@newsfe10.lga>,
> Ken Tilton <···········@optonline.net> wrote:
>
>
>>Word. I think I always consumed that non-destructive functions copied
>>and that destructives did not.
>
>
> When you CONSUME, you make a CONS out of U and ME.
Priceless.
:)
kenneth
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
···············@gmail.com wrote:
> Hi, I am new to LISP, so I apologize if this is a silly question!
>
> I am wondering if there are any general patterns on when the list
> returned by the union function will share substructure with its
> arguments. Also, will it be eq to one of them iff the other is nil?
> Cltl and the spec don't seem to say anything about this :(
>
> (If it's of interest, the context is this. I am parsing logical
> formulas. At each syntax node I have (among other things) a list of
> variables free for that subformula. This will be the union of those
> in its children. IF I KNEW that the union would preserve the
> pointers, I could implement a simple binding mechanism by only
> (rplac)ing the leafs in the tree. Alternatively, I could do
> substitution explicitly, but then I wanna know what happens to those
> lists of variables!)
The entries in sets can be more complex objects than just plain symbols.
Just put CLOS objects representing variables in your sets and modify
some slot representing a binding in each object. The CLOS notion of
unbound slots is even a pretty direct and appropriate way of
representing free variables.
Union uses #'eql for comparison by default, which respects object
identity. So the union of two lists is guaranteed to contain the same
objects (under #'eql) as the original lists. This means that side
effecting slots in those objects gives you the semantics you want, no
matter how union works.
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/
Thanks for the suggestion, that's essentially what I am trying to do
(using cons instead of objects tho), but I run into the problem
REMOVING the references to variables from those lists when they get
bound. This will happen often, so I want it to be efficient, but it
seems that just going naively through the tree, I will always have to
check whether or not I removed the reference already (because of
substructure sharing between parent and children). So I wonder if
there's any "predictable" behavior that could be exploited.
It seems that there should be an easy way to do this, but I just can't
see it!
Andrew
On Nov 20, 11:30 am, Pascal Costanza <····@p-cos.net> wrote:
> ···············@gmail.com wrote:
> > Hi, I am new to LISP, so I apologize if this is a silly question!
>
> > I am wondering if there are any general patterns on when the list
> > returned by the union function will share substructure with its
> > arguments. Also, will it be eq to one of them iff the other is nil?
> > Cltl and the spec don't seem to say anything about this :(
>
> > (If it's of interest, the context is this. I am parsing logical
> > formulas. At each syntax node I have (among other things) a list of
> > variables free for that subformula. This will be the union of those
> > in its children. IF I KNEW that the union would preserve the
> > pointers, I could implement a simple binding mechanism by only
> > (rplac)ing the leafs in the tree. Alternatively, I could do
> > substitution explicitly, but then I wanna know what happens to those
> > lists of variables!)
>
> The entries in sets can be more complex objects than just plain symbols.
> Just put CLOS objects representing variables in your sets and modify
> some slot representing a binding in each object. The CLOS notion of
> unbound slots is even a pretty direct and appropriate way of
> representing free variables.
>
> Union uses #'eql for comparison by default, which respects object
> identity. So the union of two lists is guaranteed to contain the same
> objects (under #'eql) as the original lists. This means that side
> effecting slots in those objects gives you the semantics you want, no
> matter how union works.
>
> 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/
···············@gmail.com wrote:
> Thanks for the suggestion, that's essentially what I am trying to do
> (using cons instead of objects tho), but I run into the problem
> REMOVING the references to variables from those lists when they get
> bound.
Why is that important? Can't you just ignore them?
Pascal
> This will happen often, so I want it to be efficient, but it
> seems that just going naively through the tree, I will always have to
> check whether or not I removed the reference already (because of
> substructure sharing between parent and children). So I wonder if
> there's any "predictable" behavior that could be exploited.
> It seems that there should be an easy way to do this, but I just can't
> see it!
> Andrew
>
> On Nov 20, 11:30 am, Pascal Costanza <····@p-cos.net> wrote:
>> ···············@gmail.com wrote:
>>> Hi, I am new to LISP, so I apologize if this is a silly question!
>>> I am wondering if there are any general patterns on when the list
>>> returned by the union function will share substructure with its
>>> arguments. Also, will it be eq to one of them iff the other is nil?
>>> Cltl and the spec don't seem to say anything about this :(
>>> (If it's of interest, the context is this. I am parsing logical
>>> formulas. At each syntax node I have (among other things) a list of
>>> variables free for that subformula. This will be the union of those
>>> in its children. IF I KNEW that the union would preserve the
>>> pointers, I could implement a simple binding mechanism by only
>>> (rplac)ing the leafs in the tree. Alternatively, I could do
>>> substitution explicitly, but then I wanna know what happens to those
>>> lists of variables!)
>> The entries in sets can be more complex objects than just plain symbols.
>> Just put CLOS objects representing variables in your sets and modify
>> some slot representing a binding in each object. The CLOS notion of
>> unbound slots is even a pretty direct and appropriate way of
>> representing free variables.
>>
>> Union uses #'eql for comparison by default, which respects object
>> identity. So the union of two lists is guaranteed to contain the same
>> objects (under #'eql) as the original lists. This means that side
>> effecting slots in those objects gives you the semantics you want, no
>> matter how union works.
>>
>> 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/
>
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/