[go-nuts] discussion on generics. My vision to give ideas to implementers.

[german diago]

Hello. I'm learning to use go and the feature I miss the most is
generics, so I started thinking about it and I would like to give my
vision and share it with you. It's just to make the implemeters think
about it.

First I put the code here for my proposal. It's sure there will be
some mistakes or something I didn't think about. But that's
unavoidable I think.


The code here is regular go for today, from package vector:


type LessInterface interface {
Less(y interface{}) bool
}


type Iterable interface {
// Iter should return a fresh channel each time it is called.
Iter() <-chan interface{}
}


func (p *Vector) Push(x interface{})

func (p *Vector) Pop() interface{}


The generic approach is more or less obvious:

type<T> LessInterface<T> interface {
Less<T>(y T) bool
}


type<T> Iterable<T> interface {
Iter<T>() <- chan T
}


func<T> (p * Vector<T>) Push(x T) {

}


func<T> (p * Vector<T>) Pop() T {

}

This would generate code when using it for types. I would like to
introduce constraints as well as alias types, struct templates and
type templates. This is my own invention:


type<T> ForwardSequence interface {
alias T ElementType //alias is useful for generic code. It names a
type
getNext() ElementType
}


type<T> BidirectionalSequence interface {
ForwardSequence<T>

Prev() ElementType
}


type<T> RandomSequence interface {
BidirectionalSequence<T>

At(i int) ElementType
}


//demonstrate Constrain T
func<T : RandomSequence> (p * T) Remove(elem T.ElementType) {
for idx, item := range p {
switch item {
case elem:
p.Delete(idx)
}
}
}

//template struct
type<T> Point struct {
X, Y T
}

//template type
type PointF Point<float>


You can put constrains in the interface template types as well if you
want, to ensure previous requirements are
met.

alias would be useful in interfaces to name types that can be used in
generic functions. Some usage of the code from before is here:



func main() {
var vec Vector<int>
var vec2 Vector<*PointF>

vec.Push(3) //generates Push function compile-time
vec.Push(5)
vec.Push(2)
vec.Push(4)

val := vec.Pop() //type of val is int

vec2.Push(&PointF{3.5, 2.8})
vec2.Push(&PointF{-2.1, 5.})


var sequence RandomSequence<*PointF>

//Using sequence to access a sequence
sequence = &vec


var elem RandomSequence<*PointF>.ElementType //or
sequence.ElementType
//Using interface to access T
elem := sequence.At(0) //elem is type *Point<float>
}

I think the approach is quite sensible regarding to the power they
give you, but I don't know how difficult to implement my requirements
are, namely:

- alias types.
- constraints on template parameters.
- interface templates
- struct templates
- type templates

It would be nice to have something in the lines of template typedefs
like in c++0x:

template <class T>
using MyVec = vector<T, Alloc<T> >;

in go would become something like:

type<T> MyVec vector<T, Alloc<T>>

usage:

MyVec<T>

I know allocators like that make no sense in go, but you get the
idea.

Now it's time to ask lots of questions and make me think ;-).
Thanks for your time.

[Serge Hulne]

Hi there,

In my experience, templates:
- Increase tremendously compilation time.
- Generate code at compilation time, which one has no control over.
- Make the order in which the files have to be compiled critical (and
can end-up in circular dependencies).
- Make the syntax heavier.

It is usualy impossible to predict the performance of an algorithm,
since it acts not on a given object, but on a variety of objects.

It is typically a high-level / low performance language feature (cf.
the STL: generic but very memory consuming and rather slow and
complicated).

Last but not least : It encourages "template meta-programming" which
yields extremely unreadable code with unpredictible performance (see
www.boost.org )


Serge Hulne

[Jesper Louis Andersen]

On Mon, May 17, 2010 at 12:32 AM, german diago <germa...@gmail.com> wrote:

> I think the approach is quite sensible regarding to the power they
> give you, but I don't know how difficult to implement my requirements
> are, namely:
>
> - alias types.

Gut feeling: Not too hard.

> - constraints on template parameters.

This will open a can of worms to battle. If you look at Javas
generics, they have a notion of a /bounded wildcard/ which allows you
to say List<? extends Foo>. This signifies an /unknown/ type extending
the Foo type. In Go, that would be extension of the Foo interface. Its
dual, List<? super Foo>, signifies an /unknown/ supertype of Foo. The
typing rules for these two constructions are somewhat unintuitive. The
reason for all this hoop-jumping is a peculiar thing of subtyping with
generics. If Bar extends Foo then it is /not/ the case that List<Bar>
extends List<Foo>!

In practice, the system of Java is derived from a system named F-sub,
System-F with bounded quantification. But it has to be restricted
since full F-sub type checking is undecideable (Piece, 1993 if memory
serves). Luca Cardelli was also deeply involved in F-sub IIRC.

> - interface templates
> - struct templates
> - type templates

Templates tend to avoid the problem by expansion at compile time.
Whenever you need a new template type, expand code with substitution.
This is somewhat dangerous as it tend to lead to the path of utter
despair and sheer horror, as Serge already gave examples of.

The other path to take is the naive one: Add parameters to types, but
do not allow one to use that type for anything "inside" the container.
Thus all the container has is a pointer to the type, with no
recollection of what type it is sitting with. Subtyping hierarchies
with template types are outlawed totally due to the above problem of
List<Bar>/List<Foo>. Gut feeling: Solves most real-world problems
effectively, is somewhat simple to implement. One has to be extremely
cautious when messing with type systems however. It is very easy to
mess them up so they loose nice properties. I think this idea rather
closely matches the 'map'-construction in Go.

Another idea I had a Go at, was package parametrization. The idea
stems from the ML module system. You allow to parameterize a complete
package on another package. In Go, One would perhaps opt for a simpler
variant where you can parameterize a package on one or more
interfaces. It allows the code inside the package to use the
interface-methods only when dealing with the interface type. In an
import statement, one can supply the needed interface and name:

import (
"foo"<int> as fooint // requires syntax improvement, but the idea is there
"foo"<string> as foostring
)

Compilation however, is not that simple. The above will require two
compilations of foo, one for each type. Furthermore, we will only
learn about this need when compiling the package containing the
import. If it *is* already compiled and available on disk however, we
can skip recompilation, which somewhat improves the situation. Another
even more sinister low-level path to take is to abort compilation of
the package if the prerequisites are not there. Thus, compilation
dependencies are outsourced to either the programmer, or a tool which
scans source code and builds dependency DAGs and lays them out with a
topological sorter.

The grand caveat with generics: They are hard in subtyping
environments. They come back to haunt and bite you and will happily
sink their fangs into the unsuspecting new user.

--
J.

[Kirill Zorin]

I think it's important to understand what problems the Go team has
outlined with existing implementations of generics, and to what extent
they want generics to be involved in Go considering that it can't just
be a "drop-in" solution.

Go team: Is it possible to get the above information?

I imagine the list contains at least the following:

1) The syntax shouldn't change the grammar's complexity class. It
should also be easy on the eyes.

2) There should only be one copy of any template instantiation
anywhere in the code. (If Go ends up having compile-time generics,
that is.)

3) Templates should play nice with debug info, reflection, and
packages. This is an annoying problem, because any template
function is essentially an "open overload", that is to say,
overloads are generated by the compiler, and are therefore
susceptible to the same naming problems as templates and overloads
in C++ and elsewhere.

Also, I think it's important to keep in mind that Go doesn't
necessarily have to have compile-time generics. I have a feeling that
a reasonable runtime implementation will perform well enough for the
majority of cases. If your program's performance depends solely on
compile-time versus runtime generics, then you probably shouldn't be
writing it in Go to begin with.

Bottom line: What items are on the Go team's "No Way" list?

K

On May 17, 7:35 am, Jesper Louis Andersen
<jesper.louis.ander...@gmail.com> wrote:

[David Roundy]

On Mon, May 17, 2010 at 4:35 AM, Jesper Louis Andersen

>> - constraints on template parameters.
>
> This will open a can of worms to battle. If you look at Javas
> generics, they have a notion of a /bounded wildcard/ which allows you
> to say List<? extends Foo>. This signifies an /unknown/ type extending
> the Foo type. In Go, that would be extension of the Foo interface. Its
> dual, List<? super Foo>, signifies an /unknown/ supertype of Foo. The
> typing rules for these two constructions are somewhat unintuitive. The
> reason for all this hoop-jumping is a peculiar thing of subtyping with
> generics. If Bar extends Foo then it is /not/ the case that List<Bar>
> extends List<Foo>!

Indeed, this is scary, but important. Without type constraints on
templates, they're just a powerful macro (as in C++), which is a pain,
e.g. templates themselves can't be typechecked.

I'd lean towards just requiring that a template type satisfy an
instance. That would allow a generic function to be compiled just
once and accept boxed arguments. Compiling specialized versions of
the generic function for efficiency becomes an optimization that is
also reasonable to do with ordinary functions that have interface
parameters. As far as type checking goes, I'm no expert, but I
believe the type system would be roughly equivalent to that of Haskell
98 (sans generics, but Haskel without generics is roughly equivalent
to other languages with generics), which I believe is well-understood.

> Another idea I had a Go at, was package parametrization. The idea
> stems from the ML module system. You allow to parameterize a complete
> package on another package. In Go, One would perhaps opt for a simpler
> variant where you can parameterize a package on one or more
> interfaces. It allows the code inside the package to use the
> interface-methods only when dealing with the interface type. In an
> import statement, one can supply the needed interface and name:
>
> import (
>  "foo"<int> as fooint // requires syntax improvement, but the idea is there
>  "foo"<string> as foostring
> )

I implemented this with gotgo, and actually used it in a couple of
programs. It sounds like a great idea, and seems pretty nice, but
becomes very awkward if you want to support expansion of private
types, at least in the implementation I used. Of course, I was doing
all this by a pre-processing trick to compile "foo(string)" as an
ordinary package. If this were built into the language that could
perhaps be avoided. But the trouble was that I couldn't handle things
like:

import myfoo "foo(mytype)"

type mytype struct { ... }

If the compiler could handle package parametrization via unexported
types (e.g. by generating a file that is part of the package currently
being built, which poses a challenge for the myfoo.foo syntax, since
it *looks* like it's an imported package, then this could work.
--
David Roundy

[roger peppe]

On 17 May 2010 14:57, David Roundy <rou...@physics.oregonstate.edu> wrote:
> I'd lean towards just requiring that a template type satisfy an
> instance.

excuse my ignorance, but what does that mean?

[David Roundy]

Sorry, I was pretty vague. Actually, I miswrote my vague statement.
I meant to say must satisfy an *instance*, not an interface. There
should be a rule that no two terms in any programming language can
start with the same two letters...

I mean that if I declare a template type, that I should declare that
any type it is instantiated with must satisfy a given interface. e.g.
something like (and this is a really stupid example):

type Fooer interface {
func Foo()
}

func fooTwice<T Fooer>(a T) T {
a.Foo().Foo()
return a
}

This tells the compiler that "T" in the function fooTwice must be a
Fooable type. Thus the compiler can typecheck fooTwice itself and
verify that it will always compile. At the other extreme are C++
templates (although I hear they'll soon be getting something like
this), which cannot be typechecked. Instead they behave as simple (or
not-so-simple) macros, and only the resulting code is typechecked.
The trouble with the C++ approach is that if you're going to use a
templated function, you need to examine the entire function (and any
functions it calls) in order to determine what functions and/or
methods you need to define on your type parameter. Making this
explicit (as in Fooer above) means you have one place to look, and the
compiler can (and should) verify that fooTwice doesn't use any other
methods than are provided by the Fooer interface.

Another advantage of specifying an interface like this is that the
compiler could compile a single version of the function (or even data
structure) that uses a boxed version of the type, since go already
supports boxing of interface types.
--
David Roundy

[Kirill Zorin]

David,

There's no need for a template in your example. If you want to write a
function that takes a type that satisfies some interface MyInterface,
you write:

func doSomething(x MyInterface) { ... }

The compiler already checks those. (It would be useful to have syntax
that lets you specify you want x to satisfy several interfaces, but
that's not a related concern.)

Am I missing something?

K

On May 17, 11:28 am, David Roundy <roun...@physics.oregonstate.edu>
wrote:

[roger peppe]

On 17 May 2010 16:28, David Roundy <rou...@physics.oregonstate.edu> wrote:
> On Mon, May 17, 2010 at 7:07 AM, roger peppe <rogp...@gmail.com> wrote:
>> On 17 May 2010 14:57, David Roundy <rou...@physics.oregonstate.edu> wrote:
>>> I'd lean towards just requiring that a template type satisfy an
>>> instance.
>>
>> excuse my ignorance, but what does that mean?
>

> I meant to say must satisfy an *instance*, not an interface.

that's what you did say :-)
i'll presume you mean the other way around.

> I mean that if I declare a template type, that I should declare that
> any type it is instantiated with must satisfy a given interface.  e.g.
> something like (and this is a really stupid example):
>
> type Fooer interface {
>    func Foo()
> }
>
> func fooTwice<T Fooer>(a T) T {
>    a.Foo().Foo()
>    return a
> }
>
> This tells the compiler that "T" in the function fooTwice must be a
> Fooable type.  Thus the compiler can typecheck fooTwice itself and

i presume you mean Fooer there?

> verify that it will always compile.

the difficulty with conflating generics and interfaces is that:

type Fooer interface {
func Foo() Fooer
}

is not compatible with, say, X in the following:

type X int
func (x X) Foo() X {
return x
}

whereas one main aim of generics is that we be able
to describe container types in a type-safe way, which
requires being able to describe this kind of thing.

> Another advantage of specifying an interface like this is that the
> compiler could compile a single version of the function (or even data
> structure) that uses a boxed version of the type, since go already
> supports boxing of interface types.

i don't think it's possible to do this, because all types are not the
same size, so how could you generate a single piece of code for
this function, for instance:

func Set<T>(a []T, i int, x T) {
a[i] = x
}

boxing isn't an answer here (unless you specify that
T must always be pointer-sized, which is a possible solution
but not a nice one)

[Steven]

On Mon, May 17, 2010 at 11:58 AM, Kirill Zorin <cyril...@gmail.com> wrote:

David,

There's no need for a template in your example. If you want to write a
function that takes a type that satisfies some interface MyInterface,
you write:

func doSomething(x MyInterface) { ... }

The compiler already checks those. (It would be useful to have syntax
that lets you specify you want x to satisfy several interfaces, but
that's not a related concern.)

Am I missing something?

K

Yes, "return a".

The idea is that it is guaranteed to return a value of the same type as was passed in. You can't return some random Fooer, it has to be a T. There is a mistake though: a.Foo().Foo() won't work because a.Foo() is not a Fooer. "a.Foo(); a.Foo()" would work.

[Jonathan Amsterdam]

David,
You probably arrived to Go-Nuts after I posted my generics proposal,
so I'll repeat the link:

http://docs.google.com/View?id=dcwqqgns_33dc2ksggh

I agree with you that constraints are an essential part of generics,
so that they can be compile-time checked. As I discuss in my proposal,
the "right" notion of constraint is assignment compatibility with some
type (not just an interface type). This alone does not guarantee
compile-time checkability: there are several other restrictions that
need to be imposed. My proposal results in generics that are about as
powerful as C#'s -- somewhere between Java and C++. One positive
feature is the inability to do template metaprogramming.

I also agree that package parametrization, though conceptually easy,
is not ideal, though the feature I would miss most is the ability to
write generic functions in an otherwise non-generic package.

If you look back through the Go-Nuts discussions, you'll find the Go
team was extremely concerned about compilation efficiency. C++ is
notorious in this regard, the same template might be reparsed and
recompiled often in the course of a single multi-file compilation.
Ian and I came to the conclusion that a repository-based solution,
where compiled template code is stored in one place, might be feasible
for Go.

-Jonathan Amsterdam

[P.S. darcs is really cool.]

On May 17, 11:28 am, David Roundy <roun...@physics.oregonstate.edu>
wrote:

> On Mon, May 17, 2010 at 7:07 AM, roger peppe <rogpe...@gmail.com> wrote:

[Jonathan Amsterdam]

Sorry, I meant to address German Diego in my post as well as David
Roundy. I hadn't noticed that German was the originator of this
thread.

[Jonathan Amsterdam]

> In my experience, templates:
> - Increase tremendously compilation time.
> - Generate code at compilation time, which one has no control over.
> - Make the order in which the files have to be compiled critical (and
> can end-up in circular dependencies).
> - Make the syntax heavier.

Your experience is with C++. Discount it.

> It is usualy impossible to predict the performance of an algorithm,
> since it acts not on a given object, but on a variety of objects.

Exactly true of any variety of dynamic dispatch (e.g. Go's
interfaces).

> Last but not least : It encourages "template meta-programming" ...

It encourages it only if it allows it.

[german diago]

> One positive
> feature is the inability to do template metaprogramming.

I agree. Template metaprogramming is an advanced feature that makes
code
unreadable many times. The primary reasons for
generics is type-safe type system AND avoiding unboxing for primitive
types. But
I think that writing generic code that performs well is a reason as
well. C++ allows this,
but it is complicated to master the trick. For example, in C++ you can
overload
algorithms so that they select the most efficient version. This would
be nice to be able
to do it in Go, since it is a systems programming language. That's why
I think that alias
inside interfaces should be allowed in the first place.

And generic function constraints should be allowed too, as a way to
avoid the mess that is
c++ in this regard, which has no constrained templates.

[chris dollin]

If we want template metaprogramming, can't we write
wrappers for Go which do it?

Then we don't confuse the core language with the metalayer
and leave room to experiment over time.

It would mean the Go compiler toolchain opening up
some APIs for later code to use the same base typechecker
etc, and maybe to allow nodes to carry metadata annotation,
but I don't see that being a particular problem.

Chris

--
Chris "allusive" Dollin

[german diago]

On 17 mayo, 18:12, Jonathan Amsterdam <jbamster...@gmail.com> wrote:
> David,
> You probably arrived to Go-Nuts after I posted my generics proposal,
> so I'll repeat the link:
>
> http://docs.google.com/View?id=dcwqqgns_33dc2ksggh

I like the proposal. In fact, it's very similar to mine. But it fails
in this case, which I think
it's fairly useful:


type<T> ForwardSequence interface {
getNext() ??
}

What is the return type of a ForwardSequence? That's not possible to
do without alias types.

For example, if T is a vector.Vector<int>, int should be an alias for
the element type in type Vector<T> struct . You should be able
to unintrusively say alias for existing types as well (but don't know
how). This way you could have something like

type<T> ForwardSequence interface {
alias T.ElementType ElementType

getNext() ElementType
}

Alias types are important for generic code. Otherwise there is no way
to refer to some of the things you would like
a function to return, for example.

[Ian Lance Taylor]

Speaking only for myself, these are some of the important issues.

* The syntax must continue to be easy to parse without a complete
symbol table.

* Compiling (and linking) a program must continue to be very fast.

* It must be possible to write generic algorithms--generics should
imply more than just type-safe containers.

* It must be possible to write algorithms which are generic across
types which have different runtime representations. E.g., range
works on slices, channels, and arrays; a generic algorithm should be
permitted to use range with a value of generic type; those types
have different sizes at runtime. (This is no big deal if we
recompile the generic each time it is used, but that works against
the compilation time goal.)

* As much as possible, type errors should be detected at compile time.
(The trade off between a reasonably terse syntax and good error
detection is complex, and will probably require experimentation.)

Ian

[Jonathan Amsterdam]

I think I could express that as:

type<T Sequence<E>> ForwardSequence interface {
getNext() E
}

where Sequence<T> is a generic interface.

[Cyril Zorin]

What if Sequence has type parameters that are irrelevant for the
declaration of ForwardSequence? It would be annoying to have to write
them all. What if the parameter list of Sequence changes at the source
in some trivial way? It would be even more annoying to edit all sites
where Sequence<A,B,C> is used.

Perhaps another way to tackle this issue is with "exported types", for
the case of generic structs and interfaces. That is to say, type
parameters that start with a lowercase letter are internal to the
generic, and those that start with a capital letter are exported and
can be referenced using some syntax, say Sequence.ElementType. It
would make it more difficult to use identifiers like "U" and "T" for
types, but in my opinion those aren't good identifiers anyway...

K

[german diago]

Yes, that's a way too xD. Thanks for the suggestion.

> Speaking only for myself, these are some of the important issues.
>
> * The syntax must continue to be easy to parse without a complete
> symbol table.
>
>* Compiling (and linking) a program must continue to be very fast.

>* It must be possible to write generic algorithms--generics should
> imply more than just type-safe containers.

I strongly agree with the 3rd point. It's essential to be able to
write generic code.
But my question is: without overloading and specialization a la C++
templates,
how is it possible to be sure it's selecting the appropiate algorithm
for the type (the most optimized)?
It's one of the strong points in generic programming: to select the
best overload.
Maybe you should be able to overload function templates based on the
interface
they meet and selecting based on the most specialized interface (like c
++0x concepts)? For example,
a sort algorithm should be faster on a vector than on a linked list,
because a linked
list does not have random access. Maybe overloading of templates
should be allowed.
After all, you have to mangle the name in some way for a template
function if you generate it:

func Sort<T RandomAcessSequence>(s * T)
func Sort<T BidirectionalSequence>(s * T)

>* It must be possible to write algorithms which are generic across
> types which have different runtime representations. E.g., range
> works on slices, channels, and arrays; a generic algorithm should be
> permitted to use range with a value of generic type; those types
> have different sizes at runtime. (This is no big deal if we
> recompile the generic each time it is used, but that works against
> the compilation time goal.)

It's a problem if you want fast compile times. But I think that using
a Java-like
model with type erasure isn't the way to go either. Maybe the solution
is some
kind of runtime support to generate code from an intermediate
representation.
But this needs runtime support, of course.

>* As much as possible, type errors should be detected at compile time.
> (The trade off between a reasonably terse syntax and good error
> detection is complex, and will probably require experimentation.)

I agree as well.

>On 17 mayo, 20:28, Jonathan Amsterdam <jbamster...@gmail.com> wrote:
> I think I could express that as:
>
> type<T Sequence<E>> ForwardSequence interface {
>     getNext() E
>
> }

Ok, that's another way :-)

[Stanley Steel]

Could somebody explain to me what value a generic would have over the
current implementation of dynamic interfaces? I can now write a generic
algorithm that works on a type of specific interface. The only gain is
not having to cast, right?

[roger peppe]

efficiency and static type checking.

[Ian Lance Taylor]

Take a look at the sort package. It can sort any container which
supports a few methods. It would be nice to be able to sort a slice
of any type T, where T supports a Less method. However, there is no
easy way to write that. The problem is that []T where T is an
interface value has different storage requirements compared to []int.
So the sort package has to provide IntArray, FloatArray, and
StringArray, which is nice but doesn't help if you happen to have
[]int64. It would be nice if passing []int64 to sort did not require
writing helper methods which are pure boilerplate.

This argument can be extended to more complex cases. In general,
generics should make it possible to write generic algorithms which can
then be applied to disparate runtime types.

Ian

[Marcin 'Qrczak' Kowalczyk]

2010/5/17 Serge Hulne <serge...@gmail.com>:

> Hi there,
>
> In my experience, templates:
> - Increase tremendously compilation time.

Possibly.

> - Generate code at compilation time, which one has no control over.

Possibly.

> - Make the order in which the files have to be compiled critical (and
> can end-up in circular dependencies).

I have no idea what do you mean.

> - Make the syntax heavier.

Yes. But lack of generics introduces other heaviness, like explicit
downcasts, or code duplication for different types, or additional
interfaces.

> It is usualy impossible to predict the performance of an algorithm,
> since it acts not on a given object, but on a variety of objects.

The same can be said about interfaces. It is usually impossible to
predict the performance of an algorithm, since functions it calls via
interfaces act on a variety of objects.

> Last but not least : It encourages "template meta-programming" which
> yields extremely unreadable code with unpredictible performance (see
> www.boost.org )

Only if the language does not provide any other way of compile time
expansion (e.g. Lisp-like macros).

--
Marcin Kowalczyk

[Jonathan Amsterdam]

> But my question is: without overloading and specialization a la C++ templates,
> how is it possible to be sure it's selecting the appropiate algorithm
> for the type (the most optimized)?
> It's one of the strong points in generic programming: to select the best overload.
> Maybe you should be able to overload function templates based on the interface
> they meet and selecting based on the most specialized interface (like c
> ++0x concepts)? For example,
> a sort algorithm should be faster on a vector than on a linked list, because a linked
> list does not have random access. Maybe overloading of templates should be allowed.
> After all, you have to mangle the name in some way for a template
> function if you generate it:
>
> func Sort<T RandomAcessSequence>(s * T)
> func Sort<T BidirectionalSequence>(s * T)

I have nothing bad to say about generic programming. It is elegant and
powerful. But the question for Go is, at what price? Adding template
overloading, specialization, etc. goes beyond what is necessary. To
select the best algorithm for the data structure, I recommend using
ordinary dynamic dispatch:

type Sorter interface { Sort() }

Sorter s = ...
s.Sort()

Now my linked list and vector packages can each implement Sort in
their own preferred way, and voila! the best algorithm is selected.

So what are the touted advantages of selecting algorithms in the
generic programming way?

Fast -- it happens at compile time: Yes, but we're talking about
algorithms here, essentially none of which run in constant time. The
cost of a dynamic dispatch is going to be negligible.

Type-safe: Go interfaces provide that.

Decouples algorithms from classes: this is the generic-programming
iterator idea. It makes a lot of sense in an OO language. Why bloat
vector with lots of methods like find, sort and so on, when it need
only provide an iterator of the appropropriate type? We can always
provide specialized implementations on the class if needed, like
List::sort. And how nice it is to be able to add an algorithm that
works immediately on existing types, without modifying them.

But Go is not an OO language, and interfaces already give you all
that! Existing data structures will work with your new algorithms if
they have the methods that the algorithm needs--no need to retrofit
the inheritance hierarchy. And it's easy using type tests to write
algorithms that work in a general way, but defer to specializations
when provided, by using type assertions. For instance, here are the
first few lines of io.Copy:

func Copy(dst Writer, src Reader) (written int64, err os.Error) {
// If the writer has a ReadFrom method, use it to to do the
copy.
if rt, ok := dst.(ReaderFrom); ok {
return rt.ReadFrom(src)
}
// Similarly, if the reader has a WriteTo method, use it to to
do the copy.
if wt, ok := src.(WriterTo); ok {
return wt.WriteTo(dst)
}
// .... general copying code ...


Again, the run-time cost will be trivial for nearly all algorithms.

[Serge Hulne]

> - Make the order in which the files have to be compiled critical (and

> can end-up in circular dependencies).

I have no idea what do you mean.

Here is what I meant (example taken from the C++ implementation of templates):

If one creates the following two source files:  A.cpp and B.cpp (and A.h , B.h), which contain resp.the two following template classes :

template <B> class A {
... ;
}

and

template <A> class B {
... ;
}

A uses B as a type parameter in a template and vice-versa.
By so doing one refers, ahead of time, to some code (expected to be generated via a template) which does not yet exist ... because said code has not yet been generated !

Some compilers will accept it, some (e.g. GNU g++) won't because they can't deal with that catch 21 situation.

Serge.

[Peter Williams]

On 18/05/10 04:23, Ian Lance Taylor wrote:
> * As much as possible, type errors should be detected at compile time.
> (The trade off between a reasonably terse syntax and good error
> detection is complex, and will probably require experimentation.)

I'd up this from "as much as possible" to "without exception".

One (minor) problem with using interface/embedding to do the kind of
coding that generics could help with is that it is sometimes not
possible to write code where type checking is possible at compile time
as an interface can sometimes be too inclusive. My major hope for
generics in Go is that it would eliminate this problem and if it doesn't
there'd be no point in having generics (in my opinion).

I'd be happy without generics if there was a way to tell the compiler
that when I declare a variable of some polymorphic container type that
it was my intention to use it with a specific type (or set of types) and
the compiler then rejected any code I wrote that violated my intention.
This way the implementation of the polymorphic container type can be
as broad as possible but I can use it in a (compile time checkable) type
safe manner.

I much prefer polymorphism to templates as the latter tend to lead to
bloated executables in my experience. But it would be nice to have a
little more control.

Peter
PS The good thing about Go is that it has good support for run time
checking which makes those occasions where run time type checking is the
only option much less troublesome than they could be.

[Peter Williams]

On 18/05/10 06:51, Ian Lance Taylor wrote:
> Stanley Steel<st...@kryas.com> writes:
>
>> Could somebody explain to me what value a generic would have over the
>> current implementation of dynamic interfaces? I can now write a
>> generic algorithm that works on a type of specific interface. The
>> only gain is not having to cast, right?
>
> Take a look at the sort package. It can sort any container which
> supports a few methods. It would be nice to be able to sort a slice
> of any type T, where T supports a Less method. However, there is no
> easy way to write that.

If it doesn't have to be an in place sort it can be done.
I've written a package that can sort the contents of a slice of any type
T that supports Less. The package is available at
<https://code.google.com/p/mudlark-go-pkgs/>. It's still being tested
but examples of its intended use would be:

import "mudlark/sort"

var data []TypeThatSupportsLess

// some code here to put some stuff in data then

data = sort.SortSlice(data) // same result as an in place sort

or iterate over it in order:

for datum := range sort.SortSlice(data) {
do something with datum.(TypeThatSupportsLess)
}

It provides several similar functions that do extras like filtering out
duplicates and/or reverse sorts. There are also functions that take a
<-chan as input (and return a <-chan) that are intended for use with
containers which provide a channel based iterator e.g.

var data vector.IntVector

for datum := range sort.SortChan(data.Iter()) {
do something with datum.(int)
}

NB

data = sort.SortChan(data.Iter())

wouldn't work and something more complicated would be required to
achieve the aim expressed in that snippet. Something like:

channel := sort.SortChan(data.Iter())
data = make(vector.IntVector, data.Len())
for datum := range sort.SortChan(channel) {
data.Push(datum.(int))
}


Of course, the penalty for using:

data = sort.SortSlice(data)

instead of an in place sort is that it requires more memory so there may
be occasions where memory limitations make it not viable. So it doesn't
remove the need for the in place sort provided by the standard sort
package but where it's viable it provides a simpler interface (IMHO).

Peter
PS It would've been a major headache writing the equivalent
functionality in a language other than Go.

[Marcin 'Qrczak' Kowalczyk]

2010/5/18 Serge Hulne <serge...@gmail.com>:

>
>> - Make the order in which the files have to be compiled critical (and
>> > can end-up in circular dependencies).
>>
>> I have no idea what do you mean.
>
> Here is what I meant (example taken from the C++ implementation of
> templates):
>
> If one creates the following two source files:  A.cpp and B.cpp (and A.h ,
> B.h), which contain resp.the two following template classes :
>
> template <B> class A {

I don't understand. If you mean:

template<typename B> class A {

then the B name here has nothing to do with the global B class
template, and can be locally changed. I don't know what else you could
mean.

--
Marcin Kowalczyk

[David Roundy]

Indeed, your proposal matches reasonably well with what I'd like to
see. Kiril's concern about aliases is quite a reasonable one, though.
It's quite common that we want return values to be the same as a
given type. ,e.g. your LessInterface example oddly allows for a type
T to be a LessInterface<U>, where T and U are different, which
certainly isn't the intent for a LessInterface. It's not a huge wart,
but it'd be nice to be able to write an interface that explicitly says
that it returns the same type.

On another subject, do you (or others) have any ideas as to how to
approach an implementation (since probably an implementation should
precede a consensus)? I tried a "macro expansion" approach with gotgo,
but it doesn't look like that'll work well for non-package-oriented
generics, since you want generic functions or types to be declarable
in any package and used in any other package. For purposes of
experimentation, it seems best to go with a "generic" implementation,
so the compile time remains fast, with a runtime performance unboxing
penalty. And that ought to be easier to implement. If constraints
were restricted to be interfaces (rather than
assignment-compatibility), then the "generics" compiler (implemented
as a source-to-source transformation) might simply need to add type
assertions to calls to an ordinary non-generic interface function.
Hmmm. I really shouldn't spend time on this...

David

--
David Roundy

[NoiseEHC]

Now that you want to support generic algorithms, does it mean that you will reconsider not having built in interfaces with meaning?

I talk about something like this:
interface IMath<T> {
��� Add(A T, B T) T
��� Sub(A T, B T) T
}

What about IChan<T> and ISlice<T> and the like?

[Serge Hulne]

Hi Marcin,

You're right

This code snippet was rubbish !
I' ll post a real example (to illustrate a catch 21 situation
resulting from the use of templates in C++) later today.

Serge.



On May 18, 6:28 am, "Marcin 'Qrczak' Kowalczyk" <qrc...@knm.org.pl>
wrote:
> 2010/5/18 Serge Hulne <serge.hu...@gmail.com>:

[Peter Williams]

On 18/05/10 11:20, Peter Williams wrote:
> On 18/05/10 06:51, Ian Lance Taylor wrote:
>> Stanley Steel<st...@kryas.com> writes:
>>
>>> Could somebody explain to me what value a generic would have over the
>>> current implementation of dynamic interfaces? I can now write a
>>> generic algorithm that works on a type of specific interface. The
>>> only gain is not having to cast, right?
>>
>> Take a look at the sort package. It can sort any container which
>> supports a few methods. It would be nice to be able to sort a slice
>> of any type T, where T supports a Less method. However, there is no
>> easy way to write that.
>
> If it doesn't have to be an in place sort it can be done.
> I've written a package that can sort the contents of a slice of any type
> T that supports Less. The package is available at
> <https://code.google.com/p/mudlark-go-pkgs/>. It's still being tested

The testing indicates that this doesn't work exactly as I expected.

> but examples of its intended use would be:
>
> import "mudlark/sort"
>
> var data []TypeThatSupportsLess

It turns out that this needs to be:

var data []sort.Item

as you can't use a []TypeThatSupportsLess for a []sort.Item parameter to
a function.

>
> // some code here to put some stuff in data then

But you put instances of type TypeThatSupportsLess into that array.

>
> data = sort.SortSlice(data) // same result as an in place sort
>

So it's not quite as simple to use as I thought it would be but still
usable. Just means more use of .(TypeThatSupportsLess) when accessing
the items in data.

I'm going to have another read of the assignment rules for slices/arrays
and do some more experiments to figure out exactly what they mean.

Peter

[Ian Lance Taylor]

NoiseEHC <Nois...@freemail.hu> writes:

> Now that you want to support generic algorithms, does it mean that you
> will reconsider not having built in interfaces with meaning?

I don't grok the phrasing of this question. Generics have always been
on the roadmap. That doesn't mean that they will be implemented, but
it does mean that they are being considered. To be nitpickingly
pedantically clear, I didn't say that Go will support generic
algorithms; what I said was that, in my personal opinion, not speaking
for the entire Go team, if Go gets some sort of generic support, it
must be sufficient to support generic algorithms.

> I talk about something like this:
> interface IMath<T> {

> Add(A T, B T) T

> Sub(A T, B T) T
> }
>
> What about IChan<T> and ISlice<T> and the like?

I agree that if Go supports generics, it should have some form of
generic interfaces.

Ian

[chris dollin]

But, may it please all, not with names routinely beginning with "I",
nor with brackets spelled "<" and ">".

--
Chris "allusive" Dollin

[Jonathan Amsterdam]

> On another subject, do you (or others) have any ideas as to how to
> approach an implementation (since probably an implementation should
> precede a consensus)?

I think there are still many design issues to resolve before anyone
writes any code. I don't mean nit-picky things, I mean major things.
Like:

- As I discuss in the proposal, generics are almost useless unless
built-in types have certain methods. E.g. int should have the method
Less(int) bool. That needs to be worked out in detail, with names for
all the methods, and interactions with other parts of the language.
E.g. I can now write 3.Less(4) in Go. Is that a problem for the
parser? For type checking?

- This is something that's bothered me for a while: say I define a
generic type G in package p1 that refers to private package-level
names in p1. I then instantiate G in package p2, using a type private
to p2 as argument. Where does G live? If it lives in p1, it can't see
p2's private type. If it lives in p2, it can't see private names in
p1. The simplest way out is to outlaw generics from referring to
anything private in their package. But then you can't even write a
private helper function or type for your generic implementation. How
much of a problem is that in practice? Is there another way out of the
dilemma?

- Last but not least: syntax. It's extremely hard to design a nice
syntax for generics that doesn't run afoul of the "no consulting the
symbol table during parsing" rule. I don't think angle brackets can
work, because given a sequence of tokens "a < b", the parser won't
know whether that is a less-than expression or the start of the name
for a generic type. Square brackets are probably going to get confused
with array/slice notation. E.g. "type A [ B ] C". Is that declaring A
to be type [B]C (where B is a const) or is it declaring the generic
type A[B] to be C? Whatever syntax you come up with has to work for
type declarations, uses of a type (in other declarations, type
assertions, etc.) and between the name of a function and its
arguments, for generic function calls. I thought a lot about this at
one point, and the best I could come up with was A@[T, U], or just A@T
if there was one type parameter. And I'm not even sure that works in
all cases.

> For purposes of
> experimentation, it seems best to go with a "generic" implementation,
> so the compile time remains fast, with a runtime performance unboxing
> penalty.  And that ought to be easier to implement.  If constraints
> were restricted to be interfaces (rather than
> assignment-compatibility), then the "generics" compiler (implemented
> as a source-to-source transformation) might simply need to add type
> assertions to calls to an ordinary non-generic interface function.

I like the idea of the "generic" implementation, but a while ago Ian
convinced me it was impossible, even in the absence of constraints.
Consider func f<T>(a []T) for differently-sized values of T. Any use
of a[.], even simply retrieving a value, will generate different code.

[Marcin 'Qrczak' Kowalczyk]

2010/5/18 Jonathan Amsterdam <jbams...@gmail.com>:

> - This is something that's bothered me for a while: say I define a
> generic type G in package p1 that refers to private package-level
> names in p1. I then instantiate G in package p2, using a type private
> to p2 as argument. Where does G live?

In p1, if the question is meaningful at all. This should not prevent
the instantiation with a private type in p2, because the instantiation
is done in p2.

Privacy should be resolved statically when names are written, not
after an imaginary generic expansion. There is no problem.

--
Marcin Kowalczyk

[Jonathan Amsterdam]

> > - This is something that's bothered me for a while: say I define a
> > generic type G in package p1 that refers to private package-level
> > names in p1. I then instantiate G in package p2, using a type private
> > to p2 as argument. Where does G live?
>
> In p1, if the question is meaningful at all. This should not prevent
> the instantiation with a private type in p2, because the instantiation
> is done in p2.
>
> Privacy should be resolved statically when names are written, not
> after an imaginary generic expansion. There is no problem.

First, to clarify (for others, not you -- you got it), the question is
not "Where does G live?" -- plainly p1, it is declared there -- but
"Where does G[t] live?" You may be right that it's just a matter of
interpreting privacy in the right way. But at least this much is
clear: there is no piece of legal Go source code that is the
definition of G[t]. That has implications for the implementation, I
would think.

[jimmy frasche]

If I may, I believe that NoiseEHC meant something like interfaces
baked into the language that primitive types satisfy. I've mentioned
something similiar before and have been thinking about it lately.

Say there was such an interface:
magictype Indexable $Key $Value { //ignore my foolish imaginary syntax
At(k Key) Value
}

For arrays, slices, and maps this would be a verbose synonym for []
(with Key fixed to int for arrays and slices, naturally). Given a
variable, A, of type []int you could write A[0] or A.At(0).

This would allow you the choice to write a function for any built in
type that supported indexing or any user defined type that satisfies
the Indexable interface, allowing generic code to be written that can
work with primitive and non-primitive types in a homogenous fashion.

There are some obvious downsides to this approach; namely, having to
concoct a great number of such granular built-in interfaces, it being
in a way like operator overloading, etc. But it would allow user types
to play nice with Go's built-ins, such as range being able to take
anything that implements Iterable without an explicit .Iter() or len
being able to take any Measurable, etc, and would allow for writing
algorithms that worked equally well with primitive types and user
types at the cost of not being able to use the short hand of operator
syntax (+, <, [], and so on).

The biggest downside is that it would be part of the language and not
a convention like Iter(), Less(), etc, are now, but, to me at least,
it seems like a simple enough idea that would go hand in hand with any
generic scheme that may make it into the language.

I'll end with some more examples of some such built in interface I
think would be useful:
an Number interface satisfied by all the numeric types that defines
synonyms for all the arithemetic operations (and further assumes
commutative * and + so a Matrix type would have to have it's own
matrix multiply method and use the synonym for * for scalar
multiplication)
a PartiallyOrdered and TotalOrdered interface that define the
comparison operations
an OrderedNumber interface that is just {TotalOrdered; Number} that
satisfies all the noncomplex numeric types
a Sliceable interface
The already mentioned Iterable, Measurable, and Indexable.

I also think that some operations should NOT have synonyms: No
Callable, no Derefable, no Newable, no Makeable.

This is by no means a complete proposal, just a sketch of an idea.

[Steven]

I think methods on built-in types is a non-issue. All you need is a package of derived types with the methods (which is perfectly possible, especially with generics). The package only has to be written once, and could include all the methods you would imagine being attached to the primitive types, as well as interfaces for generalizing various common behaviours.

[Jonathan Amsterdam]

> If I may, I believe that NoiseEHC meant something like interfaces
> baked into the language that primitive types satisfy. I've mentioned
> something similiar before and have been thinking about it lately.
>
> Say there was such an interface:
> magictype Indexable $Key $Value { //ignore my foolish imaginary syntax
>         At(k Key) Value
>
> }
>
> For arrays, slices, and maps this would be a verbose synonym for []
> (with Key fixed to int for arrays and slices, naturally).  Given a
> variable, A, of type []int you could write A[0] or A.At(0).
>
> This would allow you the choice to write a function for any built in
> type that supported indexing or any user defined type that satisfies
> the Indexable interface, allowing generic code to be written that can
> work with primitive and non-primitive types in a homogenous fashion.
>
> There are some obvious downsides to this approach; namely, having to

> concoct a great number of such granular built-in interfaces, ...

Agreed. But don't need to think about interfaces, just methods. It
suffices that arrays, slices, maps and strings implement the At()
method -- no need to say anything about an Indexable interface. I can
write that interface later, in my code, and call it anything I want
(or leave it anonymous), and all those types will conform to it. One
of the great things about Go interfaces.

[Beoran]

I was reading a bit aboout generics on Wikipedia:

http://en.wikipedia.org/wiki/Generic_programming

It occurred to me that what we want for Go might be much closer to ADA
style generics. C++ style "generics" are basically a Turing complete
hygienic macro system.

So how about doing something ADA-like like this in stead:
1) define two new keyword, "generic" and "specify".
2) then you can do :

generic(T) func frobnicate(foo T) {
...
}

generic(T) type Stack struct {
T stack
}

func frobnicateInt specify frobnicate(int);
type IntStack specify Stack(int);

Again, just an idea for you all to kick around.

[Ian Lance Taylor]

Steven <stev...@gmail.com> writes:

> I think methods on built-in types is a non-issue. All you need is a package
> of derived types with the methods (which is perfectly possible, especially
> with generics). The package only has to be written once, and could include
> all the methods you would imagine being attached to the primitive types, as
> well as interfaces for generalizing various common behaviours.

It's a tiny bit more complicated than that. Your suggested package
could attach methods to a new type Int, but uses of int would not pick
up those methods. Other people's code could use Int, of course, but
if they wanted their own integer type, then the type directive would
drop the methods attached to Int.

That is, the language does not provide any facility for defining
methods on an unnamed primitive type, nor for adding to a set of
methods already defined for a named primitive type. So some language
change is required for convenient use, though not necessarily a
particularly complicated one.

Ian

[Tonic Artos]

On 19 May 2010 02:07, Ian Lance Taylor <ia...@google.com> wrote:
<snip>

> pedantically clear, I didn't say that Go will support generic
> algorithms; what I said was that, in my personal opinion, not speaking
> for the entire Go team, if Go gets some sort of generic support, it
> must be sufficient to support generic algorithms.

Don't we already nearly have generic algorithms through the use of
interfaces? All that is needed now is for the type to be preserved
throughout the algorithm.

I imagine generics giving me, a Go programmer, the useful ability to
plug a type into any generic datastructure or function and get the
same type back out the other end. Of course many datastructures will
need to operate on my type so there should be some kind of constraint
based on interfaces declared up front. "You can plug in any type you
like as long as it conforms to A, B and C." Also it would be useful to
be able to declare generic types and constraints on the 'per package',
and 'per function' levels.

There does remain the slight problem of primitive types versus
declared types, where primitive operations such as +, >, and others,
have no meaning for programmer declared types. One solution is to
allow the programmer to define these operations somehow. Another
solution would be to create different classes of generics;
1) a generic that can take any type (primitive or not) but cannot
operate on the passed value.
2) a generic that can operate on the passed value but can only take
non primitive types that satisfy a specified set of interfaces.
3) a generic that can operate on the passed value but can only take
primitive types.
The third approach is to simply allow generics only for programmer
declared types and have tailored implementations for primitives.

[Ian Lance Taylor]

Tonic Artos <ghata...@gmail.com> writes:

> Don't we already nearly have generic algorithms through the use of
> interfaces? All that is needed now is for the type to be preserved
> throughout the algorithm.

Yes, "nearly" is the operative word. We have generic algorithms as
long as you restrict yourself to using methods on values of interface
type. But there are many cases that don't fit that model.

For example, let's say you want to write an algorithm which involves
sending values of some type T on a channel of type chan T. The only
way to do that is to add a method on the channel type which looks
something like

type T whatever
type ChanT chan T
func (p ChanT) Send(x interface{}) {
p <- x.(T)
}

You need to write that boilerplate method for every channel type you
want to pass to the algorithm, which is tedious. The operation
involves boxing and unboxing the type in an interface{}, though that
is not too serious as it is fairly efficient. Much more serious is
the absence of compile-time type checking of calls to the Send method;
only runtime type checking is possible. And, fatally, you can't use
this generic channel in a select statement.

Ian

[Tonic Artos]

Yes. Do you have any opinion on the rest of what I wrote?

[Ian Lance Taylor]

Tonic Artos <ghata...@gmail.com> writes:

> Yes. Do you have any opinion on the rest of what I wrote?

No useful opinion, sorry.

Ian

[Russ Cox]

> The generic approach is more or less obvious:

Less, if you ask me.

http://golang.org/doc/go_lang_faq.html#generics
is short but accurate.

The rest of your mail reads like someone reveling in
having built something complex that actually works.
It's an addictive feeling - why do you think there are
so many C++ programmers? - but I think in general
it is counterproductive.

It has been interesting to me to see programmers who
have written substantial amounts of Go code, even
outside the core Go team, say that on balance they
don't really miss generics and would not want to see
them unless they fit well with the rest of the language.
(Petar just said something like that in one of his Tonika
blog posts, and someone else said it earlier on the list.)

The kind of explicit type-oriented programming that
seems inherent to the C++/Java/C# approach to "generics"
is exactly the kind of heavyweight clumsy spell everything
out for the compiler programming that Go strives so hard
not to be.

Russ

[Marcin 'Qrczak' Kowalczyk]

2010/5/21 Russ Cox <r...@golang.org>:

> The kind of explicit type-oriented programming that
> seems inherent to the C++/Java/C# approach to "generics"
> is exactly the kind of heavyweight clumsy spell everything
> out for the compiler programming that Go strives so hard
> not to be.

It's just statically typed programming without type inference.

For me trying to enforce static typing, but resorting to effectively
dynamic typing with explicit downcasts when using "generic"
implementations of fundamental algorithms and data structures (like
sorting or a heap), excluding a few builtin constructs treated
specially by the language (like maps or channels) - is clumsy. More
clumsy than pure dynamic typing, or than pure static typing.

Not that embedding a dynamially typed mechanism in an otherwise
statically typed language is a fundamentally bad idea; sometimes it's
the only reasonable tool, since static typing is not as expresive to
fit every possible program design. But it's not acceptable to have to
resort to this ugly embedding for such fundamental things like
non-builtin data structures.

I see that Go designers love C, but this is what C got wrong, and Go
copied (with minor tweaks like adding more builtin generic data
structures). C# and C++ got this aspect acceptably right.

--
Marcin Kowalczyk

[Giles Lean]

Russ Cox <r...@golang.org> wrote:

> It has been interesting to me to see programmers who
> have written substantial amounts of Go code, even
> outside the core Go team, say that on balance they
> don't really miss generics and would not want to see
> them unless they fit well with the rest of the language.

+1, although I haven't said so before.

Possibly relevant points:

o I've written 10,000+ lines of Go code;

o I've seldom used C++: while I've been paid to write C++ at
two sites (briefly), both sites used C++ pessimally, so
perhaps I don't miss what I've seldom had;

o I was nervous about the introduction of exceptions to Go,
but am quite happy about panic()/defer(). If generics could
be fitted in as smoothly, I don't know if I'd celebrate but
I wouldn't complain;

o in both C and Go I've found wrappers an acceptable
substitute, using void * for the "real work" in C and
interface{} in Go, but only calling the type safe wrapper
functions from my application code to get the benefits of
stong type checking.

I haven't had to do even this very often, and am yet to
observe a performance problem. (Which doesn't mean I won't,
but I'll be looking at the compiler optimisation levels and
generated code if I do.)

Giles