New functions have no non-polymorphic names

[DrTimothyAldenDavis]

GrB_reduce, when reducing a matrix or vector to a GrB_Scalar using a GrB_BinaryOp (ack!) has no non-polymorphic name. All there is in Table 5.11 are these 2 functions with GrB_Scalars:

GrB_Vector_reduce_Scalar (GrB_Scalar, ..., GrB_Vector, ... )
GrB_Matrix_reduce_Scalar (GrB_Scalar, ..., GrB_Matrix, ... )

which I assume are the monoid variants:

GrB_Vector_reduce_Scalar (GrB_Scalar s, GrB_BinaryOp accum, GrB_Monoid mon, GrB_Vector u, GrB_Descriptor d)
GrB_Matrix_reduce_Scalar (GrB_Scalar s, GrB_BinaryOp accum, GrB_Monoid mon, GrB_Matrix A, GrB_Descriptor d)

I prefer that you simply not add the functions that do reduction via GrB_BinaryOps at all. That is, I ask that you simply delete lines 6937 to 6942 of the spec, and only refer to the monoid in line 6950.

But if you really insist on adding them, I need at least a name of a stub I can use to return GrB_NOT_IMPLEMENTED for those 2 methods. Otherwise it's a compile time error to try to pass in a binary op, since there's no name to use for these functions in the _Generic switch.

These nameless beasts are a problem anyway ... I suggest you just delete them. No one will miss them. I also suggest deprecating GrB_reduce matrix to vector using a binary op, which is also a problem and not needed; a monoid works best for all reductions.

[michelp]

Agreed, as it is already, pygraphblas uses only the monoid form of reduce and never the binaryop. @eriknw or @Wimmerer do you use any of the BinaryOp reduction forms?

[rayegun]

No, only monoids

[DrTimothyAldenDavis]

A nameless placeholder for now, ideally the nameless will never be named but sent back to the uttermost darkness from whence they came ;-)

https://www.azquotes.com/quote/464575 https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/b6ce5cb46ab2026bb8429b0d2ec912d8ad6ea114/Config/GraphBLAS.h.in#L8531

[eriknw]

I think that BinaryOp reductions are underspecified to be able to be implemented efficiently or even used effectively. I agree that the current forms should be scrapped. I am open (and even encouraging!) to adding more capable forms for performing reductions on non-commutative, non-monoidal binary operators in an efficient manner.

A simple example of a potentially useful BinaryOp reduction that is not a monoid and is not commutative is to use first or second to get the first and last values. I think BinaryOps could also be valuable with reductions on user-defined types, but, again, I think the current functions are severely lacking and need to be improved.

[DrTimothyAldenDavis]

If I'm able to tackle the idea of more complex aggregator-like methods, I think this should be done using an entirely different kind of object. Binary ops and even monoids don't have enough information to be able to do this, even for first or second. Since those ops are not moniods and not commutative, they shouldn't be mixed into the GrB_reduce method, but should be on their own, in some kind of GxB_aggregate method that can handle these more complex aggregations.

[tgmattso]

commenting on Tim's comment at the top of this chain ...

Tim wrote:

  "I need at least a name of a stub I can use to return GrB_NOT_IMPLEMENTED for those 2 methods."

This is an interesting point. In the draft 2.0 spec where we first mentioned GrB_NOT_IMPLEMENTED we left it wide open as to when this could be used. We wanted to forbid the situation where someone created a library of stubs that did nothing but return GrB_NOT_IMPLEMENTED and then called that a conformant implementation. Your comment above makes me think I need to go back and work on the new text some more.

For each method defined by the GraphBLAS spec, there are combinations of parameters that may not be supported (such as reduction with a binary operator) but you can't call an implementation conformant if EVERY set of parameters is not supported. In other words, for a conformant specification, you MUST have at least one function signature for EVERY function supported.

But as Tim's comment above suggests, this is not the case for the nonpolymorphic interface. Indeed, there will be cases from that list that are not implemented. I need to modify the text on GrB_not_implemented to make this clear.

[DrTimothyAldenDavis]

I have actually implemented the nameless things, for important cases. My GrB_reduce to vector or scalar when using a GrB_BinaryOp works as long as the binary op is built-in and corresponds to a known monoid. I then replace the op with the proper monoid, and use that. So GrB_PLUS_FP64 is replaced with GrB_PLUS_MONOID_FP64. See:

https://github.com/DrTimothyAldenDavis/GraphBLAS/blob/f03de5abf3e7b9da995085091048e323faee5456/Source/GrB_Matrix_reduce.c#L155

also below in its entirety:

GrB_Info GrB_Matrix_nameless        // FIXME: spec leaves it nameless
(
    GrB_Scalar S,                   // result scalar
    const GrB_BinaryOp accum,       // optional accum for c=accum(c,t)
    const GrB_BinaryOp op,          // binary op to do the reduction
    const GrB_Matrix A,             // matrix to reduce
    const GrB_Descriptor desc
)
{ 
    GB_WHERE1 ("GrB_Matrix_nameless (s, accum, binaryop, A, desc)") ;
    GB_BURBLE_START ("GrB_reduce") ;
    GB_RETURN_IF_NULL_OR_FAULTY (op) ;
    // convert the binary op to its corresponding monoid
    GrB_Monoid monoid = GB_binop_to_monoid (op) ;
    if (monoid == NULL)
    { 
        GB_ERROR (GrB_NOT_IMPLEMENTED, "Invalid binary operator:"
            " z=%s(x,y) has no equivalent monoid\n", op->name) ;
    }
    // S = reduce (A) via the monoid
    GrB_Info info = GB_Scalar_reduce (S, accum, monoid, A, Context) ;
    GB_BURBLE_END ;
    return (info) ;
}

User-defined operators are not supported. GrB_LT_FP64, for example, results in an error since it doesn't correspond to a known monoid (but it is also not commutative nor associative). Are there any binary ops that anyone can name that are commutative and associative but do not have an identity value? If there are no such binary ops, even user-defined ones, then why bother including this nameless function in the spec after all?

[DrTimothyAldenDavis]

GrB_NOT_IMPLEMENTED is another issue, see #53

[joseemoreira]

I will edit the nonpolymorphic names.

[mcmillan03]

Assign to Jose to address.

[joseemoreira]

I added the missing nonpolymorphic names. I also changed the font size in the tables to "scriptsize", since they were not fitting, even in landscape mode.

I will change the red text to black after reviewing the names one more time.

[joseemoreira]

Finished reviewing nonpolymorphic names.