making new infix operators

[Jason Grout]

I'm thinking more about how to make the Graph class easy to use. One
thing that crops up is that the operations that combine graphs only
combine two graphs at a time (e.g., g.union(h), where g and h are graphs).

Is there a way to define an infix operator that would allow one to say:

g union h union i union j union k?

I could do it with something like:

reduce(lambda x,y: x.union(y), [g,h,i,j,k])

But that doesn't seem as clear as the infix things above.

For reference, Mathematica allows an operator in backticks to be applied
to its surrounding arguments, so the equivalent operation above would be:

g `union` h `union` i `union` j `union` k

And of course, you can set whether the operator is left-associative or
right-associative.

Of course, one solution is to use a for loop:

newgraph=Graph()
for graph in [g,h,i,j,k]:
newgraph.union(graph)

But that seems a lot clunkier than the infix expression above.

I guess another solution is to return the new graph from the union, so
that you could do:

g.union(h).union(i).union(j)

Thoughts?

-Jason

[Mike Hansen]

In SAGE, '+' is used for union of sets. For example,

sage: a = Set([1,2])
sage: b = Set([2,3])
sage: a+b
{1, 2, 3}

Since currently, + is not defined for graphs, it'd be a natural choice.

--Mike

[Hamptonio]

I would appreciate any tips on how to extend the + operator in this
way, since I would like to implement Minkowski sums of polytopes and
this is natural notation for that.
Marshall

On Sep 25, 10:37 am, "Mike Hansen" <mhan...@gmail.com> wrote:
> In SAGE, '+' is used for union of sets. For example,
>
> sage: a = Set([1,2])
> sage: b = Set([2,3])
> sage: a+b
> {1, 2, 3}
>
> Since currently, + is not defined for graphs, it'd be a natural choice.
>
> --Mike
>

[Mike Hansen]

Since I don't think that graphs and polytopes fall under the SAGE
coercion model, overloading operators is pretty straightforward. You
just need to define the __add__ method in your class. x + y will call
x.__add__(y).

sage: class Foo:
....: def __add__(self, y):
....: return 42
....:
sage: a = Foo()
sage: b = Foo()
sage: a + b
42
sage: b + a
42

Note that you'll want to do some type-checking so that y is what you
actually think it should be.

--Mike

[Jason Grout]

Mike Hansen wrote:
> Since I don't think that graphs and polytopes fall under the SAGE
> coercion model, overloading operators is pretty straightforward. You
> just need to define the __add__ method in your class. x + y will call
> x.__add__(y).
>
> sage: class Foo:
> ....: def __add__(self, y):
> ....: return 42
> ....:
> sage: a = Foo()
> sage: b = Foo()
> sage: a + b
> 42
> sage: b + a
> 42
>
> Note that you'll want to do some type-checking so that y is what you
> actually think it should be.
>

Thanks! Knowing what to look for, google pulled up the following page
from the python website, delineating the overloadable operators:

http://docs.python.org/ref/numeric-types.html

I put this here for future reference.

Thanks,

Jason

[Hamptonio]

Thanks, now I understand what to do. However, I don't understand your
comment about "...the SAGE coercion model". What is an example of
that - the sage integers?

-M. Hampton

On Sep 25, 12:10 pm, "Mike Hansen" <mhan...@gmail.com> wrote:
> Since I don't think that graphs and polytopes fall under the SAGE
> coercion model, overloading operators is pretty straightforward. You
> just need to define the __add__ method in your class. x + y will call
> x.__add__(y).
>
> sage: class Foo:
> ....: def __add__(self, y):
> ....: return 42
> ....:
> sage: a = Foo()
> sage: b = Foo()
> sage: a + b
> 42
> sage: b + a
> 42
>
> Note that you'll want to do some type-checking so that y is what you
> actually think it should be.
>
> --Mike
>

[Jason Grout]

Mike Hansen wrote:
> Since I don't think that graphs and polytopes fall under the SAGE
> coercion model, overloading operators is pretty straightforward. You
> just need to define the __add__ method in your class. x + y will call
> x.__add__(y).
>
> sage: class Foo:
> ....: def __add__(self, y):
> ....: return 42
> ....:
> sage: a = Foo()
> sage: b = Foo()
> sage: a + b
> 42
> sage: b + a
> 42
>
> Note that you'll want to do some type-checking so that y is what you
> actually think it should be.

Can we define custom infix operators? Suppose I'd like "boxproduct" to
be an infix operator. Could I make that work?

Thanks,

Jason

[Mike Hansen]

No, I don't think you can make custom infix operators in Python. With
something as long as 'boxproduct', you'd probably just be better off
making it a method.

--Mike

[John Cremona]

Nostalgia for Algol68 ! The line

OP OVER = (INT n,d)RAT: cancel(RAT(n,d));

is taken from my implementation of rational numbers so "one half"
could be written

1 OVER 2

and I could also write

DET M

for the determinant of a matrix (ok, that's prefix not infix).

Don't mock, my original tables of elliptic curves of conductor up to
1000 was computed with Algol68!

John

--
John Cremona

[Nick Alexander]

On 26-Sep-07, at 10:13 AM, John Cremona wrote:

>
> Nostalgia for Algol68 ! The line
>
> OP OVER = (INT n,d)RAT: cancel(RAT(n,d));
>
> is taken from my implementation of rational numbers so "one half"
> could be written
>
> 1 OVER 2
>
> and I could also write
>
> DET M

The past is the present: haskell supports det m, 1 `over` 2, and
ocaml often writes x # foo for foo x.

Nick

[cwitty]

On Sep 26, 7:31 am, Jason Grout <jason-s...@creativetrax.com> wrote:
> Can we define custom infix operators? Suppose I'd like "boxproduct" to
> be an infix operator. Could I make that work?
>
> Thanks,
>
> Jason

If you're willing to put a lot of effort into the project, you might
be able to do something with Logix (http://www.livelogix.net/logix/).
>From the website:

"Logix compiles to Python byte-code and can be freely mixed with
regular Python modules.
...
Logix syntax can be extended on the fly - even at the interactive
prompt. Logix is like Lisp with extensible syntax. Or, Logix is Python
with syntax extension, expression based syntax, and a powerful macro
system."

(I've never used Logix myself, only read some of their documentation.)

Carl Witty

[Jason Grout]

Wow!!! Thanks for sending this link. Logix seems to implement in Python
many of the Lisp-like things that make Mathematica such a nice system to
use. (like, in this discussion, the ability to define custom infix
operators, as well as a syntax for postfix function application, like
the Mathematica "x//Foo" for Foo[x] ).

I can't spread myself too thin right now by working on Logix, but I'm
bookmarking it. For now, I'll go back to writing code/fixing bugs in
the Graph class.

-Jason

[Chris Chiasson]

It might be worth pointing out that adding "new" syntax in Mathematica
is (usually) done by assignments to the function that transforms
general two dimensional input into source code. That isn't really the
same thing as adding a new operator to the language itself.

[Mike Hansen]

Of all the code I've read in lots of different languages, I think code
written for Mathematica has been the least transparent.

--Mike

[Robert Bradshaw]

The sage coercion model guarantees that when x.__add__(y) is called
(well, technically x._add_ or x._add_c_impl), the argument y is of
the same type and parent as x. For example

sage: R.<x> = ZZ[]
sage: x+1/2
x + 1/2
sage: parent(x)
Univariate Polynomial Ring in x over Integer Ring
sage: parent(1/2)
Rational Field
sage: parent(x+1/2)
Univariate Polynomial Ring in x over Rational Field

In your case, someone could type

sage: g = CompleteGraph(5)
sage: g+1 # will call g.__add__(1)
???

which you have to deal with. Typically, just throw an error if it's
not a graph. But what about graph + digraph? Digraph + digraph? Etc.
Should graph + x be a new graph with a new (unconnected) vertex 'x'?

- Robert

[Jason Grout]

Robert Bradshaw wrote:
> The sage coercion model guarantees that when x.__add__(y) is called
> (well, technically x._add_ or x._add_c_impl), the argument y is of
> the same type and parent as x. For example
>
> sage: R.<x> = ZZ[]
> sage: x+1/2
> x + 1/2
> sage: parent(x)
> Univariate Polynomial Ring in x over Integer Ring
> sage: parent(1/2)
> Rational Field
> sage: parent(x+1/2)
> Univariate Polynomial Ring in x over Rational Field
>
> In your case, someone could type
>
> sage: g = CompleteGraph(5)
> sage: g+1 # will call g.__add__(1)
> ???
>
> which you have to deal with. Typically, just throw an error if it's
> not a graph. But what about graph + digraph? Digraph + digraph? Etc.
> Should graph + x be a new graph with a new (unconnected) vertex 'x'?

Thanks for the explanation of the coercion model. That is a very nice
way to do things.

As for graphs, there isn't a standard definition for the "+" operation
that is agreed upon, even for graphs of the same type (e.g., should it
be disjoint union or union?). That's why I was asking about custom
infix operators, so I could make a disjoint_union infix operator, which
was clearly different than the union operator, which was clearly
different than whatever else. Another reason for custom infix operators
was to allow for all sorts of different kinds of products (just look at
the Graph class to see many examples), any of which could be represented
as "graph * graph".

The best I've come up with at this point is, given graphs A,B,C,D,E, the
union is:

A.union(B).union(C).union(D).union(E)

where the union function returns the modified graph each time so I can
keep chaining union function calls. The union actually modifies the
graph A, so if you want A left alone and a new graph returned, you do:

newgraph=A.copy().union(B).union(C).union(D).union(E)

Comments? Is there a better way to do things?

With time, I suppose the graph theory community will settle on a
commonly accepted meaning for "graph + graph", but as far as I
understand, that hasn't happened yet.

Thanks,

-Jason

[Mike Hansen]

> The best I've come up with at this point is, given graphs A,B,C,D,E, the
> union is:
>
> A.union(B).union(C).union(D).union(E)
>
> where the union function returns the modified graph each time so I can
> keep chaining union function calls. The union actually modifies the
> graph A, so if you want A left alone and a new graph returned, you do:
>
> newgraph=A.copy().union(B).union(C).union(D).union(E)
>
> Comments? Is there a better way to do things?

I think A.union(B) should leave A and B unchanged and return a new
graph object since that's pretty much how everything else works in
Python. In-place operations feel very out-of-place ;-)

--Mike

[Robert Bradshaw]

On Sep 26, 2007, at 8:59 PM, Jason Grout wrote:

> Robert Bradshaw wrote:
>> The sage coercion model guarantees that when x.__add__(y) is called
>> (well, technically x._add_ or x._add_c_impl), the argument y is of
>> the same type and parent as x. For example
>>
>> sage: R.<x> = ZZ[]
>> sage: x+1/2
>> x + 1/2
>> sage: parent(x)
>> Univariate Polynomial Ring in x over Integer Ring
>> sage: parent(1/2)
>> Rational Field
>> sage: parent(x+1/2)
>> Univariate Polynomial Ring in x over Rational Field
>>
>> In your case, someone could type
>>
>> sage: g = CompleteGraph(5)
>> sage: g+1 # will call g.__add__(1)
>> ???
>>
>> which you have to deal with. Typically, just throw an error if it's
>> not a graph. But what about graph + digraph? Digraph + digraph? Etc.
>> Should graph + x be a new graph with a new (unconnected) vertex 'x'?
>
> Thanks for the explanation of the coercion model. That is a very nice
> way to do things.

It's the product of a lot of work by a lot of people.

> As for graphs, there isn't a standard definition for the "+" operation
> that is agreed upon, even for graphs of the same type (e.g., should it
> be disjoint union or union?). That's why I was asking about custom
> infix operators, so I could make a disjoint_union infix operator,
> which
> was clearly different than the union operator, which was clearly
> different than whatever else. Another reason for custom infix
> operators
> was to allow for all sorts of different kinds of products (just
> look at
> the Graph class to see many examples), any of which could be
> represented
> as "graph * graph".

The same issue came up with vector * vector. It used to be pairwise
product, but most people expected dot product, so that was changed.
In any case, the old operations should probably be left as methods
and __add__ would dispatch to one of them.

I think (normal) union is the best way to define it, as graphs are
like sets + edges, and for sets + does the normal union thing. I
don't think there's a way to make new infix operators, and am not
sure that is a good idea anyway. The logic operators of __or__ and
__and__ might make sense for union and intersection though.

> The best I've come up with at this point is, given graphs
> A,B,C,D,E, the
> union is:
>
> A.union(B).union(C).union(D).union(E)

I actually think that this looks very clear, despite the lack of
infix operators.

> where the union function returns the modified graph each time so I can
> keep chaining union function calls. The union actually modifies the
> graph A, so if you want A left alone and a new graph returned, you do:
>
> newgraph=A.copy().union(B).union(C).union(D).union(E)
>
> Comments? Is there a better way to do things?

I would rather union returns a new object rather than modifying A,
it's much easier to reason about code that way, and fits better with
the rest of SAGE. One could provide a different method to do union in
place if one needs.

[Jason Grout]

Mike Hansen wrote:
> Of all the code I've read in lots of different languages, I think code
> written for Mathematica has been the least transparent.

I guess I've always loved functional languages, so the simple core
principles appealed to me right away. Some things I love include the
consistency in naming (system things always start with a capital letter,
leaving anything starting with a lowercase letter to the user; any
function asking a boolean question ends in Q, etc), the ability to use
postfix, prefix, and infix styles fairly naturally, the compact lambda
notation, the functional ideology, etc.

However, I don't like the monetary price, for me and for others trying
to run my code or experiment with things, and I don't like being tied to
a commercial entity. Both of those dislikes are strong enough for me to
break with Mathematica when I can and use and publish work using SAGE
and contribute where I can.

I do admit, though, that you can often express things extremely
compactly in Mathematica, which has a tendency to lead to very dense
code that isn't very transparent; I see your point.

Language issues aside, though, there are some _very_ nice user features
in Mathematica, especially the latest version. For example, one small
but very useful feature is that any variable that does not have a value
attached is a different color in the front end and any variable that is
a "dummy" variable in a command is a third color.

Okay, back to the topic of what we can do in Sage and how to make Sage
better...

Thanks,

-Jason

[Craig Citro]

>> The best I've come up with at this point is, given graphs
>> A,B,C,D,E, the
>> union is:
>>
>> A.union(B).union(C).union(D).union(E)
>
> I actually think that this looks very clear, despite the lack of
> infix operators.
>

I agree -- especially since it looks like a literal translation of
the same statement as written mathematics. However, I could see a
strong argument that it could get too long -- it wouldn't take much
work to change union to support something like this:

A.union( [ B, C, D, E ] )

>> where the union function returns the modified graph each time so I
>> can
>> keep chaining union function calls. The union actually modifies the
>> graph A, so if you want A left alone and a new graph returned, you
>> do:
>>
>> newgraph=A.copy().union(B).union(C).union(D).union(E)
>>
>> Comments? Is there a better way to do things?
>
> I would rather union returns a new object rather than modifying A,
> it's much easier to reason about code that way, and fits better with
> the rest of SAGE. One could provide a different method to do union in
> place if one needs.
>

I second Robert's opinion, especially since it makes it feel more
like a functional language that way. On a related note, you mentioned
functional programming elsewhere in this thread -- python definitely
supports some functional programming notions (anonymous functions,
first-class functions, etc). Here's a nice link about that:

http://www.ibm.com/developerworks/library/l-prog.html

-cc

[Jason Grout]

That's what I always thought to. But then I saw the Python sort()
function, or the reverse() function, etc. and grudgingly accepted that
the python way was to modify things in place.

In the end, I want two options: to modify things in-place or to return a
new object. I also want some sort of consistency so that the user isn't
constantly guessing what a function will do. After playing with things
for a bit, I decided that the easiest consistent thing to do was to
modify in-place and call A.copy().whatever() when I wanted to return a
new object. That way a copy was explicitly denoted with somewhat
minimal syntax, the general case was consistent, and we still had access
to both options.

Would you suggest doing things the other way? Return a new copy by
default and always have:

A=A.union(B)

to modify A? It's slightly worse performance-wise, it seems, because we
are always making copies and throwing old copies away. Especially if we
have the above (A.union(B).union(C).union(D).union(E))---then we make 4
new copies of things and throw away all but 1 of them.

-Jason

[Jason Grout]

Craig Citro wrote:
>>> The best I've come up with at this point is, given graphs
>>> A,B,C,D,E, the
>>> union is:
>>>
>>> A.union(B).union(C).union(D).union(E)
>> I actually think that this looks very clear, despite the lack of
>> infix operators.
>>
>
> I agree -- especially since it looks like a literal translation of
> the same statement as written mathematics. However, I could see a
> strong argument that it could get too long -- it wouldn't take much
> work to change union to support something like this:
>
> A.union( [ B, C, D, E ] )

I originally was going to do things this way, but then decided the way I
presented. However, you're right---it's a trivial change to allow both
possibilities. I'll definitely add that.

Thanks,

-Jason

[Jason Grout]

Chris Chiasson wrote:
> It might be worth pointing out that adding "new" syntax in Mathematica
> is (usually) done by assignments to the function that transforms
> general two dimensional input into source code. That isn't really the
> same thing as adding a new operator to the language itself.

Adding a new operator to the language itself means that you change the
parser to interpret the new operator. That's exactly what you're doing
in Mathematica by modifying the function that converts input to a nested
list of function calls (defined by the user or by the base system
library). So I guess I don't see a difference in your distinction
between these two cases. Of course, I could be missing something here.

In the above discussion, though, I was mainly referring to the way that
Mathematica can take the same function and call it in prefix, infix, and
postfix syntax. So you can write one function, "disjoint_union", and
call it via: "disjoint_union[a,b]", "a `disjoint_union` b", or "[a,b] //
disjoint_union[#[[1]],#[[2]]]&

Thanks,

-Jason

[Jason Grout]

Robert Bradshaw wrote:
> On Sep 26, 2007, at 8:59 PM, Jason Grout wrote:
>
>> As for graphs, there isn't a standard definition for the "+" operation
>> that is agreed upon, even for graphs of the same type (e.g., should it
>> be disjoint union or union?). That's why I was asking about custom
>> infix operators, so I could make a disjoint_union infix operator,
>> which
>> was clearly different than the union operator, which was clearly
>> different than whatever else. Another reason for custom infix
>> operators
>> was to allow for all sorts of different kinds of products (just
>> look at
>> the Graph class to see many examples), any of which could be
>> represented
>> as "graph * graph".
>
> The same issue came up with vector * vector. It used to be pairwise
> product, but most people expected dot product, so that was changed.
> In any case, the old operations should probably be left as methods
> and __add__ would dispatch to one of them.
>
> I think (normal) union is the best way to define it, as graphs are
> like sets + edges, and for sets + does the normal union thing. I
> don't think there's a way to make new infix operators, and am not
> sure that is a good idea anyway. The logic operators of __or__ and
> __and__ might make sense for union and intersection though.

I guess this illustrates the problem of only having a few basic symbols
that we can overload. On the other hand, simplicity results as well
since there isn't new notation for every different kind of object. On
the third hand, though, it makes translating math into python harder,
since we do use all sorts of different notation in math. That's one
reason why the interface to Mathematica is nice---most any math
(unicode?) symbol can be assigned to a function and given mathematical
meaning.

>> The best I've come up with at this point is, given graphs
>> A,B,C,D,E, the
>> union is:
>>
>> A.union(B).union(C).union(D).union(E)
>
> I actually think that this looks very clear, despite the lack of
> infix operators.

That's why I finally settled on it.

>
>> where the union function returns the modified graph each time so I can
>> keep chaining union function calls. The union actually modifies the
>> graph A, so if you want A left alone and a new graph returned, you do:
>>
>> newgraph=A.copy().union(B).union(C).union(D).union(E)
>>
>> Comments? Is there a better way to do things?
>
> I would rather union returns a new object rather than modifying A,
> it's much easier to reason about code that way, and fits better with
> the rest of SAGE. One could provide a different method to do union in
> place if one needs.

I guess this brings up a much more general issue of conventions in SAGE
(in general, should methods modify an object in-place or pass back a new
object?). I'll post up a new thread to try to clarify and get feedback
on what conventions there are/should be.

Thanks for everyone's feedback!

-Jason

[Bill Page]

On 9/27/07, Jason Grout wrote:
> ...

> >
> >> where the union function returns the modified graph each time so I can
> >> keep chaining union function calls. The union actually modifies the
> >> graph A, so if you want A left alone and a new graph returned, you do:
> >>
> >> newgraph=A.copy().union(B).union(C).union(D).union(E)
> >>
> >> Comments? Is there a better way to do things?
> >
> > I would rather union returns a new object rather than modifying A,
> > it's much easier to reason about code that way, and fits better with
> > the rest of SAGE. One could provide a different method to do union in
> > place if one needs.
>
> I guess this brings up a much more general issue of conventions in SAGE
> (in general, should methods modify an object in-place or pass back a new
> object?). I'll post up a new thread to try to clarify and get feedback
> on what conventions there are/should be.
>

There is another very relevant thread started by Robert Bradshaw on
this list concerning the safety of in-place modifications:

http://groups.google.com/group/sage-devel/browse_thread/thread/806cd958eb28ac3b/46655d7572d11ee6?#46655d7572d11ee6

http://www.sagemath.org:9002/sage_trac/ticket/624

In general one wants to do as much in-place modification as possible
without risking unintended side-effects in other parts of the code.
Since Python maintains a reference count for every object, this means
that it is possible for an operation to know whether doing an in-place
modification represents a risk. If there is no external reference to
the object then there is no risk, so the operation should be done
in-place. If the reference count is greater than zero, then the
operation should (automatically) create a copy and then perform the
operation on the copy. Using this convention, for the sake of
efficiency all operations in Sage would be written to operate in-place
but they would transparently create copies of the object as necessary
in order to make side-effects impossible. Thus you can "have your cake
and eat it too".

Thus in

newgraph=A.union(B).union(C).union(D).union(E)

would be done entirely in-place so that 'newgraph' becomes a modified
version of A, while in

newgraph1=A.union(B).union(C).union(D).union(E)
newgraph2=A.union(B).union(C).union(D).union(E)

a new copy of A is created and modified before it is assigned to
'newgraph2'. However we do not have to be aware of this as such. The
only thing we need to remember is that there can be no side-effects.

Regards,
Bill Page.

[Fernando Perez]

On 9/27/07, Bill Page <bill...@newsynthesis.org> wrote:

> There is another very relevant thread started by Robert Bradshaw on
> this list concerning the safety of in-place modifications:
>
> http://groups.google.com/group/sage-devel/browse_thread/thread/806cd958eb28ac3b/46655d7572d11ee6?#46655d7572d11ee6
>
> http://www.sagemath.org:9002/sage_trac/ticket/624

It's worth mentioning that extensions that provide low-level views of
memory, even if they are fully refcounted, break the assumptions about
the refcount being a safe way of detecting how many accesses to the
current object exist. Here's a simple example illustrating the point:

>>> import numpy as N
>>> import sys
>>> a = N.arange(10)
>>> sys.getrefcount(a)
2
>>> b = a[::2]
>>> sys.getrefcount(a)
3
>>> c = b[::2]
>>> sys.getrefcount(a)
3
>>> c[:] = 999
>>> a
array([999, 1, 2, 3, 999, 5, 6, 7, 999, 9])
>>>

The last line modified a, even though the creation of the 'c' view
over a's memory area did NOT increment a's refcount (since it did it
via b, hence only b's refcount went up).

This example is a bit contrived, but I just want to illustrate that
extensions such as numpy (which is the basis of much of the numerical
python code in existence) can make refcount-based arguments tricky.

Cheers,

f

[Hamptonio]

I disagree. Maybe its because I grew up learning BASIC, but in-place
modification generally confuses and annoys me. Here's an example that
I think illustrates one of my issues:

Code version A:
a = something
b = [a,something_else]
c = a.a_method()
important_result(b)

Code version B:
a = something
c = a.a_method()
b = [a,something_else]
important_result(b)

...although I might be confused. What I think would happen is that in
version A, under the proposed behavior a would not be modified in-
pace, but would be in version B. I can imagine this resulting in some
nasty bugs. Am I missing something?

Marshall

On Sep 27, 8:05 am, "Bill Page" <bill.p...@newsynthesis.org> wrote:
> On 9/27/07, Jason Grout wrote:
>
>
>
> > ...
>
> > >> where the union function returns the modified graph each time so I can
> > >> keep chaining union function calls. The union actually modifies the
> > >> graph A, so if you want A left alone and a new graph returned, you do:
>
> > >> newgraph=A.copy().union(B).union(C).union(D).union(E)
>
> > >> Comments? Is there a better way to do things?
>
> > > I would rather union returns a new object rather than modifying A,
> > > it's much easier to reason about code that way, and fits better with
> > > the rest of SAGE. One could provide a different method to do union in
> > > place if one needs.
>
> > I guess this brings up a much more general issue of conventions in SAGE
> > (in general, should methods modify an object in-place or pass back a new
> > object?). I'll post up a new thread to try to clarify and get feedback
> > on what conventions there are/should be.
>
> There is another very relevant thread started by Robert Bradshaw on
> this list concerning the safety of in-place modifications:
>

> http://groups.google.com/group/sage-devel/browse_thread/thread/806cd9...

[Robert Bradshaw]

On Sep 27, 2007, at 4:43 AM, Jason Grout wrote:

> Mike Hansen wrote:
>>> The best I've come up with at this point is, given graphs
>>> A,B,C,D,E, the
>>> union is:
>>>
>>> A.union(B).union(C).union(D).union(E)
>>>
>>> where the union function returns the modified graph each time so
>>> I can
>>> keep chaining union function calls. The union actually modifies the
>>> graph A, so if you want A left alone and a new graph returned,
>>> you do:
>>>
>>> newgraph=A.copy().union(B).union(C).union(D).union(E)
>>>
>>> Comments? Is there a better way to do things?
>>
>> I think A.union(B) should leave A and B unchanged and return a new
>> graph object since that's pretty much how everything else works in
>> Python. In-place operations feel very out-of-place ;-)
>
> That's what I always thought to. But then I saw the Python sort()
> function, or the reverse() function, etc. and grudgingly accepted that
> the python way was to modify things in place.

Yes, but note that sort and reverse don't return anything, which I
think is a good convention. You don't have to worry about having two
objects, and wondering if they're actually the same thing (as you do
with an inplace operator that returns self).

> In the end, I want two options: to modify things in-place or to
> return a
> new object. I also want some sort of consistency so that the user
> isn't
> constantly guessing what a function will do. After playing with
> things
> for a bit, I decided that the easiest consistent thing to do was to
> modify in-place and call A.copy().whatever() when I wanted to return a
> new object. That way a copy was explicitly denoted with somewhat
> minimal syntax, the general case was consistent, and we still had
> access
> to both options.
>
> Would you suggest doing things the other way? Return a new copy by
> default and always have:
>
> A=A.union(B)
>
> to modify A?

Yes. Or even

A.inplace_union(B)

(or some better name than that) which returns nothing. Otherwise, for
example, every function that received a graph as an argument would
have to make a copy to avoid side effects (or the calling function
would always have to make a copy before passing in just in case).
Explicitly making a copy everywhere seems cumbersome.

> It's slightly worse performance-wise, it seems, because we
> are always making copies and throwing old copies away. Especially
> if we
> have the above (A.union(B).union(C).union(D).union(E))---then we
> make 4
> new copies of things and throw away all but 1 of them.

True, this is the price to pay. It might be worth having a function
that does things inplace if one needs the speed, but I like to avoid
side effects in general. Though I think the syntax above is the
clearest, A.union([B,C,D]) could be done more efficiently.

- Robert

[Robert Bradshaw]

You have a good point, though fortunately we're looking for refcounts
so low that (essentially) nothing else can be holding onto it but the
current stack frame. If b is pointing to a, it doesn't matter how
many other things are (directly or indirectly). If nothing is
pointing to it directly, it's difficult (but not impossible) for
things to safely point to it indirectly. Also, we would only play
this trick with SAGE elements, which we have more control over.

Also, in this case, since things are referenced, if one changes so
should the other. I gave this a lot of though, but I hope others will
too since I can't be sure I didn't miss something.

- Robert

[Fernando Perez]

On 9/27/07, Robert Bradshaw <robe...@math.washington.edu> wrote:

> You have a good point, though fortunately we're looking for refcounts
> so low that (essentially) nothing else can be holding onto it but the
> current stack frame. If b is pointing to a, it doesn't matter how
> many other things are (directly or indirectly). If nothing is
> pointing to it directly, it's difficult (but not impossible) for
> things to safely point to it indirectly. Also, we would only play
> this trick with SAGE elements, which we have more control over.

The subtlety appears if the object you're dealing with is itself a
view of something else:

In [3]: a = N.arange(10)

In [4]: b = a[::2]

In [5]: sys.getrefcount(b)
Out[5]: 2

In [6]: sys.getrefcount(a)
Out[6]: 3

In [7]: c = a[::2]

In [8]: sys.getrefcount(b)
Out[8]: 2

In [9]: c.fill(999)

In [10]: sys.getrefcount(b)
Out[10]: 2

In [11]: b
Out[11]: array([999, 999, 999, 999, 999])

In this case, b gets modified indirectly, even though its refcount
never went above 2, so it would appear 'safe' by a refcounting
argument. The problem is that b is itself a view onto another object
(a) for which someone else (c) is holding also 'write access'. So
while b appears to be 'isolated', it is still in reality subject to
modification.

Cheers,

f

[Jaap Spies]

Jason Grout wrote:
> Mike Hansen wrote:
>> Of all the code I've read in lots of different languages, I think code
>> written for Mathematica has been the least transparent.
>
> I guess I've always loved functional languages, so the simple core
> principles appealed to me right away.

See a thread from some time ago: "Why Mathematica is not my language
of choice".

I do not like functional programming languages.This not withstanding
I learned a lot from the lectures on lambda calculus in the early sixties
from Dirk van Dalen.
And I'm in good company: the originator of Python Guido van Rossum.

Python knows some functional constructs, but in the future there will be less.
In Python 3k there will be still something like map(), but other "goodies"
will be gone.

Jaap

[Jason Grout]

Robert Bradshaw wrote:
> On Sep 27, 2007, at 4:43 AM, Jason Grout wrote:
>

>> A=A.union(B)
>>
>> to modify A?
>
> Yes. Or even
>
> A.inplace_union(B)
>
> (or some better name than that) which returns nothing. Otherwise, for
> example, every function that received a graph as an argument would
> have to make a copy to avoid side effects (or the calling function
> would always have to make a copy before passing in just in case).
> Explicitly making a copy everywhere seems cumbersome.

Thanks for the direct and good advice. I guess I had convinced myself
that an object method would naturally do something to the object, so it
was pretty natural to always modify in-place.

>
>> It's slightly worse performance-wise, it seems, because we
>> are always making copies and throwing old copies away. Especially
>> if we
>> have the above (A.union(B).union(C).union(D).union(E))---then we
>> make 4
>> new copies of things and throw away all but 1 of them.
>
> True, this is the price to pay. It might be worth having a function
> that does things inplace if one needs the speed, but I like to avoid
> side effects in general. Though I think the syntax above is the
> clearest, A.union([B,C,D]) could be done more efficiently.

Is this the sort of situation your ref-counting stuff would enhance?
For example, in the above situation, if a new object were returned by
union, then A.union(B) would not be referenced anywhere else in the
system, so A.union(B).union(C) would actually not create a new object,
but do the union in-place in A.union(B)? So the system would understand
that the following code:

def union(self, othergraph):
g=self.copy()
# Modify g to be the union of g and othergraph
...
return g

should make a copy of self in the A.union(B) case, but not make a copy
when invoked in the .union(C) case above.

Am I understanding the idea behind your ref-counting thread mentioned
elsewhere?

Thanks,

Jason

[Robert Bradshaw]

On Sep 27, 2007, at 1:45 PM, Jason Grout wrote:

> Robert Bradshaw wrote:
>> On Sep 27, 2007, at 4:43 AM, Jason Grout wrote:
>
>>> A=A.union(B)
>>>
>>> to modify A?
>>
>> Yes. Or even
>>
>> A.inplace_union(B)
>>
>> (or some better name than that) which returns nothing. Otherwise, for
>> example, every function that received a graph as an argument would
>> have to make a copy to avoid side effects (or the calling function
>> would always have to make a copy before passing in just in case).
>> Explicitly making a copy everywhere seems cumbersome.
>
> Thanks for the direct and good advice. I guess I had convinced myself
> that an object method would naturally do something to the object,
> so it
> was pretty natural to always modify in-place.

What is natural depends totally on the context, but, as William
mentioned, SAGE leans towards considering mathematical objects to be
immutable. Personally, when I see A.union(B) I think (from a
mathematical point of view) I'm getting a new object that's the union
of A and B, rather than throwing all elements of B into A. On the
other hand, something like A.add_vertex('x') makes me think I'm
mutating A (and don't expect to get a new object back). Of course,
these are fuzzy matters of personal opinion.

Yes, exactly. Currently its only implemented (though not yet a part
of SAGE) for the arithmetic operators +,-,*,/ on SAGE elements.

- Robert

[Robert Miller]

> The best I've come up with at this point is, given graphs A,B,C,D,E, the
> union is:
>
> A.union(B).union(C).union(D).union(E)
>
> where the union function returns the modified graph each time so I can
> keep chaining union function calls. The union actually modifies the
> graph A, so if you want A left alone and a new graph returned, you do:
>
> newgraph=A.copy().union(B).union(C).union(D).union(E)
>
> Comments? Is there a better way to do things?

This is false. The union function returns a new graph, so the first
method already works.

[Bill Page]

On 9/27/07, Fernando Perez wrote:

>
> On 9/27/07, Robert Bradshaw wrote:
>
> > You have a good point, though fortunately we're looking for refcounts
> > so low that (essentially) nothing else can be holding onto it but the
> > current stack frame. If b is pointing to a, it doesn't matter how
> > many other things are (directly or indirectly). If nothing is
> > pointing to it directly, it's difficult (but not impossible) for
> > things to safely point to it indirectly. Also, we would only play
> > this trick with SAGE elements, which we have more control over.
>
> The subtlety appears if the object you're dealing with is itself a
> view of something else:
>
> In [3]: a = N.arange(10)
>
> In [4]: b = a[::2]
>
> In [5]: sys.getrefcount(b)
> Out[5]: 2
>
> In [6]: sys.getrefcount(a)
> Out[6]: 3
>

I think there might be some confusion here over what is an "object"
and what is a "reference" to an object. The first object here is the
result of 'N.arange(10)'.

sage: sys.getrefcount( N.arange(10) )
1

because using 'N.arange(10)' in this function call constitutes just 1
reference to this object.

But when 'a' is also created as a reference to that object

sage: a = N.arange(10)
sage: sys.getrefcount(a)
2

the object denoted by 'N.arange(10)' already has two many references
to safely be manipulated in-place! Remember that what gets passed to
'sys.getrefcount(a)' is the value of 'a', not 'a' itself. If we were
to change this object, then then the object referenced by 'a' would
also change and that is exactly the kind of side-effect that we want
to avoid.

So in this case if we can only do in-place operations on objects whose
reference count is 1, you might wonder just how useful this could be
...

But consider this:

sage: sys.getrefcount([1,2])
1

The expression '[1,2]' creates a list object. It's only reference is
in the function call. So now write:

sage: [1,2].__add__([3,5]).__add__([7,8])
[1, 2, 3, 5, 7, 8]

where __add__ is a list method. According to the proposed semantics
the __add__ operation above can safely operate in-place, i.e. first
'3,5' is inserted (distructively) into the object '[1,2]' and then
'7,8' is inserted into the *same* object.

But if I write:

sage: a=[1,2]
sage: sys.getrefcount(a)
2
sage: a.__add__([3,5]).__add__([7,8])
[1, 2, 3, 5, 7, 8]

then it is no longer safe to simply insert '3,5' into the object
denoted by '[1,2]' since that will affect the value of 'a'. So instead
we first of all make a new copy of the list '[1,2]' and perform the
insertion into it.

Regards,
Bill Page.

[Fernando Perez]

On 9/27/07, Bill Page <bill...@newsynthesis.org> wrote:
>

> On 9/27/07, Fernando Perez wrote:
> >
> > On 9/27/07, Robert Bradshaw wrote:
> >
> > > You have a good point, though fortunately we're looking for refcounts
> > > so low that (essentially) nothing else can be holding onto it but the
> > > current stack frame. If b is pointing to a, it doesn't matter how
> > > many other things are (directly or indirectly). If nothing is
> > > pointing to it directly, it's difficult (but not impossible) for
> > > things to safely point to it indirectly. Also, we would only play
> > > this trick with SAGE elements, which we have more control over.
> >
> > The subtlety appears if the object you're dealing with is itself a
> > view of something else:
> >
> > In [3]: a = N.arange(10)
> >
> > In [4]: b = a[::2]
> >
> > In [5]: sys.getrefcount(b)
> > Out[5]: 2
> >
> > In [6]: sys.getrefcount(a)
> > Out[6]: 3
> >
>
> I think there might be some confusion here over what is an "object"
> and what is a "reference" to an object. The first object here is the
> result of 'N.arange(10)'.

The problematic issue is that some extensions (numpy first and
foremost, but this buffer API is going into the core of the language
for 2.6/3.0) allow multiple, distinct *python objects* to share the
same (or parts of the same) chunk of raw memory. The refcount
mechanism only tracks python objects, not raw memory. Hopefully this
helps:

In [12]: a = N.arange(10)

In [13]: sys.getrefcount(a)
Out[13]: 2

Here the refcount is 2, as expected: the original array and the name
'a' pointing to it.

Now, a naked, unassigned slice of the original array has a refcount of 1:

In [14]: sys.getrefcount(a[::2])
Out[14]: 1

And yet, modifying it in-place has an effect on the original object
(which we have called 'a'):

In [15]: a[::2].fill(999)

In [16]: a
Out[16]: array([999, 1, 999, 3, 999, 5, 999, 7, 999, 9])

The slice 'a[::2]' has a refcount of 1, so it appears 'safe' from a
purely refcounting argument. But it actually shares memory with the
original N.arange(10) object, so it can overwrite it.

Note that I'm only pointing this out as a word of caution that there
are cases where refcounting arguments can be a bit delicate. The
basic idea of reusing in-place objects as an optimization is a very
good one for cases where you know that your underlying objects simply
don't expose any interface for antics like the above.

Cheers,

f

[Bill Page]

On 9/27/07, Fernando Perez wrote:

> ...

> In [12]: a = N.arange(10)
>
> In [13]: sys.getrefcount(a)
> Out[13]: 2
>
> Here the refcount is 2, as expected: the original array and the name
> 'a' pointing to it.
>
> Now, a naked, unassigned slice of the original array has a refcount of 1:
>
> In [14]: sys.getrefcount(a[::2])
> Out[14]: 1
>

Whoa! This looks wrong to me. The slice of some larger object (which
in turn has a reference to it) should not have a reference count of 1.
(-: Ok, maybe it should be 1.00001 but not 1! ;-) The mutable larger
object in which it is contained certainly *references* parts of
itself. No?

> And yet, modifying it in-place has an effect on the original object
> (which we have called 'a'):
>
> In [15]: a[::2].fill(999)
>
> In [16]: a
> Out[16]: array([999, 1, 999, 3, 999, 5, 999, 7, 999, 9])
>

Uggh! Awful. :-(

>
> The slice 'a[::2]' has a refcount of 1, so it appears 'safe' from a
> purely refcounting argument. But it actually shares memory with the
> original N.arange(10) object, so it can overwrite it.
>

As far as I am concerned "sharing memory" is equivalent to a reference.

> Note that I'm only pointing this out as a word of caution that there
> are cases where refcounting arguments can be a bit delicate. The
> basic idea of reusing in-place objects as an optimization is a very
> good one for cases where you know that your underlying objects simply
> don't expose any interface for antics like the above.
>

I think your points are well taken. There certainly seems to be some
confusion and a lot written about this subject on the web. For example
from the Python docs:

http://docs.python.org/ext/refcountsInPython.html

-----
Nobody ``owns'' an object; however, you can own a reference to an
object. An object's reference count is now defined as the number of
owned references to it. The owner of a reference is responsible for
calling Py_DECREF() when the reference is no longer needed. Ownership
of a reference can be transferred.
-------

And it defines the concept of a "borrowed" reference, etc., etc.

Regards,
Bill Page.

[Jason Grout]

Yes, it currently does this; good point, I should have mentioned that
that was how it was currently programmed (did I not? Sorry). I was
proposing a different design. My whole inquiry has to do with what
"should" (for a suitably defined should :) the interface be and are
there official guidelines (or should there be official guidelines) for
this type of operation on an object so that there is consistency across
SAGE.

I think the overall answer that I'm getting is that things (mathematical
objects) should generally be considered immutable unless it really
doesn't make sense or is very inconvenient to consider them immutable.
We can later use ref-counting tricks to cut down on the resulting
overhead, so don't worry too much about it. I think that that sounds
like a great convention.

Thanks,

-Jason

[Robert Bradshaw]

On Sep 27, 2007, at 2:47 PM, Fernando Perez wrote:

> The problematic issue is that some extensions (numpy first and
> foremost, but this buffer API is going into the core of the language
> for 2.6/3.0) allow multiple, distinct *python objects* to share the
> same (or parts of the same) chunk of raw memory. The refcount
> mechanism only tracks python objects, not raw memory.

Yes, but that's all we care about. If an implementation of an object
points to the memory of another object, it assume that the other
chunk of memory may change.

> Hopefully this
> helps:
>
> In [12]: a = N.arange(10)
>
> In [13]: sys.getrefcount(a)
> Out[13]: 2
>
> Here the refcount is 2, as expected: the original array and the name
> 'a' pointing to it.
>
> Now, a naked, unassigned slice of the original array has a refcount
> of 1:
>
> In [14]: sys.getrefcount(a[::2])
> Out[14]: 1
>
> And yet, modifying it in-place has an effect on the original object
> (which we have called 'a'):
>
> In [15]: a[::2].fill(999)
>
> In [16]: a
> Out[16]: array([999, 1, 999, 3, 999, 5, 999, 7, 999, 9])
>
>
> The slice 'a[::2]' has a refcount of 1, so it appears 'safe' from a
> purely refcounting argument. But it actually shares memory with the
> original N.arange(10) object, so it can overwrite it.

This is by design, and a slice object wants to mutate the underlying
object. And slice objects know that their mutations may have side
effects. The object being sliced ('a' in this example) knows it is
unsafe because b holds a reference to it. (If b held a pointer into
the memory of a, but no reference, that memory would be in risk of
getting recycled) .

> Note that I'm only pointing this out as a word of caution that there
> are cases where refcounting arguments can be a bit delicate. The
> basic idea of reusing in-place objects as an optimization is a very
> good one for cases where you know that your underlying objects simply
> don't expose any interface for antics like the above.

I agree with your caution, but don't see how the examples above mess
anything up. If an object B wants to pretend to be immutable, it
merely has to check that nothing points to it before mutating itself
(and, in mutating itself, don't mutate objects that have other
pointers to them).

- Robert

[Chris Chiasson]

Well, I don't want to take the thread off topic, but in the standard
(documented) way of creating new operators, it is done with an
assignment to MakeExpression. This will work in a notebook, where
boxes are transformed into expressions before execution, but it will
not work in a .m file, because that isn't processed by MakeExpression.

[Fernando Perez]

On 9/27/07, Robert Bradshaw <robe...@math.washington.edu> wrote:

> I agree with your caution, but don't see how the examples above mess
> anything up. If an object B wants to pretend to be immutable, it
> merely has to check that nothing points to it before mutating itself
> (and, in mutating itself, don't mutate objects that have other
> pointers to them).

Yup, I was just trying to illustrate the issues that could arise if
one uses the assumption that refcount==1 <==> no side effects on
in-place operations. But with the proper care, it's a perfectly valid
approach for optimizing expressions involving immutable objects.
Given Bill's surprise, it probably wasn't totally useless to provide
these examples :)

Cheers,

f

[Bill Page]

On 9/27/07, Fernando Perez wrote:
>

Very useful indeed, thanks! :-)

Regards,
Bill Page.