Re: substructure sharing in #'union result

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...@xxxxxxxxx> wrote:
andrew.polon...@xxxxxxxxx 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/

.

Relevant Pages

  • Re: substructure sharing in #union result
    ... This will be the union of those ... Just put CLOS objects representing variables in your sets and modify some slot representing a binding in each object. ... So the union of two lists is guaranteed to contain the same objects (under #'eql) as the original lists. ...
    (comp.lang.lisp)
  • Re: substructure sharing in #union result
    ... REMOVING the references to variables from those lists when they get ... This will be the union of those ... Just put CLOS objects representing variables in your sets and modify ...
    (comp.lang.lisp)
  • SQL Injection: Issue with UNION SELECT ALL
    ... using a UNION SELECT ALL statement. ... an equal number of expressions in their target lists. ... Column 'a.id' is invalid in the select list because it is not contained ... in an aggregate function and there is no GROUP BY clause. ...
    (Pen-Test)
  • RE: report that includes multi tables
    ... report by last name and not have to go through each report by year, ... The next question I have is how to do a UNION instead of a JOIN. ... You couldn't join the two lists because ... >> is auto generated. ...
    (microsoft.public.access.gettingstarted)
  • Re: Cantor Confusion
    ... The union of all finite trees contains all terms of the sequence ... with n in N and a_n in representing t real number r. ...
    (sci.math)
Loading