feature request: addParallelHook and runParallelHooks

[mahrud]

trafficstars

Two requests:

1. add listHooks to get a list/location of existing hooks on a methods.
2. possibly implement parallel hooks. For instance, I have two hooks, each have a quick test that checks whether the hook is appropriate. I want both hooks to start working in parallel and once one is finished the result is returned and the other is cancelled.

[mahrud]

From Mike:

Hooks are a useful way to choose algorithms or specific functions to run.

There are some improvements that should be made though:

• Improve the documentation. There should be a doc node that explains how to do this
• Need a function to get the list of hook functions, and be able to locate their code.
• Perhaps change (break result) to just return something non-null instead.
• How to find which functions/methods allow hooks.

[mahrud]

Status update: the remaining task here is to allow running hooks in parallel.

[mahrud]

A general question: what was the idea behind the way hooks are implemented? For instance:

• in (addHook, HashTable, Thing, Thing), is the HashTable supposed to be the type of the input or the output?
• why does the method above save the hooks under the HashTable?

Context: say we're implementing hooks for the quotient and saturate functions, however:

• the meaning of quotient depends on the type of the inputs, which makes the usage addHook(symbol quotient, algorithm) undesirable, because that would go through a bunch of unrelated hooks before getting to the ones we really want to try.
• even if we wanted to use the above usage, it wouldn't work:

i15 : addHook(symbol quotient, ((opts, a, b) -> a*b))
stdio:15:1:(3): error: assignment to protected variable 'quotient'

• these functions typically take two inputs, e.g. (quotient, Ideal, Ideal) and (quotient, Module, Ideal), which have exclusive algorithms. This makes installing hooks on a type like addHook(Module, symbol quotient, func) not good, because, for instance, (quotient, Module, Module) and (quotient, Module, Ideal) don't even return the same type. We could consider storing the hooks under the return type, but again there are many unrelated meanings of "quotient" that return an ideal, so that doesn't make sense either.

A couple of new items on the wish list:

• [ ] reimplement hooks to dispatch similar to methods, i.e. based on the input types:

addHook(symbol quotient, (Ideal, Ideal), function)

This could, for instance, add function to a list under a mutable global dictionary or hash table:

GlobalHooksHashTable#quotient#(Ideal, Ideal) = prepend(function, ...)

• [ ] allow the hooks function to be used like help and methods, e.g:

hooks (quotient, Ideal, Ideal)
...

This would simply list the contents of GlobalHooksHashTable#quotient#(Ideal, Ideal).

• [ ] fix usage in the documentation entry on hooks, which currently says methods(X, f).

[mahrud]

PS: the ideas above came from discussion with @mikestillman and @jchen419. Also, for the last item, cc: @haerski.

[DanGrayson]

A general question: what was the idea behind the way hooks are implemented? For instance:

• in (addHook, HashTable, Thing, Thing), is the HashTable supposed to be the type of the input or the output?
• why does the method above save the hooks under the HashTable?

Neither, it's simply the place where the hooks should be stored. Actually, this method could be eliminated easily, at the expense of changing the code where it's used to refer to Foo.cache instead of Foo as the first argument. And there may be no such places in the code.

Context: say we're implementing hooks for the quotient and saturate functions, however:

• the meaning of quotient depends on the type of the inputs, which makes the usage addHook(symbol quotient, algorithm) undesirable, because that would go through a bunch of unrelated hooks before getting to the ones we really want to try.
• even if we wanted to use the above usage, it wouldn't work:

i15 : addHook(symbol quotient, ((opts, a, b) -> a*b))
stdio:15:1:(3): error: assignment to protected variable 'quotient'

Yes, in that case, it's not possible to use it that way.

• these functions typically take two inputs, e.g. (quotient, Ideal, Ideal) and (quotient, Module, Ideal), which have exclusive algorithms. This makes installing hooks on a type like addHook(Module, symbol quotient, func) not good, because, for instance, (quotient, Module, Module) and (quotient, Module, Ideal) don't even return the same type. We could consider storing the hooks under the return type, but again there are many unrelated meanings of "quotient" that return an ideal, so that doesn't make sense either.

A couple of new items on the wish list:

• [ ] reimplement hooks to dispatch similar to methods, i.e. based on the input types:

addHook(symbol quotient, (Ideal, Ideal), function)

Better would be addHook(Ideal, (quotient, Ideal), function), since that would work right now, with existing code.

This could, for instance, add function to a list under a mutable global dictionary or hash table:

GlobalHooksHashTable#quotient#(Ideal, Ideal) = prepend(function, ...)

The disadvantage here is that when the things go away, they don't get garbage collected, since they're sitting in a global variable. Yes, "Ideal" is not going to go away, but types can get garbage collected.

[DanGrayson]

By the way, the method for addHook(Symbol,Function) could also be removed, for in the code, where we write addHook(symbol foo,fun), we could write addHook(foo,fun) instead, after initializing foo with foo=new MutableHashTable.

[mahrud]

The disadvantage here is that when the things go away, they don't get garbage collected, since they're sitting in a global variable. Yes, "Ideal" is not going to go away, but types can get garbage collected.

How are methods handled on this regard? For instance if I have a global method f, then define a type A and a function call (f, A) using it in a local frame, then the frame is closed so the function call and type are dereferenced, does methods f forget about (f, A)?

[DanGrayson]

The disadvantage here is that when the things go away, they don't get garbage collected, since they're sitting in a global variable. Yes, "Ideal" is not going to go away, but types can get garbage collected.

How are methods handled on this regard? For instance if I have a global method f, then define a type A and a function call (f, A) using it in a local frame, then the frame is closed so the function call and type are dereferenced, does methods f forget about (f, A)?

Yes. The method function for f(A) is stored in A under the key f, so if A is garbage, so is f, because the only pointers to f are inside A.

Example:

Macaulay2, version 1.16
with packages: ConwayPolynomials, Elimination, IntegralClosure, InverseSystems, LLLBases,
               MinimalPrimes, PrimaryDecomposition, ReesAlgebra, TangentCone, Truncations

i1 : code Module#res

o1 = /Applications/Macaulay2-1.16/share/Macaulay2/Core/res.m2:211:40-224:36: --source code:
     resolution Module := ChainComplex => o -> (M) -> (
          if M.cache.?ManualResolution then return M.cache.ManualResolution;
          C := runHooks(Module,symbol resolution,(o,M));
          if C =!= null then return C;
          R := ring M;
          if isField R then return chainComplex map(minimalPresentation M,R^0,0);
          k := ultimate(coefficientRing, R);
          oR := options R;
          if engineReady M and (options R).Heft =!= null
          then (resolutionInEngine default(o,if o.FastNonminimal then Strategy4 else if isQuotientRing R or isSkewCommutative R then Strategy2 else Strategy1))(M)
          else if k === ZZ then (resolutionBySyzygies o)(M)
          else if not isHomogeneous M and isCommutative R and degreeLength R === 1 then (resolutionByHomogenization o)(M)
          else (resolutionBySyzygies o)(M)
          )

[DanGrayson]

Another design feature: the method function for handling f(A,B) is stored under the key (f,A,B) in the younger of A and B. The reason is that I expect the younger one to be more likely to get garbage collected. For example, the older one might be QQ and the younger one might be QQ[x].

[mahrud]

I see, thanks for the explanation. This is better than a global hash table, so I'll try to implement it this way, but perhaps change the API so there's less confusion. For instance, addHook((quotient, Module, Ideal), function) would look at the youngest type in the sequence and add the hook there, and runHooks would also do the same. Does that sound good?

Perhaps even a new notation like quotient(Module, Ideal) := ... to add hooks would be nice, but I can't think of a natural option.

Incidentally, what is going wrong here?

WW = new Type of ZZ
f = method()
f(WW) := a -> 3*a
w = new WW from 12
f(w) -- stdio:3:16:(3):[1]: error: dummy method function called

[DanGrayson]

I see, thanks for the explanation. This is better than a global hash table, so I'll try to implement it this way, but perhaps change the API so there's less confusion. For instance, addHook((quotient, Module, Ideal), function) would look at the youngest type in the sequence and add the hook there, and runHooks would also do the same. Does that sound good?

Let's pursue the idea just below first.

Perhaps even a new notation like quotient(Module, Ideal) := ... to add hooks would be nice, but I can't think of a natural option.

Sounds good! Here's an idea: modify the code in the d directory that handles such method function assignments so it checks for collisions. Importantly, it wouldn't need to know about hooks per se, for in case of a collision (the key is already in use), it would call a generic method for resolving the collision. Method functions attached to that method at top level would detect that the value already in place is a list of hooks and that the value about to be assigned is a function. Then it could do the right thing, resulting in a longer list of functions, which be returned for assignment as the new value by the internal code.

We could say HookList = new Type of MutableList, and then appending to the list would be quicker.

If there's no method for handling the collision, we signal an error. We want those errors, anyway, because it is usually a mistake to overwrite a method function. We could devise a way to intentionally overwrite, simply by removing the value before doing the assignment.

Incidentally, what is going wrong here?

WW = new Type of ZZ
f = method()
f(WW) := a -> 3*a
w = new WW from 12
f(w) -- stdio:3:16:(3):[1]: error: dummy method function called

That "new Type of X" construction is a hack, that has to have code inserted to handle the thing. I wanted to be able to make new types of functions for some reason ...

[mahrud]

I implemented the above in 05661d7, but I'd say it's still experimental, so haven't documented it yet. I think your suggestion for how to add a syntax for installing hooks by the interpreter sounds good, and eventually we can remove manual addHook and runHooks calls.

[mahrud]

@DanGrayson have a look at 85b6e6aacd3e2c25b7da8d719d0165983383f5ff. I think the next step is adding this to the interpreter.