Opened 3 years ago

Last modified 3 months ago

#29101 needs_info defect

Refined protocol for _element_constructor_ in element classes with mutability

Reported by: Julian Ritter Owned by:
Priority: major Milestone: sage-9.8
Component: misc Keywords: vector, constructor, copy
Cc: gh-kliem, Michael Jung, Matthias Köppe, Travis Scrimshaw, Nils Bruin, David Coudert, Markus Wageringel, Peter Bruin, Kwankyu Lee, William Stein Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/mkoeppe/refined_protocol_for__element_constructor__in_element_classes_with_mutability (Commits, GitHub, GitLab) Commit: 501e7ef60ae4f46843464ed6a7c93c0ea050dec3
Dependencies: Stopgaps:

Status badges

Description (last modified by Matthias Köppe)

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:

Change History (34)

comment:1 Changed 3 years ago by Julian Ritter

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
    

comment:2 Changed 3 years ago by Julian Ritter

Status: newneeds_info

comment:3 Changed 3 years ago by Matthias Köppe

Milestone: sage-9.1sage-9.2

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

comment:4 Changed 2 years ago by Matthias Köppe

Cc: Michael Jung added

comment:5 Changed 2 years ago by Michael Jung

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.

comment:6 Changed 2 years ago by Michael Jung

Cc: Matthias Köppe Travis Scrimshaw added

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.

Last edited 2 years ago by Michael Jung (previous) (diff)

comment:7 Changed 2 years ago by Michael Jung

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

comment:8 Changed 2 years ago by Matthias Köppe

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

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

comment:9 in reply to:  8 Changed 2 years ago by Michael Jung

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.

comment:10 Changed 2 years ago by Matthias Köppe

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.

comment:11 Changed 2 years ago by Michael Jung

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.

comment:12 in reply to:  11 ; Changed 2 years ago by Matthias Köppe

Summary: New vector from old vector returns the same objectRefined protocol for _element_constructor_ in element classes with mutability

Replying to gh-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 https://trac.sagemath.org/ticket/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.

comment:13 Changed 2 years ago by Matthias Köppe

Cc: Nils Bruin added

comment:14 Changed 2 years ago by Matthias Köppe

Cc: David Coudert added

comment:15 Changed 2 years ago by Matthias Köppe

Cc: Markus Wageringel added

comment:16 in reply to:  12 Changed 2 years ago by Michael Jung

Replying to mkoeppe:

Replying to gh-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 https://trac.sagemath.org/ticket/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.

Last edited 2 years ago by Michael Jung (previous) (diff)

comment:17 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:18 Changed 2 years ago by Matthias Köppe

Cc: Peter Bruin added

comment:19 Changed 21 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

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

comment:20 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

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

comment:21 Changed 16 months ago by Matthias Köppe

Cc: Kwankyu Lee William Stein added
Description: modified (diff)

comment:22 Changed 16 months ago by Nils Bruin

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.

comment:23 Changed 16 months ago by Travis Scrimshaw

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

comment:24 in reply to:  23 ; Changed 16 months ago by Matthias Köppe

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?

comment:25 in reply to:  24 Changed 16 months ago by Travis Scrimshaw

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.

comment:26 Changed 16 months ago by Matthias Köppe

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.

comment:27 Changed 16 months ago by Matthias Köppe

Branch: u/mkoeppe/refined_protocol_for__element_constructor__in_element_classes_with_mutability

comment:28 Changed 16 months ago by Matthias Köppe

Commit: 501e7ef60ae4f46843464ed6a7c93c0ea050dec3

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:

501e7efParent._test_call: New

comment:29 Changed 16 months ago by Matthias Köppe

Description: modified (diff)

comment:30 in reply to:  26 ; Changed 16 months ago by Nils Bruin

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!)

comment:31 in reply to:  30 Changed 16 months ago by Matthias Köppe

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.

comment:32 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:33 Changed 9 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:34 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.