Operator overloading for linear algebra

[Marius Cobzarenco]

Hi all,

I have been evaluating golang for building a distributed machine learning backend (the other contender is C++) and although I must say I've been easily won over by many of golang's language features as well as the extremely clean syntax and the built-in build system & package manager, I found the lack of operator overloading a bit troublesome. I can understand why it was left out, when clarity & maintainability was high up on the priority list. However, in an application consisting of mostly of numerical code, it has the opposite effect, obscuring the mathematics and hence reducing maintainability. I would argue that support for inline operators for doing linear algebra (i.e. matrix/vector operations) is as natural as inline operators for integers/floating point numbers and it is crucial if golang is to gain traction in the scientific community. I was curios if there are any plans to ever add operator overloading to the language, even if just for matrices?

Thanks,

Marius

[Jesse McNelis]

On Thu, Jul 18, 2013 at 8:52 PM, Marius Cobzarenco <marius.c...@gmail.com> wrote:

 I would argue that support for inline operators for doing linear algebra (i.e. matrix/vector operations) is as natural as inline operators for integers/floating point numbers and it is crucial if golang is to gain traction in the scientific community. I was curios if there are any plans to ever add operator overloading to the language, even if just for matrices?

There is a near endless supply of programming languages that let you declare and overload operators.

http://golang.org/doc/faq#Why_doesnt_Go_have_feature_X

http://golang.org/doc/faq#overloading

[GreatOdinsRaven]

I, for one, absolutely despise operator overloading. 

It seems to have exactly two uses:

1. String concatenation (so useful, in fact, that Java, Go allow it as a special case to "+")

2. Matrix algebra 

C# has full-blown operator overloading a-la C++ and adds just one more "useful" (and that's debatable) case:

3. Adding/subtracting dates and timespans from/to each other. 

Every other use of operator overloading is either useless syntactic sugar or pure mental abuse (hello, C++ stream operators!) 

So basically, I feel you are proposing a language change that will complicate things just for ONE very special edge case - matrix algebra. My magic 8-ball says: "No, this will never happen". 

The Go community is *still* coming to grips with lack of compile-time generics, and that one I'm guessing is *much* higher on the priority list (higher, but still pretty low compared to yet other features) than a purely syntax sugar feature like operator overloading. Let's not try to think of Go as "C++ with missing C++ features" - we all lose.  

[Alexei Sholik]

Operator overloading is not just syntactic sugar, it is syntax.

In a language with syntax you can write (a + b * c - d). With no operator overloading, you're forced to write add(a, sub(mul(b, c), d)) or even a.add(b.mul(c)).sub(d) for any type that is not a primitive built-in.

Basically, without op overloading your arithmetic code turns into a very ugly Lisp. I would prefer to write in Lisp instead. There, you can rebind functions lexically and functions can be named with characters like "+", "-", etc.:

    (+ a (- (* b c) d).

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Best regards
Alexei Sholik

[Stefano Casillo]

On Thursday, July 18, 2013 4:10:40 PM UTC+2, GreatOdinsRaven wrote:

 

So basically, I feel you are proposing a language change that will complicate things just for ONE very special edge case - matrix algebra. My magic 8-ball says: "No, this will never happen". 

While I understand the reasoning behind the decision... making the math code unreadable makes Go REALLY hard to accept in scientific and game programming circles.. which is a shame, because Go would really shine in both scenario.

Perhaps adding a very limited number of operators (+ , -, *, /) available to overload putting a strong limit on the implementation of the overload (ie.. istruction limit, can't call other functions and so on) might solve the linear algebra debacle while retaining consistency and avoid the FUD about "expensive functions hidden behind a simple operator".

 

[atomly]

I don't see how you could possibly add operator overloading to the language as it stands-- it doesn't even have method overloading...  Would you want it to be something like this?

type Matrix interface {

  func (m Matrix) Add(other Matrix) Matrix

  func (m Matrix) +(other Matrix) Matrix

}

and the code for + basically just calls Add()?  Or would you want some special case syntax where you bind preexisting methods to a specific set of overloadable operators?

How do you specify fixity?

Go already supports full Unicode method names, right? If you could just figure out some ways around those pesky parentheses you could probably do something sneaky.

I personally really like how Scala solved the notion of operator overloading... A few strange rules you have to memorize at first, but from then on it works quite well and allows you to easily build DSLs.

:: atomly ::

[ ato...@atomly.com : www.atomly.com  : http://blog.atomly.com/ ...
[ atomiq records : new york city : +1.347.692.8661 ...
[ e-mail atomly-new...@atomly.com for atomly info and updates ...

 

--

[David DENG]

I don't think operator overloading is essential to scientific programing. Commonly I just write a comment with math form to clarify the equation. That is quite enough.

One thing operator overloading could help is generic, which is said to be designing.

But I still dislike operator overloading at all.

David

[Stefano Casillo]

On Thursday, July 18, 2013 5:17:04 PM UTC+2, atomly wrote:

I don't see how you could possibly add operator overloading to the language as it stands-- it doesn't even have method overloading...  Would you want it to be something like this?

type Matrix interface {

  func (m Matrix) Add(other Matrix) Matrix

  func (m Matrix) +(other Matrix) Matrix 

}

I don't know much about language design, I am a language user.

I would like something like this:

type Vector3f struct {

X float32

Y float32

Z float32

}

operator + (v1,v2 Vector3f) Vector3f {

// bla bla

}

The compiler would have to make sure that the operator body won't call any func.. I can imagine this being tricky when the operator is part of a package, but it seems to be handled fine by C# and other languages with operator overloading.

I understand this is a lot of work for an "exception" being linear algebra... but it really does make the difference for things like 3D and game programming.. I am already using Go for the server side of my game, I would start to use Go for my next game TONIGHT but the thought of having to write something like:

r:=a.Add( b.Scale(c).Sub(d) ) 

Instead of:

r:=a+(b*c-d)

is enough to make me want to kill myself instead... and it's a shame, cause Go could easily cover both side of a game, low level and high level.. High level game code with Go's interfaces is a dream.

[Volker Dobler]

> While I understand the reasoning behind the decision... making the math code unreadable

> makes Go REALLY hard to accept in scientific and game programming circles.. which is a

> shame, because Go would really shine in both scenario.

I doubt these arguments by personal experience.

First: You do not write math, not even with operator

overloading. Which operator would you like to overload

to indicate matrix transposition? Will you use * on vectors

as a dot product, or a cross product? You must choose.

In math you have \star, \cdot, \times and so on (and even

just a space). In code you have just one *. Your code won't

be math. Besides from x_i in math is x[i] in code and x[i]

in math might mean whatever the author chooses as meaning.

As has been said already: Overloading + and - for vectors

and matrices and * for matrix and vector is fine and helps in

just this singular use case where all you do is add, subtract

and multiply.

A personal anecdote, my learning in operator overloading:

I did some numerical simulation of light absorption and

heat diffusion in C++ and decided to use Blitz++ which

was then bleeding edge. Boost was not invented yet. It was

fine: The code read like math, it performed well, no manual

loops over vector indices, great.

At some point the "math-kernel" was done (bug-free,

documented, fast) and the project started to evolve with

fancier input, job resumes, generating gnuplot scripts

and flexible system definition. In the end the math-kernel

was maybe 5% of the overall code. It wouldn't have taken

much longer to write and debug it if I had to use functions

instead of overloaded operators but the overall program would

have been much more readable, testable and maintainable

in the current no-op-overloading Go.

I believe it is better to use function/methods than overload

operators and add some proper documentation in _real_

math notation // F^\mu_\nu = g^\mu_\alpha T^\alpha_\nu

V.

 

[yy]

Every time this discussion is on the table I wonder if anybody has considered the possibility of evaluating mathematical expressions as we do with regular expressions. Having done a good deal of scientific programming myself I think it could be really useful for some cases, and not so much for other ones, but nevertheless I think it may be an interesting experiment.

I'm not sure how this would really look like. Maybe having a map to correlate operators with functions and then a function to evaluate expressions using said operators. I'm aware that how to deal with types here may be a huge challenge and that, in general, all this may require much more effort than what is worth.

However, I think this may be even more powerful than operator overloading. We could be able to write not only simple linear algebra expressions, but also more complicated stuff, like using Einstein tensor notation or unicode symbols, even parsing LaTeX would be possible in theory.

Think, for example, being able to do something like:

norm := mathexp.MustCompile('a[i]: √(a[ii]²)')

and, then, call norm(floatarray) to evaluate the norm of floatarray.

Since the time needed to compile these expressions compared to the time needed for number crunching would be negligible, I don't think performance would be a problem. However, a real problem would be that we lost any compile time safety and instead postpone that until runtime. Tests may help there, though.

Of course, this is only a very vague idea (and, for what it's worth, maybe a stupid one). Many details would have to be well thought and it may even be impossible to find a reasonable implementation (there's also the risk of eventually implementing another full language).

I'm not really making a proposal, just asking if anybody have seen something similar before and think it could be a good fit for doing scientific programming in Go.

--
- yiyus || JGL .

[luz...@gmail.com]

On Thursday, July 18, 2013 6:03:24 PM UTC+2, Stefano Casillo wrote:

I would start to use Go for my next game TONIGHT but the thought of having to write something like:

r:=a.Add( b.Scale(c).Sub(d) ) 

Instead of:

r:=a+(b*c-d)

Both variants are pretty readable. In game development only a small part of the code is at this level. Your data structures and their behavior will quickly reach higher levels of abstraction.

[Kamil Kisiel]

The problem is that mathematical expressions don't map directly to code. Especially when you are working with floating point numbers, the order of of operations can have a significant effect on the precision of the result, and that can also depend on the relative magnitudes of the numbers involved. Sometimes a solution which works in one case will require a different approach in order to produce the correct results. I don't think it's a problem you can solve in the general case, you need to tune the algorithm carefully in each case.

[Gerard]

Well, they do. As long as you work with variable names instead of values. 

Then it's quite possible to work with strings (LaTeX). It would be really great to one day have a package that can read formatted text files with formulas. Like Mathcad.

[Sebastien Binet]

sent from my droid

Sounds a lot like SymPy, Theano or any symbolic engine...

-s

>
>
> --
> - yiyus || JGL .
>

[Stefano Casillo]

 perhaps I should just go ahead and bite the bullet and it'll turn out much less painful than I thought.

[Ian Lance Taylor]

On Thu, Jul 18, 2013 at 8:17 AM, atomly <ato...@gmail.com> wrote:
> I don't see how you could possibly add operator overloading to the language
> as it stands-- it doesn't even have method overloading...

I'm personally ambivalent about operator overloading. But I think
it's worth pointing out that although the language does not have
method overloading, it does overload the arithmetic operators. The +
operator is implicitly overloaded for all the arithmetic types. There
would be no conceptual difficulty to permitting programs to define a +
function for a type.

Ian

[Vova Niki]

I have written Game and physics engine in Go (https://github.com/vova616/GarageEngine) and the main problem was not the syntatic suga but the performance.

I had to inline huge amount of code to pure math and the performance boost was huge. (ex: p = Add(s,v)  to p.x, p.y = s.x+v.x, s.y+v.y and etc) 

[Stefano Casillo]

On Friday, July 19, 2013 9:07:10 PM UTC+2, Vova Niki wrote:

I have written Game and physics engine in Go (https://github.com/vova616/GarageEngine) and the main problem was not the syntatic suga but the performance.

I had to inline huge amount of code to pure math and the performance boost was huge. (ex: p = Add(s,v)  to p.x, p.y = s.x+v.x, s.y+v.y and etc) 

Yep.. same here, from the test I did manual inlining offers huge performances boosts... a bit like XNA on the X360. I don't know why that happens but I hope the code generation gets smarter in these cases.

[mortdeus]

If we implemented everything people miss when using Go, we would end up back at square one with C++. 

[Stefano Casillo]

On Saturday, July 20, 2013 8:43:02 AM UTC+2, mortdeus wrote:

If we implemented everything people miss when using Go, we would end up back at square one with C++. 

yes but that cannot stop considering options.... otherwise just close the shop, go home and hope ppl will come. It usually doesn't really work well that way.

I don't think anybody here is shouting asking for stuff, it's a very polite conversation.. nothing compared to the generics related threads :)

[Gerard]

Ian, you are saying that a "+" function for a type would be possible.

Then it's something like : 

type Vector []float64

func (p *Vector) +(s *Vector) (res *Vector) {

  // implementation

}

With the following restrictions:

- All variables are from the same type AND have exactly the same order as the standard predefined operators.

- There can be only ONE "+" function within each type.

- Visibility is only dependent of the visibility of the type itself.

Then the usage of these functions can be as simple as with the operators of the standard predefined types:

  a := b + c

Am I correct?

I think this is very interesting. Something for Go 1.x or for Go 2 ?

Gerard

[Gerard]

Sorry, please forget my mail. I got a little excited.

Gerard

[John Nagle]

I can live without operator overloading, and I've done a lot of
numeric code. I used to do physics engines for simulators. It's
just syntax. It's a bit verbose to have to write everything as
functions, but it's unambiguous.

In C++, operator overloading usually leads to "Why did the compiler
use that function?", or "What chain of conversions was invoked here?"
In Python, it leads to "Do I pass a Python array or a numarray here?",
and worse, both might run, but produce different results.

Multidimensional slices and arrays, though, should be fully
supported. Those aren't just syntax. They affect performance
where it's really needed, in inner loops of numeric code.
Also, not having them means that each math library rolls
their own. Then you have to write conversion functions between
math libraries and recopy arrays, maybe very large arrays.

John Nagle

[roger peppe]

On 22 July 2013 06:24, John Nagle <na...@animats.com> wrote:
> Multidimensional slices and arrays, though, should be fully
> supported. Those aren't just syntax. They affect performance
> where it's really needed, in inner loops of numeric code.
> Also, not having them means that each math library rolls
> their own. Then you have to write conversion functions between
> math libraries and recopy arrays, maybe very large arrays.

Out of interest, would you include in that requirement arrays whose
dimensionality is only known at runtime?

One difficulty with multidimensional slices is that you really
want to be able to reduce the number of dimensions without
copying all the data, and that potentially impacts on the runtime
performance of all slice operations. Perhaps it might work OK
if slices with possible strides were distinguished in the type
system.

I'd like to see a concrete proposal for how multidimensional
slices/arrays might fit nicely into Go.

[John Nagle]

On 7/22/2013 12:37 AM, roger peppe wrote:
> On 22 July 2013 06:24, John Nagle <na...@animats.com> wrote:
>> Multidimensional slices and arrays, though, should be fully
>> supported. Those aren't just syntax. They affect performance
>> where it's really needed, in inner loops of numeric code.
>> Also, not having them means that each math library rolls
>> their own. Then you have to write conversion functions between
>> math libraries and recopy arrays, maybe very large arrays.
>
> Out of interest, would you include in that requirement arrays whose
> dimensionality is only known at runtime?

For now, just being able to express Numerical Recipes in Go
cleanly and efficiently would be a big step forward. For that,
the number of dimensions can be fixed at compile time, although the
size of each dimension can vary at run time. My thinking here is
to get FORTRAN-quality optimization for common matrix number
crunching into Go.

Now that machine learning is so popular, there's more interest
in working in very high dimensional spaces. That's much harder to
express and to optimize. Few languages have ever had support
for arrays with variable numbers of dimensions. It's hard to
even talk about that at the syntax level. Do you pass an array
as a subscript, or what? Do you know of any language that has
such a syntax and does anything interesting with it at compile
time? The Julia language is trying to deal with that problem,
but it's too early to tell if that approach is a win.

This is a research problem. How to optimize for arrays with a
known number of dimensions is well understood; FORTRAN compilers
have been doing it all the way back to Backus in the 1950s.
Generalizing beyond that may overcomplicate the language without
increasing performance much.

> One difficulty with multidimensional slices is that you really
> want to be able to reduce the number of dimensions without
> copying all the data,

Flattening is sort of a problem space dependent operation.

> and that potentially impacts on the runtime
> performance of all slice operations. Perhaps it might work OK
> if slices with possible strides were distinguished in the type
> system.

All multidimensional slices would have a stride for each
dimension.

> I'd like to see a concrete proposal for how multidimensional
> slices/arrays might fit nicely into Go.

Someone into number-crunching wrote a paper on this,
which is where I got the idea.

Would you be the one implementing this?

John Nagle

[roger peppe]

Matlab and Python are two examples that I'm personally familiar
with that allow this (numpy is modelled closely after matlab, I believe).
APL too, although I've never used it in anger. Yes,
the subscript is an array (well, a tuple in python).
I'm not aware of any statically typed languages that allow
this though.

One particular advantage of allowing variable numbers of dimensions
is that it allows writing code that works generically across an
n-dimensional array (e.g. flatten). I think this is probably
orthogonal to generics across types.

It's quite likely that if Go allowed multidimensional types,
it would eschew variable dimensionality outside of reflect,
but it's worth considering.

> This is a research problem. How to optimize for arrays with a
> known number of dimensions is well understood; FORTRAN compilers
> have been doing it all the way back to Backus in the 1950s.
> Generalizing beyond that may overcomplicate the language without
> increasing performance much.
>
>> One difficulty with multidimensional slices is that you really
>> want to be able to reduce the number of dimensions without
>> copying all the data,
>
> Flattening is sort of a problem space dependent operation.

Agreed, but I think there are quite a few very common operations
that are useful (e.g. deleting a dimension of length 1; treating a
2D matrix as a 1D vector containing all its elements).
It might be nice (but it's by no means essential) if at least some of those
might be easily expressed without writing a function

>> and that potentially impacts on the runtime
>> performance of all slice operations. Perhaps it might work OK
>> if slices with possible strides were distinguished in the type
>> system.
>
> All multidimensional slices would have a stride for each
> dimension.

Is a single-dimensional slice not just a special case of a multi-dimensional
slice?

>> I'd like to see a concrete proposal for how multidimensional
>> slices/arrays might fit nicely into Go.
>
> Someone into number-crunching wrote a paper on this,
> which is where I got the idea.
>
> Would you be the one implementing this?

No. I think it's worth coming up with something
that might work though. If it works well with the rest of
the language and the core devs like the idea, I'm guessing it
could be a possibility for Go 2.

cheers,
rog.

[hamnaa...@gmail.com]

Can we overload the same operator e.g "  *   " for two functios like dot and cross product ????

[Nate Finch]

There's a quote from Clean Code - write your code in the solution domain, not the problem domain.  Operator overloading tries to keep the code too close to the problem domain.  Code is not math, despite what some people may say.  If you want to fill a page of code with math equations, you're doing it wrong.  Yes, at some point you'll probably have to do a dot product of a couple vectors, but it should be limited to a small function with very few lines, which is used by more generic functions, and can be easily tested.  We should be producing packages that help abstract away the details of the math so that you can solve the problem, not solve the math.  Trying to duplicate math in Go simply perpetuates the problem... everyone has to solve the math over and over, rather than solving the problem.

[Stan Steel]

While working on a missile simulation project at Boeing, I had to translate, code, and optimize mathmatical formulas and algorithms into java code for the better part of four months.  While I would have loved to have written code that more closely resembled the math I was using, writing unit tests amd fast iterations was the most important factors.  I'd surmise that because math is easy to test and verify, the significance of native feeling syntax is of lesser importance.   It also helps that those are the parts of the systems, that once coded, typically can be left alone.

On Sep 25, 2013 1:58 PM, "Nate Finch" <nate....@gmail.com> wrote:

There's a quote from Clean Code - write your code in the solution domain, not the problem domain.  Operator overloading tries to keep the code too close to the problem domain.  Code is not math, despite what some people may say.  If you want to fill a page of code with math equations, you're doing it wrong.  Yes, at some point you'll probably have to do a dot product of a couple vectors, but it should be limited to a small function with very few lines, which is used by more generic functions, and can be easily tested.  We should be producing packages that help abstract away the details of the math so that you can solve the problem, not solve the math.  Trying to duplicate math in Go simply perpetuates the problem... everyone has to solve the math over and over, rather than solving the problem.

--

[Harry de Boer]

Hi Marius,

if you care about readability mathematical operations, maybe you can take a look at Julia: http://julialang.org/
I have not tried it myself yet, but it looks promising.

Harry

[Robert Johnstone]

Unless you're using Haskell (which allows users to define binary operators with any characters that they like), you don't.  You use the operator for the most common operation, and use user a function for the other.  You end up with code like a * cross( b, c ).

[Robert Johnstone]

Using C++ as an example in this case is very misleading.  It is well known in the C++ community that mixing implicit conversions with method overloading is bad design, as you quickly end up in the situation that you described, where the two features interact in very confusing ways.  This is further complicated by the fact that C++ has some fairly complicated name lookup rules.  Since go does not support implicit conversions, nor argument dependent lookup, the same confusion would not occur.

While I would not advocate for adding method overloading to Go, comparisons to C++ are misleading.  The complexity in C++ stems from the interaction of many other language factors that are not present in Go.

As a side note, Go already support function overloading, it is just that the overloading is restricted to the receiver.

[Kevin Gillette]

I think what he's saying is "there would be no conceptual difficulty to permitting programs to define a + function for a type." That doesn't imply that it will be added to the language, or that it's a good idea: for one thing, it strongly violates Go's principle of avoiding hidden costs.