updating version of binary arithmetic operators

[Gabor]

I experience that the += operator gives a new allocation, instead of
working in-place.

E.g.

julia> a = [1:5]
[1, 2, 3, 4, 5]

julia> uid(a)
0x0618b67c

julia> a += 10
[11, 12, 13, 14, 15]

julia> uid(a)
0x0618b988


Please tell me: Is this intentional or is it a bug?
(I am using the first Windows version of Julia.)

I have rechecked += in Numpy, naturally it works in-place.

[Jeff Bezanson]

It's intentional. We err on the side of not mutating things. But we want to do more with in-place operators.
I like being able to assume a+=b is always the same as a=a+b, it's one less thing to worry about writing generic code. Probably need some more syntax.

[Gabor]

Thank you for your prompt answer.

However, I am somewhat disappointed that this is intentional
behaviour.
I admit that I am not CS-trained to see the big picture of language
design,
but as a plain user I utilize the updating operators exclusively for
in-place mutation ...

Any chance to reconsider?

> > I have rechecked += in Numpy, naturally it works in-place.- Hide quoted text -
>
> - Show quoted text -

[Stefan Karpinski]

Being able to mutate arrays in-place is a priority, but it's unclear whether using += to do it is the best approach. I was going to suggest that we could make += an operator, but it's not obvious how to do that. One option would be to make `x += y` mean `x = (+=)(x,y)` with a default definition `(+=)(x,y) = x+y`. The array version could modify its left argument in-place *and* return it. The net effect is just in-place array mutation: the reassignment of x to x is a no-op, whereas in the immutable numeric case, the reassignment is the *only* effect.

[Krzysztof Kamieniecki]

Is / could there some way to wrap "a" with a type (InplaceArray{T}?) and define additional methods to do the assign inplace?

[Tim Holy]

On Friday, April 20, 2012 02:20:47 PM Jeff Bezanson wrote:
> It's intentional. We err on the side of not mutating things. But we want to
> do more with in-place operators.
> I like being able to assume a+=b is always the same as a=a+b, it's one less
> thing to worry about writing generic code. Probably need some more syntax.

Hmm, I've been assuming += operates in-place. I'm not sure I really understand
how an in-place a+=b is not the same as a=a+b? Aside from the extra memory
allocation?

Other in-place operations, such as reshape!, would be nice. In Matlab, a =
reshape(b,dims...) is very fast, because it's essentially in-place due to
copy-on-write. Currently, our reshape is slow because it copies the data. And
I guess that
a = b
reshape!(a,dims...)
would also reshape b, because a is a reference for all of b, not just b's
data. (right?) So either way, there are traps for the unwary.

--Tim

[Stefan Karpinski]

No, that won't help. The trouble is that `x += y` means `x = x + y` and `x + y` needs to continue to mean "create a new array that is the sum of x and y". Basically what I'm proposing is to stick a different operator in there instead of `+` that can be overridden to modify its first argument in-place so that `+` can continue to act like it should.

[Tim Holy]

On Friday, April 20, 2012 03:11:50 PM Stefan Karpinski wrote:
> Basically what I'm proposing is to stick a different operator in there
> instead of `+` that can be overridden to modify its first argument in-place
> so that `+` can continue to act like it should.

I like this plan.

--Tim

[Stefan Karpinski]

`x = x + y` means "construct the matrix `x + y` and make the variable x reference that new matrix". In-place modification means "modify each element of x by adding the corresponding element of y to it".

Reshape already shares memory with the original copy, so that's effectively in-place, although since the type of a value cannot change, reshape needs to give a new value. Thus reshape! is not mutating, but you can change one array via a reshaped copy of it. This is different than copy-on-write. I really dislike copy-on-write. It seems like a clever trick but then you get very brittle performance behavior. The assignment `a = b` does not copy an array, it just makes `a` refer to the same array as `b`.

[Stefan Karpinski]

If we did this for all the in-place operators, then each method could decide whether in-place operation was appropriate or not.

[Stefan Karpinski]

One major danger here would be a function like this:

function foo(x,y,n)

  while n > 0

    x += y

    n -= 1

  end

  return x

end

When x is a scalar, this has no effect on the x in the caller of foo; when x is an array, it would. Does seem like a potentially huge pitfall. I guess we could maybe do this anyway and just give big warnings about writing generic code that uses += like this.

[Toivo Henningsson]

On Apr 20, 9:11 pm, Stefan Karpinski <ste...@karpinski.org> wrote:
> No, that won't help. The trouble is that `x += y` means `x = x + y` and `x
> + y` needs to continue to mean "create a new array that is the sum of x and
> y". Basically what I'm proposing is to stick a different operator in there
> instead of `+` that can be overridden to modify its first argument in-place
> so that `+` can continue to act like it should.

How about using

a[] += b # inplace addition
a[] = b # inplace assignment

It feels reasonable for arrays, don't know if there are other types
where it wouldn't feel as good. No idea how easy it is to get it to
work either, with two operators involved and all (I guess the second
line would actually call assign). Not sure how people feel about it
(myself included :)

But it would make inplace mutation for arrays generalize to things
like a[3:5] += 1,
which might be nice.

[Patrick O'Leary]

On Friday, April 20, 2012 2:27:15 PM UTC-5, Toivo Henningsson wrote:

On Apr 20, 9:11 pm, Stefan Karpinski <ste...@karpinski.org> wrote:
> No, that won't help. The trouble is that `x += y` means `x = x + y` and `x
> + y` needs to continue to mean "create a new array that is the sum of x and
> y". Basically what I'm proposing is to stick a different operator in there
> instead of `+` that can be overridden to modify its first argument in-place
> so that `+` can continue to act like it should.

How about using

    a[] += b # inplace addition
    a[] = b   # inplace assignment

Not terribly discoverable. We already use ! for in-place operations; is a +!= b unacceptable for parsing reasons?

[Tim Holy]

On Friday, April 20, 2012 03:16:24 PM Stefan Karpinski wrote:
> Reshape already shares memory with the original copy, so that's effectively
> in-place, although since the type of a value cannot change, reshape needs
> to give a new value.

OK, I guess I was confused by
function reshape(a::AbstractArray, dims::Dims)
if prod(dims) != numel(a)
error("reshape: invalid dimensions")
end
b = similar(a, dims)
for i=1:numel(a)
b[i] = a[i]
end
return b
end

but I guess there must be an Array-specific counterpart that works in-place:
julia> a = [1,2,3,4,5,6]
6-element Int64 Array:
1
2
3
4
5
6

julia> convert(Ptr{Int},a)
Ptr{Int64} @0x0000000003e6cb88

julia> a = reshape(a,2,3)
2x3 Int64 Array:
1 3 5
2 4 6

julia> convert(Ptr{Int},a)
Ptr{Int64} @0x0000000003e6cb88

So, never mind!
--Tim

> The assignment `a = b` does not copy an
> array, it just makes `a` refer to the same array as `b`.

Yep, overall I really like this behavior, I just thought I'd seen one
downside.

--Tim

[Patrick O'Leary]

On Friday, April 20, 2012 2:53:18 PM UTC-5, Tim wrote:

On Friday, April 20, 2012 03:16:24 PM Stefan Karpinski wrote:
> Reshape already shares memory with the original copy, so that's effectively
> in-place, although since the type of a value cannot change, reshape needs
> to give a new value.

OK, I guess I was confused by
function reshape(a::AbstractArray, dims::Dims)
    if prod(dims) != numel(a)
        error("reshape: invalid dimensions")
    end
    b = similar(a, dims)
    for i=1:numel(a)
        b[i] = a[i]
    end
    return b
end

but I guess there must be an Array-specific counterpart that works in-place:

There is; it's in base/array.jl and in turn does a ccall defined in src/array.c as jl_reshape_array.

[Stefan Karpinski]

Arguably, we should get rid of that fallback definition.

[Gabor]

> I like being able to assume a+=b is always the same as a=a+b, it's one less
> thing to worry about writing generic code. Probably need some more syntax.

Maybe new syntax could be avoided, if

1. c=a+b is a fresh allocation

2. a=a+b and a+=b are the same and work in-place

3. a=b+a is the only questionable case.
I would suggest to do a fresh allocation here,
i.e. the same numeric result as a=a+b,
but with a fresh memory allocation.

So as expressions a+b and b+a are identical
but as assignments their allocation differ.
For in-place work one is forced to use the a=a+b variant.

Is this crazy?

On Apr 20, 8:20 pm, Jeff Bezanson <jeff.bezan...@gmail.com> wrote:

[Stefan Karpinski]

Making `a = a + b` be in place is a complete non-starter because it changes the meaning of assignment. Having `a += b` mean something different than `a = a + b` is a different question. I guess it's a matter of whether its more important for `a += b` to be safe for generic programming or to be a way to write in-place array operations. It's a tough call since both generic programming and efficient array operations are very important.

[Toivo Henningsson]

> > How about using
>
> >     a[] += b # inplace addition
> >     a[] = b   # inplace assignment
>
> Not terribly discoverable. We already use ! for in-place operations; is a
> +!= b unacceptable for parsing reasons?

I think the main downside would be that it would make in-place
assignment be !=
Speaking of that, I think this discussion is getting pretty close to

http://groups.google.com/group/julia-dev/browse_thread/thread/6d6196788761b272/1dd0e17017eeabfc?lnk=gst&q=in-place+vectorized#

[Stefan Karpinski]

Yeah, I was going to mention that thread. Basically the same issue. We never came to a satisfactory conclusion. I might be willing to have `+=` be unsafe for generic code since for generic code you can always just write out `x = x + y` for the sake of making it in-place for array operations.

[Gabor]

Thanks for articulating the problem so clearly,
and forget for my useless suggestion.

I can only hope you will make the right choice.
If possible without any new syntax.

> > > - Show quoted text -- Hide quoted text -

[Stefan Karpinski]

On Apr 20, 11:00 pm, Stefan Karpinski <ste...@karpinski.org> wrote:

Making `a = a + b` be in place is a complete non-starter because it changes the meaning of assignment. Having `a += b` mean something different than `a = a + b` is a different question. I guess it's a matter of whether its more important for `a += b` to be safe for generic programming or to be a way to write in-place array operations. It's a tough call since both generic programming and efficient array operations are very important.

On Fri, Apr 20, 2012 at 5:21 PM, Gabor <g...@szfki.hu> wrote:

Thanks for articulating the problem so clearly, and forget for my useless suggestion.

I can only hope you will make the right choice. If possible without any new syntax.

Programming language design is full of all sorts of nasty little tradeoffs like this. It's why the problem is never really solved — so many unfortunate dilemmas simply don't have perfect solutions and every language is a collection of different tradeoffs. I hope we make the right choice too — the question is what it is :-\

[Stefan Karpinski]

There is another option that would give the best of both worlds, but it's harder and wouldn't happen immediately. We've talked about doing approximate reference counting with the low bits of array pointers (basically: 00 = 1 ref, 01 = 2 refs, 10 = 3 refs, 11 = many refs; once you reach 11, ref counting stops, the object is copied). In that case, you could conceivably know when doing an operation like `x += y` that there's only one reference to x so that it can be modified in place. It's a pretty sophisticated optimization, but it would make `x += y` safe for generic programming and do the array addition in-place when possible. Has some of the same drawbacks as copy-on-write though, in that it makes performance a bit brittle (not quite as bad, however).

[Vitalie Spinu]

This thread made me wonder about SETF and generalized assignment (from
Common Lisp) which, as far I can see, are not available in Julia.

In short (setf place value) assigns value into place where place can be
a function call (fun foo). So SETF is sort of "dispatched" on function
name.

For example suppose (dim A) returns (3 2) -- the dimension of A. Then
(setf (dim A) (1 6)) would reshape A in place to a [1 6] matrix.

In R you can do this with

dim(A) <- c(1, 5)

And you can define custom methods for "dim<-". Julia needs a separate
function "reshape" for this.

As experience with R shows, there are plenty of useful cases when
generalized assignment is useful. Basically, if language doesn't have
this feature, whenever you have an accessor FUN one would need to define
a separate setter SETFUN (for example "size" and "reshape" in Julia).

This relates to the += discussion as follows. If you have a generic
SETF method then += and all other operators which modify places can just
be defined in terms of generic SETF (or "setplace" if you like):

+=(place, value)=setf(place, place+value)

An obvious advantage being that once SETF is defined for some type Bar,
all "in-place" operators become automatically available for Bar. This is
perfectly in line with "generic programming".

Obviously +=, -= etc will be "in-place" and not just equivalent to
place=place+value. But my guess is that in all other languages += is an
"in place", isn't it'? Would be good to have the same in Julia for
consistency.

Moreover, if generalized assignment were available in Julia one might do
something like

fun(foo) += value

to set in-place FOO depending on the meaning of the accessor FUN.

>>>> Stefan Karpinski <ste...@karpinski.org>

[Stefan Karpinski]

Using setf to change the dimensions of an array like this changes its type, which we're never going to allow: if code can change the type of a value, absolutely all type analysis falls apart and you'll never be able to get decent performance.

The expression `x += y` does not actually do in-place mutation for things like numbers — because numbers are immutable in every (sane) language. Hence the problem for generic programming: if `x += y` does in-place modification of arrays, then it has one behavior for arrays and another behavior for numbers, violating genericness of the code.

[Vitalie Spinu]

My dim example was just an illustration (hopefully dimnum as part of
array type is a really useful feature).

There are milliards of accessors and thus setters what don't and should
not affect the type of the placeholder. My whole point is that Julia is
missing an extremely valuable feature.

As to arrays, I don't understand your statement. As long as you define
SETF which does not mutate it's type, +=, -= won't mutate it
either. That + operator can mutate in Julia, is a completely different
story.

>>>> Stefan Karpinski <ste...@karpinski.org>

[Stefan Karpinski]

I wasn't talking about += mutating a type, but rather mutating values. If `x += y` operates on arrays in-place, consider the following generic function:

function foo(x,y,n)

  while n > 0

    x += y

    n -= 1

  end

  return x

end

Now consider using this where x is a number:

julia> x = 5; y = 2;

julia> foo(x,y,3)

11

julia> x

5

The outer x is still 5 because incrementing x inside a function doesn't mutate x outside the function. Consider calling this on matrices instead:

julia> X = rand(3,3)

3x3 Float64 Array:

 0.676528   0.883306  0.0973269

 0.34819    0.543362  0.777249 

 0.0366185  0.120236  0.0488515

julia> Y = eye(3,3)

3x3 Float64 Array:

 1.0  0.0  0.0

 0.0  1.0  0.0

 0.0  0.0  1.0

julia> foo(X,Y,3)

3x3 Float64 Array:

 3.67653    0.883306  0.0973269

 0.34819    3.54336   0.777249 

 0.0366185  0.120236  3.04885  

julia> X

3x3 Float64 Array:

 0.676528   0.883306  0.0973269

 0.34819    0.543362  0.777249 

 0.0366185  0.120236  0.0488515

Currently, the outer X is unchanged, just like for a number. If, however, `x += y` operates on x in-place, the outer X would be changed after the call, having the same value that is returned by the call to `foo(X,Y,3)`.

That's a problem for generic programming since it's often reasonable and desirable to write a function like this and be able to use it on numbers or things like matrices. Think of, for example, applying a polynomial function like `f(x) = x^2 + 2x - 1` to matrices — perfectly reasonable to do. However, for this to work for something like matrices, some care does need to be taken. For example, the constant term should be written as `one(x)`, or maybe even `x^0`, which will give an identity matrix of the correct type and size. So, given that some care already needs to be taken to write effective generic code, it's arguable that we can insist that if one wants to avoid mutating `x` in generic code, one needs to write `x = x + 1` instead of `x += 1`. But hopefully you can see why I'm hesitant to just make that kind of a change without serious consideration.

[Toivo Henningsson]

I think this is a neat idea, but it clashes right on with the function
definition syntax

f(x,y) = x*y

Apart from that, I agree that it could be useful in many ways, and
improve consistency. But of course things like reshape would still
have to be done the normal way.

[Toivo Henningsson]

On Apr 20, 11:20 pm, Stefan Karpinski <ste...@karpinski.org> wrote:
> Yeah, I was going to mention that thread. Basically the same issue. We
> never came to a satisfactory conclusion. I might be willing to have `+=` be
> unsafe for generic code since for generic code you can always just write
> out `x = x + y` for the sake of making it in-place for array operations.

I guess the thing that's at the heart of this issue is lack of ascii
real estate.
That's the reason I came to think about a[] = b, a[] += b in the first
place; it doesn't need any new literal operators.

[Vitalie Spinu]

>>>> Toivo Henningsson <toiv...@gmail.com>

>>>> on Sat, 21 Apr 2012 00:03:15 -0700 (PDT) wrote:

> On Apr 21, 1:06 am, Vitalie Spinu <spinu...@gmail.com> wrote:
>> This thread made me wonder about SETF and generalized assignment (from
>> Common Lisp) which, as far I can see, are not available in Julia.
>>
>> In short (setf place value) assigns value into place where place can be
>> a function call (fun foo). So SETF is sort of "dispatched" on function
>> name.

> I think this is a neat idea, but it clashes right on with the function
> definition syntax

> f(x,y) = x*y

> Apart from that, I agree that it could be useful in many ways, and
> improve consistency. But of course things like reshape would still
> have to be done the normal way.

I personally have hard time understanding and getting used to this
design choose. There must be really serious reasons to steal this syntax
form generalized assignment.

The language already has a neat assignment for lambda definitions
"->". Why not to use that for the function definition? It's also more
notationally consistent this way, and doesn't confuse people used to
generalized assignment from other languages.

[Vitalie Spinu]

>>>> Stefan Karpinski <ste...@karpinski.org>

>>>> on Fri, 20 Apr 2012 20:13:35 -0400 wrote:

> I wasn't talking about += mutating a type, but rather mutating values. If
> `x += y` operates on arrays in-place, consider the following generic
> function:

Ah, I see now what you mean ... but the problem is only with function
arguments. Given that julia's pass by reference semantics and huge
number of basic types, it's already pretty difficult to write generic
code. But one cannot have everything :).

Generally speaking, having different syntax for the same thing is a bit
of waste of potentially useful programing tools. In programs += is most
often used in loops when efficiency is important. One will just have to
take care to use local variables, not a big deal. Interactively +=,
saves typing and does not matter for the end result if it's in-place or
not, but matters for efficiency.

[Jeff Bezanson]

It seems promising to observe that a[:]+=1 is in place, but not very
efficient currently since it does a[:] = a[:] + 1. We could make
"a[b]+=c" syntax for something like update(a, +, c, b), or (+=)(a, c,
b) which could default to calling the more general update(). Also
useful for hash tables.

[Toivo Henningsson]

On Apr 24, 9:49 pm, Jeff Bezanson <jeff.bezan...@gmail.com> wrote:
> It seems promising to observe that a[:]+=1 is in place, but not very
> efficient currently since it does a[:] = a[:] + 1. We could make
> "a[b]+=c" syntax for something like update(a, +, c, b), or (+=)(a, c,
> b) which could default to calling the more general update(). Also
> useful for hash tables.

+1

[Konrad Hinsen]

Stefan Karpinski writes:

> I wasn't talking about += mutating a type, but rather mutating values. If `x += y`
> operates on arrays in-place, consider the following generic function:

...

Python has the same problem with += etc., whose semantics depend on
how each particular type implements it. Pretty much everyone gets bitten
by this sooner or later, which is why many pythonistas avoid using +=
except as an explicit optimization for array updates.

My personal preference would be to have += defined *only* for mutable
data (in particular arrays) and fail for any other type, such as a
plain number. That choice provides an important optimization facility
for array updates without creating any confusion.

On the other hand, I know others like += just as a shorthand. It's
hard to please everyone...

Konrad.

[Vitalie Spinu]

Update has a very general meaning, it could mean update a model, run
more simulations, update a plot etc. May be set, setplace, assign, or
assingplace?

If you can reconsider using foo(a)= b for function definition, and use
foo(a)-> b instead, general "set" might look like set(:foo, object,
value) to get the assignment:

foo(object) = value

and set(:ref, object, value, inx) to do

object[inx]=value

and set(:ref, object, value, inx, +) to do

object[inx]+=value


Alternatively julia might parse foo(object)=value into (foo=)(object,
value), although not a valid syntax right now. Then a developer of the
accessor "foo" can just define (foo=) method to implement the
setter. a[b]+= might parse as (ref=)(a, b, +). This is how it works in
R.

Any chance to reconsider the use of generalized assignment? It's a very
useful feature and syntactically more consistent IMO. Shall I create an
issue as a reminder?

For the description of the SETF in CL:
http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node80.html
http://clhs.lisp.se/Body/m_defset.htm


Vitalie.