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:  sage9.8 
Component:  misc  Keywords:  vector, constructor, copy 
Cc:  ghkliem, 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: 
Description (last modified by )
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 oneargument 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 multipleargument 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 argumentscopy
andmutable
.
 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 toTrue
for mutable inputsx
because (as discussed) this is not compatible with (1).
mutable=False
andcopy=False
MUST be an error for mutable inputx
.
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/sagedevel/c/DNrbtItMVmQ
 #32353 Guide for parents with immutable elements
Change History (34)
comment:1 Changed 3 years ago by
comment:2 Changed 3 years ago by
Status:  new → needs_info 

comment:3 Changed 3 years ago by
Milestone:  sage9.1 → sage9.2 

Moving tickets to milestone sage9.2 based on a review of last modification date, branch status, and severity.
comment:4 Changed 2 years ago by
Cc:  Michael Jung added 

comment:5 Changed 2 years ago by
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
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.
comment:7 Changed 2 years ago by
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 followup: 9 Changed 2 years ago by
Note that FreeModule_generic._element_constructor_
has some optional arguments...
def _element_constructor_(self, x, coerce=True, copy=True, check=True):
comment:9 Changed 2 years ago by
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
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 1argument calls of the parent.
comment:11 followup: 12 Changed 2 years ago by
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 followup: 16 Changed 2 years ago by
Summary:  New vector from old vector returns the same object → Refined protocol for _element_constructor_ in element classes with mutability 

Replying to ghmjungmath:
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 oneargument 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 multipleargument 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 argumentscopy
andmutable
.
 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 toTrue
for mutable inputsx
because (as discussed) this is not compatible with (1).
mutable=False
andcopy=False
MUST be an error for mutable inputx
.
We could add _test_...
methods that check this protocol.
comment:13 Changed 2 years ago by
Cc:  Nils Bruin added 

comment:14 Changed 2 years ago by
Cc:  David Coudert added 

comment:15 Changed 2 years ago by
Cc:  Markus Wageringel added 

comment:16 Changed 2 years ago by
Replying to mkoeppe:
Replying to ghmjungmath:
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()
andM(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 useM.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.
comment:17 Changed 2 years ago by
Milestone:  sage9.2 → sage9.3 

comment:18 Changed 2 years ago by
Cc:  Peter Bruin added 

comment:19 Changed 21 months ago by
Milestone:  sage9.3 → sage9.4 

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:20 Changed 17 months ago by
Milestone:  sage9.4 → sage9.5 

Setting a new milestone for this ticket based on a cursory review.
comment:21 Changed 16 months ago by
Cc:  Kwankyu Lee William Stein added 

Description:  modified (diff) 
comment:22 Changed 16 months ago by
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 inplace mutation works! v.scale_by(c)
See the API of libraries like mpfr
for inspiration.
comment:23 followup: 24 Changed 16 months ago by
For that, we would want to (also?) override __iadd__
, __imul__
etc. for +=
and =
.
comment:24 followup: 25 Changed 16 months ago by
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 Changed 16 months ago by
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 followup: 30 Changed 16 months ago by
I agree, this is not a normal binopcoercion; nevertheless taking care of it is a task for the coercion system, so I'm +1 for singleunderscore _iadd_
etc. methods.
comment:27 Changed 16 months ago by
Branch:  → u/mkoeppe/refined_protocol_for__element_constructor__in_element_classes_with_mutability 

comment:28 Changed 16 months ago by
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:
501e7ef  Parent._test_call: New

comment:29 Changed 16 months ago by
Description:  modified (diff) 

comment:30 followup: 31 Changed 16 months ago by
Replying to mkoeppe:
I agree, this is not a normal binopcoercion; nevertheless taking care of it is a task for the coercion system, so I'm +1 for singleunderscore
_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 microoptimizations such as using mutable structures and inplace 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 coefficientwise operation (the action discovery currently available won't tell you).
In any case, these 2argument mutation operations do not cover what is needed for efficient mutable object manipulation. There is the threeargument 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 3operand 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 Changed 16 months ago by
Replying to nbruin:
for a
v += w
the question really is: is there a coercion fromw.base_ring()
intov.base_ring()
or forv *= c
if there is an action ofc
onv
and whether you can unwind that to a coefficientwise 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 mutableupdate business, so we can shelve this until a need arises.
comment:32 Changed 12 months ago by
Milestone:  sage9.5 → sage9.6 

comment:33 Changed 9 months ago by
Milestone:  sage9.6 → sage9.7 

comment:34 Changed 3 months ago by
Milestone:  sage9.7 → sage9.8 

Some examples for comparison:
For basic python types, similar constructions return
list
,set
,dict
)tuple
)Regarding two examples of Sage objects,
Graph
s, a new object is returned, whether the old one was set immutable or notSet
s, which wrap around an immutable frozenset, the old object is returned