InstallFalseMethods etc.

[mohamed-barakat]

This issue is just a reminder for me. Once we have completed profiling and see how much time we spend doing logic I'll come back with more details:

@stevelinton: When I visited St Andrews some years ago I asked if it would be possible to have InstallFalseMethods as well. I remember that you started something (even more elaborate) back then. Now that the new category theory project CAP of Sebastians is extensively using logic more than homalg it would be nice to reconsider this.

[fingolfin]

There was a proposal for this on GAP devel in 2011. Steve proposed to add the following new API:

InstallExtendedImplication(
  <and  of flags that must be true>,
  <list of filters that must all be false>,
  <and of flags to set true>)

For an example:

InstallExtendedImplication(
    IsGroup and HasIsNilpotentGroup,
    [IsNilpotentGroup],
    HasIsAbelian)

Some notes:

1. The entries of the second argument likely should be simple flags, to avoid amibguities for the reader (as those filters are implicitly negated, so any "and" turns into an "or", etc. -- if you want an "or" effect on those filters, you can invoke InstallExtendedImplication multiple times.
2. No filters are set to "false" by it. That is sufficient, because if one e.g. sets HasIsAbelian to true, but does not set IsAbelian to true, then in fact IsAbelian returns false (as its corresponding "bit" in the flag has not been set).

[fingolfin]

There are many cases where this would be useful. E.g. as soon as IsFinitelyGenerated is known to be false for a group, we can conclude a lot of things about it (e.g. is infinite and has infinite rank).

[hungaborhorvath]

If I am not mistaken, this can already be done.

InstallImmediateMethod(Size, IsGroup and HasIsFinitelyGenerated, 1000
function(G)
  if IsFinitelyGenerated(G) then
    TryNextMethod();
  else
    return infinity;
  fi;
end);

For me having InstallFalseMethod (or whatever name) would just make things complicated. There must be a good reason why it is done this way, but for me allowing to use the logical expressions (not only and of true expressions) would be the way to go. But I guess this would need a lot of rewriting.

[fingolfin]

[UPDATE: my answer below is wrong, and the code provided by hungaborhorvath works just fine. Details followd later in the discussion]

What you propose does not work. It would trigger a size computation as soon as group learns that it is finitely generated. But such a computation need not terminate.

And yes, there is a good reason why arbitrary logical implications are not allowed: Because there is no way to express this efficiently, at least not in the current setup, without a major rewrite of the GAP core -- and such a rewrite would have to disable many nifty optimizations.

Right now, checking whether a filter is applicable is a simply bit-operation, requiring AND/OR operations on a bit set, which maps directly to machine code instructions. In particular, it requires a constant amount of time. In contrast, evaluating arbitrary logical expressions require branches and can take arbitrarily long if you expression is complicated. Even if you only use "simple" logical expressions, your code needs to be ready to deal with more complex ones, and thus cannot apply the simple optimization with bitmasks anymore (unless you in turn invest work to make it work anyway, making the whole thing more complex, and thus more error prone, etc.). I wouldn't say it's impossible, but it is a much larger and riskier change than the above proposal.

[ChrisJefferson]

I haven't delved into the code deeply enough, I thought I'd ask if someone else knows:

Do we need to worry about setting HasIsAbelian before we have set IsAbelian?

[mohamed-barakat]

InstallImmediateMethod invokes a true function call while an InstallFalseMethod would just change a bit or two. This is what I understood from discussions with Steve. And as we are increasingly using logic in homalg/CAP fewer CPU cycles will become essential.

[fingolfin]

I am not completly sure how you mean that. If HasIsAbelian is set but IsAbelian is not, then of course this means the group is not abelian. So one needs to be a bit careful to make sure both are set correctly before immediate methods run (perhaps this is what you are asking about?). I.e. before RunImmediateMethods is invoked -- which is called by SetTypeObj (which is just Objectify), ChangeTypeObj, SetFilterObj and its synoym SET_FILTER_OBJ. The latter then is called from the kernel in DoSetProperty, DoProperty, DoVerboseProperty, DoSetterFunction

[fingolfin]

@ChrisJefferson Or perhaps you question was motivated by the example, above, i.e

InstallExtendedImplication(
    IsGroup and HasIsNilpotentGroup,
    [IsNilpotentGroup],
    HasIsAbelian)

The idea here is indeed to only set the HasIsAbelian filter (which actually is just a synonym for HasIsCommutative resp. Tester(IsCommutative)) -- and since the filter IsAbelian is not set, this amount to saying SetIsAbelian(obj, false).

However, InstallExtendedImplication is of course more generic. It could at the same time be used to set multiple things to true and false. The main new thing here is that it would triggered by something which we learn to be false.

My hope is that implementing this should basically be about modifying RunImmediateMethods (but carefully, to avoid speed regressions). In there, in addition to the checks that are already there, the "list of filters that must all be false" would also need to be checked.

Perhaps one would want some extra work to be done to make this safer InstallExtendedImplication could check the list of filters that must all be false and for each entry in there which is a property, make sure its tester is in the and of flags that must be true (and either raise an error if it is not; or, more helpful, automatically add it). Otherwise, incorrect calls like this would very likely be added by folks who are not aware of the deep details:

InstallExtendedImplication(
    IsGroup,
    [IsNilpotentGroup],
    HasIsAbelian)

(This is incorrect because it would fire immediately for any group which does not know yet whether it is nilpotent or not).

[ChrisJefferson]

So one needs to be a bit careful to make sure both are set correctly before immediate methods run (perhaps this is what you are asking about?)

Yup, that's the bit I'm talking about -- I haven't carefully traced through when the immediate methods are invoked, but from your description we look OK.

The actual coding here isn't too much of a concern to me (I dug into this code recently to speed it up, and it is reasonably easy to understand), we just need to decide on the interface.

I'm wondering if there are good applications for the second argument to contain anything other than property testers, where we require the Tester in the first list, as in your example (so IsNilpotentGroup must be false, and HasIsNilpotentGroup must be true). That seems harder to make mistakes with, if we required it in the interface (at least at a high-level).

[fingolfin]

I can't think of any such applications. Doesn't mean they exist, of course -- but I would err on the cautious side here, and just require properties in the "false" list. Then, if somebody tries to use this for something that is not covered, these people can file an issue, describing their specific use case, and based on that, we can extend what this can do.

[hungaborhorvath]

@fingolfin Ok, then I probably do not understand how immediate methods work.

Would it work without TryNextMethod()?

InstallImmediateMethod(Size, IsGroup and HasIsFinitelyGenerated, 1000
function(G)
  if not IsFinitelyGenerated(G) then
    return infinity;
  fi;
end);

[fingolfin]

[UPDATE: the original code provided by hungaborhorvath was actually correct]

No, that would result in an error, because the method ends without a return value.

[stevelinton]

I think @hungaborhorvath is right;

InstallImmediateMethod(Size, IsGroup and HasIsFinitelyGenerated, 1000
function(G)
  if IsFinitelyGenerated(G) then
    TryNextMethod();
  else
    return infinity;
  fi;
end);

Works fine. Immediatemethods are expressly allowed to exit with TryNextMethod() and that does not cascade through into non-immediate methods.

So this is purely a performance issue. People would like to deal with this by efficient bit-list manipulation rather than having zillions of little immediate methods.

I attach my proposal on this from 2011.

REVISED PROPOSAL_ More flexible implications.txt

[bh11]

@hungaborhorvath @fingolfin The original ImmediadeMethod appears to work fine (modulo syntax errors), it does not (in GAP 4.8.2) trigger a size computation. (I tried both perm group and f.p. groups.) Why should an immediate method trigger a non-immediate one if exiting via TryNextMethod()?

@mohamed-barakat I'm not sure about the overhead – creating a group already triggers immediate methods at least for Size, IsCommutative, IsCyclic. Otoh, one should always weight the cost of such a method (which will be called for almost every group created) against the number of cases where useful information can be gained.

[stevelinton]

On 23 Feb 2016, at 12:17, bh11 notifications@github.com wrote:

@mohamed-barakat I'm not sure about the overhead – creating a group already triggers immediate methods at least for Size, IsCommutative, IsCyclic. Otoh, one should always weight the cost of such a method (which will be called for almost every group created) against the number of cases where useful information can be gained.

It’s not just calls when a group is created, it’s the calls whenever the object acquires a new filter that get expensive. It’s easy to get into a situation in an inner loop where a series of objects are created and then each progressively acquires a number of filters. If immediate methods get called every time this happens, it’s bad.

—
Reply to this email directly or view it on GitHub.

[fingolfin]

@hungaborhorvath You are of course completely right, and I was utterly wrong -- it was me who should have read the manual entry for InstallImmediateMethod method again. My sincere apologies.

Still, I believe that something like the API proposed here (which is just quoting a proposal by @stevelinton) would be valuable for performance reasons (at least potentially, under the assumption that it is implemented efficiently)

[fingolfin]

So I still wonder about this from time to time.

An actual use case that I have is that a group learned that it is not solvable, but GAP doesn't realize that this means it is also not nilpotent, nor supersolvable. I can of course add immediate methods for that, e.g.

InstallImmediateMethod(IsSupersolvableGroup, IsGroup and HasIsSolvableGroup, 1000,
function(G)
  if IsSolvableGroup(G) then
    TryNextMethod();
  else
    return false;
  fi;
end);

and similarly for the implication not supersolvable => not nilpotent. Then once a group learns it is not solvable, the first immediate is run, and the group learns it is not supersolvable. At that point, the next immediate is triggered, and the group learns it is not nilpotent.
And then potentiall a third iteration follows, for the implication not nilpotent => not abelian. So now I am worried a bit about performance overhead... :-/