equality of raw rings

[mahrud]

I couldn't track down where === is defined for arbitrary objects. Is it using equalmethod in actors3.d? I don't understand what lookupBinaryMethod and lookup1 are doing.

debug Core
hash raw ZZ -- 13
hash rawZZ() -- 13
assert(raw ZZ === rawZZ()) -- stdio:4:1:(3): error: assertion failed

[DanGrayson]

To find it, use the TAGS file in the d directory and find "===" with tags search in emacs. It is found in binding.d:

     export EqualEqualEqualS := makeKeyword(binaryright("==="));

Now search for EqualEqualEqualS, finding this:

EqualEqualEqualfun(lhs:Code,rhs:Code):Expr := (
     x := eval(lhs);
     when x is Error do x
     else (
     	  y := eval(rhs);
     	  when y is Error do y
	  else equal(x,y)));
setup(EqualEqualEqualS,EqualEqualEqualfun);

Now we know we have to find "equal", so search for "export equal" with arguments being of type Expr, finding this:

export equal(lhs:Expr,rhs:Expr):Expr := (
     if lhs == rhs then True else 
     when lhs
     is Error do lhs
     is x:List do (
	  when rhs
	  is y:List do (
     	       if x.hash != y.hash
	       || x.Mutable 
	       || y.Mutable
	       || length(x.v) != length(y.v)
	       || x.Class != y.Class && False == equal(x.Class,y.Class) 
	       then False
	       else (
		    foreach z at i in x.v do (
			 if equal(z,y.v.i) == False then return False;
			 );
		    True ) )
	  else False)
     is x:ZZcell do (
	  when rhs 
	  is y:ZZcell do (
	       if x.v === y.v then True else False
	       )
	  -- other cases needed soon
	  else False)
     is x:HashTable do (
	  when rhs
	  is y:HashTable do equal(x,y)
	  else False)		    
     is x:stringCell do (
	  when rhs 
	  is y:stringCell do if x.v === y.v then True else False
	  else False
	  )
     is x:Net do (
	  when rhs
	  is y:Net do if x === y then True else False
	  else False)
     is x:Sequence do (
	  when rhs
	  is y:Sequence do (
	       if length(x) != length(y)
	       then False
	       else (
		    foreach z at i in x do (
			 if equal(z,y.i) == False then return False;
			 );
		    True))
	  else False)
     is Boolean do False
     is Nothing do False
     is file do False
     is CompiledFunction do False
     is CompiledFunctionClosure do False
     is a:DictionaryClosure do (
	  when rhs
	  is b:DictionaryClosure do (
	       if a.frame == b.frame
	       && a.dictionary == b.dictionary		    -- strictly speaking, this part is redundant
	       then True else False
	       )
	  else False)
     is x:QQcell do (
	  when rhs
	  is y:QQcell do (
	       if x.v === y.v then True else False
	       )
	  -- other cases needed soon
	  else False)
     is c:CodeClosure do (
	  when rhs
	  is d:CodeClosure do (
	       if c.frame == d.frame
	       && c.code == d.code
	       then True else False)
	  else False
	  )
     is x:RRcell do (
	  when rhs
	  is y:RRcell do (
	       if strictequality(x.v,y.v) then True else False
	       )
	  else False)
     is x:CCcell do (
	  when rhs
	  is y:CCcell do (
	       if strictequality(x.v,y.v) then True else False
	       )
	  else False)
     is x:SymbolClosure do (
	  when rhs 
	  is y:SymbolClosure do (
       	       if x === y
	       then True else False
	       )
	  else False
	  )
     is x:SymbolBody do (
	  when rhs is y:SymbolBody do if x.symbol == y.symbol then True else False
	  else False)
     is FunctionClosure do False
     is NetFile do False
     is RawMonomialOrderingCell do False
     is RawMonoidCell do False
     is x:RawMonomialCell do (
	  when rhs
	  is y:RawMonomialCell do (
	       if Ccode(bool, "(",x.p,")->is_equal(*(",y.p,"))")
	       then True else False
	       )
	  else False
	  )
     is RawRingCell do False
     is x:RawMonomialIdealCell do (
	  when rhs
	  is y:RawMonomialIdealCell do (
	       r := Ccode(int, "IM2_MonomialIdeal_is_equal(",x.p,",",y.p,")");
	       if r == -1 then engineErrorMessage() else toExpr(r == 1))
	  else False
	  )
     is x:RawRingElementCell do (
	  when rhs
	  is y:RawRingElementCell do (
	       if Ccode(bool, "IM2_RingElement_is_equal(",x.p,",",y.p,")")
	       then True else False
	       )
	  else False
	  )
     is x:RawFreeModuleCell do (
	  when rhs
	  is y:RawFreeModuleCell do (
	       if Ccode(bool, "IM2_FreeModule_is_equal(",x.p,",",y.p,")")
	       then True else False
	       )
	  else False
	  )
     is x:RawMatrixCell do (
	  when rhs
	  is y:RawMatrixCell do toExpr(Ccode(bool, "1 == IM2_Matrix_is_equal(",x.p,",",y.p,")"))
	  else False
	  )
     is x:MysqlConnectionWrapper do (
	  when rhs
	  is y:MysqlConnectionWrapper do if x.mysql == y.mysql then True else False
	  else False
	  )
     is MysqlFieldWrapper do False
     is MysqlResultWrapper do False
     is RawMutableMatrixCell do False			    -- mutable matrices may not stay equal, so they aren't equal
     is RawMutableComplexCell do False			    -- mutable matrices may not stay equal, so they aren't equal
     -- NAG begin
     is RawHomotopyCell do False
     is RawSLEvaluatorCell do False
     is RawSLProgramCell do False
     is RawStraightLineProgramCell do False
     is RawPathTrackerCell do False
     is RawPointArrayCell do False
     -- NAG end
     is x:RawComputationCell do (
	  when rhs
	  is y:RawComputationCell do (
	       False
	       -- toExpr(Ccode(bool, "IM2_GB_is_equal(",x,",",y,")"))
	       )
	  else False
	  )
     is functionCode do False
     is f:CompiledFunctionBody do when rhs is g:CompiledFunctionBody do if f.fn == g.fn then True else False else False
     is s:SpecialExpr do when rhs is t:SpecialExpr do if s.Class == t.Class && equal(s.e,t.e) == True then True else False else False
     is x:RawRingMapCell do (
	  when rhs
	  is y:RawRingMapCell do toExpr(Ccode(bool, "IM2_RingMap_is_equal(",x.p,",",y.p,")"))
	  else False
	  )
     is Database do False
     is pythonObjectCell do False
     is xmlNodeCell do False				    -- unimplemented
     is xmlAttrCell do False				    -- unimplemented
     is x:TaskCell do False
     is x:fileOutputSyncState do False
     );

[mahrud]

Are raw rings always unequal?

M2/M2/Macaulay2/d/equality.dd

Line 164 in 8b2bdcf

is RawRingCell do False

That doesn't seem to make sense because this is true:

i3 : assert(raw ZZ === raw ZZ)

How does it know the difference between raw ZZ and rawZZ()? After evaluation, don't they both point to the same object?

[DanGrayson]

Ah, yes, but the first line of the function equal is this:

     if lhs == rhs then True else 

[DanGrayson]

That line of code looks a little fishy at first glance, because we don't know yet that lhs and rhs are of the same type (both are unions), but if they're at the same address, then they're the same type, too. This is a perhaps obscure feature of the D language.

[mahrud]

Are lhs and rhs pointers? I didn't realize that. In that case, why do raw ZZ and rawZZ() have different addresses? Is there a M2 function to get the address of a raw object in memory?

Also, what's your way of debugging the D language? Is there some sort of printerr command?

[DanGrayson]

lhs is of type Expr, which is declared this way:

export Expr := (
     CCcell or
     RRcell or
     Boolean or
     CodeClosure or
...

It's a union type. Look at one of those components:

export Boolean := {+v:bool};

It's a struct with one component of type bool -- all structs are allocated on the heap, not on the stack, nor in static memory. The plus sign indicates that a type indication tag should be prepended to the struct so those pointers can be used in unions safely. Null pointers can be allowed by suitable declaration.

[DanGrayson]

One way to debug D is with gdb -- but it's a bit sad, because the names of identifiers get mutated in the symbol table, so sometimes it's necessary to look at the C code in the build tree into which D gets translated. Sometimes, in order to have gdb show me the C code instead of the D code, I remove the source line number indications from the C code and recompile.

I don't know what a "printerr" command would do.

[DanGrayson]

PS: The main point of D is that it's a type-safe language, so it rarely needs debugging with gdb. Instead, one can insert print statements into the code temporarily to see what's going on, without any fear of causing the bug in your logic to evaporate.

[mahrud]

@DanGrayson is this solvable? At least a couple of of failing tests in the Macaulay2/tests directory would be resolved if this was fixed.

[DanGrayson]

What problem needs solving?

[mahrud]

What do you mean? Are you saying that this isn't a bug?

[DanGrayson]

It depends on what "this" means, but the discussion above doesn't reveal a bug, as far as I can tell.

[mahrud]

Here is the bug from the text of the issue:

debug Core
hash raw ZZ -- 13
hash rawZZ() -- 13
assert(raw ZZ === rawZZ()) -- stdio:4:1:(3): error: assertion failed

This, and similar assertions, are in many places in Macaulay2/tests, indicating that at some point they worked, but there was a regression that nobody noticed.

[DanGrayson]

Oh. I think the test is wrong and the assertion can be deleted.

[DanGrayson]

On second thought, the underlying C++ code returns the same thing every time:

const Ring *IM2_Ring_ZZ(void) { return globalZZ; }

Hmm...

[DanGrayson]

Ah, it probably stopped working in 2010, when we started putting raw rings inside "raw ring cells" of type RawRingCell. Those are created each time, and the addresses differ. It wouldn't do any harm to make the equality test return true if the underlying raw rings are equal. That would be done by modifying the code for export equal(lhs:Expr,rhs:Expr):Expr by modifying this line: is RawRingCell do False.

[DanGrayson]

That code is now in the file equality.dd.

[mahrud]

Do you have any suggestions on how one might fix this?
Here are a number of assertions that currently fail:

M2/M2/Macaulay2/tests/engine/raw-ring.m2

Lines 36 to 39 in 818b61c

	assert(raw ZZ === rawZZ())
	assert(raw QQ === rawQQ())
	assert(raw RR === rawRR())
	assert(raw CC === rawCC())

[mahrud]

Also, a number of tests have a header that says:

--status: this old test depends on internal things and probably should be deleted

Testing internal things in order to avoid accidental regression is very important. I don't think they should be deleted.

[DanGrayson]

Something like this ought to work for those four assertions:

diff --git a/M2/Macaulay2/d/equality.dd b/M2/Macaulay2/d/equality.dd
index 010fffd98..a56935aa2 100644
--- a/M2/Macaulay2/d/equality.dd
+++ b/M2/Macaulay2/d/equality.dd
@@ -161,7 +161,13 @@ export equal(lhs:Expr,rhs:Expr):Expr := (
 	       )
 	  else False
 	  )
-     is RawRingCell do False
+     is x:RawRingCell do (
+	  when rhs
+	  is y:RawRingCell do (
+	       if x.p == y.p then True else False
+	       )
+	  else False
+	  )
      is x:RawMonomialIdealCell do (
 	  when rhs
 	  is y:RawMonomialIdealCell do (

[mahrud]

Thanks! Most were fixed, except these two: (I added the 53 precision option)

assert(raw RR_53 === rawRR(53))
assert(raw CC_53 === rawCC(53))

See the linked PR if you'd like to try it.

This makes slightly more sense, given that a new ring seems to be created:

M2/M2/Macaulay2/e/x-relem.cpp

Lines 85 to 97 in 818b61c

	const Ring /* or null */ *IM2_Ring_RRR(unsigned long prec)
	{
	if (prec <= 53)
	return M2::ConcreteRing<M2::ARingRR>::create(new M2::ARingRR());
	return M2::ConcreteRing<M2::ARingRRR>::create(new M2::ARingRRR(prec));
	}
	const Ring /* or null */ *IM2_Ring_CCC(unsigned long prec)
	{
	if (prec <= 53)
	return M2::ConcreteRing<M2::ARingCC>::create(new M2::ARingCC());
	return M2::ConcreteRing<M2::ARingCCC>::create(new M2::ARingCCC(prec));
	}

Is there an easy way to avoid making a ring that already exists?

In particular, notice that each hash rawRR(53) creates a new hash, but hash RR_53 and hash raw RR_53 produce a hash once and for all:

debug Core
hash RR_53 -- 1133379
hash RR_53 -- 1133379
hash raw RR_53 -- 21
hash raw RR_53 -- 21
hash rawRR(53) -- 22
hash rawRR(53) -- 23

I'll look into how rawRR and rawZZ are different later.

[DanGrayson]

I don't any point in arranging for rawRR 53 to always return the same ring, since at user level, the answers are always the same. One easy way to arrange it would be rawRR = memoize rawRR, though.

[mahrud]

Even though this is not very significant, I feel like trying to keep the language as functional as possible is worth the effort, and one part of that is that if a function returns the same object in memory, then the outputs of multiple calls should be equal.

Also, I think using memoize for internal things might be troublesome. Do we do that anywhere else with raw objects at the moment?

[DanGrayson]

I doubt we do that elsewhere. Mike might prefer to cache them in the code for IM2_Ring_RRR.

[mahrud]

This isn't quite done yet. There are a couple of missing cases.

[mahrud]

@mikestillman can this be fixed?

i1 : hash GF(2) === hash GF(2)

o1 = false

[DanGrayson]

That's a top level issue -- probably when writing the code, I figured that Galois files should be garbage collectable, the way polynomial rings are.

[mikestillman]

I also want GF(p) === ZZ/p, but currently it is constructed as a GF(p^n). This is easy to fix, perhaps we should do so?