MNT: Make `is_convex` consistently return something of type `(result, envelope)`

[knappa]

The function is_convex has an inconsistent return type, returning either a boolean or a tuple. This causes the tuple unpacking at line 1226 to fail: https://github.com/tulip-control/polytope/blob/beadd1263adda6093c8ced3db1afd1a6ceeb069c/polytope/polytope.py#L1226 when either https://github.com/tulip-control/polytope/blob/beadd1263adda6093c8ced3db1afd1a6ceeb069c/polytope/polytope.py#L999-L1000 or https://github.com/tulip-control/polytope/blob/beadd1263adda6093c8ced3db1afd1a6ceeb069c/polytope/polytope.py#L1001-L1002 is triggered. As mentioned in @johnyf 's comment below, the first of these tests is in error as polytopes that are not full-dimensional can be convex. The updated PR deletes the erroneous test.

[johnyf]

Thank you for finding this API bug. The function polytope.polytope.is_convex is named as a predicate (a Boolean-valued expression). Based on the naming convention in CPython (e.g., the function os.path.isfile) and other software, I would suggest that the function is_convex in all cases return a value of type bool.

Regarding current usage, within polytope the function is_convex is called at only one line:

https://github.com/tulip-control/polytope/blob/beadd1263adda6093c8ced3db1afd1a6ceeb069c/polytope/polytope.py#L1226

The variable env that is assigned on the above line is unused. So env could have been _, though that would still store the returned Polytope object. To reuse the memory from the object referenced by the variable _, the statement del _ would be needed in CPython (and it seems that the memory deallocation that is made possible by del _ would be deferred in PyPy, based on how PyPy's memory management works, because the memory deallocation is an implementation detail and not part of Python's specification).

So this API change requires changing only one other line outside of the function is_convex.

The suggested change would be an API change due to what the docstring of the function is_convex currently specifies:

https://github.com/tulip-control/polytope/blob/beadd1263adda6093c8ced3db1afd1a6ceeb069c/polytope/polytope.py#L995-L997

Given that the set of input arguments to function is_convex that resulted in returning a bool value (instead of a tuple) is of measure zero (for the case of region having a nonempty list of polytopes), it is expected that this API change can affect code that uses the package polytope. Nonetheless, I think that parts of the API can change (the regular expression 0\..*\..* matches polytope's version), provided that suitable error messages be given, and a deprecation period ensue, where applicable.

In this case, the implementation of the signature of function is_convex has a bug. The current change in this pull request, to in all cases return a tuple, could be applied first, together with raising a FutureWarning that would inform about the upcoming API change. After a number of releases of the package polytope, the API change would be applied.

In this particular case, it seems to me that the change to in all cases return from function is_convex a bool value could be included in the next release of polytope (so without first changing to a FutureWarning). A bool value cannot be unpacked, so any existing call sites outside of the package polytope will raise an exception:

TypeError: cannot unpack non-iterable bool object

Thus, the API change will not result in a silent error.

About deprecation policies, PEP 387 defines CPython's deprecation process (PEP 4 is relevant), and NEP 23 numpy's deprecation policy.

Regarding the title of the commit message, I would recommend using the prefixes defined in numpy's documentation (with "MNT" for maintenance), and summarizing the change within 50 characters, with more details placed in the rest of the commit message (which if applicable can start with a more detailed version of the title line without the prefix).

Other bugs

The function is_convex returns True if is_fulldim returns False:

https://github.com/tulip-control/polytope/blob/beadd1263adda6093c8ced3db1afd1a6ceeb069c/polytope/polytope.py#L999-L1000

This appears to be an error, because a polytope can be nonconvex and have dimension smaller than the ambient (Euclidean) space.

Another note is what happens when there are no polytopes in a nonconvex polytope's (region's) list of polytopes:

https://github.com/tulip-control/polytope/blob/beadd1263adda6093c8ced3db1afd1a6ceeb069c/polytope/polytope.py#L1001-L1002

I am not sure why the function is_convex returns True in this case, which would imply to the caller that the given polytope is convex. Whether the code of polytope relies on assigning this meaning to empty lists of convex polytopes needs further checking. In any case, I would suggest raising a ValueError in this case, because:

• the empty set of points can be represented using the halfspace representation (e.g., x <= -1 /\ -x <= -1)
• the ambient (Euclidean) space can be represented using the halfspace representation (by A and b having zeros)
• any other subset of the ambient space (e.g., a point) requires storing more information than the amount of information contained in an empty list (assuming that the ambient space has at least 1 dimension).

So it seems that relevant use cases can be accommodated without using an empty list (and for any other reason, None could be assigned to the attribute where the list of polytopes is stored).

[knappa]

Also, I think that a related error occurs at https://github.com/tulip-control/polytope/blob/beadd1263adda6093c8ced3db1afd1a6ceeb069c/polytope/polytope.py#L1015-L1016 as outer.diff(reg) should have a higher co-dimension than reg, but the test as-written will only produce the correct result when reg is itself full-dimensional. I'm leaving this one alone, as I don't know how you want to fix that.

[victoraalves]

Hi all,

I also came across this bug when trying to create a polytope as a union of other ones, due to the OP's same reason . I see that the PR is still pending. Are there any updates or foreseeable releases in the near future fixing this in Polytope?

Thanks in advance.

[slivingston]

I see that the PR is still pending. Are there any updates or foreseeable releases in the near future fixing this in Polytope?

@victoraalves My best estimate is that we will work on this in the next 3 days.