Generics - Maybe we don't need them?

[Miki Tebeka]

Greetings,

Maybe we don't need generics. Maybe the solution is enhancing interfaces to
cover basic types.

This idea came to me while going over http://learnyouahaskell.com. There if you
want to have a generic "max" function, it takes "Ord" typeclass (interface). If
we'll have Go numbers also implement "Ord" interface then a generic "max" will
be easy to write.

What are your thoughts on this?

Thanks,
--
Miki

[John Asmuth]

Can you fill this out a bit? What methods would the Ord interface have, and how could we use them to compare arbitrary numerical types? Only thing I can thing of is a Float64() method, but that is a very inefficient way to do a comparison.

[Evan Shaw]

On Tue, Nov 22, 2011 at 10:44 AM, Miki Tebeka <miki....@gmail.com> wrote:
> This idea came to me while going over http://learnyouahaskell.com. There if
> you
> want to have a generic "max" function, it takes "Ord" typeclass (interface).
> If
> we'll have Go numbers also implement "Ord" interface then a generic "max"
> will
> be easy to write.

This does make interfaces much more useful, but doesn't provide
everything generics could. Let's imagine we do have an Ord interface.
Max's signature will look something like

func Max(a, b Ord) Ord

I still have to use a type assertion to get a concrete type back,
which means I don't get type safety at compile time. It also doesn't
provide the performance benefits that one might hope to see from
generics.

- Evan

[Ryanne Dolan]

Today we already can have MaxInt, MaxFloat, and Max(Ord, Ord) Ord.

I suppose it would be neat if the compiler automatically specialized Max for basic types, but right now the only "problem" we have with the lack of generics is that we hafta write a few extra functions by hand.  Notice that there are only a small number of basic types so writing a "generic" Max is not hard.  Moreover, a lot of generic code must be specialized by hand anyway, so you end up writing Max<int,int> by hand instead of MaxInt.

I'm not impressed.

By the way, MaxIndex(Ord ...) int is even more "generic" and doesn't require a type assertion.

Thanks.
Ryanne

--
www.ryannedolan.info

[Jonathan Wills]

On Mon, Nov 21, 2011 at 1:46 PM, John Asmuth <jas...@gmail.com> wrote:

Can you fill this out a bit? What methods would the Ord interface have, and how could we use them to compare arbitrary numerical types? Only thing I can thing of is a Float64() method, but that is a very inefficient way to do a comparison.

Having a Float64 method won't work anyway, float64 has less than 64 bits of precision so it can't represent all int64 values:

  var a int64 = 0xeeeeeeeeeeeeeed

  var b int64 = 0xeeeeeeeeeeeeeee

  fmt.Printf("%t %t\n", a < b, float64(a) < float64(b))

output:

  true false

[Ryanne Dolan]

Probably should provide a Less(other Ord) bool method instead.

Thanks.
Ryanne

--
www.ryannedolan.info

[KarateCode]

> want to have a generic "max" function, it takes "Ord" typeclass
> (interface). If
> we'll have Go numbers also implement "Ord" interface then a generic "max"
> will
> be easy to write.

I had a very similar idea for an Enumerable package. An example using
generics can be found for C++ in Qt. Their QList<T> object provides
some niceties. However, to implement this in Go, I was thinking that
there could be convenience functions like:

func (Enumerable) HasAny(func() bool) bool
func (Enumerable) All(func() bool) bool
func (Enumerable) None(func() bool) bool

Where Enumerable could be just a simple interface with an Each
function. For any slice or array type, if you implement an Each
function, then your type will inherent all the Enumerable
functionality (making the code look like Ruby-ish shorthand).

[David Roundy]

As others have pointed out, the trouble with using interfaces is that
you don't have static type checking. See, for example, a potential
implementation and use of Max:

type Ord interface {
LessThan(Ord) bool
}

type Foo int
func (f Foo) LessThan(o Ord) bool {
if o, ok := o.(Foo); ok {
return f < o
}
return true // yuck, but what else to do, panic?
}

func Max(a, b Ord) Ord {
if a.LessThan(b) {
return b
}
return a
}

func main() {
var Foo a = 10, b = 11
c := Max(a, b).(Foo)
fmt.Println(c)
}

Notice how type casts are sprinkled everywhere. Every time you use
the Max function, you need to typecast its result. Every
implementation of LessThan needs to typecast internally in order to
perform the comparison. It's nasty. The primary idea of generics (in
my view) is to allow static typechecking of code like this. Of
course, once you're able to write generic functions, you can also do a
lot more, like possibly use generic data types.

David

--
David Roundy

[Mikael Gustavsson]

My Haskell is very rusty, but type classes and go interfaces are quite
different.
Look at this definition:

> type Ord interface {
>   LessThan(Ord) bool
> }

This says that everything that can be ordered can be compared to
anything else which can be ordered. This is not very useful.
What the Ord type class in Haskell says is that "an ordered type is a
type whose values can be compared among themselves".

A simple Ord type class in Haskell could be defined like this:
class Ord a where
(<) :: a -> a -> Bool

And a simple max function in Haskell could be written like this:
max :: Ord a => a -> a -> a
max x y
| x >= y = x
| otherwise = y

This is a generic function, so that if you use it on two ints, the
type checker knows that the result will be int and so on..

If we would try to translate this into some kind of imaginary generic
Go it might look something like this:
type Ord interface<Self> {
LessThan(Self) bool
}

generic Ord<T>
func Max(a,b T) T {
if b.LessThan(a) { return a }
return b
}

[si guy]

But with assertion in the LessThan function can't you do This?
type Ord interface {
LessThan(interface{})
}

[si guy]

Whoops, mis send, code should be:

type Ord interface {
LessThan(interface{}) (bool,error)
}

[André Moraes]

Take a look at:

https://github.com/petar/GoLLRB

Red-Black tree that can handle any kind of value.

--
André Moraes
http://andredevchannel.blogspot.com/

[eaburns]

Here is another implementation of a red-black tree: http://eaburns.googlecode.com/hg/rbtree/.  This implementation separates the keys from their associated values so it is more of an ordered map than an ordered set.  Instead of using a comparison function defined on interface{}, as GoLLRB does, this implementation uses an interface similar to the Ord interface described in this thread for the key types.  Both implementations will require type assertions to get at the contents of the interfaces used in the comparisons so it is not quite the same as truly having generics in the language.   Using interfaces like this requires run-time checks which are less safe and probably slower than generics.  In my (tiny amount of) experience type assertions are pretty cheap but probably not ideal for use within a tight loop.  Has anyone done any experiments with something like the gotgo generics implementation for Go [1] to see what the  performance difference looks like between data structures using generics versus one implemented with interfaces?

A bit off topic, but I am actually quite curious about gotgo because it sounds like it is a working implementation of generics, however, as far as I can tell, most of the generics proposals on this list seem to ignore it.  Is there some flaw with this type of package-level generics?

Ethan

[1] https://github.com/droundy/gotgo

[Miki Tebeka]

func (f Foo) LessThan(o Ord) bool {
  if o, ok := o.(Foo); ok {
     return f < o
  }
  return true // yuck, but what else to do, panic?
}

There are some cases where you can compare two different types (like ints and floats).
I'm not sure how you can tell *in compile time* that two types are comparable.

[John Asmuth]

On Monday, November 28, 2011 9:51:27 AM UTC-5, Miki Tebeka wrote

There are some cases where you can compare two different types (like ints and floats).
I'm not sure how you can tell *in compile time* that two types are comparable.

Not in go, you can't...

http://play.golang.org/p/Fg7KhcuGJA 

[Miki Tebeka]

There are some cases where you can compare two different types (like ints and floats).
I'm not sure how you can tell *in compile time* that two types are comparable.

Not in go, you can't...

http://play.golang.org/p/Fg7KhcuGJA 

I stand corrected, Thanks.

[David Roundy]

On Mon, Nov 28, 2011 at 5:51 AM, eaburns <burns...@gmail.com> wrote:
> A bit off topic, but I am actually quite curious about gotgo because it
> sounds like it is a working implementation of generics, however, as far as I
> can tell, most of the generics proposals on this list seem to ignore it.  Is
> there some flaw with this type of package-level generics?
> Ethan
> [1] https://github.com/droundy/gotgo

I thought package-level generics (generic packages) was a reasonable
idea, but it turns out to have some pretty severe flaws in practice.
The biggest one is that it requires you to put any data type that you
want to deal with generically in a separate package. Very often,
you'd like to do something like:

type Foo struct { ... }

func (f *Foo) MyMethod() []Foo {
[code that uses generic code on lists of Foo, but can't, since it
can't import a package that uses Foo]
}

Of course, you can always work around these things using type synonyms
and so forth, but it doesn't improve the readability of code.

There are also some technical difficulties in using gotgo (which
probably is sufficiently bitrotted that it will no longer compile),
but the biggest issue is that package-level generics just don't
address that many of the situations where you'd really like to use
generics.

David

[josvazg]

Hi David, 

I know this thread is quite old, but I just came across it right now. I understand these limitations you say are impossible to solve from a library but...

Wouldn't all be solvable INSIDE the Go language runtime and implementation?

I mean, lets say for a moment a "kind of gotgo" is built into the compiler:

A) When a package that has NO generics and USES NO generics is compiled, the behaviour is just like it is now, nothing new.

B) When the package HAS some generic type specification:

   1) The gotgo part of the compiler extracts the template snippet in "nearly pure" Go source, like a .got file, and makes it available for THIS or OTHER packages to specialize later WITHIN THIS compilation or ONE from other package. (The extraction should be done AFTER the AST tree is build and errors are detected, it would even be a good idea to replace the generic type with interface{} to have some basic type checking errors if possible)

   2) Then the gotgo part of the compiler would then eliminate ALL generic parts from the compilation before the actual compiler kicks in to generate assembly code.

C) If the package USES some generic type, either from this package of from another compiled before:

   1) The .got-like snippet will be retrieved, the code expanded with the given type.

   2) The new autogenerated source code (maybe a bit hidden to the user) will be compiled WITHIN the original package or this one. I guess the compiler could to be a bit more flexible with the packaging rules than it is now: If the specialisation is from another package it can be compiled as a appendix of the original package and link everything together in the end. 

   3) Finally the compiler, before actually compiling all the code, can make all compile time type checks but it should report the generic type problems ON the user-written specialized code rather than the autogenerated one.

Is this right? Am I making any sense?

What problems or side-effects would this generate?

(I guess if it were so easy Go would already have Generics and it doesn't so I must have missed something)

Thanks in advance, this will help me understand greatly the problems and trade-offs of generics implementations...

Jose

[Paul Borman]

C++ started out as C with Classes, a preprocessor to C.  It sounds like that is what you are suggesting here.  Run you code through got before handing it to go.  

Please see:

    http://research.swtch.com/generic

The important line is:

The generic dilemma is this: do you want slow programmers, slow compilers and bloated binaries, or slow execution times?

You assert the first first is true (slow programmers) while I do not see the Go team giving into the the other two.

Quite frankly, I don't agree that the Go slows you down much and my experience is that you make up for that minimal time by the fast compiles.

    -Paul

[André Moraes]

>> The generic dilemma is this: do you want slow programmers, slow compilers
>> and bloated binaries, or slow execution times?
>
>
> You assert the first first is true (slow programmers) while I do not see the
> Go team giving into the the other two.
>
> Quite frankly, I don't agree that the Go slows you down much and my
> experience is that you make up for that minimal time by the fast compiles.

Go is slow during the warm period when the programmer needs to change
it's mind to think in terms of Go.
If there are people in this list that never programmed before and are
just starting to learn using then the "slow programmer" could be
checked if it's true or not.

[josvazg]

I am not suggesting anything in particular. I am just trying to understand the problem and may be helping find a compromise solution.

I do like the generics concept, "write once and use many times with different types" but I HATE the side effects, like the way my code looks in Java when I deal with complex containers and generics: List<Map<String,Object>> wtf!, this is ugly.

But I ALSO hate being unable to have any help from the language as to be able to "write once and use many times with different types".

Yes there are times, when you can avoid generics in Go altogether, but there are also times than not or that the solution is suboptimal.

For instance, I was doing some tests on sorting algorithms in Go. I was testing mergesort with []int types, the first naive approach was not in place, so the memory allocating made it very inefficient. Then I did a merge in-place and I compared it again to the sort.Ints in the Go standard package, and my crappy non smartass implementation was FASTER than the standard library... why?

Well it was obvious: Having to comply with the sort.Interface was the problem, it is much faster to compare by just doing list[i]<list[j] than doing list.Less(i,j) and swapping list[i],list[j]=list[j],list[i] instead of calling list.Swap(i,j)

I rewrote my in-place mergesort to use sort.Interface instead and then it was MUCH worse than the Go standard implementation, just as expected.

So, as a summary, due to the lack of "a generic like solution" right now some parts of the Go standard library might be less performant than they could be, even though the algorithms they use are solid, cause it's TOO much work to repeat yourself for each and every primitive type and make it an ah-hoc solution for those.

Back to my question.

I guess the problem with my suggestion would be when pulling a snippet from a imported package pulls in turn snippets form other packages NOT imported directly by the compiling package/program. Go fast compiling times are based on the fact that it just needs to know about the directly imported packages instead of recompiling everything at that moment.

Is that right?

Is that all or I am missing something else?

Jose

[josvazg]

Here you have the tests about the performance of sort that I was talking about:

https://github.com/josvazg/algorithms

In the sorting folder when running with go run *.go I get on my machine:

mergesort sorted 100000 times in 2.193734s

swap mergesort sorted 100000 times in 1.156584s

quicksort sorted 100000 times in 925.247ms

heapsort sorted 100000 times in 1.189657s

sort.Ints sorted 100000 times in 750.536ms

native in-place mergesort sorted 100000 times in 432.433ms

native quicksort sorted 100000 times in 429.791ms

native heapsort sorted 100000 times in 531.219ms

The native implementations are just like the non native ones BUT NOT using the sort.Interface.

I haven't tested it but if I copy the Go standard package sort.Int and rewrite to be "native" we could probably get 400ms or less cause it is clearly a much efficient algorithm that mines (as expected) but it is made slower by the use of an interface.

Another interesting case is strings, we could probably gain there as well as it might be faster to do inline list[i]<list[j] AND list[i],list[j]=list[j],list[i] than calling the interface.

For the rest of the types (non primitives), the sort.Interface performance is probably as good as it gets, so no need to make them native.

[Ian Lance Taylor]

josvazg <jos...@gmail.com> writes:

> So, as a summary, due to the lack of "a generic like solution" right now
> some parts of the Go standard library might be less performant than they
> could be, even though the algorithms they use are solid, cause it's TOO
> much work to repeat yourself for each and every primitive type and make it
> an ah-hoc solution for those.

I think it's important to realize that there are different ways to
implement generics. In order to be able to use generics to make the
standard library much faster at runtime, you need to use an
implementation along the lines of C++ templates, in which each function
that uses a generic type is in effect rewritten to use that type and
then recompiled. This approach means that compilation slows down.

A different approach would be to, in effect, use the reflection
interface in the generic code. That would give you the programming
convenience, and keep the fast compilation times, without any large
runtime benefit. This approach is closer to (although certainly not the
same as) the way that C# or Java implement generics.

Or, in other words, http://research.swtch.com/generic .

Ian

[Joubin Houshyar]

On Apr 26, 11:03 am, Ian Lance Taylor <i...@google.com> wrote:

Java generics are a compile time mechanism and bounded by the
compilation unit. It simply uses type erasure. Generic info is
retained in the class files but the runtime doesn't reify them and
they are not covariant. This is precisely the reason why programmers
have difficulty reasoning about generic types beyond the basics of
containers, etc.

http://docs.oracle.com/javase/specs/jls/se5.0/html/typesValues.html#4.6

example:
https://gist.github.com/2500494

Note that in Java's case, the above (unfortunate) decision was due to
extant legacy code. So basically if there is a lesson to take away
from Java it is: //don't wait too long to finally make a decision.//


>
> Or, in other words,http://research.swtch.com/generic.
>
> Ian

[Glenn Brown]

Go's Sort() is also top of my (very short!) list of things to dislike about Go.

Generics are not the only option for addressing the performance and inconvenient interface of Sort, or addressing the broader problem of creating general purpose containers.

For example, one could allow a special type '_' in interface declarations to mean "the same type as the method's receiver" and then declare interfaces like this:
type Lesser interface {
Less(_) bool
}
Then one can conveniently write general-purpose containers that hold Lessers, such as priority queues, trees, etc., using 'a.Less(b)' for comparison. Compiled Less methods such as
(a int) Less(b int) bool {
return a < b
}
would satisfy the Lesser interface and include no internal type assertions. When 'a.Less(b)' is called, the compiler would ensure that 'a' and 'b' have the same underlying type, requiring a runtime check in some cases. Sort performance should be comparable to C's qsort(), though not as fast as with C++ templates. Compilation would not suffer significant overhead.

Most of Haskell's famous "type classes" can be simulated with this approach:
type Eq interface { Equals(_) bool }
type Ord interface { Less(_) bool }
type Show interface { String() string }
type Enum interface { Pred() _; Succ() _ }
type Bounded interface { MaxBound() _; MinBound() _ }
type Num interface { Add(_)_;Sub(_)_;Div(_)_;Mul(_)_;... }
So, the '_' type would enable lots of generic programming approaches that are not currently convenient in Go.

--Glenn

[Erwin]

I think it's important to realize that there are different ways to
implement generics.  In order to be able to use generics to make the
standard library much faster at runtime, you need to use an
implementation along the lines of C++ templates, in which each function
that uses a generic type is in effect rewritten to use that type and
then recompiled.  This approach means that compilation slows down.

I don't quite get this argument of the 'slow' compilation. When the programmer wants the best performance, he or she needs to implement the specialized functions as well, so in effect, the final amount of code remains the same. no? Or would the rewriting of the generic code be such a bottleneck for the compiler? I can hardly imagine that. 

[bugpowder]

I was about to write exactly that.

The compiler wouldn't add/compile any more code than what the programmer will be forced to add manually anyway.

[Ian Lance Taylor]

On Thu, Apr 26, 2012 at 11:31 AM, Erwin <snes...@gmail.com> wrote:
>>
>> I think it's important to realize that there are different ways to
>> implement generics.  In order to be able to use generics to make the
>> standard library much faster at runtime, you need to use an
>> implementation along the lines of C++ templates, in which each function
>> that uses a generic type is in effect rewritten to use that type and
>> then recompiled.  This approach means that compilation slows down.
>
>

> I don't quite get this argument of the 'slow' compilation. When thet

> programmer wants the best performance, he or she needs to implement the
> specialized functions as well, so in effect, the final amount of code
> remains the same. no? Or would the rewriting of the generic code be such a
> bottleneck for the compiler? I can hardly imagine that.

If we rewrite the sort package to use generics, then everybody using the sort
package gets the slower compilation, even if they don't care about performance.
In other words, adding generics to packages slows down compilation for
everybody,
even people who would prefer fast compilation to fast runtime performance.

Rewriting the generic code is not a bottleneck, but compiling the generic code
multiple times is. Also the question arises of when the code is
compiled; if done
at compile time, as most C++ compilers do, then if two different
packages want to
sort ints, the compiler has to compile the sort<int> code twice.

These issues may seem minor, but remember that fast compilation is a major
goal of the Go project, and that we want Go to be fast even when building large
projects. One of the reasons C++ does not have fast compilation
is that the standard library is heavily templatized and the classes are compiled
many times when building a large project.

Ian

[Peter Bourgon]

> Rewriting the generic code is not a bottleneck, but compiling the generic code
> multiple times is.  Also the question arises of when the code is
> compiled; if done
> at compile time, as most C++ compilers do, then if two different
> packages want to
> sort ints, the compiler has to compile the sort<int> code twice.

If there were a C++-style, compile-time generics proposal for Go,
which somehow managed to abide "compile only once per concrete type"
semantics, would that be a "winner" from your perspective?

[josvazg]

"Rewriting the generic code is not a bottleneck, but compiling the generic code 
multiple times is.  Also the question arises of when the code is 
compiled; if done 
at compile time, as most C++ compilers do, then if two different 
packages want to 
sort ints, the compiler has to compile the sort<int> code twice. "

Why should be sort<int> compiled more than once?

When compiling the first time you cache it, the object is available somewhere (as a .a static library or the go compiler produced equivalent) to be linked by the other packages that need sort<int>.

In fact it should be like a package appendix. For instance, lets say packages sort, sortuser and the main.

1) sort is compiled, the non generic part produces a sort.a

2) sortuser expands sort<int> so it produces sortuser.a and sort_int.a

3) main uses sort<string> and sort<int> and so it produces main.a, sort_string.a BUT sort_int.a is already available.

At link phase the program is composed of sort.a, sort_int.a (once), sort_string.a, sortuser.a and main.a

Why would it had to be different?

Jose

[Kyle Lemons]

On Thu, Apr 26, 2012 at 2:05 PM, josvazg <jos...@gmail.com> wrote:

"Rewriting the generic code is not a bottleneck, but compiling the generic code 
multiple times is.  Also the question arises of when the code is 
compiled; if done 
at compile time, as most C++ compilers do, then if two different 
packages want to 
sort ints, the compiler has to compile the sort<int> code twice. "

Why should be sort<int> compiled more than once?

If you define sort<T> in a package "sort" and package "heap" uses it, then heap.a either needs to keep the code around or it has to be compiled into it.  Now, if you use it in your code and then include heap, you've got two instances of the compiled library that are duplicates.

 

When compiling the first time you cache it, the object is available somewhere (as a .a static library or the go compiler produced equivalent) to be linked by the other packages that need sort<int>.

In fact it should be like a package appendix. For instance, lets say packages sort, sortuser and the main.

1) sort is compiled, the non generic part produces a sort.a

2) sortuser expands sort<int> so it produces sortuser.a and sort_int.a

But what if you have more than one generic thing in sort?  How do you sort a sort<int> or a sort<sort<int>>?

 

3) main uses sort<string> and sort<int> and so it produces main.a, sort_string.a BUT sort_int.a is already available.

At link phase the program is composed of sort.a, sort_int.a (once), sort_string.a, sortuser.a and main.a

Why would it had to be different?

It's not an easy problem.

[josvazg]

Thanks for the explanation, Kyle

Maybe it would make sense to forbid "recursive generics" instead of generics altogether?

(Recursive generics look awful anyway)

All other generic usages can be separated one expansion into one .a at a time, can't they?

Jose

[Glenn Brown]

> If we rewrite the sort package to use generics, then everybody using the sort
> package gets the slower compilation, even if they don't care about performance.

While this is true of C++ generics, it need not be true for Go if one thinks outside the box. Here's what I mean:

Assume C++-style generics were added to the Go grammar, but the compiler completely ignored the '<<T>>' annotations. The compiler would generate the same output as it currently does, in the same time (plus epsilon).
Lessons learned:
Go's code is already generic in the sense that container/list can handle any type, albeit slowly.
Dumb compilers can ignore generics.
It's not the grammar of Generics that significantly slows the compiler.

Now add Generics to the type system, but don't recompile-per-type. This doesn't dramatically slow compilation, but it gives type-safe container classes: There is no need for a type assertion when removing an int from a "List of ints", and the compiler can verify type-safety within the generic code at compile-time.
Lessons learned:
Even without recompilation-per-type, generics have advantages:
More type details can be checked at compile-time.
Run-time type assertions can be eliminated.

Now assume Go is compiled to run on a VM, and that the Generic type information is available to the VM. User-compilation speed is not slowed, but now the VM has the information it needs to recompile hotspot code at runtime. Hotspot compilation can actually create FASTER programs than static compilation since it can inline functions across modules, producing surprising performance. For example, Javascript V8 is 4x faster than C++ and 30x faster than Go on the regexdna benchmark. See also
http://wingolog.org/archives/2011/06/10/v8-is-faster-than-gcc.
Lessons learned:
Not all compilation need be at "compile time".
Compile+Run time is important, too.
Go+generics+hotspot would compile about as fast as Go.
Go+generics+hotspot could run faster than C++ for some programs.

Don't fall into the trap of adding generics implies slow compilation, or requires a complicated compiler.

--Glenn

P.S.: I blogged on some of this before at http://gosailthec.blogspot.com/2011/11/go-generics-in-3-parts.html

[kortschak]

I think I understand the motivation that the Go team has for fast compilation - correct me if I'm wrong - that fast compilation is an aid and comfort during development.

However, slow compilation with a resultant gain in execution time seems like a benefit if T(compilation) < nT(run), this trade off starts to benefit slow compilation with fast running code when the number of times code is compiled reduces relative to the total amount of time the code is actually running for.

So, is there a possibility (I understand that this makes the project much more complex) for two modes of compilation, a development mode where compilation is rapid, but code is not so good and a production mode where compilation time may be nearly awful, but code is excellent.

It seems to me that Russ's three options, when viewed dogmatically, are a real problem, but if use context is taken into account then it actually may give guidance about what to do.

This is probably a simplistic view, but is there some way that something like this could be achieved and would it be worth it?

Dan

On Friday, April 27, 2012 5:05:05 AM UTC+9:30, Ian Lance Taylor wrote:

[Paul Borman]

That is why there is gccgo, to improve execution time.  Use the fast tools to develop and the slow tools to make the production version.

    -Paul

[Dan Kortschak]

Yeah, I was including that in my thinking, but was wondering if that
notion could be extended further.

thanks
Dan

[Michael Jones]

I would be more than happy to have an "expand" phase that applies rewrites.

--

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

[Paulo Pinto]

.NET generics are a halfway solution between C++ and JVM way.

Generic code that make use of value types is generated for each
set of types, the same way as C++ does.

Generic code that makes use of references, makes use of a generic
pointer.

http://blogs.msdn.com/b/csharpfaq/archive/2004/03/12/how-do-c-generics-compare-to-c-templates.aspx

--
Paulo

On Apr 26, 5:03 pm, Ian Lance Taylor <i...@google.com> wrote:

[Ian Lance Taylor]

Peter Bourgon <pe...@bourgon.org> writes:

>> Rewriting the generic code is not a bottleneck, but compiling the generic code
>> multiple times is.  Also the question arises of when the code is
>> compiled; if done
>> at compile time, as most C++ compilers do, then if two different
>> packages want to
>> sort ints, the compiler has to compile the sort<int> code twice.
>
> If there were a C++-style, compile-time generics proposal for Go,
> which somehow managed to abide "compile only once per concrete type"
> semantics, would that be a "winner" from your perspective?

It's hard to answer that sort of question. The exact details matter.

And of course I should add that now that Go 1 has been released we are
not going to change the language for some time even if we had a perfect
proposal.

Ian

[Ian Lance Taylor]

josvazg <jos...@gmail.com> writes:

> Maybe it would make sense to forbid "recursive generics" instead of
> generics altogether?
> (Recursive generics look awful anyway)

We absolutely want to be able to have a list of list of int.

Ian

[Ian Lance Taylor]

Glenn Brown <tornad...@gmail.com> writes:

> Assume C++-style generics were added to the Go grammar, but the
> compiler completely ignored the '<<T>>' annotations.

I guess I'm not sure what that means.

> Now add Generics to the type system, but don't recompile-per-type.

This is not as easy in Go as it is in some languages, because types in
Go are not all the same size. E.g., since we've been talking about
sort, sort on []int8 is a different operation from sort on []float64,
not just because you need to use different comparison routines, but
because you need to use different indexing operations.

Ian

[josvazg]

You are right, of course.

And replying to my own earlier comment:

"All other generic usages can be separated one expansion into one .a at a time, can't they?"

I guess they can't, cause when you use a package you get it all, you can't pick to get ONLY what you really use of it. 

That means that, for a big project linking with many packages that use generic expansions will pull ALL the generic expansions on imported packages even if they are not used by the final program.

And this will have no solution that DOESN'T make the compiler slower because making the packages to be able to subdivide themselves into actual used and unused parts also costs time and means recursion.

[cmjohnson....@gmail.com]

On Thursday, April 26, 2012 7:49:18 AM UTC-10, Glenn Brown wrote:

 

For example, one could allow a special type '_' in interface declarations to mean "the same type as the method's receiver" and then declare interfaces like this:
        type Lesser interface {
                Less(_) bool
        } 

That looks like the sweetspot 80-20 solution to me. It lets you do performant container types without getting into the C++ brain busting meta-programming. The fact is almost all of what people want generic programming for can be done at runtime using reflection. So, the real question is how much syntactic support should be added to make common tasks easier and where we can get performance wins without sacrificing compile time. Getting rid of int --> interface{} --> int does it for me.

[Glenn Brown]

>> Assume C++-style generics were added to the Go grammar, but the
>> compiler completely ignored the '<<T>>' annotations.
>
> I guess I'm not sure what that means.

Here's a concrete example I used at http://gosailthec.blogspot.com/ , where '~Int' means 'of Int' and 'default T interface{}' means 'T defaults to interface, but may be any type implementing that interface.' It is a generic version of 'List'.

default T interface{}
type Element~T struct {
next, prev *Element~T
list *List~T
Value T
}
type List~T struct {
front, back *Element~T
len int
}
func (l *List~T) Init() *List~T {
l.front = nil
l.back = nil
l.len = 0
return l
}
func New() *List~T {
return new(List~T)
}
...
func (l *List~T) PushFront(value T) *Element~T {
e := &Element~T{nil, nil, l, value}
l.insertFront(e)
return e
}
...

In that example, if you replace 'default' with 'type' and remove all the '~T' annotations, then you effectively return to the original container/list code, which can hold any type. The code already works for all T that satisfy interface{}. In this sense, the Go container is already generic and can be used for all T. Adding the "~T" annotations (or "~(T1,T2,…)" in general) simply provides additional type checking information, so the compiler can enforce type-preservation within the compilation unit, can verify that callers insert consistent types, and can know that consistent types are returned.

Other than this additional type checking, the compiler is free to ignore the '~' annotations and emit code for 'type T interface{}'. This is what the current Go compilers do, and it generic enough for the first pass at compilation.

>> Now add Generics to the type system, but don't recompile-per-type.
>
> This is not as easy in Go as it is in some languages, because types in
> Go are not all the same size. E.g., since we've been talking about
> sort, sort on []int8 is a different operation from sort on []float64,
> not just because you need to use different comparison routines, but
> because you need to use different indexing operations.

Yes, I've been focusing so much on non-array containers that I have neglected this issue when thinking about array sorting, and would need something like
type Array interface {
Get (index int) interface{}
Put (index int, interface{})
}
to use a.Less(b) for comparison in array sorting. Not good.

But please note that the 'Less(a,b int) bool' approach used by sort does not generalize to containers that don't use ordinal addressing, such as priority queues, trees, skip-lists, graphs… For these, it is more natural to use 'interface { Less(other interface) bool }' described by others or the 'interface { Less(_) bool }' approach described elsewhere in this thread and the blog.

Thank you for your feedback,
--Glenn

[egon]

I've been thinking that generics could be also implemented by specializing on interfaces.

For example:

type Comparable interface{ Less(Comparable) bool }

func Min(a Comparable, b Comparable) c Comparable {

if a.Less(b){

return a

}

return b

}

Min`{Comparable int}(3,4)

// which would be same as implementing function Min with all Comparable-s replaced with int.

// of course you would need to be able to say:

MinInt := Min`{Comparable int}

// or maybe?

func MinInt Min`{Comparable int}

generic compose function

type T interface{}

func Compose(a func(T)T, b func(T)T) func(T)T {

return func(x T)R{ return b(a(x)) }

}

Compose`{T int}

// this idea could easily work with structs (or maybe even packages):

type N interface{

Compare(b N) int

}

type BinaryTree struct{

Left *BinaryTree

Right *BinaryTree

Value N

}

type MyValue struct { V int }

type MyTree struct {

  tree BinaryTree`{N MyValue}

  // alternatively BinaryTree`{N MyValue, BinaryTree MyTree}

}

// essentially says that N should be replaced with MyValue and BinaryTree with MyTree

// also all methods declared on BinaryTree would need to be interface specialized as well

This seems to make sense because you first need to implement everything so that it works on a specific interface and then specialize. So if your code works with general interfaces it must therefore work with specialized types. Also this seems to fit nicely with interfaces.

- egon

On Monday, November 21, 2011 11:44:39 PM UTC+2, Miki Tebeka wrote:

Greetings,

Maybe we don't need generics. Maybe the solution is enhancing interfaces to
cover basic types.

This idea came to me while going over http://learnyouahaskell.com. There if you
want to have a generic "max" function, it takes "Ord" typeclass (interface). If
we'll have Go numbers also implement "Ord" interface then a generic "max" will
be easy to write.

What are your thoughts on this?

Thanks,
--
Miki

[Ian Lance Taylor]

Glenn Brown <tornad...@gmail.com> writes:

> In that example, if you replace 'default' with 'type' and remove all
> the '~T' annotations, then you effectively return to the original
> container/list code, which can hold any type. The code already works
> for all T that satisfy interface{}. In this sense, the Go container
> is already generic and can be used for all T. Adding the "~T"
> annotations (or "~(T1,T2,…)" in general) simply provides additional
> type checking information, so the compiler can enforce
> type-preservation within the compilation unit, can verify that callers
> insert consistent types, and can know that consistent types are
> returned.
>
> Other than this additional type checking, the compiler is free to
> ignore the '~' annotations and emit code for 'type T interface{}'.
> This is what the current Go compilers do, and it generic enough for
> the first pass at compilation.

Thanks for the explanation. To me that approach sounds very much like
Java's type erasure approach. I think that approach has a serious
problem: when I pass List~int to a function that takes interface{}, I've
lose the type information. There is nothing preventing me from doing a
type assertion to List~float64; I do get the runtime checks when I try
to pull the values out, but I don't know the type of the container.

Ian

[Glenn Brown]

> Thanks for the explanation. To me that approach sounds very much like
> Java's type erasure approach. I think that approach has a serious
> problem: when I pass List~int to a function that takes interface{}, I've
> lose the type information. There is nothing preventing me from doing a
> type assertion to List~float64; I do get the runtime checks when I try
> to pull the values out, but I don't know the type of the container.
>
> Ian

Thanks for the feedback.

I'm afraid I don't understand how this problem is specific to the '~T' approach: when you pass *anything* to func(interface{}) you lose the type information, except that you can recover it through reflection/inference plus type assertions. What are you hoping would be handled better?

Ironically, my main motivation for thinking about ~T and the '_' type was annoyance at containers based on interface{} discarding type information! If there is anywhere type information can be preserved without recompilation, it is for containers.

--Glenn

[Kyle Lemons]

On Fri, Apr 27, 2012 at 10:40 AM, Glenn Brown <tornad...@gmail.com> wrote:

> Thanks for the explanation.  To me that approach sounds very much like
> Java's type erasure approach.  I think that approach has a serious
> problem: when I pass List~int to a function that takes interface{}, I've
> lose the type information.  There is nothing preventing me from doing a
> type assertion to List~float64; I do get the runtime checks when I try
> to pull the values out, but I don't know the type of the container.
>
> Ian

Thanks for the feedback.

I'm afraid I don't understand how this problem is specific to the '~T' approach: when you pass *anything* to func(interface{}) you lose the type information, except that you can recover it through reflection/inference plus type assertions.  What are you hoping would be handled better?

One thing that's nice about a []int is that you can type assert to it.  If you have a List<int> and pass it to an interface{}, with type erasure it is simply a List at runtime and you cannot, for instance, distinguish easily between what used to be a List<int> and List<string>.

[Glenn Brown]

On Apr 27, 2012, at 11:06 AM, Kyle Lemons wrote:

One thing that's nice about a []int is that you can type assert to it.  If you have a List<int> and pass it to an interface{}, with type erasure it is simply a List at runtime and you cannot, for instance, distinguish easily between what used to be a List<int> and List<string>.

But you can!  An interface is a pair of pointers, one for data and one for metadata.  The runtime simply needs a different metadata pointer for each constructed type.  Then, List<int> and List<string> are distinct types.  In other words, just because one doesn't use C++ code recompilation doesn't mean one can't have distinct types that use the same machine instructions behind the scenes, but different metadata.

--Glenn

[Kyle Lemons]

Isn't that contrary to the purpose of type erasure?  And they can't have the same instructions if it's type List~T []T.

[Glenn Brown]

> Isn't that contrary to the purpose of type erasure?

I never intended type erasure: I intend type preservation.

> And they can't have the same instructions if it's type List~T []T.

Do you mean "And they can't have the same instructions if it's type List~T versus List~([]T)"? The latter is illegal, since T must be an interface type. The closest you could get to List~([]T) would be List~(Slice~T) where Slice is a generic interface.

I should write 'List~I' and 'generic interfaces' to avoid this confusion in the future.

Thanks for the feedback,
--Glenn

P.S.: Man it's hard to escape C++'s mental baggage!

[Glenn Brown]

> The latter is illegal, since T must be an interface type. The closest you could get to List~([]T) would be List~(Slice~T) where Slice is a generic interface.
>
> I should write 'List~I' and 'generic interfaces' to avoid this confusion in the future.

I just wrote that, but it's not right. At all. Total brain fart. It's only the 'default T ...' line that must be an interface. Sorry for the confusion.

I want to mediate on List~([]T) for a bit before commenting further, since I don't see how its any different from List~char for type recovery. Either I'm missing something, or I'm not communicating my perspective well enough.

Thanks,
--Glenn

[Kyle Lemons]

On Fri, Apr 27, 2012 at 11:51 AM, Glenn Brown <tornad...@gmail.com> wrote:

> Isn't that contrary to the purpose of type erasure?

I never intended type erasure: I intend type preservation.

Having the compiler know about types to do type checking and not do the type checking at runtime is type erasure.

 

> And they can't have the same instructions if it's type List~T []T.

Do you mean "And they can't have the same instructions if it's type List~T versus List~([]T)"?  The latter is illegal, since T must be an interface type.  The closest you could get to List~([]T) would be List~(Slice~T) where Slice is a generic interface.

No, I mean making a List~T []T that specializes List~int to []int.  But it sounds like you want List~int to actually always be a []interface{}, with an implied .(int) for every access.  If that's the case, then my objection is to the runtime performance, particularly the extra overhead you're introducing to EVERY type assertion because it now has to handle type aliasing :).  Either way though, you're adding a lot of complexity by somehow having multiple vtable pointers all really mean the same underlying []interface{}.

[Glenn Brown]

> No, I mean making a List~T []T that specializes List~int to []int. But it sounds like you want List~int to actually always be a []interface{}, with an implied .(int) for every access. If that's the case, then my objection is to the runtime performance, particularly the extra overhead you're introducing to EVERY type assertion because it now has to handle type aliasing :). Either way though, you're adding a lot of complexity by somehow having multiple vtable pointers all really mean the same underlying []interface{}.

If your main objection is 'it runs too slow', note that nothing in the grammar precludes C++-like template recompilation, and nothing in the grammar precludes fast compiles. In theory, one could use fast compiles for interactive development and recompilation for offline automated testing and production.

Correct me if I'm wrong, but it sounds like when you say "List~T []T" you are talking about a new List class (lets call it "Slice" to be clear). Something like

package slice
default T interface{}
type Slice~T []T
func (s Slice~T) Set (index int, value T) {
s[index] = value
}
func (s Slice~T) Get (index int) T {
return s[index]
}
func (s Slice~T) Append (a T) Slice~T {
return s.append(a)
}
func (s Slice~T) Reslice (a, b int) Slice~T {
return s[a:b]
}

That code has no type assertions, since the emitted instructions behave the same as the following, which has no type assertion. (It's the same code without type annotation.)

package slice
type Slice []interface{}
func (s Slice) Set (index int, value interface{}) {
s[index] = value
}
func (s Slice) Get (index int) interface{} {
return s[index]
}
func (s Slice) Append (a interface{}) Slice {
return s.append(a)
}
func (s Slice) Range (a, b int) Slice {
return s[a:b]
}

As for the caller-side having type assertions, and if you meant "type Slice~T []T" then this simple main() can illustrate what happens:

package main
import (
"fmt"
"slice"
)
func main () {
var s Slice~int // 1
s = s.append(0) // 2
s.Set(0,1) // 3
fmt.Println (s.Get(0)) // 4
fmt.Println (s) // 5
}

Then from the Caller's point of view,
(1) creates a slice of interface objects (in the absence of recompilation) which is bigger than we'd like.
(2) constructs and passes in a interface object pointing to int{0}.
(3) constructs and passes in a interface object pointing to int{1}.
(4) returns int{1} as an interface object, but skips the type assertion, because the compiler knows the data pointer of the returned interface object points to an int.
(5) The array of interface objects is passed in by value.

Yes, 1-4 can be considered to be a form of type assertions, in that they add or remove an interface object, but type safety ensures no runtime checking is required.
Yes, the resulting program does not run as fast as if recompilation were used.

But, type annotation allows compile-time type checking, runs a bit faster that the current Go approach by eliminating runtime type checks and eliminates the possibility of runtime type assertion failure, and it doesn't have the slow-compile and application bloat problems of C++ templates, and it maintains type information for runtime hotspot recompilation.

I agree that generics bring complexity. I don't see how it brings any more complexity than currently exists in Java. In fact, as I understand it, the type annotation eliminates much of the speculative type inference hacks necessary in Java hotspot compilers. (There's a Google tech talk by Azure Systems on that.) Heck, if executables included the AST for the generic class, a hotspot compiler's jobs is much simplified, though boxing and unboxing is still a major pain at runtime.

Thanks again to all who are helping with this brainstorm,
--Glenn

[tim.mas...@gmail.com]

On Thursday, April 26, 2012 4:03:47 PM UTC+1, Ian Lance Taylor wrote:

josvazg <jos...@gmail.com> writes:

> So, as a summary, due to the lack of "a generic like solution" right now
> some parts of the Go standard library might be less performant than they
> could be, even though the algorithms they use are solid, cause it's TOO
> much work to repeat yourself for each and every primitive type and make it
> an ah-hoc solution for those.

I think it's important to realize that there are different ways to
implement generics.  In order to be able to use generics to make the
standard library much faster at runtime, you need to use an
implementation along the lines of C++ templates, in which each function
that uses a generic type is in effect rewritten to use that type and
then recompiled.  This approach means that compilation slows down.

A different approach would be to, in effect, use the reflection
interface in the generic code.  That would give you the programming
convenience, and keep the fast compilation times, without any large
runtime benefit.  This approach is closer to (although certainly not the
same as) the way that C# or Java implement generics.

Or, in other words, http://research.swtch.com/generic .

Is there any reason why the choice between the options outlined can't be made at compile time by the programmer? If one wants quick compiles but slower, less bloated code, the compiler could produce code using reflection; if one wants quick code, a final binary to be distributed for example, then a compile switch could enable aggressive specialisation.

[Florian Weimer]

> Why should be sort<int> compiled more than once?

Most C++ compilers lack a project-wide view and work on one
translation unit at a time. GCC used to have -frepo, but it in the
end, it was deemed to over-compile, rather to somehow get a
project-wide view.

There's also the question whether two sort<int>s in different
translation units are really the same because of different #includes,
#defines and definitions affecting argument-dependent lookup. At
least that wouldn't be an issue with Go.

[JONNALAGADDA Srinivas]

On Saturday, 28 April 2012 06:19:39 UTC+5:30, Glenn Brown wrote:

Heck, if executables included the AST for the generic class, a hotspot compiler's jobs is much simplified, though boxing and unboxing is still a major pain at runtime. 

        I have an old (``work in progress") proposal that takes the said AST approach, but without a need for boxing and unboxing.  Please see http://oneofmanyworlds.blogspot.in/2011/11/draft-2-of-proposal-for-generics-in-go.html for more details.

                                                            Greetings,

                                                                    JS

____

http://oneofmanyworlds.blogspot.com 

[Andy Balholm]

What if generics had to be explicitly instantiated? In other words, a generic type declared like generic type Vector<T> []T could not be used in a variable declaration, only to define a concrete type like this: concrete type intVector Vector<int> 

Then the generic type would be compiled exactly once for each concrete type derived from it. 

The same would apply to functions:

generic func Sort<T>(data []T) {

    // TODO: replace the bubble sort with something faster!

    done := false

    for !done {

        done = true

        for i := range data {

            if i > 0 && data[i-1] > data[i] {

                data[i-1], data[i] = data[i], data[i-1]

                done = false

            }

        }

    }

}

concrete func sortInts Sort<int>

[Ian Lance Taylor]

Andy Balholm <andyb...@gmail.com> writes:

> What if generics had to be explicitly instantiated? In other words, a
> generic type declared like generic type Vector<T> []T could not be used in
> a variable declaration, only to define a concrete type like this: concrete
> type intVector Vector<int>
>
> Then the generic type would be compiled exactly once for each concrete type
> derived from it.

I guess I don't see how. Two different packages might say

concrete func sortInts Sort<int>

When does that concrete function get compiled?

Ian

[Andy Balholm]

On Tuesday, May 1, 2012 9:27:01 AM UTC-7, Ian Lance Taylor wrote:

I guess I don't see how.  Two different packages might say

concrete func sortInts Sort<int>

When does that concrete function get compiled?

There are two concrete functions, pkgA.sortInts and pkgB.sortInts. One gets compiled when each package is compiled. We would still have a certain amount of the slow compile/bloated binary problem (but less than the C++ way where, at least in theory, the template gets expanded every time it is used). But if someone wanted to make only one copy, he could put it in pkgC and import it into pkgA and pkgB. 

Also, pkgA.intVector and pkgB.intVector would be two separate types. To assign one to the other would require an explicit conversion. (Just as if both packages had contained type intVector []int) The only real advantage of generics over []int in this case would be that the intVector types would get the methods that were defined on Vector.

Perhaps a more general proposal would actually be clearer. My generalized idea is a type-safe, scope-safe macro system where the macros could only be used as top-level declarations. 

macro Sort(type T, func less) {

    func Sort(data []T) {

        done := false

        for !done {

            done = true

            for i := range data {

                if i > 0 && less(data[i], data[i-1]) {

                    data[i-1], data[i] = data[i], data[i-1]
                    done = false
                }

            }

        } 

    }

}

func lessInt(x, y int) bool {

    return x < y

}

usemacro sortInts Sort(int, lessInt)

macro Vector(type T) {

    type Vector []T

    func (v *Vector) Append(items ...T) {

        v = append(v, items...)

    }

    func (v *Vector) Delete(i int) {

       v = append(v[:i], v[i+1:]...)

    }

}

usemacro intVector Vector(int)

The macro parameters would be identifiers (potentially qualified by package name). The macro definition would specify whether they refer to constants, variables, types, or functions, but further type checking would wait until the macro is used. When the macro is used, the parameters would effectively be substituted into the macro text, except that they would be resolved using the scope of the package where the macro is used and all other identifiers would be resolved using the scope of the package where the macro was declared. The macro would export only one identifier: the name in the usemacro statement would refer to the item declared with the same name as the macro (i.e. the type defined by the last usemacro statement in my example would be intVector). If the macro declared any other identifiers, they would be mangled to avoid polluting the namespace or colliding with other uses of the macro.

[Robert Johnstone]

Doesn't the go tool already do this?  If I import a package that needs to be rebuilt, the go tool arranges for that package to be rebuilt.  Building a specialized Sort<int> doesn't fundamentally change this.  I don't see how the performance will be any worse than any other package import.

If you want finer control of the instantiation of generic functions, then the function will have to be compiled with each package, and then have redundant versions eliminated at link time.  This will have a performance impact, but will only be paid by packages that make use of generics.  Presumably they would need to compile non-DRY non-generic functions in any case.

I haven't yet seen a proposal for generics that I believe is worth adding to Go (including my own), but I don't see arranging for instantiation as a road block.

[josvazg]

Ok,

But generics aside.

Imagine we had the standard sort package as it is now, allowing us to sort any type implementing the sort.Interface with a very efficient mixture of quicksort/heapsort and insertsort algorithms.

BUT imagine we ALSO had a subpackage at sort for each primitive type NOT USING the sort.Interface:

sort/ints

sort/floats

sort/strings

...

Each package has the same efficient implementation for sorting (quicksort+heapsort+insert) BUT it does INLINE comparisons and swaps instead of calling sort.Interface.

I timed this raw/native implementations to be more than 2x times faster than the same sort but using sort.Interface (for int, and a little less that 2x for string) [https://github.com/josvazg/algorithms/tree/master/sorting]

What would be the price/penalty in this case (if any)?

I see none: Only when you need a sort for primitive type X will you import sort/X, and only in that case the package will be linked within the program and the package will only add that specialized code once, Right?

I think this was not done because 2x performance was considered not worth against the tedious, repetitive (and error prone) manual expansion of the same algorithm for N primitive types just changing the primitive type spec everytime it is mentioned.

Or is there any problem this specialized packages would create that is more important to avoid than getting twice the performance?

Jose

On Thursday, April 26, 2012 5:03:47 PM UTC+2, Ian Lance Taylor wrote:

josvazg <jos...@gmail.com> writes:

> So, as a summary, due to the lack of "a generic like solution" right now
> some parts of the Go standard library might be less performant than they
> could be, even though the algorithms they use are solid, cause it's TOO
> much work to repeat yourself for each and every primitive type and make it
> an ah-hoc solution for those.

I think it's important to realize that there are different ways to
implement generics.  In order to be able to use generics to make the
standard library much faster at runtime, you need to use an
implementation along the lines of C++ templates, in which each function
that uses a generic type is in effect rewritten to use that type and
then recompiled.  This approach means that compilation slows down.

A different approach would be to, in effect, use the reflection
interface in the generic code.  That would give you the programming
convenience, and keep the fast compilation times, without any large
runtime benefit.  This approach is closer to (although certainly not the
same as) the way that C# or Java implement generics.

Or, in other words, http://research.swtch.com/generic .

Ian

[Glenn Brown]

the generic type would be compiled exactly once for each concrete type derived from it. 

I'm starting to think this is a good idea, if taken a couple steps further: only recompile when T is not an interface type.

That is: avoid the recompilation when there is no downside to doing so.  (Use "type erasure" only when it's not problematic.)

For example, one could modify your example as follows:

default T interface { Less(_) bool }

func Sort(data []T) {

…

if i > 0 && data[i].Less(data[i-1]) {

...

}

The 'generic' keyword is dropped, because it is implicit.

The 'default' line is added to specify the minimum interface required by any interface T.

The '<T>' is dropped because it is redundant and sometimes doesn't play well with gofmt + semicolon insertion.

The '_' (receiver type matching) is necessary to provide a generic interface to binary operators.

Then, compiling

Sort([]int{})

or

Sort([]char{})

would imply a dynamic recompilation for types "[]int" and "[]char" BUT

Sort([]interface{…}{})

could use the default interfaced-based compilation for all interfaces.

I don't worry that 

data[i].Less(data[i-1])

is slower than

data[i] < data[i-1]

for built-in types because I assume Go will eventually support automatic inlining of small methods like

func (a int) Less (b int) bool { return a < b }

, and I assume such methods will be built into the Go runtime to implement a small number of interfaces equivalent to Haskell's type classes

(See http://learnyouahaskell.com/types-and-typeclasses#typeclasses-101 ) which have proven to be broadly applicable.

With this approach, I think it is possible to avoid much recompilation, generalize generics to interfaces, and have an optimally efficient Sort.

--Glenn

[egon]

I've suggested similar approach before, but I think let's just go one step further. Let's get rid of the "<>" notation.

If we just regard interfaces as things that can be specialized (made concrete) if the type implements that interface.

type T interface{

    Less(T) bool

}

func Sort(data []T) {

    // TODO: replace the bubble sort with something faster!

    done := false

    for !done {

        done = true

        for i := range data {

            if i > 0 && data[i].Less(data[i-1]) {

                data[i-1], data[i] = data[i], data[i-1]

                done = false

            }

        }

    }

}

Then this would automatically implement a generic, and also it has the benefit of working with both an interface and a concrete type. Also anything that implements an interface becomes a generic type/func. Essentially if your code uses interfaces and works on some specific interface it also becomes a valid generic type/func.

Now there's a problem which interface the generic declares. That problem we can solve if we just must specify on which interface we want to sepcialize.

Example of specialization of the sort function:

func SortMy Sort~{T MyType}

Or a min function:

func Min(a V, b V) V {

    if a.Less(b) {

        return a

    }

    return b

}

func MyMin Min~{T MyType}

Min~{T MyType}(a, b)

Changes to the language spec would be something like:

Specialization = "~" "{" { InterfaceSpez ";" } "}" .

InterfaceSpez = InterfaceTypeName Type .

Type = TypeName | TypeLit | TypeSpez | "(" Type ")"

TypeSpez = Type Specializaton .

FunctionLit = AnonymousFunc | SpezFunc .

AnonymousFunc = FunctionType Body

SpezFunc = (FunctionName | FunctionLit) Specialization

FunctionDecl = "func" FunctionName (FunctionSpec | SpezFunc)

FunctionSpec = Signature [ Body ]

[Eleanor McHugh]

On 1 May 2012, at 21:30, josvazg wrote:
> Ok,
>
> But generics aside.
>
> Imagine we had the standard sort package as it is now, allowing us to sort any type implementing the sort.Interface with a very efficient mixture of quicksort/heapsort and insertsort algorithms.
>
> BUT imagine we ALSO had a subpackage at sort for each primitive type NOT USING the sort.Interface:
> sort/ints
> sort/floats
> sort/strings
> ...
> Each package has the same efficient implementation for sorting (quicksort+heapsort+insert) BUT it does INLINE comparisons and swaps instead of calling sort.Interface.
>
> I timed this raw/native implementations to be more than 2x times faster than the same sort but using sort.Interface (for int, and a little less that 2x for string) [https://github.com/josvazg/algorithms/tree/master/sorting]
>
> What would be the price/penalty in this case (if any)?
>
> I see none: Only when you need a sort for primitive type X will you import sort/X, and only in that case the package will be linked within the program and the package will only add that specialized code once, Right?
>
> I think this was not done because 2x performance was considered not worth against the tedious, repetitive (and error prone) manual expansion of the same algorithm for N primitive types just changing the primitive type spec everytime it is mentioned.
>
> Or is there any problem this specialized packages would create that is more important to avoid than getting twice the performance?

I tried something similar with for UDT slices derived from all the primitive types in slices [1] and for node-based lists in chains [2]. It's a tedious process, there being a score or so of commonly-used types that it seemed reasonable to cover, with considerable code repetition, and casts are still required to deal with the primitive types directly.

With sequences [2] I decided to explore what a generic API might look like and see how close I can get using existing Go idioms. It's upset a few people because it necessarily offloads type-checking to runtime to be able to handle primitive slice types, but I personally see nothing wrong with that given the use case. If similar functions were implemented as part of the core language they could be specified the same way as append() and therefore have compile-time type checking.

On the other hand there's the advantage with my current approach that I can specify interfaces which allow individual UDTs to provide their own implementation at very little additional runtime cost.

I've argued here before for some kind of category typing which would expose the concepts Map and Slice directly in the type system rather than via reflection, and I still think that would be the most elegant solution to the collection conundrum. However based on my experiments to date I think expanding the set of generic functions to cover common cases (insert, reverse, etc.) is very much a viable alternative which avoid all the complexities generics would add to the language.


Ellie

[0] http://github.com/feyeleanor/slices
[1] http://github.com/feyeleanor/chains
[2] http://github.com/feyeleanor/sequences

Eleanor McHugh
Games With Brains
http://feyeleanor.tel
----
if _, ok := reality.(Reasonable); !ok { panic(reality) }

[Andy Balholm]

Please ignore my first proposal (the one with <>) and look at the generalized, macro-based one. The whole point of the first proposal was the idea that interfaces can only be specialized explicitly. This would tend to reduce the bloat of C++-style generics, and also fits well with "Go doesn't implicitly anything."

But I realized that if generics can only be specialized explicitly, it would be possible to add more power and be less disruptive to the rest of the language by using a macro system. Although it would add complexity to the compiler and linker, this second proposal would not require any changes to the semantics of Go's type system. No covariance, contravariance, type erasure, etc. A specialization of a generic type or function would just be a regular type or function.

By the way, I think that basing generics on an extension of interfaces is a bad idea. Many of the use cases for generics involve numeric types, which do not fulfill any interface.

[josvazg]

"I don't worry that 

data[i].Less(data[i-1])

is slower than

data[i] < data[i-1]

for built-in types because I assume Go will eventually support automatic inlining of small methods like

func (a int) Less (b int) bool { return a < b }"

That would be cool indeed, but I don't think it is that easy.

When you compile to assembler the problem is not only to INLINE but also to VERSION multiple options depending on the final concrete type.

For each piece of code within the sort function to be inlined and specialized there would be N different small versions, one for each primitive type and one for the non-primitive interface call.

For instance, over egon's bubble sort sample:

func Sort(data []T) {

    // TODO: replace the bubble sort with something faster!

    done := false

    for !done {

        done = true

        for i := range data {

            if i > 0 && 

               data[i].Less(data[i-1] // <-- THIS PIECE OF CODE HAS N inline assembly versions to CHOOSE ONCE T is known

            ) {

                data[i-1], data[i] = data[i], data[i-1] // <-- THIS PIECE HAS N inline versions as well

                done = false

            }

        }

    }

}

Well, assuming the inline is simple and does not mess around the process registers being used before and after the inlining, the compiler could probably set a FIXED RELATIVE JMP amount depending on the type, for instance to compare or swap int JMP 0, float JMP 20, JMP 40 for strings, etc This is would be quite fast and cheap in terms of speed, I guess, at the beginning of the function the amount to jump for each inline operation that has multiple versions is set (so one of the versions for each inline operation is chosen). Then, for each versionable-inline-operation you have the cost of the JMP itself and the jump once the inline is done to continue normal common code.

But the problem will be that, the compiler will make a sort function TOO BIG with, probably, V inline versions that your program is not using at all but are there "just in case". On the other hand the code will be ONE and much sorter than having 5,6 or more sort nearly equal functions, one for each primitive or non primitive sort you are using.

[josvazg]

I agree that there are probably a lot of things that can be done in Go within the language and ALSO the standard core library that could help mitigate the need for generics at all.

Containers and collections are a huge use case for generics. If Go support avoids most "Do It Yourself" (and for each type) for uncovered cases generics will not be such an issue.

Jose

[David Roundy]

I think this is tending in the right direction:  generic types would have distinct type metadata pointers (or integers).  Once such pointers are created, generic functions need only have an additional pointer argument for each generic argument supplied, and the result is generic code that need only be compiled once, and is just as fast as ordinary go functions taking interface arguments (e.g. io.ReadFull, to pick a random example).  With suitable optimizations, one should be able to write a generic Append that works *almost* as fast as the builtin append.

I have some ideas in this direction, but it's waiting on time, and may never happen.  I think a generics proposal for go will need to include a sample implementation in order to be taken seriously.

David

--
David Roundy

[Kyle Lemons]

On Mon, May 7, 2012 at 5:42 PM, David Roundy <rou...@physics.oregonstate.edu> wrote:

I think this is tending in the right direction:  generic types would have distinct type metadata pointers (or integers).  Once such pointers are created, generic functions need only have an additional pointer argument for each generic argument supplied, and the result is generic code that need only be compiled once, and is just as fast as ordinary go functions taking interface arguments (e.g. io.ReadFull, to pick a random example).  With suitable optimizations, one should be able to write a generic Append that works *almost* as fast as the builtin append.

I have some ideas in this direction, but it's waiting on time, and may never happen.  I think a generics proposal for go will need to include a sample implementation in order to be taken seriously.

This gets me thinking.  If I have been following this correctly, what we want with generics is the way to have specialized code that runs without the overhead of type assertions when we know the concrete type.  Perhaps this is something that can be done purely in the compiler and/or linker.  I am not a compiler architect, but it seems like the compiler could annotate function calls with concrete types when it knows them.  This could be linked together normally to produce the ususal interface code, but an extra "pre-link" compile pass could be done to examine which function calls have concrete implementations known.  It could generate these once and replace the calls for them.  Since it would know the concrete type, it could eliminate dead code (type switches, etc), flatten known conditionals (type assertions) and potentially even cascade into other calls.  This wouldn't allow an []interface{} to take up the same amount of space as a []int, but assignments would be nominally just as fast and it could potentially allow for inlining of interface function calls (which is currently not possible because of the dynamic lookup) and modifying of interface values without type assertions.

Just a thought.

[David Roundy]

On Tue, May 8, 2012 at 9:19 AM, Kyle Lemons <kev...@google.com> wrote:
> This gets me thinking.  If I have been following this correctly, what we
> want with generics is the way to have specialized code that runs without the
> overhead of type assertions when we know the concrete type.  Perhaps this is
> something that can be done purely in the compiler and/or linker.

I don't see this at all as the role of generics. It's the syntax and
semantics that matter most, not efficiency. Currently there is no way
to write the append function in go, so it must be a builtin. I would
like to be able to write functions like append or copy. That is the
*primary* function of generics. If those functions are slow, it's not
the end of the world, but when you can't write them at all, that's not
so great.

As I see it there are N purposes for generics:

(A) Being able to write a function or method that could work a
container type regardless of what it contains (i.e. to write append or
copy). This would be useful for our existing container types: slice,
map or channel. e.g. you can't write a function that returns the
union of any two maps.

(B) Being able to define interfaces (and methods) that are
type-dependent, so a type-safe min(a,b) function could be written.

(C) Being able to write your own container types, i.e. if you wanted
to define a general red-black tree, or a linked list. (Requires A but
not B in order to be useful.)

(D) Being able to write type-safe functions involving multiple
arguments of a constrained type (but not a container type). e.g. to
write a function that returns the minimum of its two arguments.
(Requires B, but not A or C.)

(E) Being able to write interesting type-safe functions involving
containers (such as sort) in a type-safe way. (Requires A, B and D,
but not C.)

None of these uses for generics require that they be fast. They do
require an extension to the language's type system. I'd be interested
to hear if there are any other uses for generics that people have
considered.

Of course, practically speaking, we'd also like generics to be fast to
compile and fast to run. Fast to compile I expect is a hard
requirement for go. Fast to run, I expect, is a softer requirement.
Go already has "slow" interfaces, which require method lookup from a
table for every method call, and no one (including myself) seems to be
concerned about that particular slowness.

David

[Darren Grant]

On Tue, May 8, 2012 at 1:03 PM, David Roundy
<rou...@physics.oregonstate.edu> wrote:
>
> As I see it there are N purposes for generics:

...

I like it!

Can't most of these results be achieved cleanly with go's duck-type
approach to interfaces? For instance, in order for many container
algorithms to operate effectively I'd be looking for a way to supply
copy, assignment, equivalence and often hashing semantics anyway.

I'm not sure which of these features are already automatic for go's
built-in types, if any.

Cheers,
Darren

[Kyle Lemons]

I agree that my approach doesn't allow you to write a generic append, as that would require reflection.  It also doesn't preclude generics, but it does allow you to get a lot farther with what the language currently provides.  I'm not convinced that generic containers are actually as useful as people claim, but I won't argue the point.  My optimization (since that's really what it is, not generics) would allow sort.Sort to be much more performant and encourage people to create behavioral interfaces for such things instead of writing generic containers (I vastly prefer sort.Interface to something akin to a java "Comparable").  For many things, it would allow interface methods to be inlined:

type reversed []int

// sort.Interface methods here

a := []int{1,2,3}

sort.Sort(reversed(a))

The compiler would annotate that call with the fact that it knows that the sort.Interface is a pkg.reversed.  The "pre-link" step could then specialize this, and all calls to sort.Interface.Less are known to be pkg.reversed.Less, which is (theoretically) inlineable, which seriously speeds up the inner loop.  I haven't thought about how this interacts with heap.Interface, but I suspect that it could also allow almost all operations on a heap to be inlined as well.

[John Asmuth]

On Tuesday, May 8, 2012 4:03:09 PM UTC-4, David Roundy wrote:

As I see it there are N purposes for generics:

I'd like to list one more: currently it is impossible to give a chan X to a function that wants a chan Y without introducing a buffer (and making it no longer useful as a synchronization point). We'd need some kind of generics for this.

Either that, or modify the language so that if you can X(aY) then you can (chan X)(aChanY). It would not be a simple change.

[Chris Hines]

On Tuesday, May 8, 2012 4:03:09 PM UTC-4, David Roundy wrote:

On Tue, May 8, 2012 at 9:19 AM, Kyle Lemons wrote:
> This gets me thinking.  If I have been following this correctly, what we
> want with generics is the way to have specialized code that runs without the
> overhead of type assertions when we know the concrete type.  Perhaps this is
> something that can be done purely in the compiler and/or linker.

I don't see this at all as the role of generics.  It's the syntax and
semantics that matter most, not efficiency.  Currently there is no way
to write the append function in go, so it must be a builtin.  I would
like to be able to write functions like append or copy.  That is the
*primary* function of generics.  If those functions are slow, it's not
the end of the world, but when you can't write them at all, that's not
so great.

Such different goals or requirements attached to the name "generics" is likely part of the problem designing a good solution.

 

As I see it there are N purposes for generics:

I applaud your effort to break the problem down into more precisely defined capabilities. Allow me to comment on each one.

 

(A) Being able to write a function or method that could work a
container type regardless of what it contains (i.e. to write append or
copy).  This would be useful for our existing container types: slice,
map or channel.  e.g. you can't write a function that returns the
union of any two maps.

Unless I misunderstand you, it would seem like you could do this with reflection today.

 

(B) Being able to define interfaces (and methods) that are
type-dependent, so a type-safe min(a,b) function could be written.

I would call this "scoped type constraints", with the scope being an interface, method, or function declaration. In other words, given a function that would otherwise accept and return unconstrained interface{} values, you would like to require that the concrete types of the values be related in some way (maybe limited to one of the properties of types and values).

 

(C) Being able to write your own container types, i.e. if you wanted
to define a general red-black tree, or a linked list.  (Requires A but
not B in order to be useful.)

Why aren't interfaces good enough here?

 

(D) Being able to write type-safe functions involving multiple
arguments of a constrained type (but not a container type).  e.g. to
write a function that returns the minimum of its two arguments.
(Requires B, but not A or C.)

This sounds like the same thing as B to me, or so similar that they might be doable with the same syntax.

 

(E) Being able to write interesting type-safe functions involving
containers (such as sort) in a type-safe way.  (Requires A, B and D,
but not C.)

Maybe I'm missing the point, but it seems to me that the sort packages is already type safe. I.e. if you try to pass a value to sort.Sort() that doesn't implement sort.Interface you will get a compile time error.

 

None of these uses for generics require that they be fast.

No, but people require their code to be fast (enough) and won't use the feature if it is (too) slow.

From your list I think only B and D are essentially impossible in Go1. The others are doable, but may not be as pretty or as performant as some would like.

Please set me straight if I have misunderstood any of your points, but it would seem that for A, C, and E there are ways to do what you want in Go1. If true then some form of generics would have to substantially improve on the available techniques in some way to make it carry its weight. The two categories of improvement that seem possible to me are either making idiomatic Go in these cases easier to read and write, or providing extra information to the compiler so it can produce faster binaries, or (preferably) both.

 

 They do
require an extension to the language's type system.  I'd be interested
to hear if there are any other uses for generics that people have
considered.

Of course, practically speaking, we'd also like generics to be fast to
compile and fast to run.  Fast to compile I expect is a hard
requirement for go.  Fast to run, I expect, is a softer requirement.
Go already has "slow" interfaces, which require method lookup from a
table for every method call, and no one (including myself) seems to be
concerned about that particular slowness.

I have personally had to code type-specific versions of container/heap and sort.Ints(). The performance gain was completely worth the work, but at the same time it was disappointing that code in the standard library had such poor performance when operating on trivial data types.

In general I think the debate about generics in Go is a really good thing. I have a lot of experience with both C++ templates and Java generics, both using and writing generic types as well as template meta-programming, and I'm a big fan of type safety. But I also really appreciate what the Go team is trying to do. I don't feel like I really grok "the Go way" yet, but I'm working on it.

I am learning to appreciate how the features of Go are pretty orthogonal to each other. In that spirit I think your effort to break down generics into more specific capabilities is very valuable. Identifying which, if any, of those capabilities are truly orthogonal to existing language capabilities seems like a valuable exercise.

Chris Hines

[Steven Blenkinsop]

On Tue, May 8, 2012 at 9:17 PM, Chris Hines <chris....@gmail.com> wrote:

 

(A) Being able to write a function or method that could work a
container type regardless of what it contains (i.e. to write append or
copy).  This would be useful for our existing container types: slice,
map or channel.  e.g. you can't write a function that returns the
union of any two maps.

Unless I misunderstand you, it would seem like you could do this with reflection today.

Sure. You could, you're just doing runtime type checking, which really leads into B. The code is also very different from the normal Go code for doing this. But certainly it is within the realm of possibility, if you don't consider the far-from-optimal performance.

  

(C) Being able to write your own container types, i.e. if you wanted
to define a general red-black tree, or a linked list.  (Requires A but
not B in order to be useful.)

Why aren't interfaces good enough here?

Defining the necessary methods for each type can be a bit of a pain. Changing the problem from implementing the container from scratch to implementing a set of simple operations certainly reduces the cognitive load and opportunity for error, but it's still a bit heavy. Also, see (E).

 

(E) Being able to write interesting type-safe functions involving
containers (such as sort) in a type-safe way.  (Requires A, B and D,
but not C.)

Maybe I'm missing the point, but it seems to me that the sort packages is already type safe. I.e. if you try to pass a value to sort.Sort() that doesn't implement sort.Interface you will get a compile time error.

Maybe look at heap.Interface, though. Push isn't compile-time type safe, and neither would be a lot of code using Pop. And that's just the tip of the iceberg for basic operations. If you start trying to manipulate multiple containers it really becomes an issue. 

[egon]

Here's another simple example. (Maybe it can be done without it as well, but I haven't figured out how to do it.)

I have several maps with string keys and some struct value...

map[string]A, map[string]B, map[string]C, map[string]D, map[string]E...

I would like to print the map-s in sorted order...

Currently I have to write this 6 times, for each map type separately:

m := make(map[string]A)

keys := make([]string, len(m))

for key := range m {

keys = append(keys, key)

}

sort.Strings(keys)

for _, name := range keys {

val := m[name]

print("%s : %s\n", name, val.Desc)

}

I would like to write something like:

for _, name := range sorted(keys(m)){

val := m[name]

print("%s : %s\n", name, val.Desc)

}

instead.

On Wednesday, May 9, 2012 7:09:32 AM UTC+3, Steven Blenkinsop wrote:

[josvazg]

"(A) Being able to write a function or method that could work a 

container type regardless of what it contains (i.e. to write append or 

copy).  This would be useful for our existing container types: slice, 

map or channel.  e.g. you can't write a function that returns the 

union of any two maps."

Like this...?

type K,V generic;

func keys(m map[K]V) []K {

ks=make([]K,len(m))

i:=0

for k,_ :=range m {

ks[i]=k

}

return ks

}

[josvazg]

"(B) Being able to define interfaces (and methods) that are 

type-dependent, so a type-safe min(a,b) function could be written."

Like this...?

type T generic;

type Minimum interface {

min(a, b T) T

}

[josvazg]

"(C) Being able to write your own container types, i.e. if you wanted 

to define a general red-black tree, or a linked list.  (Requires A but 

not B in order to be useful.) "

type T generic;

type listItem struct {

e T

prev,next *listItem

}

type LinkedList struct {

start, end *listItem

}

...

func (l *LinkedList) Append(e T) {

    newItem=*ListItem{e,nil,nil}

    l.end.next=newItem

    l.end=newItem

}

func (l *LinkedList) Start() T {

return l.start.e

}

...

[josvazg]

"(D) Being able to write type-safe functions involving multiple 

 arguments of a constrained type (but not a container type).  e.g. to 

 write a function that returns the minimum of its two arguments. 

 (Requires B, but not A or C.) "

Like this...?

type P primitive; // P would have to be primitive or a primitive derivate 

                 // Otherwise "a<b" would have to be automatically converted to "a.LT(b)" on-the-fly

                // BUT Go doesn't like to do that cause "Go does nothing implicitly"

func min(a, b P) P {

if(a<b) {

return a

}

return b

}

[josvazg]

"(E) Being able to write interesting type-safe functions involving 

containers (such as sort) in a type-safe way.  (Requires A, B and D, 

but not C.)"

Like this...?

type P primitive;

func Sort(data []P) { 

    // TODO: replace the bubble sort with something faster! 

    done := false 

    for !done { 

        done = true 

        for i := range data { 

            if i > 0 && data[i]<data[i-1] { 

                data[i-1], data[i] = data[i], data[i-1] 

                done = false 

            } 

        } 

    } 

} 

[In my case I don't see a problem with current Go Sort package APART from the fact that is slower for primitive types cause is doing a couple of interface call on a tight loop that could be avoided]

[egon]

I think rather than adding generic type let's use interfaces and add some way to replace those interfaces with some concrete type. Declaring those things interfaces gives you the benfit of adding conditions that the type in the generic must adhere to.

type T interface {

Less(T) bool

}

func min(a,b T) T {

if a.Less(b) {

return a

}

return b

}

This way you can easily check whether a type can be used in a generic function. Also checking the correctness of the generic function becomes easier. Essentially you can just check whether the interface contains all the methods required in the function. If the new type implements this interface it can replace the "generic" interface. There are probably many ways to replace the interface:

// infer it

a := MyThing{3}

b := MyThing{45}

min~(a, b)

// be explicit

min~{T MyThing}(a,b)

I like the explicit way more because you would be able to make it work for structures, interfaces, functions, methods.

[Eduard Castany]

What about a partial solution?

func Max_(){} //this

func MaxInt(a, b int){}

func MaxUint(a, b uint){}

...

then you can call Max(1, 2) without thinking about witch Max function you are calling

[egon]

I think this doesn't scale very well if you have generics over multiple types

consider a function composition 

func Compose(a func(A)B, b func(B)C) func(A)C {

   return func(x A) C {

       return b(a(x))

   }
}

This would mean that you need to specify ComposeABC

More typical is probably the generic with two types eg. a tree with a specific key and value.

When a tree becomes the value as well you get the same kind of problem.

[Robert Johnstone]

I agree with your points, but would still like to propose another way of looking at the need for generics:

(A) Specialization:  Writing a generic function or type that can be recompiled or relinked with a concrete type in place of an interface.  Presumably, because the compiler know the exact type, a more efficient implementation can be obtained (fewer runtime checks, less boxing, ... ).  Specialization is a tool for optimizing performance.

(B) Type-safety:  A function such as max could be written using reflection, but will always return interface{}.  This is also important for custom containers, turning a heterogeneous container of interface{} into a container of some fixed type.  Potentially, the compiler could generate code only for interface{}, but enforce the type constraints.  Type-safety is a tool for protecting code correctness.

Additionally, I'd like point out that C++, as a design principle, worked to erase the difference between built-in and user-defined types.  This has a big impact on the design of templates.  In Go, built-in and user-defined types are quite different, so I think that a proposal for generics that treats them both equally may be much trickier than one that only looks at interfaces, for example.

[egon]

I would be happy with B... although I would also like A. I think you can do a combination of both.

Do a compilation with that specific interface{} type. When putting/removing things to that container/function/struct you just cast it to that specific type. 

Internally the container would still use the interface but to the outside it would only show the specific type.

Essentially this min:

type T interface { Less(T) T }

func Min(a T, b T) T {

if a.Less(b) {

return a

}

return b

}

b := Min~{T MyType}(a, b)

// could be safely translated to

b := Min(a,b).(MyType)

but in the second version it's result is guaranteed by the generics

to be MyType, therefore the current typeassert can be discarded and can be

cast directly to MyType. Similarly this could work with structs and methods as well.

It wouldn't be as fast and memory efficient as compiling the function for the specific type.

It would be faster than B but slower than A.

[Eduard Castany]

True, but at least simplifies caller's life, looks pretty simple and thus more % of being implemented some day.

(golang devs prefer macros to templates in C++..)

El dimecres 9 de maig de 2012 16:34:37 UTC+2, egon va escriure:

[egon]

I don't mind whether it's a macro system or templates, but I do care about type safety of generics.

If it's possible to do macros with adding type asserts or doing some type checking and testing the macros then

fine by me... because both solve my problems.

[David Roundy]

On Tue, May 8, 2012 at 6:17 PM, Chris Hines <chris....@gmail.com> wrote:
> Such different goals or requirements attached to the name "generics" is
> likely part of the problem designing a good solution.

Indeed.

>> As I see it there are N purposes for generics:
>
>
> I applaud your effort to break the problem down into more precisely defined
> capabilities. Allow me to comment on each one.
>
>> (A) Being able to write a function or method that could work a
>> container type regardless of what it contains (i.e. to write append or
>> copy).  This would be useful for our existing container types: slice,
>> map or channel.  e.g. you can't write a function that returns the
>> union of any two maps.
>
> Unless I misunderstand you, it would seem like you could do this with
> reflection today.

Anything that can be programmed can be programmed in a
dynamically-typed language. Reflection allows us to treat go as a
dynamically-typed language, so yes, any program or function can be
written using reflection. I failed to specify in A that I'd like it
to be type-safe. That we cannot do with current go + reflection.
i.e. there is no way to specify the type of a function that computes
the union of two maps.

>> (B) Being able to define interfaces (and methods) that are
>> type-dependent, so a type-safe min(a,b) function could be written.
>
> I would call this "scoped type constraints", with the scope being an
> interface, method, or function declaration. In other words, given a function
> that would otherwise accept and return unconstrained interface{} values, you
> would like to require that the concrete types of the values be related in
> some way (maybe limited to one of the properties of types and values).

Now that I look at it, B is indeed pretty much confused with D below.

>> (C) Being able to write your own container types, i.e. if you wanted
>> to define a general red-black tree, or a linked list.  (Requires A but
>> not B in order to be useful.)
>
> Why aren't interfaces good enough here?

How would I write the type of a linked list as an interface type? If
you can't specify its type, you can't declare data. Of course, with
reflection we could make all our arguments to functions be of type
interface{}, as well as the output of every function. But that isn't
particularly satisfying. e.g. imagine

type List struct {
Value interface{}
Next *List
}

func Head(list *List) interface{} {
if list == nil {
panic("head of empty list")
}
return list.Value
}

You need a manual type check on every access to a list element.

>> (D) Being able to write type-safe functions involving multiple
>> arguments of a constrained type (but not a container type).  e.g. to
>> write a function that returns the minimum of its two arguments.
>> (Requires B, but not A or C.)
>
> This sounds like the same thing as B to me, or so similar that they might be
> doable with the same syntax.

Yeah, it's pretty redundant (which happened during a hurried edit of my email).

>> (E) Being able to write interesting type-safe functions involving
>> containers (such as sort) in a type-safe way.  (Requires A, B and D,
>> but not C.)
>
> Maybe I'm missing the point, but it seems to me that the sort packages is
> already type safe. I.e. if you try to pass a value to sort.Sort() that
> doesn't implement sort.Interface you will get a compile time error.

You're write, sort.Sort is type-safe, which is possible because it
doesn't return a value, and only has one input. There are more
interesting functions that require two inputs, or return an output,
and they would require "generics" language extensions. I'll also note
that sort.Sort doesn't work on *any* of the slice types... instead you
are required to create a new type (which can satisfy the interface)
and cast your slice into that type. It's "only" an inconvenience, but
it has major implications for API design, since you can't possibly
hide this sort of ugliness behind a nice API. Essentially every user
has to create a new type and write three simple methods, just to use
the one reusable function.

A simple example of a function that you can't yet write would be to
write a Filter function, which takes a slice and a bool-valued
function of the element type, and returns a new slice with only those
elements that the function says are true. Or a lookup function, that
returns the first element of a slice that matches some criterion.

Thus E not possible in Go1, since you can't write the type of such a
function (except in simple cases where there is just one argument
involving the types of interest, and you don't mind forcing users to
typecast their container type to something else in order to satisfy an
interface).

>> None of these uses for generics require that they be fast.
>
> No, but people require their code to be fast (enough) and won't use the
> feature if it is (too) slow.

True, but we're already using go because speed isn't our first priority.

> From your list I think only B and D are essentially impossible in Go1. The
> others are doable, but may not be as pretty or as performant as some would
> like.
>
> Please set me straight if I have misunderstood any of your points, but it
> would seem that for A, C, and E there are ways to do what you want in Go1.
> If true then some form of generics would have to substantially improve on
> the available techniques in some way to make it carry its weight. The two
> categories of improvement that seem possible to me are either making
> idiomatic Go in these cases easier to read and write, or providing extra
> information to the compiler so it can produce faster binaries, or
> (preferably) both.

I would say that neither A, C or E are possible in type-safe Go1--by
which I mean that your function's types must describe the input
sufficiently that user code that uses them cannot panic with a
wrong-type input. The key here is type safety, which is one of the
main reasons for me to use go.

I will agree that if you give up on type safety, you could accomplish
any of these goals (including B or D) in Go1. So I would say that the
major improvement that a generics approach would bring would be to
allow you to do these tasks in a type-safe manner (which will also be
considerably easier to read and write than the existing hacks).

I agree that the orthogonality and minimality of the Go language being
extremely valuable, and something we wouldn't want to break. Whatever
solution is found (if any) needs to be go-like.
--
David Roundy

[Steven Blenkinsop]

On Thursday, May 10, 2012, David Roundy wrote:

A simple example of a function that you can't yet write would be to
write a Filter function, which takes a slice and a bool-valued
function of the element type, and returns a new slice with only those
elements that the function says are true.  Or a lookup function, that
returns the first element of a slice that matches some criterion.

Unless you follow the example of sort and use indices as references to elements which you then pass into type aware methods or closures. You still have to manually code the operations for each container type, but as I was saying, it's better to have to write a set of simple functions for each type that have low cognitive load than it is to write a more complex algorithm for each type that has high cognitive load. That's not to say that there aren't cases where you can't do this, but it is a useful approach. Even with generics, it seems like this approach should be applied to determine what needs to use generics and what can be built without them.

 

Thus E not possible in Go1, since you can't write the type of such a
function (except in simple cases where there is just one argument
involving the types of interest, and you don't mind forcing users to
typecast their container type to something else in order to satisfy an
interface).

I don't really see the type casts as a problem. You're essentially just creating a templated multi-closure.

[David Roundy]

On Thu, May 10, 2012 at 3:31 PM, Steven Blenkinsop <stev...@gmail.com> wrote:
> On Thursday, May 10, 2012, David Roundy wrote:
>> A simple example of a function that you can't yet write would be to
>> write a Filter function, which takes a slice and a bool-valued
>> function of the element type, and returns a new slice with only those
>> elements that the function says are true.  Or a lookup function, that
>> returns the first element of a slice that matches some criterion.
>
> Unless you follow the example of sort and use indices as references to
> elements which you then pass into type aware methods or closures. You still
> have to manually code the operations for each container type, but as I was
> saying, it's better to have to write a set of simple functions for each type
> that have low cognitive load than it is to write a more complex algorithm
> for each type that has high cognitive load.

I agree about simple functions being better than more complicated
ones, which is why I like the idea of enabling generics. I disagree
about generic functions (if generics are done right) having a higher
cognitive load than ordinary functions. You're right that a Filter
function could be written with the type:

func Filter(func(sort.Interface, int) bool, sort.Interface) []int

where the caller would then have to use the slice of indices to
construct the filtered slice. But this is sufficiently hard to use
that it would be pointless, because you could write the same function
in one line. So simple functions *can't* be written using the
sort.Sort approach, which is therefore only useful for for
*complicated* functions. But simple functions (like append and copy)
are *really* useful, so much so that we haven't been able to live (in
Go world) without generic versions of them. We can keep adding every
useful simple function to the language definition as a new primitive
(well, actually, we can't add any until Go 2), but that doesn't seem
like the best-scaling approach.

A nice Filter would look something like:

func Filter(f func(a) bool, x []a) []a {
out := []a{}
for _,v := range x {
if f(v) {
out = append(out, v)
}
}
return out
}

But of course there are various reasons why you might prefer to have a
slightly trickier implementation (just as is the case with append).
This function (if somehow the type a were generic) would be very
simple to understand and easy to use.

> That's not to say that there
> aren't cases where you can't do this, but it is a useful approach. Even with
> generics, it seems like this approach should be applied to determine what
> needs to use generics and what can be built without them.

I'd say that the sort.Sort approach is sufficiently complicated (and
has a sufficiently high cognitive load) that it's almost always the
wrong thing to do. But, of course, I'm coming with something of a
declarative bias, that functions should accept parameters as input and
return values (so they can be combined together in readable ways).
I'd be really sad if sin and cos had types like

func sin(x *double)

so you had to make copies of the input first and then remember that
you modified it, and you couldn't construct expressions out of
multiple functions. But to each his own!
--
David Roundy

[Steven Blenkinsop]

On Thu, May 10, 2012 at 8:39 PM, David Roundy <rou...@physics.oregonstate.edu> wrote:

On Thu, May 10, 2012 at 3:31 PM, Steven Blenkinsop <stev...@gmail.com> wrote:
> Unless you follow the example of sort and use indices as references to
> elements which you then pass into type aware methods or closures. You still
> have to manually code the operations for each container type, but as I was
> saying, it's better to have to write a set of simple functions for each type
> that have low cognitive load than it is to write a more complex algorithm
> for each type that has high cognitive load.

I agree about simple functions being better than more complicated
ones, which is why I like the idea of enabling generics.  I disagree
about generic functions (if generics are done right) having a higher
cognitive load than ordinary functions.

I don't disagree. I was saying Sort has a higher cognitive load than Len, regardless of whether either is generic, so if you have to rewrite something for each type, it's better to implement sort.Interface than to implement sort.Sort.

 

 You're right that a Filter function could be written with the type:

 

func Filter(func(sort.Interface, int) bool, sort.Interface) []int

where the caller would then have to use the slice of indices to
construct the filtered slice.  But this is sufficiently hard to use
that it would be pointless, because you could write the same function
in one line.  So simple functions *can't* be written using the
sort.Sort approach, which is therefore only useful for for
*complicated* functions.  But simple functions (like append and copy)
are *really* useful, so much so that we haven't been able to live (in
Go world) without generic versions of them.  We can keep adding every
useful simple function to the language definition as a new primitive
(well, actually, we can't add any until Go 2), but that doesn't seem
like the best-scaling approach.

Again, I agree. It seems to me that you'd want to be able to write the simple functions/methods generically, and then write the more complex functions in terms of those simple operations. Once you've written these, the value of generics in implementing the more complex functions (like sort.Sort) is much decreased. It's just a line of (unoriginal) thought I'm contributing to the generics question. People are often concerned about code bloat in generic code that uses macro expansion. However, if you use generics primarily for simple, reusable functions, and then build larger algorithms on top of these, it seems you could greatly reduce the amount of code bloat you'd suffer, at least from generics alone. Optimizations that remove dynamic dispatch would still be possible and bring back the bloat.

I was thinking about this, actually, since I was trying to see if I could implement the heap package in a type safe way. http://play.golang.org/p/h2-SDUoE5d

I'm not saying this is a good approach. However, the Apply method does somewhat address what you're saying about accepting input and returning output. I can imagine doing this sort of thing where the input/output is a collection as well. However, it does start to get increasingly ugly.

[JONNALAGADDA Srinivas]

On Friday, 11 May 2012 06:09:45 UTC+5:30, David Roundy wrote:

But simple functions (like append and copy)
are *really* useful, so much so that we haven't been able to live (in
Go world) without generic versions of them.  We can keep adding every
useful simple function to the language definition as a new primitive
(well, actually, we can't add any until Go 2), but that doesn't seem
like the best-scaling approach.

        Yes.  While certain foundations have been designed with orthogonality in mind, a tendency to grow the language by agglutination has been present since the beginning, as well.  Introduction of `append' (which can operate only on slices) and `delete' (which can operate only on maps) illustrate it.  Those built-in functions are also red flags: compiler magic is becoming necessary for some simple operations!

 

I'd say that the sort.Sort approach is sufficiently complicated (and
has a sufficiently high cognitive load) that it's almost always the
wrong thing to do.  But, of course, I'm coming with something of a
declarative bias, that functions should accept parameters as input and
return values (so they can be combined together in readable ways).

        That is an interesting observation, David!  Those participating in this debate arguing for explicit loops, etc., probably have a corresponding imperative bias.

        Could it also be probable that people who do not see a need for generics mostly deal with applications in which the number of distinct user-defined types is small?  Consequently, the pain of repetition is proportionally smaller -- small enough to ignore it?

                                                            Greetings,

                                                                    JS

____

http://oneofmanyworlds.blogspot.com

[Corey Thomasson]

On 10 May 2012 23:15, JONNALAGADDA Srinivas <sigm...@gmail.com> wrote:

        Yes.  While certain foundations have been designed with orthogonality in mind, a tendency to grow the language by agglutination has been present since the beginning, as well.  Introduction of `append' (which can operate only on slices) and `delete' (which can operate only on maps) illustrate it.  Those built-in functions are also red flags: compiler magic is becoming necessary for some simple operations!

 

s/necessary/convenient/

We could append to slices and delete from maps all we wanted before those builtins existed. 

[Robert Johnstone]

Fair enough, but we could also be programming in assembly, so the s/necessary/convenient/ is not very helpful.

There were a lot of custom versions of append floating around.  Sometimes, it is better to live with a single more complicated version of a function than thousands of partial implementations.  At present, only the Go authors have the tools to fix these DRY violations.  Srinivas made a valid point.

While it would be nice, I don't think that Go needs generics.  That does not mean that we should turn a turn a blind eye to valid use-cases for generics.


On Friday, 11 May 2012 00:48:40 UTC-4, Corey Thomasson wrote:

On 10 May 2012 23:15, JONNALAGADDA Srinivas:

[Job van der Zwan]

> Why aren't interfaces good enough here?

How would I write the type of a linked list as an interface type? If
you can't specify its type, you can't declare data.  Of course, with
reflection we could make all our arguments to functions be of type
interface{}, as well as the output of every function.  But that isn't
particularly satisfying.  e.g. imagine

type List struct {
  Value interface{}
  Next *List
}

func Head(list *List) interface{} {
  if list == nil {
    panic("head of empty list")
  }
  return list.Value
}

You need a manual type check on every access to a list element.

How about the other way around?

//A Link is any type with a Next method that returns a pointer to the next Link. 

type Link interface{

Next() *Link

}

type IntLink struct{

int

*Link nextLink

}

func (i *IntLink) Next() *Link {

return nextLink

}

Or something like that. Not sure if this works, actually, just made this up on the spot (well.. I adapted it from what I remember of Rob Pike's lecture on Lexical Scanning).

[Job van der Zwan]

On Friday, 11 May 2012 21:18:15 UTC+2, Job van der Zwan wrote:

type IntLink struct{

int

nextLink *Link 

}

D'oh... 

[Steven Blenkinsop]

You generally want pointers in interfaces, not pointers to interfaces. Also, this doesn't really solve anything, since you can't actually operate on the list in a generic way. Right now, in Go, you have to provide a simple, type safe interface that a generic algorithm can use to manipulate your specialized datatypes. Here's a shot at sorting a linked list in a type safe way:

http://play.golang.org/p/J86iBh-Izg

While I won't claim this is the best approach or ideal, implementing SortState took a couple of minutes and was correct the first time, while implementing Sort took longer and required debugging. While arguably by using this approach I made Sort harder to write, there still is a gain in that you can easily see that the code that would be duplicated for each list type is correct, while the code that is more likely to require bug fixing at a later time doesn't need to be duplicated, making it easier to maintain the code.