#496 Is/equal doesn\'t work for [], matrix, etc./FIX

closed
nobody
Lisp Core (471)
5
2012-12-04
2004-01-26
No

Currently, IS doesn't understand semantic-equality of
bags (lists, matrices, sets) at all:

is(equal([1],[1])) => true OK
is(equal([0],[1])) => Unknown NO

The first case only works because the two expressions
are syntactically equal (is/= or ?like).

The problem is that meqp uses compare, which
compares x and y by comparing x-y to (scalar) 0,
obviously irrelevant here. The solution is to explicitly
add bags to meqp and mnqp. See code attached. With
this code, we have:

is(equal([1],[1])) => true
is(equal([0],[1])) => false
is(equal([a,0],[a,1])) => false
is(equal([a,b],[a,c])) => unknown

HOWEVER: a) this code ignores doscmxplus, so lists are
never considered equal to matrices; b) the assume
database is not consulted in cases like equal(x,[a,b]),
because compar thinks this is the same as equal([x-a,x-
b],0).

I considered also adding ordering inequalities (< etc.),
but I don't think it's worth it right now given the limited
capabilities of compar. Also, it's not clear whether
lexicographic ([a,b]<[c,d] iff (a<c or (a=c and b<d)) or
dominating order (a<c and b<d -- non-trichotomic) is
more useful.

This was originally reported by Robert Dodier in email.

Discussion

  • Stavros Macrakis

    Logged In: YES
    user_id=588346

    These are some design notes I posted to the Maxima mailing
    list on this subject.

    Robert Dodier said:

    > is(equal([1],[[1]]))) => UNKNOWN.
    > I would expect that different structures are always not
    > equal, unless they're equivalent (i.e., you could substitute
    > one for the other in any expression and get the same
    result).
    > So either TRUE or FALSE seems possible here, but not
    UNKNOWN.

    I had written code to assume that objects of differing
    dimensions were different (in particular, that non-scalars can
    never be equal to scalars), but ran into a whole bunch of
    inconsistencies in Maxima semantics. These are not
    accidental inconsistencies, they are not bugs; they are in
    fact design features to make the use of Maxima more
    convenient. But as is often the case, convenience conflicts
    with consistency.

    Clearly is(1=[1]) is false; remember, = performs structural
    (syntactic) comparison. However, it is not at all clear
    whether is(equal(1,[1])) is false. (And whether it is False or
    True depends not only on various flag settings, but also the
    context of use.) Consider:

    Lists, 1xn, and nx1 matrices are coerced into each other in
    various ways and with Scalarmatrixp=True (the default), a
    1x1 matrix is converted to a scalar:

    [1,2] . matrix([3],[4]) => 11
    [1,2] . matrix([3,4]) => 11
    matrix([1,2]).matrix([3,4]) => 11
    matrix([1],[2]).matrix([3],[4]) => 11

    So perhaps 11 == [11] and [1,2] == matrix([1,2]) == matrix
    ([1],[2]) ? On the other hand, matrix([11]) by itself does not
    automatically simplify to 11 and 11-[11]=>[0], not 0.

    Of course, outside the context of vector/matrix operations,
    lists, 1xn matrices, and nx1 matrices are completely distinct:
    after all,
    member(a,[a,b]) => true and member(a,matrix([a,b])) =>
    false.

    Now consider symbolic expressions. You might think that
    a==b must be false if nonscalar(a) and scalar(b). But that's
    not true. If you declare(vec,nonscalar), then nonscalar
    (vec.vec) => True, though in fact the .-product of two
    vectors is a scalar (nonscalar is a *syntactic* check for the
    presence of nonscalar objects within the expression tree). So
    it is wrong to assume that is(equal(vec1.vec2,0)) is false
    because nonscalar(vec1.vec2)=True and nonscalar(0)=False.

    This is not theoretical. I think it perfectly reasonable that a
    user might check whether q and r are perpendicular by
    checking is(equal(q.r,0)), where q and r are sometimes
    concrete vectors -- in which case you might well get a valid
    True or False --, sometimes symbols (in which case the
    answer should be Unknown, not False).

    There is another simple case that has nothing to do with
    vector/matrix semantics. To do bag comparisons correctly,
    you need to solve
    conjunctions: [x,x] =? [1,2] is equivalent to (x==1 and x==2),
    which is clearly false, but Is doesn't know it. Similarly for
    [x,1] =? [1,x+1].

    Another limitation on the power of is/equal/bag: the compar
    subsystem is not currently terribly useful for vectors etc. For
    example, assume(equal(q,[a,b])), is(equal(q,[a,b+1])) =>
    Unknown.

    I think there are several possible conclusions for all this:

    1) Make Maxima more rigorous. Distinguish between lists,
    vectors, and 1xn matrices everywhere. Distinguish between
    scalars, 1-vectors, and 1x1 matrices everywhere. In that
    case, the correct results for is/equal are much clearer. But
    pragmatism is one of the central characteristics of Maxima;
    there are certainly other systems which emphasize rigor, with
    its advantages and disadvantages.

    2) Decide that is/equal/bag always refers to .-product
    semantics (not list semantics and not + or * semantics): if
    two objects act the same in the context of a .-product, then
    they are the same.

    2ay) The result of is/equal depends on the various switches
    controlling vector/matrix operations. So if Scalarmatrixp
    and Listarith are true, then 1 == [1] == matrix([1]).

    2by) Assume default settings for the various switches.

    2xa) Consider an n-list, an n-row, and an n-column equal
    (with
    appropriate switches set), even though they don't act
    equally in all contexts.

    2xb) Consider an n-list and an n-row equal, but not an n-
    column.

    3) Decide that is/equal/bag is true iff there is NO context in
    which the objects can be distinguished. This emphasizes the
    programming-type aspect of Maxima over the mathematical
    aspect. But 'equal' is supposed to be about mathematical
    equality. After all, is/equal considers 1/2, 0.5, and 0.5b0 to
    be equal, even though 1/2 is an exact number and 0.5 and
    0.5b0 are approximate.

    3a) Assume that non-scalar *identifiers* (but not non-scalar
    expressions) are never equal to scalars.

    3b) Do not take into account the nonscalar property of
    identifiers.

    4) Maintain the current behavior, which gives Unknown for all
    the difficult cases.

    What I had started out trying to program was 2aa, but it was
    too messy (because when I started, I was also trying to take
    into account the behavior of + and *). Now that I've written
    out this design note, it seems like the two reasonable
    alternatives are 3a and 2ax (not sure whether 2aa or 2ab is
    better). But I suspect that in actual fact, I have already
    spent too much time on this, that no one but Robert will ever
    care, and that 4 is just fine....

     
  • Robert Dodier

    Robert Dodier - 2006-07-22
    • labels: --> Lisp Core
     
  • Robert Dodier

    Robert Dodier - 2006-09-09
    • milestone: --> Includes_proposed_fix
    • summary: Is/equal doesn't work for [], matrix, etc./FIX --> Is/equal doesn\'t work for [], matrix, etc./FIX
     
  • Robert Dodier

    Robert Dodier - 2006-12-19
    • status: open --> closed
     
  • Robert Dodier

    Robert Dodier - 2006-12-19

    Logged In: YES
    user_id=501686
    Originator: NO

    Fixed by r1.16 src/compar.lisp (by Barton Willis).

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks