Refined protocol for _element_constructor_ in element classes with mutability

[sagetrac-nailuj]

Problem description:

Given a vector v with base ring R, the constructions

• w = vector(R, v)
• w = vector(v, R)
• w = vector(v)
  all return the original vector v. As a consequence, all changes applied to w are also applied to v and vice versa.

sage: v = vector([1,2,3])
sage: w = vector(v, ZZ)
sage: w is v
True
sage: w[1] = 7
sage: v
(1, 7, 3)

Proposal:

The __call__ method of a parent object serves several purposes: In one-argument calls, (1) it is the identity (in the strong sense of Python's id) on elements of its parent and (2) in general, a convert map, with (3) input 0 as a permissive special case, which is also the default argument of Parent.__call__. (4) In multiple-argument calls, it is the element constructor.

Proposal: Define a general protocol for element classes with mutability which does NOT change the above but only refines it for mutable classes as follows:

• In element classes with mutability, _element_constructor_(x, ...) MUST support optional arguments copy and mutable.

• These arguments are allowed to have various defaulting behavior that is the most appropriate for the specific class, but there are some restrictions:

• copy MUST NOT default to True for mutable inputs x because (as discussed) this is not compatible with (1).

• mutable=False and copy=False MUST be an error for mutable input x.

Moreover, arithmetic operations need to be consistent: Either always return a new element (even for trivial operations), or always return an immutable element.

We add _test_... methods that check this protocol.

Related:

• https://groups.google.com/g/sage-devel/c/DNrbtItMVmQ
• Guide for parents with immutable elements #32353 Guide for parents with immutable elements

CC: @kliem @mjungmath @mkoeppe @tscrim @nbruin @dcoudert @mwageringel @pjbruin @kwankyu @williamstein

Component: misc

Keywords: vector, constructor, copy

Branch/Commit: u/mkoeppe/refined_protocol_for__element_constructor__in_element_classes_with_mutability @ 501e7ef

Issue created by migration from https://trac.sagemath.org/ticket/29101

[sagetrac-nailuj]

comment:1

Some examples for comparison:

For basic python types,
similar constructions return

• a new object, if it's mutable (list, set, dict)

sage: L = [1,2,3]
sage: M = list(L)
sage: L is M
False
sage: S = {1,2,3}
sage: T = set(S)
sage: S is T
False
sage: D = dict({1:2, 3:4})
sage: E = dict(D)
sage: D is E
False

• the old object, if it's immutable (tuple)

sage: X = (1,2,3)
sage: Y = tuple(X)
sage: X is Y
True

Regarding two examples of Sage objects,

• in Graphs, a new object is returned, whether the old one was set immutable or not

sage: G = graphs.CompleteGraph(5)
sage: H = Graph(G)
sage: H is G
False

• in Sets, which wrap around an immutable frozenset, the old object is returned

sage: S = Set([1,2,3])
sage: T = Set(S)
sage: S is T
True

[mkoeppe]

comment:3

Moving tickets to milestone sage-9.2 based on a review of last modification date, branch status, and severity.

[mjungmath]

comment:5

We have a similar discussion running for FiniteRankFreeModule and elements in the manifolds module, take a look at #30302, especially comment:3.

In my opinion, this should not happen.

[mjungmath]

comment:6

Even though the corresponding check via the flac copy is implemented in FreeModule, the coercion model preempts it. The corresponding change should be

-        if R is self and no_extra_args:
-            return x

in sage.structure.parent.Parent.

But I don't know anything about the whole string of consequences coming from this.

[mjungmath]

comment:7

Just for fun, I've deleted these lines and ran a doctest:

File "src/sage/structure/parent.pyx", line 1473, in sage.structure.parent.Parent._is_valid_homomorphism_._is_coercion_cached
Failed example:
    R._is_coercion_cached(QQ)
Expected:
    False
Got:
    True

[mkoeppe]

comment:8

Note that FreeModule_generic._element_constructor_ has some optional arguments...

    def _element_constructor_(self, x, coerce=True, copy=True, check=True):

[mjungmath]

comment:9

Replying to @mkoeppe:

Note that FreeModule_generic._element_constructor_ has some optional arguments...

    def _element_constructor_(self, x, coerce=True, copy=True, check=True):

Regarding the default copy=True argument, a copy should be returned. But it is not due to the coercion framework.

[mkoeppe]

comment:10

Right. So how about changing this default to False?
If one really needs a copy (which is currently not guaranteed, as you have observed), then one would call it with copy=True. I think (haven't tested!) that this will not go through coercion because this path is only taken for 1-argument calls of the parent.

[mjungmath]

comment:11

This could only be a temporary solution. As you already pointed out, and I totally agree with you, the element constructor should behave consistently, i.e. always returning a mutable element. Returning the very same instant, assuming it is immutable, would contradict this behavior.

[mkoeppe]

comment:12

Replying to @mjungmath:

As you already pointed out, and I totally agree with you, the element constructor should behave consistently, i.e. always returning a mutable element. Returning the very same instant, assuming it is immutable, would contradict this behavior.

I don't think this is my position; if I did say this, let me try to refine it here.

In #30302 comment:3 I pointed out that arithmetic operations need to be consistent: Either always return a new element (even for trivial operations), or always return an immutable element.

It is not true that the parent object "is" the element constructor. Its __call__ methods serves several purposes: In one-argument calls, (1) it is the identity (in the strong sense of Python's id) on elements of its parent and (2) in general, a convert map, with (3) input 0 as a permissive special case, which is also the default argument of Parent.__call__. (4) In multiple-argument calls, it is the element constructor.

My proposal is to define a general protocol for element classes with mutability which does NOT change the above but only refines it for mutable classes as follows:

• In element classes with mutability, _element_constructor_(x, ...) MUST support optional arguments copy and mutable.

• These arguments are allowed to have various defaulting behavior that is the most appropriate for the specific class, but there are some restrictions:

• copy MUST NOT default to True for mutable inputs x because (as discussed) this is not compatible with (1).

• mutable=False and copy=False MUST be an error for mutable input x.

We could add _test_... methods that check this protocol.

[mjungmath]

comment:16

Replying to @mkoeppe:

Replying to @mjungmath:

As you already pointed out, and I totally agree with you, the element constructor should behave consistently, i.e. always returning a mutable element. Returning the very same instant, assuming it is immutable, would contradict this behavior.

I don't think this is my position; if I did say this, let me try to refine it here.

In #30302 comment:3 I pointed out that arithmetic operations need to be consistent: Either always return a new element (even for trivial operations), or always return an immutable element.

I was more referring to your first paragraph:

Both M() and M(0) return a new mutable element. That's how one creates a new vector, whose components can then be modified. If you want the immutable 0 element, you can use M.zero().

Consider the following code:

sage: M = FreeModule(QQ, 3)
sage: v = M([1,2,3])
sage: v.set_immutable()
sage: M(v).is_immutable()
True

I don't see a point if the element constructor sometimes returns a mutable and sometimes an immutable element. This is how I understood your argument that we should M(0) return a new mutable "zero" istead of the same instance as M.zero(). If it really doesn't matter whether the element is mutable or not, we should allow M(0) returning the cached M.zero() instance since this is much much faster (especially in the manifold setting).

I'd say, if M a priori creates mutable elements, the element constructor should always return mutable elements. This would be consistent.

[mkoeppe]

comment:19

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:20

Setting a new milestone for this ticket based on a cursory review.

[nbruin]

comment:22

Given that in some parents it is possible to create both mutable and immutable elements, having a mutable parameter for the relevant _element_constructor_ makes perfect sense. Calls to it are usually only made indirectly, since generally element construction happens through conversion or coercion. So we still need methods for getting the appropriate setting to it and most importantly, control what the default value is that needs to be passed in. In particular, for arithmetic like

D=dict()
D[v+w] = D[v]+D[w]

we need a way to have parents that use default value "immutable".

In the usual paradigm of mutable data structures, there should be a way of getting an uninitialized mutable element; something like v=VectorSpace(QQ,3).mutable_element and, it being mutable, should have an easy way of being assigned to; like v.assign(bla) or, perhaps more pythonic, v[:]= ....

With that in place, there would be a clear expressive way for people to get mutable vectors and matrices, freeing up the default constructors to just produce immutable elements. This would be quite backwards incompatible, but that might be a hit we need to take.

Note that for efficient use of mutable elements, we need a whole slew of extra routines as well, because normal expression notation doesn't jive with efficient use of mutable data structures.
For instance, for efficient mutable vector sums and scalar products, we'd need

v.assign_sum(v,w) #make sure in-place mutation works!
v.scale_by(c)

See the API of libraries like mpfr for inspiration.

[tscrim]

comment:23

For that, we would want to (also?) override __iadd__, __imul__ etc. for += and -=.

[mkoeppe]

comment:24

Replying to @tscrim:

For that, we would want to (also?) override __iadd__, __imul__ etc. for += and -=.

Yes. Does the coercion system already have preparation for this at all?

[tscrim]

comment:25

Replying to @mkoeppe:

Replying to @tscrim:

For that, we would want to (also?) override __iadd__, __imul__ etc. for += and -=.

Yes. Does the coercion system already have preparation for this at all?

Strictly speaking, coercion doesn't quite make sense here because the coefficients might have to leave the current coefficient ring (say, we are working over ZZ['x'] and then add something in QQ, we get something in QQ['x']). So it doesn't quite fit into the pattern for the other binary operators. Instead, we would need something like this:

P = self.parent()
if P.has_coerce_map_from(other.parent()):
    return self.inplace_add(P(other))
return coercion_model.bin_op(self, other, op)

However, we currently do not have, e.g., _iadd_ methods. Perhaps we should have a generic one? This might slow some code down due using v += w for some extra indirection/checks when it has the same result as v = v + w.

[mkoeppe]

comment:26

I agree, this is not a normal binop-coercion; nevertheless taking care of it is a task for the coercion system, so I'm +1 for single-underscore _iadd_ etc. methods.

[mkoeppe]

Branch: u/mkoeppe/refined_protocol_for__element_constructor__in_element_classes_with_mutability

[mkoeppe]

comment:28

Here's the beginning of a _test_... method to enforce the proposed protocol.

git grep mutable= reveals that various classes use the keyword mutable=..., others use immutable=.... Should we aim to support both for all classes?

---

New commits:

501e7ef

Parent._test_call: New

[mkoeppe]

Commit: 501e7ef

[nbruin]

comment:30

Replying to @mkoeppe:

I agree, this is not a normal binop-coercion; nevertheless taking care of it is a task for the coercion system, so I'm +1 for single-underscore _iadd_ etc. methods.

Before you start designing all kinds of fancy features, I think you first want to establish a need. I don't think there is one. By the time you need micro-optimizations such as using mutable structures and in-place modification, you don't want the overhead of coercion to occur.

Anyway, for a v += w the question really is: is there a coercion from w.base_ring() into v.base_ring() or for v *= c if there is an action of c on v and whether you can unwind that to a coefficient-wise operation (the action discovery currently available won't tell you).

In any case, these 2-argument mutation operations do not cover what is needed for efficient mutable object manipulation. There is the three-argument version too:
for i in range(n): u[i] = v[i] + w[i] where the target is not one of the operands. It would really defeat the purpose if you'd have to execute that as u[:]=v; u+=w.

(I have some recent experience with inplace mutation (with mpfr) in order to get a fast evaluation of Riemann theta functions -- ticket TBA :-). If these inplace features above would have existed, I would still not have used them, because I really needed the 3-operand versions and because I wouldn't want to pay the incref/decref price for manipulating python objects. Make sure you have a usage scenario before you design the tools!)

[mkoeppe]

comment:31

Replying to @nbruin:

for a v += w the question really is: is there a coercion from w.base_ring() into v.base_ring() or for v *= c if there is an action of c on v and whether you can unwind that to a coefficient-wise operation (the action discovery currently available won't tell you).

That's a great point, although for sparse updates of the kind (large_sparse_vector += small_sparse_vector) even with coercion kicking in on the route __iadd__ -> _iadd_ ( converting small_sparse_vector first), there could be a speedup over what we have now.

In any case, I wouldn't expect that anyone has immediate plans to work on the mutable-update business, so we can shelve this until a need arises.