Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

provide interface-conformance testsets #312

Closed
kalmarek opened this issue May 24, 2019 · 42 comments
Closed

provide interface-conformance testsets #312

kalmarek opened this issue May 24, 2019 · 42 comments

Comments

@kalmarek
Copy link
Contributor

I'm moving some of my old code to AbstractAlgebra ring interface: @wbhart (or whoever did this) thanks so much for taking time to define and describe it.

It would be great if we could provide testsuite for each defined interface. Something like:

test_ring_interace_conformance(x,y) # for non-parametrized rings (x,y are two distinct elements)
test_ring_interface_conformance([x_T, y_T], [x_S, y_S]) # for parametrized rings: pairs of ring elements parametrized by T or S
@wbhart
Copy link
Contributor

wbhart commented May 24, 2019

That's a great idea. I like it!

@kalmarek
Copy link
Contributor Author

@wbhart have a look at first try here:
https://gist.github.com/kalmarek/76b674c63b62c0d02605e7d0c1068f17

I don't really know how to test rand as it depends on the actual implementation; maybe we should ask for rand(R) that will make some standardised choices?

also:

R, x = PolynomialRing(AbstractAlgebra.JuliaZZ, "x")

test_ringinterface(x^2, x-1) # fails: promote rules return `Union{}`
test_ringinterface(big(2), big(3)) # passes
test_ringinterface(big(2.0), big(3.0)) # fails: `divexact(f, R(0))` does not throw

@kalmarek
Copy link
Contributor Author

ok, the second iteration is ready; I have a few questions:

  • is canonical_unit(f) an element of parent(f) or base_ring(parent(f))?? e.g. canonical_unit(::Poly{BigInt}) returns a BigInt;

I'm somehow struggling with divexact[_left, _right] and AbstractAlgebra.promote_rules:

divexact

  • it is not clear from the documentation what kind of error should be thrown
  • moreover for Rings the documentations states

If no exact quotient exists or an impossible inverse is unavoidably encountered, an error should be thrown.

however

julia> R, x = PolynomialRing(AbstractAlgebra.JuliaZZ, "x");

julia> divexact(x^2, x-1)
x+1
  • looking at example implementations of divexact_left it is clear that they call divexact_left on the coefficients, which may or may not implement it:
  • divexact_left(f::Poly{BigInt}, parent(f)(1)) leads to StackOverflowError
  • divexact_left(::BigInt, ::BigInt) is a MethodError`
  • f = big(2.0); divexact(f, parent(f)(0)) does not throw: Inf is returned.
  • divexact_left, _right throw MethodError for BigFloats as well

promote_rules

  • AbstractAlgebra.promote_rule(BigInt, Int16) = Union{}
  • AbstractAlgebra.promote_rule(BigFloat, Int16) = Union{}

@thofma
Copy link
Member

thofma commented May 27, 2019

See Nemocas/Nemo.jl#300 for the canonical_unit part. I am all in favor of returning something in the ring that we are working in. But it is quite a rabbit hole to change it.

The promote_rule business also needs some love.

@wbhart
Copy link
Contributor

wbhart commented May 27, 2019

The promote_rule is explained by the following:

julia> R, x = PolynomialRing(AbstractAlgebra.JuliaZZ, "x")
(Univariate Polynomial Ring in x over Integers, x)

julia> promote_rule(typeof(x^2), typeof(x - 1))
Union{}

julia> AbstractAlgebra.promote_rule(typeof(x^2), typeof(x - 1))
AbstractAlgebra.Generic.Poly{BigInt}

Note, we define our own promote_rule, as we cannot overload the Julia promote_rule function for a variety of reasons.

I'm not really sure that divexact should throw for bigfloats, as this wouldn't be very useful behaviour. Perhaps we just change the documentation to say that it is an exact division if the ring is exact, if not divexact(a, b) returns c such that a = bc in the given ring assuming a and b have the same precision and assuming such a value exists. (I'm not even sure that is correct, so perhaps we just change the docs to talk about exact rings, i.e. types for which isexact_type returns true).

@wbhart
Copy link
Contributor

wbhart commented May 27, 2019

This is a bug:

julia> R, x = PolynomialRing(AbstractAlgebra.JuliaZZ, "x");

julia> divexact(x^2, x-1)
x+1

You can open a ticket for that.

@wbhart
Copy link
Contributor

wbhart commented May 27, 2019

Regarding what kind of error should be thrown: we would use the InexactError that Julia prints, but it says something about integers could not be divided, which is useless as a general error when not working over the integers. We'll have to create our own exception for this or pressure the Julia people to change their error message. But very few errors in AbstractAlgebra are throwing specialised exceptions. Many of them just call error("Some message here").

@wbhart
Copy link
Contributor

wbhart commented May 27, 2019

The divexact_left things are bugs. You can open a ticket for these,

@wbhart
Copy link
Contributor

wbhart commented May 27, 2019

We don't consistently implement stuff for Int16, Int32, Int8, UInt16, etc. I'm not sure if it is really a bug. It's a waste of time to fix. The minimum Integer we should recognise is Int in my opinion. Admittedly the docs do indicate in one place that you can define an integer ring for any size integer. We probably should just change that. It's too much work to support all these cases no one will ever use, at least until someone does.

@wbhart
Copy link
Contributor

wbhart commented May 27, 2019

I should point out that inexact rings are not mathematically rings. Typically associativity fails or equality is not an equivalence relation or something like that. Another case we don't always cover is non-integral domains. Mathematically it is very hard to support everything. In some cases it is theoretically possible, but no one has the energy to make it work in practice or theory.

@kalmarek
Copy link
Contributor Author

@wbhart, @thofma thanks for your replies;

  • yes, I already use AbstractAlgebra.promote_rule in the second iteration tests (those errors for Poly{BigInt} are gone). My suggestion is to indicate in docs where does the extended method come from: e.g. zero! is from AbstractAlgebra, but mul! is not; I'd be nice if a warning banner would appear in docs just before promote_rule with the same message as is in src/AbstractTypes.jl (most people would assume it's extending Base.promote_rule).
  • divexact encountering an impossible inversion sounds to me more like a DomainError (and we can customize the message)
  • whenever docs state that a method should work for T<:Integer I test it for two opposite types on the spectrum: Int16 and (when it makes sense) for BigInt; I'm just reading docs and producing code that should work according to API ;)
  • i'm perfectly aware that inexact rings are not mathematical; still a test suite for (inexact) rings could be produced since I don't have to @test iszero(f-f) or @test isapprox(g+f - g, f): to check conformance it's enought to @test isequal(f, g) isa Bool.

If You can find time please have a look at the linked proposed @testset (You have much more experience implementing rings). I made some (mathematical) assumptions which might be too tight for inexact rings in general, but still PolynomialRing( ... , "x") over AbstractAlgebra.RDF fails exactly those four tests which AbstractAlgebra.ZZ does.

And its good to collect concrete topics fo discussions before June ;-)

@wbhart
Copy link
Contributor

wbhart commented Sep 27, 2019

You mentioned that there were some failures in the tests you did write. Perhaps you could mention what these are.

I doubt that we will have time to implement interface-conformance tests before the release. But at least we should close known issues that you found (assuming they are not special cases that have to violate the interface for the time being).

@wbhart
Copy link
Contributor

wbhart commented Sep 27, 2019

Oh, I should mention, we have plans to make the Ring interface a little lighter so it is easier to satisfy. Perhaps writing conformance tests after that time would make more sense anyway.

@kalmarek
Copy link
Contributor Author

mostly undefined functions (for some reasons some people don't like to implement hash ;);
divexact_left going into StackOverflow; wrong errors thrown on impossible divisions and so on;
It's been a while since I touched this code (June?) as there was no will to make it usable, and I had more urging stuff to do.

@wbhart
Copy link
Contributor

wbhart commented Sep 27, 2019

I'll do a check on Monday to see what hash functions are still not defined.

But the divexact_left I will need some more information about. What ring?

Same for impossible divisions.

@kalmarek
Copy link
Contributor Author

#316 #315

out of the top of my head: neither arb nor acb provide hash;

@kalmarek
Copy link
Contributor Author

kalmarek commented Sep 27, 2019

but to be honest: I think that AbstractAlgebra.promote_rule needs to be fixed before we release...

also https://gist.github.com/kalmarek/76b674c63b62c0d02605e7d0c1068f17 was written with the old testing framework in mind, but I don't have an idea how to make it more @testset-ish.
The idea was to run the same tests for two "generic" elements of a ring to test that what we promise in the docs holds true. And this should probably be run for all rings that we construct in our tests.

@rfourquet could you have a look and suggest something?

@rfourquet
Copy link
Contributor

@rfourquet could you have a look and suggest something?

I don't really see a problem with defining functions containing testsets, test_ringinterface(f, g) can just be called where needed at the toplevel of test files. (Or did I misunderstand your question?)

@wbhart
Copy link
Contributor

wbhart commented Sep 27, 2019

@kalmarek Can you remind me what's wrong with AbstractAlgebra.promote_rule?

@kalmarek
Copy link
Contributor Author

@rfourquet no, that was the question; those functions will need to be compiled for all types, unless we @nospecialize

@wbhart as defined now (or was in June, I don't know if there have been any changes since) it is asymmetric and will produce non-equal results depending on the order, unless special binary ops methods are defined

@rfourquet
Copy link
Contributor

no, that was the question; those functions will need to be compiled for all types, unless we @nospecialize

@nospecialize is a good idea indeed. I guess you could also get away without defining functions, provided you don't need to call sub-functions which test only part of the interface. Then all testsets could be nested, and have a toplevel @testset "..." for (f, g) in list_of_fg ..., provided that all (f, g) pairs can be reached from a single place in the tests.

@wbhart
Copy link
Contributor

wbhart commented Sep 27, 2019

@kalmarek That is the idea. Note that we are not overloading Julia's promote_rule here.

If you can give me an example of code that won't work because of this, we can change it. But I don't currently know that it is really broken. It was designed to be like this.

@kalmarek
Copy link
Contributor Author

all points as written here #324 (comment) stand;

including the case where generic == is not symmetric;

it works only because a) there are hand-written very specific cases of == and/or it is not thoroughly tested. Try constructing a ring parametrized by other ring where == dispatches through generic, or commenting-out the specific method.

@wbhart
Copy link
Contributor

wbhart commented Oct 2, 2019

Ah, that discussion.

I feel that I answered it well enough and it is really too much to read through it all again.

I am not interested in making our interface design work well for Int as a parameter. If there are examples that just involve BigInt as a parameter, I'll work on fixing that. Otherwise I disagree that we need to fix things (other than possibly changing the name of our promote_rule to something_else).

If someone can come up with a different promotion system that works for all our systems better than the current one, I'll merge it. But I have no plans to work on that myself.

I still support writing interface conformance testsets, but only for actual rings. Poly{Int} is not a ring, in my humble opinion.

@fieker
Copy link
Contributor

fieker commented Oct 2, 2019 via email

@kalmarek
Copy link
Contributor Author

kalmarek commented Oct 3, 2019

@wbhart wait, didn't you say in Saarbrucken that it is a good idea to support different type of Ints, like SafeIntegers suggested by @jmichel7 ?!

A promotion system which causes == to be asymmetric is broken by design. Currently it works only because there are ad-hoc methods defined for our rings. Yes, there is lots of text in that issue, but none of it addresses the points raised. Way too much text I'd say.

@fieker if you know (for theoretical reasons) that your polynomials/matrices etc. will fit into Int16 you can use this to your advantage as this easily may lead to 4×speed-up (or much more if counted for cache locality). And julia is one of the few languages that allows you to change that on the fly without much hassle.

So You may either be more pragmatic and benefit from smaller types, or say "it's not mathematically a ring" (but are arbs a field?) and leave performance on the table, but of course it's your choice.

@wbhart
Copy link
Contributor

wbhart commented Oct 3, 2019

Yes, but that can be done safely.

The rest of it I'm not going to go over again.

@fieker
Copy link
Contributor

fieker commented Oct 4, 2019 via email

@jmichel7
Copy link

jmichel7 commented Oct 4, 2019 via email

@fieker
Copy link
Contributor

fieker commented Oct 4, 2019 via email

@jmichel7
Copy link

jmichel7 commented Oct 4, 2019 via email

@kalmarek
Copy link
Contributor Author

kalmarek commented Oct 6, 2019

@fieker I'm for providing safe defaults, but when user decides to use objects which do not form an algebraic structure (Ints, arbs) to model computations in mathematical ideal object he/she needs to understand what is happening. And especially when squeezing the last bits of performance we can relax some safeguards, as only the advanced users will venture there.

So how far do you want to push this support?

An ideal situation would be to take pm_Integers, or SafeInt128, or WhateverInt and plug it into perms, polynomials and whatnot from Generic. It's supposed to be generic code, right?
I fully second @jmichel7 point about usefulness and speed of SafeInts but if we decide go the (figurative) mile to support them, there is little reason not to go additional meter to support anything that subtypes Integer. This usually requires just a little bit more consideration when writing code (and of course no assumptions on the concrete type of Integers).
I tried to write Perms so that PermGroup(SafeInt(50)) should work and pass all the tests out of the box. If it doesn't I consider this a bug (and will fix it). And there's not much more code to make it work, really. The rule of thumb is that if it works type-stably for UInt16 and BigInts it should work for all integers.

G = PermGroup(SafeInt(40)); 
A = [rand(G) for _ in 1:10]; # rand(G, 10) on master, array of `Perm{SafeInt}`s
let A = deepcopy(A)
    prod(order.(A)) # BigInt as `order` easily overflows
end
let A = deepcopy(A)
    prod(order.(SafeInt, A)) # SafeInt, usually overflows
end
let A = deepcopy(A)
    prod(order.(SafeInt128, A)) # SafeInt128, should be sufficient
end

yts = YoungTableau.(permtype.(A));
dim.(yts) # Array of BigInts
for yt in yts
    @show dim(SafeInt128, yt) # this will probably overflow for one of perms
end

... do we need to meet face to face at some point?

It would be much easier to discuss this in person, definitely, but given that Bill said that he is not tackling the issue before the release, let's postpone this until after the first release. Maybe we can schedule this for the next meeting and ask @rfourquet to join the discussion as by then he will have the fullest view of both julia and AA worlds.

@wbhart
Copy link
Contributor

wbhart commented Oct 6, 2019

@kalmarek I literally have no idea how you could make the generic code safe for Int's without checking for overflows everywhere? And how would one do that in generic code? And what advantage would there be over using SafeInt's in the first place?

Do you have any idea just how much generic code there is now? This is a job that would never be finished. We just don't have the resources to be doing something like this.

If I put any time into something like this, I would put time into the linear algebra in Flint and make it (provably) use machine words where possible, with a fallback to fmpz's when there can be an overflow (I started work on this after learning that Normaliz does this heuristically with no proof of correctness). But just that task right there is already months of work for someone!!

On a related topic: you still didn't explain what promote_rule should return for BigInt and Poly{Int}. BigInt or Poly{Int}? Again, this is "complex coercion", which we are not supporting.

It's only possible to support rings in which there is a canonical (and safe) coercion from a safe model of the integers (e.g. from BigInt). This is not the case for Int, but it is the case for SafeInt (assuming you are prepared to raise an exception on overflow).

If you really believe you can implement a symmetric promote_rule system which works for all the cases that the current promote_rule system works, be my guest. But I claim it is nontrivial if you don't want to introduce Julia ambiguities that will drive everyone insane. Bear in mind we had a symmetric system before I changed it, to work around deficiencies in the existing system!

But if you think you can do better, I look forward to the PR.

And if you really believe you can safely support Int parameters in all our generic code without polluting it with zillions of overflow checks, I very much look forward to the PR.

But let me emphasise this so it's clear: I am not working on any of these things! I have far too much other important work to do. I cannot take a year out of Oscar development to support this stuff which would have marginal usefulness over say further speeding up Flint with word sized arithmetic where possible.

@wbhart
Copy link
Contributor

wbhart commented Oct 6, 2019

Something that I should also stress is that we MUST release Oscar version 1.0 before the end of the year. That's a little over 2 months away, and we still have zero documentation, zero code to convert between all the types of the different systems and few mathematical examples to show off its usefulness. All of that MUST be delivered by the end of the year at the latest, with no possibility of extension! We still can't even build the system quickly on OSX (e.g. Singular.jl and Gap.jl).

@kalmarek How is it that you can even countenance some of the stuff you are suggesting? Don't you also have pressing research deadlines and projects you are involved with?

@kalmarek
Copy link
Contributor Author

kalmarek commented Oct 6, 2019

@wbhart I wrote:

let's postpone this until after the first release.

I mention those issues because I care, and not because I criticize You or someone else. I'm sorry if You felt like this. But if this is the response I might as well stop caring.

@wbhart
Copy link
Contributor

wbhart commented Oct 7, 2019

@kalmarek This has nothing to do with me thinking I am being criticised, or anything personal, for that matter. It is about me not understanding why you keep suggesting to do things which seem more or less impossible, especially given the resources we have.

I've tried to explain why it would be hard, and I would welcome being proven wrong. But I can't keep going over the same issues. I don't believe it is possible to do what you want.

As I said before, I welcome interface conformance testsets. These would be very useful, and certainly possible, so long as they are reasonable. In particular, they have to test actual rings, and moreover, ones that we actually implement. This would already be of great benefit over what we have. I understand that you don't have time to implement them right now. Nor do I, and I would expect that no one does, due to the tight deadlines we are all under. So let's do it at some later date when one of us has the time.

@fieker
Copy link
Contributor

fieker commented Oct 7, 2019 via email

@fieker
Copy link
Contributor

fieker commented Oct 7, 2019 via email

@fieker
Copy link
Contributor

fieker commented Oct 7, 2019 via email

@kalmarek
Copy link
Contributor Author

kalmarek commented Oct 7, 2019

@fieker
about the returned type by dim, order: yes, we had a discussion (with @thofma, if I remember correctly?!) when I worked on this code and this was the solution we came up with, as one of the reasonable things to do. Problem with returning the integer of type defining PermGroup was that you couldn't compute order(PermGroup(Int8(7))), those pesky small Ints are really small... ;)

by safe defaults I mean that e.g. our ZZ is true integer and this is what user will see, and it's a completely ok.

Do you expect the documentation to spell out that intermediate results
can be larger than the result or the input? Do you expect, in AA, to
only see the 1st version? Or to code in such a way that internally
BigInt can be used and translations happen?

  1. I don't expect, but it would be definitely user friendly, especially if overflow is likely even for middle-size numbers;
  2. this is very much function dependent; e.g. in dim we made the decision that the operation will likely overflow, therefore we provide the one that works. Case in point: factorial vs. ^; the first throws, as overflow is very likely, the second silently overflows. And of course I'd try my best to provide one that will work with user supplied (safe or not, ringy or not) types.

I think that the policy of not overflowing at any cost is somehow defeating the purpose of generic functions, as even a function that doubles its argument mus pass through BigInt: f(x:T) where T = ( y::T = 2big(x); y). And I understand that we probably care more about correctness than average julia and I'd have nothing against e.g. making AA.zz defaulting to SafeInts to avoid accidental overflows, but this is an issue I am very much disinterested in.

In Oscar alone there are already four types of mathematical Integers: BigInts, fmpzs, pm_Integers and n_Zs from Singular. sooner or later somebody will write GAPInts as well and it's only natural, that when Polymake gives You an array of its integers you call perm on it and Your algorithm runs further. And it's good to be prepared for this, even though we will not be able predict all the possible interactions between components.

ahh well, we are planning to meet for perms anyway

I'd prefer not to bring the actual issue which, if somebody still remembers ;), is the conformance testing (and the asymmetry of generic == for Rings) during the groups meeting and rather postpone it until the next year, at the request of @wbhart

@fieker
Copy link
Contributor

fieker commented Oct 8, 2019 via email

@fingolfin
Copy link
Member

We have had test_Ring_interface and friends for quite some time now. It certainly could and should be further improved, but that's always true.

There is much more discussion in here, however, the actual topic of the issue is resolved. Hence I am going to close this now. That does not mean a decision on other things said here. But if anyone feels anything in here should still be acted upon, it would be best to open a new issue (or multiple) with specific actionable requests/suggestions.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

7 participants