How to deal with optional return values

[fingolfin]

We have all kinds of computations that "naturally" (based on the name) return one value, but for applications one often really wants multiple return values... But we have different conventions for these. It would be good to agree on a common scheme!

To this end, I'll try to describe the primary variants I am aware of with examples. Note that these are not always mutually exclusive, nor can every one applied in every case.

At the end I'll write some of my personal thoughts. I hope for feedback and opinions by everyone, though!

1. always return the "optional" return values: we used to do this for is_isomorphic, and e.g. is_pgroup still always returns a pair bool, hom

   • easy to implement and maintain
   • confusing for users ("why doesn't is_pgroup just return a boolean?")
   • quite easy to produce type unstable code with this
   • this is how we used to do it in a lot of places, but we already agreed that we do not want this, it is listed just so it can be easily referenced in the discussion

2. keyword arguments: e.g. direct_sum for modules: takes a keyword argument task::Symbol which indicates what to return: it always returns the direct sum as a module; and then either nothing more; or the injection maps; projection maps; or both injections and projections.

   • problem: breaks type stability
   • problem: the default value for task must be coordinated between all implementations (and it currently isn't, at least according to the doc string). This can be addressed in principle (e.g. by setting a global const default_direct_sum_task = :none or so and using it everywhere; or by renaming the existing direct_sum methods to, say, direct_sum_internal and then adding a single frontend direct_sum method which delegates to direct_sum_internal but determines the default value), though neither options seems particularly nice?

3. multiple functions: is_isomorphic returns just a boolean, if one also wants the isomorphism, use is_isomorphic_with_map

   • pro: a default method for is_isomorphic can be added which just calls is_isomorphic_with_map and discards the second return value (simplifies implementations), while it is still possible to provide an optimized version that does not bother to compute an actual homomorphism (e.g. if both groups have same order and it is prime, they must be isomorphic...)
   • type stability can be preserved if one returns a "trivial" homomorphism in case of non-isomorphic objects
   • alternatively one may return false, nothing which breaks type stability, but arguably is nicer for the user (and still not too bad, as Julia is quite good at splitting Union types over just two types)
   • drawback: long names, esp. if there are multiple optional return values: direct_sum, direct_sum_with_injections, direct_sum_with_projections, direct_sum_with_injections_and_projections
     • though one upside of this is that the name at least describes the order of the return values (useful if I can't remember whether d, i, p or d, p, i is returned)
   • these variants are easy to discover via tab completion
   • but in the manual, make sure to link all, and possibly add refs between the various docstrings?
   • easy to forget implementing some of these variants (though of course one can provide default delegations, and have a conformance test suite, and what not)

4. allow returning nothing: as a variant to the previous point, one can also decide that a function like isomorphism(G, H) should be allowed to return a special value (typically nothing) in case no isomorphism exists.

   • worse type stability than option 2
   • but again not too bad (thanks to type splitting)
   • IMHO comparatively nice for end users
   • this is not applicable in general (i.e., good for is_pgroup, is_isisomorphic but not for direct_sum)

5. use exceptions: of course isomorphism(G,H) could also throw an exception of there is no isomorphism. But exceptions are very expensive. But this is still a good option for functions where the failure mode is very rare, or does not matter to "typical" callers (but what is that? Hmm), or if the function is very expensive anyway (isomorphisms for groups quickly get very expensive; but of course if you only deal with tiny ones, that might be different)

   • is type stable, but may require handling exceptions, which complicates the code

6. ... more?

Here are my personal thoughts:

• re 1.: I really don't like is_FOO functions returning anything besides a boolean, that's confusing; so I'd like to get rid of these
• re 2. and 3.: I am a bit concerned about the number of return values changing based on they keyword argument. So: I am not a fan o 2, I'd prefer option 3, as I am not scared by long function names as I use tab completion anyway
• re 4.: I am not really worried about the type instability incurred by sometimes returning nothing, so this is also a great option from my POV
• re 5.: I'd prefer to reserve exceptions to true error situations, and not this case here

[thofma]

If this is a poll, I am voting for 3).

PS.: I think the union splitting is very efficient for the case it was implemented for, namely for the temporary variables introduced during iteration, where the variable of union type is located in a very small section of the code. For variables spread over the whole function and interaction between variables of type Union it is not that great. If you throw in comprehension it gets worse.

function h(x)
  f = rand() < 0.5 ? sin : cos
  g = rand() < 0.5 ? cos : tan
  return f(x) + g(x)
end # this will infer ok

function h(x)
  f = rand() < 0.5 ? sin : cos
  g = rand() < 0.5 ? cos : tan
  return [f(i) + g(i) for i in 1:x]
end # this won't

[fingolfin]

Thanks for the input. It's not really a poll (for starters, the options I listed are not mutually interchangeable; e.g. 4 and 5 are useless for direct_sum).

Regarding the union splitting: well, it depends on the code patterns how the impact is, don't you think? From that point of view, I think that returning a Tuple{Bool,SomeType} (as in option 1) is often more problematic than returning a Union{SomeType,Nothing} (as in option 4). With the former, I may end up writing code like this:

function isfoo(x::Int)
  b = isodd(x)
  return b, b ? 1 : nothing
end

function bar(x::Int)
  b, val = isfoo(x)
  b || return -100
  x = val + 1
  return val # does not infer, Julia does not know the correlation between b and the type of val
end

So this is very easy to get wrong, and one of the various reasons I don't like option 1.

In contrast, when returning a Union{SomeType,Nothing} writing type stable code happens quite naturally in many cases:

function foo(x::Int)
  return isodd(x) ? 1 : nothing
end

function bar2(x::Int)
  val = foo(x)
  isnothing(val) && return -100
  x = val + 1
  return val  # Julia correctly infers this is an Int
end

Alas, the main argument against option 4 is code that "knows" that for the given inputs, nothing won't be returned (e.g. calling isomorphic with two groups that dye to the setup must be isomorphic), and hence does not bother to check for nothing.

If it wasn't for that, I'd say there is no need for is_isomorphic_with_map at all....

[thofma]

Yes, I agree, that 1) is not good. But I considered 1) already off the table, since we changed is_isomorphism to only return a Bool etc.

I think for many options the premise is that nothing is not that bad because of the small union splitting. But I don't think this is a realistic assumption.

[fingolfin]

Yeah, we don't want option 1, but I felt I should include it for completeness. Bu I'll update my post to state that we already ruled it out

[lkastner]

Could you not avoid breaking type stability by passing callback functions? In your examples something like

function do_something_with_iso
function do_something_with_nonisomorphic
function is_isomorphic(G,H, do_something_with_iso, do_something_with_nonisomorphic)
    [...]
    if are_isomorphic
        return do_something_with_iso(G,H, ISO)
    else
        return do_something_with_nonisomorphic(G,H)
    end
end

I am unsure whether one can require an exact signature for the functions passed as arguments (but probably one can?).

I also want to remark that it is possible for certain functions to have different algorithms depending on whether one only wants to know the bool or also the auxiliary information.

[fingolfin]

Callbacks: interesting idea, thanks for mentioning this. May personal thoughts are that it can be OK for internal stuff that only "hardcore" programmers interact with; but I don't think the average user will be happy (or even able...) to use them...

I also want to remark that it is possible for certain functions to have different algorithms depending on whether one only wants to know the bool or also the auxiliary information.

Yes, absolutely! That's absolutely the case; I listed this example under option 3:

e.g. if both groups have same order and it is prime, they must be isomorphic...

So is_isomorphic may end up doing quite different computations than is_isomorphic_with_maps or isomorphism.

[fieker]

There are no really good options here:

• type stability, to my understanding, is irrelevant in cases like is_isomorphic as this is really expensive. If you're worried, you can add the assertion on the callers side
• it needs to be workable. Callbacks are fine, in some situations, but totally confusing to non specalists. Also, there are situations where the 2nd return value is (currently)(de facto) always computed, hence "for free", and others (hnf) where the 2nd return value might dominate the runtime
• direct sum is difficult: when used as a binary operator, it can only return one value. As a "normal" function, it can do more.
• exceptions are expensive, yes, but that just means to not use them as a means of communication... if I, as a user ask for an isomorphism between 2 objects, then an error is fine if they are not. If, as a programmer, I try to "abuse" this to implement a test for isomorphism - without possibly computing it - then an excepction is bad.
• On the other hand, in ECM, propagating the failed inverse from deep down in the algorithm: this is what exceptions are for! Code doesn't become more readable or maintainable by guarding every function call with checking of return values..

[fieker]

PS.: especially if code was originally not even written to support the failed division/ inversion as an asset...

[fingolfin]

To be clear, I think exceptions are super useful, and wish we had them in GAP. Be it for handling weird edge cases, or by aborting computations across several layers, as in your ECM examples.

Actually, thinking about it now makes me realize that there is one advantage using them for e.g. isomorphism over option 4 (return nothing): with the latter, if code "knows" that inputs are isomorphic, and hence does not bother to check the return value with isnothing, this results in type unstable code. But if an exception is thrown, that's not the case. The downside of exception is: if you call isomorphism many times, and expect a lot of non-isomorphic groups, the overhead does add up. But of course, as you pointed out, isomorphism computation in general is expensive anyway, so the cost of catching the exception may not matter that much...

I wanted to know a bit better what timings we are talking about, so I run a little benchmark. This is my test code:

function myiso_nothing(x::Int, y::Int)
    x == y && return :iso
    return nothing
end

function myiso_exception(x::Int, y::Int)
    x == y && return :iso
    error("inputs are not isomorphic")
end

function test_nothing(x::Int, L::AbstractVector{Int})
   count = 0
   for y in L
     iso = myiso_nothing(x, y)
     isnothing(iso) && continue
     count += 1
   end
   return count
end

function test_nothing_all_good(x::Int, L::AbstractVector{Int})
   count = 0
   for y in L
     iso = myiso_nothing(x, y)
     # no check, we just assume everything to be isomorphic
     count += 1
   end
   return count
end

function test_exception(x::Int, L::AbstractVector{Int})
   count = 0
   for y in L
     try
       iso = myiso_exception(x, y)
       count += 1
     catch
     end
   end
   return count
end

function test_exception_all_good(x::Int, L::AbstractVector{Int})
   count = 0
   for y in L
     iso = myiso_exception(x, y)
     # no check, we just assume everything to be isomorphic
     count += 1
   end
   return count
end

And these are some test results:

julia> using BenchmarkTools

julia> data = fill(5,10); @btime test_nothing(5, data);
  11.428 ns (0 allocations: 0 bytes)

julia> data = fill(4,10); @btime test_nothing(5, data);
  11.512 ns (0 allocations: 0 bytes)

julia> data = fill(5,10); @btime test_nothing_all_good(5, data);
  8.917 ns (0 allocations: 0 bytes)

julia> data = fill(5,10); @btime test_exception(5, data);
  123.569 ns (0 allocations: 0 bytes)

julia> data = fill(4,10); @btime test_exception(5, data);
  522.792 μs (10 allocations: 160 bytes)

julia> data = fill(5,10); @btime test_exception_all_good(5, data);
  13.054 ns (0 allocations: 0 bytes)

As you can see using a try/catch block slows things down even if there are no exceptions being thrown. However, we are talking about something like 11 nanoseconds per loop iteration. Even in fast cases, computing those isomorphisms will usually be several orders of magnitude slower:

julia> G=GAP.Globals.CyclicGroup(5);

julia> @btime GAP.Globals.IsomorphismGroups(G,G);
  5.910 μs (131 allocations: 8.17 KiB)

As predicted, the situation is bit different when there actually are exceptions.

Anyway, not sure what conclusion I am drawing from this right now, but at least next time I wonder what the performance impact really is, I can look here ;-)

[HechtiDerLachs]

1. This has already become the convention for several constructors, for instance for quo: It always returns the new object and the map relating it to the original object. I think it makes sense to make one such convention all over Oscar, because users will most likely be very confused and annoyed if such choices are not coherent.
2. Personally, I strongly object keyword arguments for such purposes. Because of the already mentioned reasons: They break type stability and make the functions behavior inconsistent in general. For me as a user, this is not only about type stability, but about workflow, really. I want to have one clear picture in mind, how functions behave throughout Oscar and not be forced to look up the output format of return values, given special keywords! Also, it seems that it would really be the julia thing to do to introduce several functions with longer (resp. extended) names for specific purposes and not introduce a second artificial 'dispatch-level' using keywords. I know that this is not about dispatch, really, but it comes close to replacements of dispatch via internal if typeof(input_var) <: Type1 ... else if typeof(input_var)<: Type 2... end that can, at times, still be found in the code. Since we already have the powerful framework for multiple dispatch from julia, why refer to such second layers? To me this seems just wrong and potentially confusing for follow up programmers that will eventually pick up on the code in some months/years from now.
3. An existing example of how to resolve the issues with is_isomorphic is the divexact vs. divides routine, right? This works just fine for me as I can choose my favourite function depending on the actual use case: If I am not sure that a is divisible by b, then I call divides. Otherwise, even throwing an error is fine, since then I probably did some mistakes in my code elsewhere. I picked up on such conventions recently in my PR for has_non_empty_intersection(U::AbsMultSet, I::Ideal), which checks whether $U \cap I \neq \emptyset$ and, in the affirmative case, returns an element in that intersection as a linear combination of the generators of I. Here, it is customary to provide the option to skip the check (which might be expensive) via an additional keyword. However, I think it is important that this does not affect the output format. I found this approach to work quite well.
4. Good to know that type splitting does not ruin julias runtime completely. Also for iterators, this is the mandatory way to go already from the julia side, right? But in 'low-level routines', such as e.g. divides, I would refrain from using these.

[HechtiDerLachs]

I do not really see the problem with the code duplication here. Personally, I would prefer not to wrap some internal routine with an if ... else if ... end block into a posteriori type-stable methods. In the end, every method does something else! And if they need some common intermediate product (as for instance A+B in the above example), it is probably worthwhile writing another internal function for that that can be called by either one of the user facing ones.

I did not encounter a situation, where this approach lead to severe code duplication, yet. But if something is already written up and easy to wrap this way for the moment, then, of course, I am not objecting.

[fingolfin]

But you don't have to use an if ... elseif ... end block (though I'd like to point out that this is exactly what several of the existing methods are doing right now!), I just did that for the sake of the example where people were concerned about code duplication. Of course you can also do this:

function direct_sum(::Val{:none}, A::T, B::T) where {What, T <: Integer}
    return A+B
end 

function direct_sum(::Val{:sum}, A::T, B::T) where {What, T <: Integer}
    return A+B, :+
end

function direct_sum(::Val{:prod}, A::T, B::T) where {What, T <: Integer}
    return A+B, :*
end

function direct_sum(::Val{:both}, A::T, B::T) where {What, T <: Integer}
    return A+B, :+, :*
end

[fingolfin]

(I should note that I am also not a fan of the terms ":sum" and ":prod" here, I'd prefer ":injections" and ":projections" or something like that, but I wanted to focus on the argument at hand, not start yet another side discussion. So, don't take my code snippet as endorsement of these names, just as me trying to match the status quo)

[HechtiDerLachs]

function direct_sum(::Val{:none}, A::T, B::T) where {What, T <: Integer}
    return A+B
end 

function direct_sum(::Val{:sum}, A::T, B::T) where {What, T <: Integer}
    return A+B, :+
end

function direct_sum(::Val{:prod}, A::T, B::T) where {What, T <: Integer}
    return A+B, :*
end

function direct_sum(::Val{:both}, A::T, B::T) where {What, T <: Integer}
    return A+B, :+, :*
end

And that is precisely what I would do. I don't see any problem with code duplication here. But I don't say that there can be no cases where this is not the best solution! It's just that personally I did not encounter them.

Either way, this is becoming a discussion on coding style rather than return values, which was not really the point. I mean, as long as we agree on the fact that we want fixed return types for fixed function names.

[fingolfin]

The problem with code duplication can crop up when the code for computing the injections resp. projections needs to be duplicated. It's great that in your cases, this is not a problem, but apparently it can be in others, so I choose to just believe the people who claims so :-)

The point of my example with value types is that both styles are possible: you can write four methods if this is more convenient for you, or a single one (or even a mix). And be type stable in either case if you do it right. And all of that can be hidden from the user, too, as my example showed; we can even provide consistent default in case we want to keep using a keyword argument.

[fingolfin]

So right now I am trying to apply this to the function is_pgroup, which right now returns a boolean and a prime. My plan is to split this into two:

1. the function is_pgroup stays but from now on only returns a boolean
2. I could add a function is_pgroup_with_prime, but the prime is cached inside the group anyway, so it's not strictly necessary -- but of course future implementation of group objects may not do such caching... so should I added it
3. a new function prime_pgroup (off-topic: or should it be prime_of_pgroup ?) returns the prime $p$ for which the input group is a $p$-group.

This leaves the question how to deal with corner cases, once in is_pgroup_with_prime and once in prime_pgroup:

1. when the group is trivial, then any prime could be returned... in GAP the special value fail is returned then. What should I do? Return nothing ? Return any prime, e.g. 2? Return a special integer like 0 or 1 or -1? Throw an exception?
2. when the group is not a p-group, then again: what to do?

Of course the answers may differ for the two functions:

• is_pgroup_with_prime should definitely not raise an exception
• for type stability reasons, is_pgroup_with_prime should perhaps return a "fake primes" for the two corner cases? But which ones? (and different values for trivial vs. non-pgroup?)
• for prime_pgroup I plan to have a variant where you can specify the desired return type anyway, e.g. prime_pgroup(Int, G) if you are sure the prime is small. From this POV, allowing it to return nothing for non-p-groups would somewhat fit in....

Aaaanyway: for now I will follow the precedent we set with is_isomorphic and friends:

1. is_pgroup returns just a bool, like is_isomorphic
2. is_pgroup_with_prime return a Tuple{Bool,fmpz}; for the trivial group the prime will be .... 1 (because at least it divides the group order???)?? for non-p-groups it will be ... 0 ?3.
   • It will also have an optional first argument to indicate the desired type of the second return value (so that you can get an Int if you know your groups are defined over small-ish primes.
3. prime_pgroup will throw an exception for trivial groups and non-p-groups.
   • It will also have an optional first argument to indicate the desired return type.

Sounds OK?

[fieker]

I'd rather not return a fake prime - it is going to bite you one way or other later. Trivial groups (and rings) always seem to require special cases, so here I'd rather throw an error if a prime is desired: returning 2 or 3 breaks the idea of p dividing the group order, 1, or -1 breaks the ideal of being able to compute residue fields or valuations. Are there "any" generic p-group methods that would apply to the trivial group?

[fingolfin]

Not really, other in "trivial" cases, but I mean, the trivial group is trivial to handle with anyway, no need to apply p-group code to it.

Anyway, for prime_pgroup it's clear to me that the trivial group should just give an error.

Now if the trivial group can pop up and results in an error when calling is_pgroup_with_prime on it, then some code may need to add checks like is_trivial(G) before that. Which of course is not a major issue, just slightly inconvenient.

But what about non-trivial non-pgroups? What should the second return value for is_pgroup_with_prime be? If we don't want a "fake prime" like 0 here, what else then? (to be clear: I am not a fan of "fake" return values either -- likewise the non-bijective homomorphism returned by is_isomorphic_with_map is also borderline for me).

Perhaps the answer in this case is to simply not bother with is_pgroup_with_prime, as there is no cost saving for using it over is_pgroup plus prime_pgroup anyway? Alas, that this is so is kind of an implementation detail, so I am slightly wary about settling on that...

[fieker]

On Tue, May 24, 2022 at 12:31:18AM -0700, Max Horn wrote: Not really, other in "trivial" cases, but I mean, the trivial group is trivial to handle with anyway, no need to apply p-group code to it. Anyway, for `prime_pgroup` it's clear to me that the trivial group should just give an error. Now if the trivial group can pop up and results in an error when calling `is_pgroup_with_prime` on it, then some code may need to add checks like `is_trivial(G)` before that. Which of course is not a major issue, just slightly inconvenient. But what about non-trivial non-pgroups? What should the second return value for `is_pgroup_with_prime` be? If we don't want a "fake prime" like 0 here, what else then? (to be clear: I am not a fan of "fake" return values either -- likewise the non-bijective homomorphism returned by `is_isomorphic_with_map` is also borderline for me). Perhaps the answer in this case is to simply not bother with `is_pgroup_with_prime`, as there is no cost saving for using it over `is_pgroup` plus `prime_pgroup` anyway? Alas, that this is so is kind of an implementation detail, so I am slightly wary about settling on that...

The convention (or my understandanding) is that is_..._with_... has 2 cases true + meaningful false + garbage historically, for type stability, garbage had to ave the correct type (hence fake primes and similar - and I was bitten by it as I ignored the false...) If julia is up to it, I'd be happy with false + nothing But the key point is to, mostly, not throw errors but return false

…

-- Reply to this email directly or view it on GitHub: #1348 (reply in thread) You are receiving this because you commented. Message ID: ***@***.***>

[HechtiDerLachs]

This is not a plea against the return format (true/false, data), right? Because, as you say, you are only going to be bitten when you ignore the true/false part; so just catch that and you should be fine.

[fingolfin]

Yeah, so I am confused as to what @fieker is saying here with respect to is_pgroup_with_prime: if the second value is not allowed to be garbage / "a fake prime" then either we must return something like nothing (which @thofma seems to be concerned about), or else we don't provide that function at all.

So which do you prefer here, @fieker ?

[thofma]

If one gets bitten by a garbage result, one was not interested in the is_ part and should have called prime_pgroup directly (just taking this as an example).

[fingolfin]

Fair enough. And I was prepared to just return garbage in the second value, but @fieker's comment confused/s me

[fingolfin]

I've thought more about it, and now think this: humans make mistakes, and so even if I intend to properly use is_FOO_with_BLA function, I can make a mistake and slip up.

As it is, there is a choice:

1. either we provide "safe" defaults, and anyone who wants fast code (here: type stable) needs to jump through extra hoops (here: code the checks the right way / add a type assertion in the right place)
2. or we provide "fast" defaults, and anyone who wants to be safe from mistakes must be perfect and just not make mistakes.

For me it's a no brainer that 1 is what I want. And I wish more software in general would do that (and CAS in particular).