mutable rows of immutable matrix?

[Nathann Cohen]

Hello everybody,

When calling .row() on an immutable matrix, one gets mutable vectors.
I can easily avoid it for the code I am writing, but do you think we
should do something about it?

sage: m = matrix.ones(10)
sage: m.set_immutable()
sage: hash(m.row(0))
...
TypeError: mutable vectors are unhashable

Nathann

[Nathann Cohen]

This is more problematic:

sage: v=vector([1,1,1])
sage: v.set_immutable()
sage: hash(2*v)

...
TypeError: mutable vectors are unhashable

Nathann

[William Stein]

On Fri, Oct 23, 2015 at 5:04 AM, Nathann Cohen <nathan...@gmail.com> wrote:
> Hello everybody,
>
> When calling .row() on an immutable matrix, one gets mutable vectors.
> I can easily avoid it for the code I am writing, but do you think we
> should do something about it?

m.row() returns a new (copy) of the row of the matrix, so making that
immutable would be inconsistent with how copy works for matrices.

sage: m = matrix.ones(10)
sage: m.set_immutable()

sage: copy(m).is_immutable()
False

The set_immutable method on matrices solves exactly *one* problem,
which is it makes it possible to create matrices and then efficiently
cache them without having to worry about some other code breaking
them. For example, it would be very bad indeed if the matrix T below
were mutable (like it was for a few years of Sage...):

sage: M = ModularSymbols(11)
sage: T2 = M.hecke_matrix(2); T2
sage: T2.is_immutable()
True

There are a **TON** of interesting programming problems that the idea
of "immutable data structures" can solve. Designing and implementing
immutable data structure that actually solve these problems is
interesting and highly nontrivial. It's not done in Sage to much
extent.

A good example in the Javascript world of a systematic library for
immutable data structures, which really solves some interesting
problems is

https://facebook.github.io/immutable-js/

It provides immutable versions of all standard Javascript data
structures, but very efficiently builds them on top of mutable data
structures, minimizing wasted space. It would be interesting to have
something similar in Sage, at least for matrices/vectors, but don't
think that we do now. What's in Sage is really trivial by comparison.
For starters, we might create a new immutable vector type in Sage
that is a reference to a row in an immutable matrix, etc., etc. It's
a lot of work to design and implement something like this.

At least you can do "v = m.row(0); v.set_immutable()".

-- William

>
> sage: m = matrix.ones(10)
> sage: m.set_immutable()
> sage: hash(m.row(0))
> ...
> TypeError: mutable vectors are unhashable
>
> Nathann
>

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/d/optout.



--
William (http://wstein.org)

[William Stein]

Work that I *really* wish somebody would get interested in doing! I
think it could be extremely useful for Sage.

William

>
> At least you can do "v = m.row(0); v.set_immutable()".
>
> -- William
>
>
>>
>> sage: m = matrix.ones(10)
>> sage: m.set_immutable()
>> sage: hash(m.row(0))
>> ...
>> TypeError: mutable vectors are unhashable
>>
>> Nathann
>>
>> --
>> You received this message because you are subscribed to the Google Groups "sage-devel" group.
>> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
>> To post to this group, send email to sage-...@googlegroups.com.
>> Visit this group at http://groups.google.com/group/sage-devel.
>> For more options, visit https://groups.google.com/d/optout.
>
>
>
> --
> William (http://wstein.org)

--
William (http://wstein.org)

[sage-goo...@lma.metelu.net]

On Fri, Oct 25, 2015 at 06:04:45AM -0700, William Stein wrote:
[...]

>
> At least you can do "v = m.row(0); v.set_immutable()".

There is some issue with this when trying to use set comprehension, see

http://ask.sagemath.org/question/30102/how-do-i-define-and-work-with-a-set-of-matrices/

Perhaps should we have a "mutable" argument (True by default to be consistent
with the current behaviour) in the matrix/vector constructors, so that we can
do:

{vector(m.row(0), mutable=False) for m in blah}

Ciao,
Thierry

[Nathann Cohen]

Yo,

> m.row() returns a new (copy) of the row of the matrix, so making that
> immutable would be inconsistent with how copy works for matrices.
>
> sage: m = matrix.ones(10)
> sage: m.set_immutable()
> sage: copy(m).is_immutable()
> False

I do not see why matrix.row(0) should return a *copy* of the row when
the matrix is immutable.

Depending on how matrices are implemented matrix.row(0) could very
well be a O(1) operation giving me a pointer toward an internal data
structure. Why not after all, since I can't modify what I have?

Plus there is nothing of 'copy' in the row(i) semantic. Ideally, here,
I would get a O(1) pointer toward internal data. As efficient as it
gets.

> At least you can do "v = m.row(0); v.set_immutable()".

I take the rows of a matrix, and multiply each of them by a set of values.

At first I wrote:

values = [...]
M.set_immutable()
M = [set([r*x for x in values]) for r in M]

But that does not work, because r is not immutable. Then I tried:

values = [...]
M = M.rows()
for r in M:
r.set_immutable()
M = [set([r*x for x in values]) for r in M]

But that does not work because multiplying an immutable row by
anything is not immutable anymore. So now I write

values = [...]
M = [[r*x for x in values] for r in M]
for r in M:
for x in r:
x.set_immutable()
M = map(set,M)

Easy, isn't it?

Nathann

[Nathann Cohen]

> Perhaps should we have a "mutable" argument (True by default to be consistent
> with the current behaviour) in the matrix/vector constructors, so that we can
> do:
>
> {vector(m.row(0), mutable=False) for m in blah}

That would be a "working fix", but really the problem is that
operations between immutable objects stubbornly keep returning
immutable objects that you don't want. I don't expect to see
"immutable + immutable = mutable" become practical anytime soon.

sage: M = Matrix()
sage: M.set_immutable()
sage: hash(M+M)
...
TypeError: mutable matrices are unhashable
sage: hash(tuple()+tuple())
3527539

And of course the same happens with our clusmy "copy" policy. But when
people refuse to see something, well...

Nathann

[Volker Braun]

On Friday, October 23, 2015 at 3:20:19 PM UTC+2, Nathann Cohen wrote:

Depending on how matrices are implemented matrix.row(0) could very
well be a O(1) operation

None of the examples you quoted would have a lower complexity with O(1) row references. If temporaries are a real problem (Benchmarks first, please) then why not use a library like Blitz++.

[Nathann Cohen]

> None of the examples you quoted would have a lower complexity with O(1) row
> references. If temporaries are a real problem (Benchmarks first, please)

Volker, please do not change the subject. I did not say that
complexity was a problem. My problem is with the behaviour of .row
which returns mutable rows from an immutable matrix. To illustrate it,
I merely mentionned that forcing .row( ) to return a *copy* also
forced us to have a linear-time method when we could expect a O(1) --
thus pointing another flaw of its current implementation.

Nathann

[Volker Braun]

On Friday, October 23, 2015 at 3:52:18 PM UTC+2, Nathann Cohen wrote:

Volker, please do not change the subject.

I did not.

 

I did not say that complexity was a problem.

So we agree that there is no performance problem, great. Then don't try to illustrate your problem with computational complexity, because as you said that is not a problem.

[Nathann Cohen]

> So we agree that there is no performance problem, great. Then don't try to
> illustrate your problem with computational complexity, because as you said
> that is not a problem.

O_o

Nathann

[Nils Bruin]

On Friday, October 23, 2015 at 6:20:19 AM UTC-7, Nathann Cohen wrote:

I do not see why matrix.row(0) should return a *copy* of the row when
the matrix is immutable.

It depends on the implementation. I think most matrices allocate their element store as a contiguous block. Hence the vectors aren't available as individual objects to own/reference.

You would need a vector object that remembers it's addressing part of the data of another object (and hence keep that object alive). This actually sounds like a "view" object, which python internally has for some things. I'd expect scipy/numpy also have good tools for it.

It really depends on your application whether doing this is a good or a horrible idea, though. But certainly the object lifetime considerations give a very good reason why our first implementations didn't bother.

[Nathann Cohen]

>> I do not see why matrix.row(0) should return a *copy* of the row when
>> the matrix is immutable.
>
>
> It depends on the implementation.

I agree, and that was my point. As you say, under different
circumstances (different implementation of matrices) we may have
chosen to return 'views' on the rows of an immutable matrix instead. I
am not proposing to do this in Sage: this would indeed require a heavy
amount of changes.

What I wanted to show is that there is nothing in the semantics of
matrix.row(i) that says that it is necessarily a copy. In different
software people did it differently, and that is fine too.

Thus, I claim that nothing in the semantics of .row( i ) hints at a
copy (especially for immutable matrices), and thus I do not believe
that .row() should follow the behaviour of copy(a_matrix).

In particular, I still believe that the behaviour of our objects should be [1]:
- immutable+immutable = immutable
- immutable*immutable = immutable
- immutable_matrix.row( i ) is an immutable vector.

As two examples showed, we have to get out of our way to set "back" to
immutable objects which we expect to be from the start. Otherwise it
is indeed very (very) hard to work with sets of immutable objects.

Nathann

[1] As it is the case in Python, as illustrated above with tuples.

[William Stein]

Hi Nathann,

What problem are you solving by using immutable matrices/vectors? Why
is anything immutable for what you are doing?

For reference, I explained above the actual problem which motivated my
writing immutable matrices/vectors for Sage in the first place.

-- William

[Nathann Cohen]

> You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/ddzJj4cceqI/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.

[Nathann Cohen]

> What problem are you solving by using immutable matrices/vectors?

I have many vectors v1,...,vk and a ring R, and I want to see if two
of them are R-collinear (hoping that it's how you guys say it).

> Why is anything immutable for what you are doing?

I multiply vi by R, and take this as a set. R is usually very small
(<10 elements).

Nathann

[Nathann Cohen]

The code is there: http://trac.sagemath.org/ticket/19462

Nathann