oldk1331 wrote:
>
> On 11/23/18 3:42 AM, Waldek Hebisch wrote:
> > oldk1331 wrote:
> >> "node?(u, v)" should return true only when they point to the
> >> same data structure, aka when they share part of data structure,
> >> so it should use 'eq?' instead of '='.
> >>
> >> Because this is much more faster and fits well to functional
> >> programming style.
> >
> > Well, this is controversial. Theoreticaly aggregate can be
> > represented in a compressed way and create nodes only on
> > demand, so that '=' is true, but not 'eq?'. More realistically
> > user my create a node which should be '=' to some node in
> > the aggregate and use say search to find position. With 'eq?'
> > such code would fail.
>
> Even in such cases, there exists _equality_ that can be tested
> in O(1) instead of O(N).
Well, 'eq?' gives you positive answer in O(1). '=' normally
gives you negative answer just after few comparizons.
So if you first test for 'eq?' and then do full thing
expected time is similar to just using 'eq?'.
> In this compressed representation,
> we can use such operation to replace 'eq?'.
>
> Searching should still use "=", the change with "node?' doesn't
> conflict with that.
>
> > I am not sure if the two reasons above are important enough
> > to always use '='. But if we decide to use 'eq?' it would
> > need some big red scare in documentation. Also, bugs due to
> > using 'eq?' are likely to be hard to find. In the past
> > code used '=' and 'eq?' was limited to use as an optimization
> > (with appropriate care to avoid bugs).
> >
>
> I think the idea behind RecursiveAggregate is to encourage sharing
> data structure through linking (by pointer). And "node?(x, y)" asks
> the question that if x is part of y. It doesn't make sense
> to say "a copy of part of y" is still part of y.
It make sense. Namely, old trick is to compress tree by sharing
of subtrees. ATM simplest (and inefficient) way to detect shared
subtree is delete a subtree and to call 'node?'.
Mathematicaly there is no such thing as a copy: two things are
either equal (and treated as the same thing) or not. Put
it differently: copy at programming language level is still
the same thing. And re-building something from part is still
the same thing. Another question is if we want to support
this. It is reasonable to say that the test in 'node?' uses
'eq?' but given that FriCAS normally uses '=' that requires
resonaby prominent mention in documentation.
To be clearer, I have many times found situations when person 1
says "nobody needs feature F", while person 2 writes large
program that depends on feature F. So my point is that
saying 'It doesn't make sense' or 'nobody expect this' is
not helpful -- somebody _surely_ expect current behaviour.
In fact, current code may by just inattention to performance,
but equally likely author of current code deliberatly
used '=' to get "correct" semantics.
>
> Function "distance" is also similar in spirit, I think it makes
> most sense when we are talking about "how many nodes between two
> pointers that point to the same structure".
> (And current declaration of 'distance' doesn't require BasicType.)
Well, ATM for me main problem is what 'distance' should mean.
Then make sure that code actually implements this definition
(if current code is correct than I would say that definition
is a bit weird).
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
