Generics

340 views
Skip to first unread message

Jonathan Amsterdam

unread,
Dec 18, 2009, 1:46:16 PM12/18/09
to golang-nuts
Since the Go roadmap says that the Go team is talking about generics,
I thought readers of this group might want to do the same...

To start things off, I wrote a draft proposal for generics in Go,
which you can find at http://docs.google.com/View?id=dcwqqgns_33dc2ksggh.
It's a bit detailed (though not quite detailed enough for a real
spec), but it's easy to summarize in a few sentences:

Types, functions and methods can be made generic by writing them with
type parameters, like so:

type Vector<T> struct { data []T }

You can add a constraint to any type parameter, which is another type.
A constraint C on a type parameter T says that values of type T can be
assigned to variables of type C. Usually, C will be an interface:

type MapKey<T> interface { Hash() int; Equal(T) bool}

type Map<K MapKey<K>, V> struct { ... }

This says that only types T that implement MapKey<T> can be used as
the first parameter of a Map.

For a generic definition to be legal, it must result in legal code for
any types you substitute in, provided those types match the
constraints. And of course, when you use (instantiate) a generic
definition, the types you supply must match the constraints.

This proposal is in the tradition of languages like CLU, Ada, Eiffel,
Java and C# (but not C++). I consider it to be the minimum reasonable
proposal for generics in Go.

Here's a list of things I would love to see happen:

* People find technical flaws in the proposal. (It is statistically
very likely that there are some.) For instance, is there anything else
that needs to be forbidden inside a generic definition to make sure it
is checkable?

* People write some code in Go + generics and see if the proposal is
expressive enough to say what you want. E.g., someone translates the
Boost Graph Library. (There are things there that you definitely
cannot express. What are the workarounds? How much pain is there? Are
there small additions that would help?)

* Someone uses the Go code in go/parser, go/scanner, go/ast, etc., to
build something that will parse and typecheck generics.

* Someone figures out how to implement the proposal with good
efficiency and minimal code bloat. (Might be worth a conference paper,
or maybe a PhD.)

I hope this doesn't turn into a flamewar about why the C++ way (with
or without concepts) is better. I address that a bit in the proposal.
Just keep in mind that we are talking about generics in Go, not in
some idealized language that is perfect for Stepanov-style generic
programming.

John Asmuth

unread,
Dec 18, 2009, 1:57:49 PM12/18/09
to golang-nuts
Personally, I'd rather see the type specification be in the import
statement.

import MyVec "container/vector"<MyElementType>

and then have MyVec be the type, rather than Vector<MyElementType>.

Of course, the issue then would be what to do when you need something
templated inside your current package. Easy to make an infinite
compile loop with...

package thispackage<T>

type TPair struct {
t1, t2 T
}

import MyType "thispackage"<TPair>

So I may have sunk my own proposal. So it goes.

On Dec 18, 1:46 pm, Jonathan Amsterdam <jbamster...@gmail.com> wrote:
> Since the Go roadmap says that the Go team is talking about generics,
> I thought readers of this group might want to do the same...
>
> To start things off, I wrote a draft proposal for generics in Go,

> which you can find athttp://docs.google.com/View?id=dcwqqgns_33dc2ksggh.

Ian Lance Taylor

unread,
Dec 18, 2009, 2:11:58 PM12/18/09
to Jonathan Amsterdam, golang-nuts
Jonathan Amsterdam <jbams...@gmail.com> writes:

> To start things off, I wrote a draft proposal for generics in Go,
> which you can find at http://docs.google.com/View?id=dcwqqgns_33dc2ksggh.
> It's a bit detailed (though not quite detailed enough for a real
> spec), but it's easy to summarize in a few sentences:
>
> Types, functions and methods can be made generic by writing them with
> type parameters, like so:
>
> type Vector<T> struct { data []T }

Thank you for writing this up.

I think the main issue--which is certainly not insurmountable--with
this sort of approach is that it means that at the point of
instantiating a generic function the compiler needs to have access to
a form of the generic source code of the function. Your doc alludes
to this briefly. That means that if you write an exported generic
function in a package, the source code must be copied into the export
data of the package. And it leads to the question of how to handle
the case where the function is imported and instantiated multiple
times by different packages using the same types. The obvious
approaches are to compile it multiple times and discard duplicates in
the linker, which wastes space in the object files and slows down
compilation, or we instantiate the function at link time, which slows
down the linker.

The idea of permitting generic types to be constrained to types like
"chan T", not just interfaces, is a good one.


Here is one type of code it would be nice to write using generics:

func Repeat(x T, n int) []T {
a := make([]T, n)
for i := range a {
a[i] = x
}
return a
}


Here is another:

type Iterable interface {
func Iter() chan T
}

func Range(x Iterable) chan T {
return x.Iter()
}

func f(x Iterable) {
for i := range Range(x) {
...
}
}

I think your proposal can handle both cases with appropriate
instantiation guidance.

Ian

roger peppe

unread,
Dec 18, 2009, 2:36:56 PM12/18/09
to Ian Lance Taylor, Jonathan Amsterdam, golang-nuts
2009/12/18 Ian Lance Taylor <ia...@google.com>:

> func Repeat(x T, n int) []T {
>        a := make([]T, n)
>        for i := range a {
>            a[i] = x
>        }
>        return a
> }

it is largely a syntactic issue, but i do prefer
it when, as above, you don't have to list the
type parameters next to the function name.

several languages would have you do
something like:

func Repeat<T>(x T, n int) []T {

where the <T> adds no information - it
just marks T as a unification symbol. i've
found it tedious in the past.

perhaps it's better to reserve some special syntax
for such symbols (because it's useful to distinguish
them from normal type names). in the same
way that ML uses ' and haskell uses lower case.

you could use a unary "." perhaps:

func Repeat(x .T, n int) [].T {
}

obviously for type declarations you do
need the symbols with the name (because there's no parameter list
as with functions), but maybe it's possible to do:

type (Vector .T) struct { data [].T }

allowing some number of generic-type symbols after
the type keyword.

then you could have (Vector int) etc.

Jonathan Amsterdam

unread,
Dec 18, 2009, 3:16:35 PM12/18/09
to golang-nuts
> I think the main issue--which is certainly not insurmountable--with
> this sort of approach is that it means that at the point of
> instantiating a generic function the compiler needs to have access to
> a form of the generic source code of the function.  

I don't think that's true. At least, it's not supposed to be true. I
think my proposal could be implemented by generating only one function
body. Anyway, it doesn't immediately preclude that approach as a macro-
expanding proposal would. The two hard parts are keeping the generic
type information around for reflection, and handling new. I suppose
new could be done by reflection, but I don't quite see how to do it
for arbitrary types that depend on a type parameter, e.g. []*T. I
haven't though much about it because I don't much like this approach
for performance reasons, but it may be a steppingstone to a better
implementation.

So let's assume you're right:

> And it leads to the question of how to handle
> the case where the function is imported and instantiated multiple
> times by different packages using the same types. The obvious
> approaches are to compile it multiple times and discard duplicates in
> the linker, which wastes space in the object files and slows down
> compilation, or we instantiate the function at link time, which slows
> down the linker.

The first questions to ask are, how much space and how much time? I
believe most of the evidence is from C++, which will have many more
generic instantiations than Go. Isn't it true that every file that
uses std::string instantiates std::basic_string<char>? Even if they've
optimized that case, template metaprogramming has caused an explosion
in C++ template code, and my proposal does not permit template
metaprogramming. And if an implementor is concerned about this, she
can use a generic wrapper around an implementation that uses
interfaces. So whether this idea is a bad one for Go is an open
question.

Now let's assume it does slow things down too much. Then what? I
realize it is a very different exercise to design the ideal
compilation/link scheme, than to build one that works with the current
standard tools (gcc, ld, etc). That said, I don't see why the C++
community gave up on the repository idea. Namely, put the compiled
code for an instantiation somewhere, and look for it before compiling
again. Here are three problems I can see with that, and my naive
solutions.

1. Dependencies: what if the source has changed since the
instantiation was generated? Solution: timestamps on the files, just
as make uses now.

2. Race conditions: we're compiling in parallel, and two processes
both instantiate Vector<int> and overwrite each other's output.
Solution: have them write to temporary files, and rename when done. I
(naively?) believe rename to be atomic on Unix. It doesn't matter who
wins, because the generated code is identical.

3. The generated objects must be included in the final link. Solution:
Makefile writers need to be aware of this, and write something like "./
repository/*.o" on their link lines.

I'm sure you and others can tell me why these ideas suck, and why a
repository-based approach can't work. But as I said in the doc, if we
can just nail down the front end, we can work over time -- and in
parallel -- on better and better implementations.

> I think your proposal can handle both cases with appropriate
> instantiation guidance.

It can certainly express them. (I translated all of exp/iterable.go as
an exercise, and didn't see any problems.) "Instantiation guidance"
sounds ominous to me, though. I hope you don't want me to have to
write in my code, "instantiate Repeat<int> please" before I use it.
That would be nasty.

Brian Slesinsky

unread,
Dec 18, 2009, 3:17:37 PM12/18/09
to golang-nuts

On Dec 18, 2:11 pm, Ian Lance Taylor <i...@google.com> wrote:

> I think the main issue--which is certainly not insurmountable--with
> this sort of approach is that it means that at the point of
> instantiating a generic function the compiler needs to have access to
> a form of the generic source code of the function.  Your doc alludes
> to this briefly.  That means that if you write an exported generic
> function in a package, the source code must be copied into the export
> data of the package.  And it leads to the question of how to handle
> the case where the function is imported and instantiated multiple
> times by different packages using the same types.  The obvious
> approaches are to compile it multiple times and discard duplicates in
> the linker, which wastes space in the object files and slows down
> compilation, or we instantiate the function at link time, which slows
> down the linker.

Perhaps this is restating the obvious, but it seems like the main
issue causing code generation is that for generic types, sizeof(T) is
variable. If generics were restricted to interface types, then there
would be no problem because the size of an interface value is always
the same (implicit boxing), and the result is a lot like Java
generics.

It might be possible to get away with a small number of variants.
Suppose we generate three variations of a generic function:
- code where sizeof(T) is the size of a pointer or smaller (with
padding).
- code where sizeof(T) is the size of an interface value or smaller
(with padding).
- generic code for larger sizes of T, which takes sizeof(T) as a
runtime parameter.

Then it might be okay to generate three versions at compile time. But
such code couldn't work directly with ordinary data structures (such
as []byte) but only with special genericized datatypes with padding
added, implying some kind of conversion.

I suspect that to get the best performance, it's necessary to generate
specialized code for so many different values of sizeof(T) that code
will have to be generated either at link time or maybe even at runtime
via a JIT compiler. JIT compilers do have other advantages such as
optimizing for a specific processor.

- Brian

SnakE

unread,
Dec 18, 2009, 3:18:07 PM12/18/09
to roger peppe, Ian Lance Taylor, Jonathan Amsterdam, golang-nuts
2009/12/18 roger peppe <rogp...@gmail.com>

func Repeat<T>(x T, n int) []T {

where the <T> adds no information - it
just marks T as a unification symbol. i've
found it tedious in the past.

In C++ order of type parameters is important when you want to specify some but let the compiler infer others.  That's why there is a type parameter list very much as there is a function parameter list.

Though I don't think that copying angle brackets from C++ is a good idea either.  I think they bring syntactic ambiguity.  Here's the code:

a := MyType1 < MyType2 > { }

"MyType1 < MyType2" looks like an expression.  Then "expr > { }" looks like a syntax error.  Either look-ahead or semantic knowledge is required to disambiguate this usage which is no good.

D uses !() instead of <> to specialize types, and () instead of <> to introduce type parameters.  So in D style it looks like this:

type Point(T) struct { x, y T }
a := &Point!(int){1, 2}

roger peppe

unread,
Dec 18, 2009, 3:34:31 PM12/18/09
to SnakE, Ian Lance Taylor, Jonathan Amsterdam, golang-nuts
2009/12/18 SnakE <snake...@gmail.com>:

> In C++ order of type parameters is important when you want to specify some
> but let the compiler infer others.  That's why there is a type parameter
> list very much as there is a function parameter list.

you could still do this by creating a new type:
e.g.
type Pair .a .b {x .a; y .b}

func MkPair (x .p, y .q) (Pair .p .q) {
return (Pair .p .q){x, y}
}

type IntMkPair .p func(x int, y .p) (Pair int .p)

var mymkpair = IntMkPair(MkPair)

hmm monomorphism restrictions anyone?

Ian Lance Taylor

unread,
Dec 18, 2009, 3:37:01 PM12/18/09
to Jonathan Amsterdam, golang-nuts
Jonathan Amsterdam <jbams...@gmail.com> writes:

>> I think the main issue--which is certainly not insurmountable--with
>> this sort of approach is that it means that at the point of
>> instantiating a generic function the compiler needs to have access to
>> a form of the generic source code of the function.  
>
> I don't think that's true. At least, it's not supposed to be true. I
> think my proposal could be implemented by generating only one function
> body.

I think that you have to recompile, because []struct{i int} and
[]struct{i int; j int} are different types which are implemented
differently. If you only implement the function body once, you have
to write it for one or the other. I don't see how to write it for
both.

It is of course also possible that I misunderstand your proposal.


> I'm sure you and others can tell me why these ideas suck, and why a
> repository-based approach can't work.

The ideas don't suck, and a repository-based approach can work. g++
even implements it via the -frepo option. The main reason that people
don't use it much is distcc: C++ compilation is slow enough that big
C++ shops use farms of machines as compilation clusters.

It's a good point that Go compilation may be fast enough that we can
reasonably use a repository based approach for instantiated templates;
I had not considered that possibility.


> But as I said in the doc, if we
> can just nail down the front end, we can work over time -- and in
> parallel -- on better and better implementations.

That is true but we must have a clear understanding of how to write
that better implementation before we start.


>> I think your proposal can handle both cases with appropriate
>> instantiation guidance.
>
> It can certainly express them. (I translated all of exp/iterable.go as
> an exercise, and didn't see any problems.) "Instantiation guidance"
> sounds ominous to me, though. I hope you don't want me to have to
> write in my code, "instantiate Repeat<int> please" before I use it.
> That would be nasty.

No, I meant something more like you might have to write Range<MyType>.
If you don't, that would be great.

Ian

jimmy frasche

unread,
Dec 18, 2009, 3:37:30 PM12/18/09
to SnakE, roger peppe, Ian Lance Taylor, Jonathan Amsterdam, golang-nuts
> Though I don't think that copying angle brackets from C++ is a good idea
> either. I think they bring syntactic ambiguity. Here's the code:
>
> a := MyType1 < MyType2 > { }
>
> "MyType1 < MyType2" looks like an expression. Then "expr > { }" looks like
> a syntax error. Either look-ahead or semantic knowledge is required to
> disambiguate this usage which is no good.
>
> D uses !() instead of <> to specialize types, and () instead of <> to
> introduce type parameters. So in D style it looks like this:
>
> type Point(T) struct { x, y T }
> a := &Point!(int){1, 2}
>

I was thinking, in a similiar purely syntactical vein, that there
should be a "type adjective" for parmaterization, like
generic(params) thetype

so that you could do
generic(T) func(a T) []T {...}
as well as
generic(K,V) struct { x K; y V }
etc.


Originally I thought these parameters should be inferred at
instantiation time, but that creates a lot of headaches and would make
it impossible to do
generic(T) func converter(a string) T
for conversion routines as T's inference would have to happen at the
call site making compilation and/or linking more of an ordeal than it
reasonably should be, but the other alternatives are
converter<int>("3") //ugly and terrible
or
converter(int)("3") //confusing
or
converter!(int)("3") // weird
or create a second class metatype so that you can write
generic(T) func converter(T typeof(T), a string) T
called like
converter(int, "3")
which is a terrible hassle

The other alternative is to have type aliases that allow refining parameters
so that
alias toint converter(int) //implicit in this is my feeling that an
alias keyword is superior to type a = b for type aliasing
would give you a function string -> int so that
toint("3")
would work as expected, but that seems like another terrible hassle if
you only want to call toint once

I don't have an answer for this specific case, but I think that the
generic "type adjective" is in general the Go way for generics, at
least syntactically.

Qtvali

unread,
Dec 18, 2009, 3:40:13 PM12/18/09
to golang-nuts
Agree. I think Vector[int] should be considered to make it look like
an array or map of Vector classes.

Also, as another case - I would greatly like to have there a way to
define optional functions. For example, if I create an interface,
which is able to query given set of types of XML files - and this
should be possible to have a list of types -, then if some of those
files do use "name" field and others dont, then "getByName(name
string) []Node" should simply not exist in some use case of this
template. If some interface needs getByName(name string), then it
should not apply. Class might not need this constraint, but a function
needs. This should be allowed.

Also, how those template classes are extended? Can I write
type a struct {
B<Vector[a]>;
}

Also, given that few types, like some specific number types, can have
their own optimizations to some algorithms. I don't suggest compiling
different instances, but I suggest including additional info, which
could make typeswitch really fast - also a good way to check that it
is fast for a given case. If the result of typeswitch with given
instance is known at compile time, type switch should be a simple
comparison of few bytes or smth. inside that template.

Also, could I have some variables declared only if a specific type is
chosen? For example, sorting rational numbers would need some add-ons
for that.

And, if I have:
type IntVector Vector<int>;

Then what about casting that? And what about writing functions, which
belong to IntVector now? Is IntVector a normal type to be used in any
way?

Or:
type IntVector<T int<A>> Vector<int>;

Where intvector itself is typed, but any needed casts happen inside it
- maybe after some checks.

On Dec 18, 10:18 pm, SnakE <snake.sc...@gmail.com> wrote:
> 2009/12/18 roger peppe <rogpe...@gmail.com>

Mark Chu-Carroll

unread,
Dec 18, 2009, 3:42:13 PM12/18/09
to golang-nuts

On Dec 18, 2:11 pm, Ian Lance Taylor <i...@google.com> wrote:

> Jonathan Amsterdam <jbamster...@gmail.com> writes:
> > To start things off, I wrote a draft proposal for generics in Go,

> > which you can find athttp://docs.google.com/View?id=dcwqqgns_33dc2ksggh.


> > It's a bit detailed (though not quite detailed enough for a real
> > spec), but it's easy to summarize in a few sentences:
>
> > Types, functions and methods can be made generic by writing them with
> > type parameters, like so:
>
> >     type Vector<T> struct { data []T }
>
> Thank you for writing this up.
>
> I think the main issue--which is certainly not insurmountable--with
> this sort of approach is that it means that at the point of
> instantiating a generic function the compiler needs to have access to
> a form of the generic source code of the function.  

I don't think so.

There are two different ways of looking at the parametric
declarations in the proposal. One is to think of them as being like
templates: then you need at least one concrete implementation
for each value size3. But the other is to look at them as being
exactly what we do today in Go, but with the parametric type
declaration being used as a correctness annotation.

Right now, vector is implemented as a collection of
"interface { }". You could do the same thing for parametric
declarations: generated code for a parametric declaration
as if the type parameters were "interface { }". At the points
of use, you'd generate the type conversion code, just like we
do manually for the contents of a vector today.

To use the vector example, in code, you'd write vector
parametric on type T. In the implementation of vector, you'd
generate exactly the same code that you do right now where
it's a vector of "interface { }".

For functions that return elements, you'd insert the type conversions.
So if you had:

func f(t *Vector<*T>) {
var bar *T = t.At(12)
}

you'd generate code equivalent to:

func f(t *Vector) {
var bar *T = t.At(12).(*T);
}

There's obviously a runtime performance impact to that - but it's
exactly the runtime
performance impact that we get today for non-generics. You could
generate specialized
code for certain types as an optimization.

-Mark


Qtvali

unread,
Dec 18, 2009, 3:44:03 PM12/18/09
to golang-nuts
An idea of having another type parameter in import seems reasonable if
can be done well. I still would not like to do new import for each
case, so this should be optional use case.

-------------------------------------------------------------------------------------------

I did notice the following:

I have had, as my biggest problem with generics, the fact that they
often do not provide casting rules. I give an example:
* I have a collection of "Cats" as in Vector<Cats>.
* I also have a method, which only takes collections of animals.
* I also have a collection of "Dogs" as in Vector<Dogs>
* I would like to put Cats and Dogs into one array.
* Thus, I will do Vector<Animals>(catvector); cast. This cast is not
possible in Java. Cast is needed to add both arrays to another array
of generic type without recreating an object and without having some
kind of method like catvector.Add<Vector<Dogs>>(dogvector).

If this cast was possible, the following situation would happen:
* I have a classes like "Point2D" and "Point3D". Point3D extends
Point2D. Point3D will return some projected point when used as Point2D
and adds few methods. "Point" interface will return point's position
as array containing at least zero float coordinates.
* I also have a class "CollisionDetector<T Point>", which takes one of
them as input. It has a "register" method for registering objects into
it. Objects can use it's "Try" method to be sure that they do not move
to a position, which already has a point.
* When getting this input, it will make a zero-instance and ask the
number of dimensions from it. After that it will set up some caches
etc. Now it highly depends it's type to be CollisionDetector<T
Point2D> or CollisionDetector<T Point3D> - when cast, it might become
simply broken.

I would like to have clear conversion rules to handle both cases. I do
not vote for any implementation, which does not address this problem,
because it's serious one.

-------------------------------------------------------------------------------------------

How are generics for Lambda functions defined and handled?

-------------------------------------------------------------------------------------------

I could not understand, how it separates struct and interface types.
For example, lets suppose that A is a struct and B is an interface.
Vector<A> - this is allowed to use "make" and "new"
Vector<B> - this is not allowed to use them, but it's allowed to use
B.create() if there is such thing or NewB<B>() if there was NewB with
constraints same or stricter than B's.

-------------------------------------------------------------------------------------------

I will think about the case more, but these are probably the
noticeable problems right now.

roger peppe

unread,
Dec 18, 2009, 3:47:08 PM12/18/09
to Mark Chu-Carroll, golang-nuts
2009/12/18 Mark Chu-Carroll <mchuc...@google.com>:

> At the points
> of use, you'd generate the type conversion code, just like we
> do manually for the contents of a vector today.

that's the sticking point: how do you convert a type

type T<a> struct {
data a
neighbours []T
}

you can't do it without substantial (and unreasonable) overhead.

SnakE

unread,
Dec 18, 2009, 4:03:52 PM12/18/09
to jimmy frasche, roger peppe, Ian Lance Taylor, Jonathan Amsterdam, golang-nuts
2009/12/18 jimmy frasche <soapbo...@gmail.com>

I was thinking, in a similiar purely syntactical vein, that there
should be a "type adjective" for parmaterization, like
 generic(params) thetype

so that you could do
 generic(T) func(a T) []T {...}
as well as
 generic(K,V) struct { x K; y V }
etc.

I like it being very Go-style.

But these are both ambiguous if you replace int with a non-keyword:

converter<blah>("3") //ugly and terrible

"converter<blah" is a valid expression
 
 converter(blah)("3") //confusing

"converter(blah)" is a valid function call, and "converter(blah)("3")" could be a valid expression either if converter returns a function with a single string argument.

Ian Lance Taylor

unread,
Dec 18, 2009, 4:06:12 PM12/18/09
to jimmy frasche, SnakE, roger peppe, Jonathan Amsterdam, golang-nuts
jimmy frasche <soapbo...@gmail.com> writes:

> I was thinking, in a similiar purely syntactical vein, that there
> should be a "type adjective" for parmaterization, like
> generic(params) thetype

Another approach:

type TYPENAME generic [RESTRICTION]

Then a use of TYPENAME makes the type/function/method generic.

The difficulty is knowing how to explicitly instantiate when there are
multiple parameters. One possibility is something like:

NAME{TYPENAME : REALTYPE}

Ian

jimmy frasche

unread,
Dec 18, 2009, 4:07:05 PM12/18/09
to SnakE, roger peppe, Ian Lance Taylor, Jonathan Amsterdam, golang-nuts
> I like it being very Go-style.
>
> But these are both ambiguous if you replace int with a non-keyword:
>
>> converter<blah>("3") //ugly and terrible
>
> "converter<blah" is a valid expression
>
>>
>> converter(blah)("3") //confusing
>
> "converter(blah)" is a valid function call, and "converter(blah)("3")" could
> be a valid expression either if converter returns a function with a single
> string argument.
>

Sorry if I wasn't clear. I've been a little rambly lately, but that
was my intended point. Though I suppose since there's no function
overloading the compiler could tell the difference between a function
instantiation and a function call if all the parameters are valid
types and not values.

Ian Lance Taylor

unread,
Dec 18, 2009, 4:14:20 PM12/18/09
to Qtvali, golang-nuts
Qtvali <qtv...@gmail.com> writes:

> I have had, as my biggest problem with generics, the fact that they
> often do not provide casting rules. I give an example:
> * I have a collection of "Cats" as in Vector<Cats>.
> * I also have a method, which only takes collections of animals.
> * I also have a collection of "Dogs" as in Vector<Dogs>
> * I would like to put Cats and Dogs into one array.
> * Thus, I will do Vector<Animals>(catvector); cast. This cast is not
> possible in Java. Cast is needed to add both arrays to another array
> of generic type without recreating an object and without having some
> kind of method like catvector.Add<Vector<Dogs>>(dogvector).

I think it's useful to avoid mixing this sort of thing with the
general issue of generics. In a language like Go, this issue can be
expressed entirely in terms of slices. It's not really a generics
issue.

That is, the question is whether if Cat is a type, and Animal is an
interface, and Cat satisfies the Animal interface, you can convert
from []Cat to []Animal. The answer right now is no. Whether to
change that answer is not affected by adding generics to the language.


> I could not understand, how it separates struct and interface types.
> For example, lets suppose that A is a struct and B is an interface.
> Vector<A> - this is allowed to use "make" and "new"
> Vector<B> - this is not allowed to use them, but it's allowed to use
> B.create() if there is such thing or NewB<B>() if there was NewB with
> constraints same or stricter than B's.

In Jonathan's proposal it is not obvious to me that Vector<A> is
permitted to use make and new. I think his proposal restricts a
generic function to using only the operations which are permitted for
the constraining type in the generic definition.

Ian

jimmy frasche

unread,
Dec 18, 2009, 4:29:49 PM12/18/09
to Ian Lance Taylor, SnakE, roger peppe, Jonathan Amsterdam, golang-nuts
> Another approach:
>
> type TYPENAME generic [RESTRICTION]
>
> Then a use of TYPENAME makes the type/function/method generic.
>
> The difficulty is knowing how to explicitly instantiate when there are
> multiple parameters. One possibility is something like:
>
> NAME{TYPENAME : REALTYPE}

I'm afraid that I'm not quite sure what you're getting at here. I
think it may follow from a lack of clarity in my first post. For the
record, I meant generic to be used like

type pair generic(T) struct { a, b T }

but never said so explicitly. Also, I was only proposing syntax and
not a means to infer paramaterization or instantiate the type.

Also, since I didn't say anything about methods I think it would be
best if they just inherited the paramaterization of their named type

ie

type name generic(T) struct {...}

func (self name) someFunc(a T) T {...} //no need to redeclare each
time. Unless there's a type specilization (should that be supported)

NoiseEHC

unread,
Dec 18, 2009, 4:56:10 PM12/18/09
to Ian Lance Taylor, Jonathan Amsterdam, golang-nuts

> I think the main issue--which is certainly not insurmountable--with
> this sort of approach is that it means that at the point of
> instantiating a generic function the compiler needs to have access to
> a form of the generic source code of the function. Your doc alludes
> to this briefly. That means that if you write an exported generic
> function in a package, the source code must be copied into the export
> data of the package. And it leads to the question of how to handle
> the case where the function is imported and instantiated multiple
> times by different packages using the same types. The obvious
> approaches are to compile it multiple times and discard duplicates in
> the linker, which wastes space in the object files and slows down
> compilation, or we instantiate the function at link time, which slows
> down the linker.
>

This is the same thinking that Russ Cox showed us here:
http://research.swtch.com/2009/12/generic-dilemma.html
I have offered an alternative in the comments just did not get any
response but you know I am getting to be used to that.
Anyways, here is another half-finished "proposal" you can chew on:

I see this problem as an optimization problem rather that a language
design problem so please forgive me if my "proposal" does not address
any fancy features and only touches implementation details (I also skip
syntax because it does not matter, something like C++ or C# or
Jonathan's proposal would be adequate). So, as I see it, either the
compiler must generate one or two versions of generic machine code (or
more than two, the point is that it is a finite number), or the compiler
can store some intermediate code representation and create the final
machine code in link time (it means run or install time). What I see is
that people on this list expect to have some speed advantage from
knowing the size of the generic type parameter but it simply will not
happen. Accept it! The speed advantage comes from inlining the addresses
of the generic type's methods (this is related to the processor's jump
prediction) or the code of the methods itself (and so specializing all
the generic code to the actual generic type). Since it would require
runtime code generation which would require redesigning all of Go it
just simply will not happen. (.NET does exactly this because it uses JIT
but it will not happen unless Go transitions into some JIT environment -
for example generating code at install/update time like NGEN does.)

Now my "proposal" is this: (okay, just call it an "idea")
1. Compile all the code in compile time (this constraint could be
relaxed but currently I do not see any good reasons why).
2. Implement some code generation features (meta programming facilities
or compiler extensions) which can generate either one or two versions of
the generic methods or could generate freely any code like some type
safe preprocessor (I would like the latter one). This does not have to
be so advanced as Nemerle because those very-very-very advanced
meta-programming-macro-matching constructs could be incompatible with
Go's simplicity but at least reaching some C# LINQ level would be useful.
3. If 2 is implemented then it is up to the implementer of the generic
library whether he chooses to create a single generic code or inlined
code but the rule is that his library must be already compiled when the
compiler compiles some code which uses the library.
4. "Genericity" could be achieved with type erasure of generic
interfaces (like Java) so the linker should not be modified at all.
(This requires further considerations.)
5. There must be at least this two (or three) features supported.
5.1. Constraining/generalizing types by using interfaces (like C#).
5.2. Creating generic objects (new or make). It should not only support
the default parameterless constructor like C# but should allow something
like static interfaces (generator function in Go).
5.3. Probably giving meaning to predefined interfaces (like the ones
Jonathan defined for math or IChan, ISlice, IRange, IMap) would become
necessary, but I am not sure if it is mandatory or just some convenience.
6. What Nemerle teached us was that modifiable compiler internals sux.
It is necessary to have these macros to work on thread-safe,
copy-on-write language constructs.
7. Now this would be really an orthogonal feature! I especially would
like it for generating some XML processing or database accessing
libraries but keeping it simple should be the most important design
criteria.
8. With type erasure all the container types would be compile time
libraries but could be used for dynamically loaded code compiled by
different compilers.
9. To simplify the compiler, syntax enchantments would require some
marker like @property ... for the code generating macro "property".
10. I do not even touch reflection but of course it can be "funny" to
solve. It can be that with type erasure it is not even a problem but it
also needs some considerations.

Now I know that this is a little bit strange, bold and far reaching
"proposal" but at least try to wrap your mind around it.

If you have not heard about it:
http://nemerle.org/Features


Steven Blenkinsop

unread,
Dec 18, 2009, 6:03:53 PM12/18/09
to golang-nuts

What about:
generic name.(T) struct {a T}

name isn't a type
name.(int) is a type

func m.(T)(b T) T {....}

Expand the concept of type assertion...

jimmy frasche

unread,
Dec 18, 2009, 6:11:57 PM12/18/09
to Steven Blenkinsop, golang-nuts
I don't know about in general as that's a little too concise, but that
would certainly solve the problem I mentioned of a function with a
non-inferrable return type quite nicely

Russ Cox

unread,
Dec 18, 2009, 7:08:34 PM12/18/09
to NoiseEHC, Ian Lance Taylor, Jonathan Amsterdam, golang-nuts
> I have offered an alternative in the comments just did not get any response
> but you know I am getting to be used to that.

The mail and blog traffic has gotten to the point that
we can't reasonably reply to every suggestion anyone
makes. That doesn't mean we ignore them, though.
I've been thinking a lot about generics, and the
collected comments on the blog post have been helpful.

Russ

Russ Cox

unread,
Dec 18, 2009, 7:08:44 PM12/18/09
to golang-nuts
For many people "generics" means "templates" or "Java generics"
or "C# generics" or some other thing that essentially boils down
to a macro system with types as the parameters. The discussion
on this thread so far has assumed we want to build something
equivalent in power to Java's or C#'s generics and has been focusing
on what the syntax should be. That's not really interesting.

This paper
http://www.osl.iu.edu/publications/prints/2003/comparing_generic_programming03.pdf
makes a pretty good argument that the "type parameters" approach
to generics is fundamentally weak. I think it would be much more
interesting to consider how to apply something like ML's module
system to Go in a way that fits nicely with the rest of the system.
The paper makes a pretty good case that ML's modules have
important benefits over C# and Java's generics and even over
C++'s templates.

The problem I have trying to apply ML's model to Go is what
the ideas map to. A structure feels most like a Go package,
and a signature could be a new concept (interface for a package,
more or less) but then what does a functor return? It probably
can't return a new package, but if not it can't be the input to
another functor, and you do want to be able to write things like
Vector(Vector(int)). At the same time, mapping structure to type
and signature to interface is probably too limiting. The paper
makes a good case that much of the verbosity of the non-ML
systems boils down to not having a structure/signature
idea to represent a collection of names.

I am skeptical of any proposal that includes the words
"type erasure". Reading the papers about Java generics
suggests that type erasure is more a clumsy hack than a
model to be emulated. I think that if the source code says
Vector(Vector(int)) and all you can see at runtime is Vector,
that's a serious limitation. Java made that decision for
backwards compatibility with a large (at the time) installed
base. Whatever Go does, backwards compatibility with
existing containers should not be a constraint.

Russ

NoiseEHC

unread,
Dec 18, 2009, 7:45:22 PM12/18/09
to r...@golang.org, golang-nuts

Qtvali

unread,
Dec 18, 2009, 7:53:26 PM12/18/09
to golang-nuts
On Dec 19, 2:08 am, Russ Cox <r...@golang.org> wrote:
> I am skeptical of any proposal that includes the words
> "type erasure".  Reading the papers about Java generics
> suggests that type erasure is more a clumsy hack than a
> model to be emulated.  I think that if the source code says
> Vector(Vector(int)) and all you can see at runtime is Vector,
> that's a serious limitation.  Java made that decision for
> backwards compatibility with a large (at the time) installed
> base.  Whatever Go does, backwards compatibility with
> existing containers should not be a constraint.
>
> Russ

Yes, this is a common case of bad features.

Good example is qwerty keyboard. This is done so because there was a
problem with typewriters that characters had to arranged so that the
ones you would hit almost at same time must be far from each other.
There is, on the other hand, a dvorak keyboard - nice thing with
having keys ordered in such way that the most probable keys are in
middle row right at starting position of finger, also in general one
is using both hands by turns having always enough time to move one
hand into correct position when using another. Except for "f", I would
put it into better position - as in dvorak, standard position is very
efficient and "f" is far away from that. Otherwise it's fun to work
with dvorak.

I will read this text of ML's model and then maybe comment the topic.

Brian Slesinsky

unread,
Dec 19, 2009, 12:04:26 AM12/19/09
to golang-nuts
On Dec 18, 3:42 pm, Mark Chu-Carroll <mchucarr...@google.com> wrote:

> To use the vector example, in code, you'd write vector
> parametric on type T. In the implementation of vector, you'd
> generate exactly the same code that you do right now where
> it's a vector of "interface { }".

That would be okay if we were satisfied with how vector currently
works and just wanted to get rid of the casts. But once we want to
have containers whose memory layout doesn't have slots that are the
size of an interface value, code generation becomes a problem again.

(You might ask why we even care about memory layout, but that seems to
be what makes Go a systems language, despite otherwise having high-
level features like garbage collection. Controlling memory layout when
using structures and arrays of types such as byte or int32 is quite
different than in other languages where memory layout is a hidden
implementation detail.)

- Brian

Peter Froehlich

unread,
Dec 19, 2009, 2:12:38 AM12/19/09
to golang-nuts
I sent this out before, but since there's renewed generics interest:

http://research.microsoft.com/en-us/um/people/cszypers/pub/jmlc97.pdf

Gives you most of what you'd want, although not all of course. I think
a version adding simple interface constraints would be a good fit.
--
Peter H. Froehlich <http://www.cs.jhu.edu/~phf/>
Senior Lecturer | Director, Johns Hopkins Gaming Lab

Marcin 'Qrczak' Kowalczyk

unread,
Dec 19, 2009, 7:01:08 AM12/19/09
to Qtvali, golang-nuts
2009/12/18 Qtvali <qtv...@gmail.com>:

> I have had, as my biggest problem with generics, the fact that they
> often do not provide casting rules. I give an example:
> * I have a collection of "Cats" as in Vector<Cats>.
> * I also have a method, which only takes collections of animals.
> * I also have a collection of "Dogs" as in Vector<Dogs>
> * I would like to put Cats and Dogs into one array.
> * Thus, I will do Vector<Animals>(catvector); cast. This cast is not
> possible in Java.

And rightly so. You can put a dog in a mutable vector of animals, but
you can't put a dog in a mutable vector of cats. Thus a mutable vector
of cats is not a mutable vector of animals, and allowing such a cast
would be incorrect: it would allow code which breaks solid type rules
without an obvious place where such breakage could be detected.

Java does allow such casts for builtin arrays and detects the breakage
at array assignment. This is because Java used to have half-baked
generics of only builtin arrays, without making user code generic,
without the possibility of saying e.g. "the argument must be an array
of T, where T is any subtype of X". With proper generics such casts
are not needed.

Go is in the similar position to Java: it also has half-baked generics
of only builtin types. It can easily repeat Java mistakes.

--
Marcin Kowalczyk

Jonathan Amsterdam

unread,
Dec 21, 2009, 10:43:42 PM12/21/09
to golang-nuts
> http://research.microsoft.com/en-us/um/people/cszypers/pub/jmlc97.pdf

The main differences between this proposal and mine (ignoring
implementation) are:

1. Generic types are restricted to being pointers only. This
simplifies the implementation (it's by type erasure) and ensures that
there will be only one piece of code emitted per generic entity, but I
think it is too restrictive for a language like Go, where efficiency
is important. I don't want a Vector<*int>, I want a Vector<int>.

2. There is no way to express constraints at the level of the generics
system. Instead, you would do the equivalent in Go of a type switch or
type assertion:

My way:

func IndexOf<T interface {Equal(T)}>(x T, a []T) int {...}

Extended Oberon:

type Eq<T> interface {Equal(T)};

func IndexOf<T>(x T, a []T) int {
y := x.(Eq<T>);
b := a.([]Eq<T>)
...
}

The type assertions would of course be evaluated at compile time.

I think that's an interesting idea, though it does make things
clumsier. Also, I'm not sure how you'd express assignment
compatibility -- type assertions only give you type identity, or
implementation of an interface.

Jonathan Amsterdam

unread,
Dec 21, 2009, 11:18:02 PM12/21/09
to golang-nuts
Russ,

I agree we should explore other approaches. I don't think the
discussion of syntax was uninteresting, just premature perhaps.

> This paper http://www.osl.iu.edu/publications/prints/2003/comparing_generic_prog...


> makes a pretty good argument that the "type parameters" approach
> to generics is fundamentally weak.

I think you are overgeneralizing the paper's conclusions in two
dimensions. They show that certain languages' generics -- not an
entire approach -- make it clumsy -- not fundamentally impossible --
to describe certain possibly rather esoteric relationships among
types. They argue for structural rather than named constraints (not
incompatible with a type params approach, and something that falls out
in Go because of how interfaces work), implicit instantiation (got
it), type aliases (yes, please, but orthogonal to my proposal), and
richer ways to express relationships among types. My to-do list after
reading the paper is: (1) implement (portions of) the Boost Graph
Library in idiomatic Go + my generics, and see if their supposed
issues don't go away, and (2) think about how to add type associations
to Go, in case they don't.

> I think it would be much more
> interesting to consider how to apply something like ML's module
> system to Go in a way that fits nicely with the rest of the system.

What I like about ML's approach is that signatures, structures and
functors are (almost) purely second-order: they sit on top of the
language and parallel its entities (functor = function, signature =
type, structure = value). You can actually do a lot of programming in
ML and notice the generics part.

What I don't like about it is its verbosity. Just to express something
like

func pick<T interface{Better(T)}>(x, y T) T { if x.Better(y) { return
x} else {return y}}

takes several lines of code; and a call, which is one line in most
type parameter approaches, requires first applying a functor to get a
structure, and then doing the call. ML can get away with this amount
of stuff because it already has a very good mechanism for parametric
polymorphism using type variables; this more verbose mechanism is only
needed for more complicated situations.

> The problem I have trying to apply ML's model to Go is what
> the ideas map to. A structure feels most like a Go package,
> and a signature could be a new concept (interface for a package,
> more or less) but then what does a functor return?

Another problem with ML's approach is the amount of new machinery it
would require introducing into Go, as you observe. You couldn't leave
packages as they are either, because it would really be beastly if you
had a write a package, thus a separate file, just to have something to
apply a functor to.

> It probably
> can't return a new package, but if not it can't be the input to
> another functor, and you do want to be able to write things like
> Vector(Vector(int)).

It's extremely interesting you should mention this. I was recently
reading Nelson's Modula-3 book, and in Chapter 8 where they discuss
generics, exactly this issue of nested application is discussed.
(Modula-3's generics were also second-order, applying only to modules
(= packages) and interfaces (= signatures)). I recommend that book and
that chapter in particular.

> I am skeptical of any proposal that includes the words
> "type erasure". Reading the papers about Java generics
> suggests that type erasure is more a clumsy hack than a
> model to be emulated.

Totally with you there.

-Jonathan

Qtvali

unread,
Dec 22, 2009, 4:59:42 AM12/22/09
to golang-nuts, Jonathan Amsterdam
Such relations are not "esoteric" at all - they are actually very
common.

Say you have a constructor for square matrices - you have implemented
some operations, which are only possible with square matrices.

This means the following:
* It must be a container - have some kind of iterator or getters/
setters, also width and height
* It must be two-dimensional - either array inside array, array inside
vector, vector inside vector etc.
* It must have elements of numeric type; any type supporting some
primitive operations (add, multply etc.) you are going to use will
fit.
* It must contain n*n matrix - if container is made of arrays inside
arrays, the number of arrays and count of elements in each must be the
same.

Maybe you have function to multiply matrix and a vector - then they
both must be containers, one must be one- and another must be two-
dimensional, their sizes must fit and they must contain elements of
same type.

It's somewhat question, which properties you check at runtime and
which ones at compile time (ideally you should be able to check
everything at compile time in case it's known at compile time; if
array size is constant, you should be able to check it and if it's
not, you should be able to let it through). Less ideally you cant
write those constraints out - and you get an example Russ told here
that Vector<Vector<int>>, which could be a matrix, is expressed as
Vector. Anyway, you might want to say that both Vector<Vector<int>>
and [][]int goes, as does [][]float, but that [][]string does not. And
you want to get your code work at top speed as if you didn't do such
dynamics for each case - and you don't want to get into some total
mess because of those generics.

Matrix is a math primitive and it should be possible to declare math
primitives neatly.

On Dec 22, 6:18 am, Jonathan Amsterdam <jbamster...@gmail.com> wrote:
> Russ,
>
> I agree we should explore other approaches. I don't think the
> discussion of syntax was uninteresting, just premature perhaps.
>

> > This paperhttp://www.osl.iu.edu/publications/prints/2003/comparing_generic_prog...

Qtvali

unread,
Dec 22, 2009, 5:09:44 AM12/22/09
to golang-nuts, Jonathan Amsterdam
I give you more "real-world" example:

You are probably used to notion map[int]int or [int]a.

In terms of generics - Map<Int, Int> or Vector<Int>.

Getting such input types you can do:
a := Vector.getElement(3); // So that a will be int

You can also be sure that you can do:
Vector.getElement(1) + Vector.getElement(3)
without casting, maybe throwing etc.

So your code gets shorter, simpler and more reliable if you have those
constraints - especially if you use generics created by others and
don't know that they could take both array and vector types etc., you
can just see it easily from specification or get compile errors when
trying to give wrong input.

Qtvali

unread,
Dec 22, 2009, 7:49:55 AM12/22/09
to golang-nuts
On Dec 19, 2:01 pm, "Marcin 'Qrczak' Kowalczyk" <qrcza...@gmail.com>
wrote:

> 2009/12/18 Qtvali <qtv...@gmail.com>:
>
> > I have had, as my biggest problem with generics, the fact that they
> > often do not provide casting rules. I give an example:
> > * I have a collection of "Cats" as in Vector<Cats>.
> > * I also have a method, which only takes collections of animals.
> > * I also have a collection of "Dogs" as in Vector<Dogs>
> > * I would like to put Cats and Dogs into one array.
> > * Thus, I will do Vector<Animals>(catvector); cast. This cast is not
> > possible in Java.
>
> And rightly so. You can put a dog in a mutable vector of animals, but
> you can't put a dog in a mutable vector of cats. Thus a mutable vector
> of cats is not a mutable vector of animals, and allowing such a cast
> would be incorrect: it would allow code which breaks solid type rules
> without an obvious place where such breakage could be detected.
>
> Go is in the similar position to Java: it also has half-baked generics
> of only builtin types. It can easily repeat Java mistakes.

Yes, but the casting rules must be there. Sometimes you can cast one
generic to another [without changing the underlying data structure]
and you must be able to do it - having a long vector of some integer-
compatible structs, I want a fast cast to integer vector without going
through elements one-by-one. Did the initialization process depend on
them being of the exact type they are, I don't.

Some part of that could be solved by some initialization rules - as
there are rules right now to declare arrays and maps:
[]int
map[int]int

There could be a convention that if I created MyMap, then
initialization would be MyMap[myint]myint and this can be cast to MyMap
[myint]int, but not MyMap[int]myint. In other cases, rules must be set
explicitly.

Bill Trost

unread,
Dec 24, 2009, 12:20:08 AM12/24/09
to golang-nuts
Well, it looks like you shut *that* conversation down, Russ. (-:

Reading over this thread, I'd coming to the same sorts of ideas you
suggest: packages certainly feel like Go's equivalent of structures.
By the same token, functors are parameterized packages, where each
parameter is itself a package. Taken literally, functor application is
means providing parameter packages to the functor in order to create
another package.

Offhand, it seems like the easiest way to express that notion is to do
it extra-linguistically: Rather than try to instantiate functors in go
code, instantiate them in the Makefile. For example, if we have a
"pick" functor that takes a package parameter named "comparable",
similar to the one in the paper, and an "apple" package that
implements comparable, you could create the pick_apples package with
the command

8g pick.go 'comparable=apple' -o pick_apples.o

Then, any package that needs to compare apples can simply import the
pick_apples package.

This approach seems to deal with the problem that Ian(?) raised
regarding how you decide when and what variants to compile -- that's
all handled in the Makefile.

Thoughts?
Bill

On Dec 19, 12:08 am, Russ Cox <r...@golang.org> wrote:
> This paperhttp://www.osl.iu.edu/publications/prints/2003/comparing_generic_prog...


> makes a pretty good argument that the "type parameters" approach

> to generics is fundamentally weak....

roger peppe

unread,
Dec 24, 2009, 8:14:07 AM12/24/09
to r...@golang.org, golang-nuts
a few random thoughts i've had over the last few days around
the generics issue.

if packages map to ML's structures (which does seem
like a nice way to go) then:

- you need some way of talking about a package instance,
so a package identifier becomes more than just something you
can name - it has a type. does that mean you can put it into
an interface{}?

- what happens about package-global variables? is there
a separate instance of all global variables for each instantiation
of a package with a different type? maybe generic packages
should be explicitly instantiated. alternatively, you could
disallow the storage of generic types in global variables.

- what happens if you put a generic type inside an interface?
for instance, using the ml notation to denote type variables,
and ignoring the package=structure thing (which is a superset
of generic functions AFAICS), say you have a function:

func foo (a 't1) interface{} {
return a
}

and you use it like this:

a := foo(int(34))

will this then succeed?

b := a.(int)

i think it should.
but would the first call succeed if i defined foo() like this?

func foo(a 't1) int {
return a.(int)
}

we're getting onto shakier ground here.
what about this?

func foo(a 't1) 't1 {
var i interface{} = a
return i.('t1)
}

i think this should work too, but when you bring this
together with the first example, it seems that an
interface can satisfy more than one "underlying" type.

you can't just substitute the original type either, otherwise
this:

func foo(a 't1, b 't2) 't1 {
var i interface{} = b
return i.('t1)
}

would incorrectly succeed when 't1 and 't2
have the same actual type.

this issue needs to be solved before generics in whatever
form are added to Go.

Qtvali

unread,
Dec 24, 2009, 8:39:48 AM12/24/09
to golang-nuts
On Dec 24, 3:14 pm, roger peppe <rogpe...@gmail.com> wrote:
> - what happens about package-global variables? is there
> a separate instance of all global variables for each instantiation
> of a package with a different type? maybe generic packages
> should be explicitly instantiated. alternatively, you could
> disallow the storage of generic types in global variables.
>
> - what happens if you put a generic type inside an interface?

I did address some of those, I think, in my last proposal -
http://groups.google.com/group/golang-nuts/browse_thread/thread/84eaea4dd6315aad#
- where I tried to address the goal of simplicity in Go. I did reword
this simplicity in such way that it should be good intermediate
language for code generation - as I personally favor each kind of
"complexity" if this is addressed to make language more extensible, I
can think only that way. Thinking like that makes me think about what
specific structural units Go lacks, which seems to be most similar
mode of thinking I can easily get with you.

I addressed them in such way:
* A generic class is normal class with constants, which can be used to
declare variables and in-function array sizes etc.
* Those constants, thus, can be of normal types or type types. Type
types should be accessible by reflection.
* Instantiating such class goes in two steps - first step instantiates
constants, next step instantiates other variables. Constant-
initialization part will calculate address table, stack sizes etc. and
thus be very costly; after that, the class can be used to boost each
kind of initializations of actual instances.
* Initialization of constants actually gives a kind of type, not a
kind of value, roughly.
* As this initialization can be pretty complex and one of purposes of
templates in, say, C++, is to allow several ghost types to backup one
template - it's decided from type parameters etc., which one will be
instantiated. First, this could slow down compiler to make all
calculations for all possible cases; second, all optimizations can be
done without doing it that way. Initialization should happen at
runtime for specific class.
* Interfaces will apply to const-initialized form of this class, which
knows the exact types. You cant check if class has "int Add(int)"
before it has actually decided return type of this function;
practically, you are not interested in the set of abstract
possibilities at runtime, but only if it contains those specific
types. Templates are more or less dynamic and give casting error at
runtime.
* There is no way to use such kind of class in interfaces - first,
this is not needed so much and you can make functions excplicitly
check this (programmer knows best the properties, which are needed for
a class to apply and can also boost this with good practices). Second,
in all languages I have seen, this part is "buggy" or at least not a
common case; it's very hard to actually say, which template classes
are subsets (assignment-compatible) to which ones; the markup language
to say that Vector[humans] is a kind of supertype to Vector[dogs] if
this is the value type, but Map[humans] is not a supertype of Map
[hashableHumans] - this gets obfuscated. Using simply interface types
to decide such things is better. This gets into serious
metaprogramming in a kind of other [logical paradigm] language [which
I proposed here - http://groups.google.com/group/golang-nuts/browse_thread/thread/8d3268eb241ab1ea/aedd33cd97ec2da0
-, by the way] and having two languages in one might not be what Go is
willing to get into.

My last proposal (not this two-in-one one) is somewhat robust and
unobfuscated extension to language.

Jonathan Amsterdam

unread,
Dec 24, 2009, 8:41:34 AM12/24/09
to golang-nuts
> if packages map to ML's structures (which does seem
> like a nice way to go) then:

The fundamental problem is that packages as they currently stand are
too heavyweight. Must I write a package just to write a generic binary
search function?


> - what happens if you put a generic type inside an interface?

This and all that follows is based, I think, on a misunderstanding.
There isn't really any such thing as a generic type at runtime. All
usable types are fully instantiated. To go through your examples:

> func foo (a 't1) interface{} {
>     return a
>
> }
>
> and you use it like this:
>
> a := foo(int(34))
>
> will this then succeed?
>
> b := a.(int)
>

Absolutely, since you implicitly instantiated foo<int>. In that
instantiation, 't1 is int.

> i think it should.
> but would the first call succeed if i defined foo() like this?
>
> func foo(a 't1) int {
>   return a.(int)
>
> }

Certainly. Why on earth not?

> what about this?
>
> func foo(a 't1) 't1 {
>   var i interface{} = a
>   return i.('t1)
>
> }

Perfectly fine.


> i think this should work too, but when you bring this
> together with the first example, it seems that an
> interface can satisfy more than one "underlying" type.
>

I don't understand that at all. Are you comparing 't1 to int? That
doesn't make sense. 't1 is a dummy variable that can be instantiated
with any type:

a := float(foo(3)) + foo(4.0)

> you can't just substitute the original type either, otherwise
> this:
>
> func foo(a 't1, b 't2) 't1 {
>     var i interface{} = b
>     return i.('t1)
>
> }
>
> would incorrectly succeed when 't1 and 't2
> have the same actual type.
>

Still confused. Why would it incorrectly succeed in that case? It
would CORRECTLY succeed!

Qtvali

unread,
Dec 24, 2009, 9:33:30 AM12/24/09
to golang-nuts
I think you a bit miss the case that all those types actually _have_
to be instantiated - in compiler or by runtime.

In C++, there will simply be generated a lot of classes like with
macro - this takes memory, but will go through actual cases. Why I
think this is too much for Go is that it needs complex turing-complete
macro languages as C++ template syntax is. Also, it definitely slows
down compiler. It must actually generate a bunch of types and derived
types (internally, when you create some type-tree of several levels
inside a class, occasionally you have to put together a map of
relations between all these).

In Java, the whole thing is actually just a constraint - Java keeps
all that data in runtime. In Java, you don't get those templates often
faster (probably they have optimized built-in's in some way), but
simply somewhat strong-typed. Where C++ programmer chooses templates
for speed, Java programmer should choose not using templates for
speed.

Having templates and mappings between types, when you say "MyMap[int]
int" or smth., you will actually need to do a number of calculations
to know if something applies to MyMap[int]int interface. You must have
this interface stored in some map or you must have calculated it out
at compile time. If you can instantiate those with your own reflection
classes, they have to register your new template initialization in
some map and make it work with all other type system so that you can
ask if it applies to some interface etc. If you have two places, where
you do this check with reflection, you get extremely slow code - and
that's not what this is meant for. C++ has no reflection and thus
there is no such problem. You don't have to know anything in runtime
about anything there. In Go, it's clear that one definitely wants to
reflect those. Thus, there has to be some specific command, which is
documented as being slow and a bunch of others, which rely on
calculations premade by it. Obviously this one command has to be
initialization - and I make it definitely even slower by proposing one
to use reflection inside it to match actual implementation etc., but I
also totally avoid having another language to specify relations
between generic types; also I avoid very complex and slow mappings
between template types generated by runtime on the fly (for example,
when you check some compabilities). Without giving that part to
programmer, making explicitly slow and also making programmer
responsible about moving those half-instantiated classes around
instead of regenerating them makes things faster. Internally, const
types of such kind might also have a map from which they are searched
first, then it's possible to avoid some cost of checking them for
equality.

Mike Zraly

unread,
Dec 24, 2009, 9:33:59 AM12/24/09
to Bill Trost, golang-nuts
On Thu, Dec 24, 2009 at 12:20 AM, Bill Trost <tro...@cloud.rain.com> wrote:
Well, it looks like you shut *that* conversation down, Russ.  (-:

Reading over this thread, I'd coming to the same sorts of ideas you
suggest: packages certainly feel like Go's equivalent of structures.
By the same token, functors are parameterized packages, where each
parameter is itself a package. Taken literally, functor application is
means providing parameter packages to the functor in order to create
another package.

Offhand, it seems like the easiest way to express that notion is to do
it extra-linguistically: Rather than try to instantiate functors in go
code, instantiate them in the Makefile. For example, if we have a
"pick" functor that takes a package parameter named "comparable",
similar to the one in the paper, and an "apple" package that
implements comparable, you could create the pick_apples package with
the command

 8g pick.go 'comparable=apple' -o pick_apples.o

Then, any package that needs to compare apples can simply import the
pick_apples package.

This approach seems to deal with the problem that Ian(?) raised
regarding how you decide when and what variants to compile -- that's
all handled in the Makefile.

Thoughts?
Bill

I really, really like the simplicity of this, but how would you handle nested generics, for example a generic graph package that relies on generic list or matrix packages?

Once the design settles down you will want a tool that analyzes the source or object files and discovers the complete set of additional objects that must be generated.  This could be part of the linker, or could be a separate tool executed before the linker.


Bill Trost

unread,
Dec 24, 2009, 10:18:28 AM12/24/09
to golang-nuts
On Dec 24, 5:20 am, Bill Trost <tros...@cloud.rain.com> wrote:
> Well, it looks like you shut *that* conversation down, Russ.  (-:

Don't ask. I don't know what I was thinking, either.

Sorry,
Bill

Qtvali

unread,
Dec 24, 2009, 10:28:17 AM12/24/09
to golang-nuts
On Dec 24, 4:33 pm, Mike Zraly <mzr...@gmail.com> wrote:
> I really, really like the simplicity of this, but how would you handle
> nested generics, for example a generic graph package that relies on generic
> list or matrix packages?
>
> Once the design settles down you will want a tool that analyzes the source
> or object files and discovers the complete set of additional objects that
> must be generated.  This could be part of the linker, or could be a separate
> tool executed before the linker.

You are talking about slow compiler. By the way - this compiler could
hang.

Consider the case:
* You make a vector class, which internally creates a vector of given
type
* You do Vector[Vector]

Vector[Vector] creates a Vector[Vector][Vector]-s
Vector[Vector][Vector] creates a Vector[Vector][Vector][Vector]

If you instantiate those as you imagine, this case is possible. I
haven't yet analyzed if this common case could be analyzed and
appropriate infinite-loop error given, but I somewhat doubt, because
this easily leads to this kind of turing-complete interface, which
can't be ultimately checked to not halt - I'm somewhat a fan of
halting problems and this is actually quite hard to design things,
which are easy to detect for that. Actually, my own example of Prolog-
like syntax is also a subject of halting paradox (which is why I
started to analyze this case, because I'm keeping in mind my own goal
to create a programming language quite different from Go, but such
general problems occur everywhere).

I would not like to see a compiler telling me:
The compilation process has taken quite long time for now, probably
you have circular templates somewhere ...and then get it to compiler
by making some timeout larger ;)

Jonathan Amsterdam

unread,
Dec 28, 2009, 1:00:38 PM12/28/09
to golang-nuts
I've thought some more about type associations, and I don't share the
concerns expressed in Garcia et. al. (the paper comparing generics in
several different languages).

Type associations let you express relationships between types
generically. E.g. in C++, if I have a graph class G, I will define the
member graph_traits<G>::vertex_type to be the type of vertices for
that graph class. The paper has two concerns with languages that don't
allow type association:

1. Users are forced to know about implementation details of classes.
E.g. A user of G would need to know the type of a vertex of G.

2. It becomes cumbersome to express generic functions.

I explored what implementing a simplified piece of the Boost Graph
Library would look like in Go, and the bottom line is: I'm not worried
about either of those things.

Regarding #1, implementation details: it seems reasonable that if
you're going to implement a kind of graph, you'll put it in a package,
and by convention you'll export types like Edge and Vertex. E.g. a
basic graph datatype using adjacency lists:

--------
package listgraph

type Vertex int

type Edge struct { src, tgt Vertex }

func (e *Edge) Source() Vertex { return e.src }
func (e *Edge) Target() Vertex { return e.tgt }

type Graph [][]*Edge // g[v] is the list of edges leaving vertex v

func (g *Graph) Vertices() []Vertex {...}
func (g *Graph) OutEdges(v Vertex) []*Edge { return g[v] }
...
------

I have no problem with referring to listgraph.Vertex and
listgraph.Edge. I don't think doing so really exposes any
implementation details. Note that the fields of the Edge struct are
not exported.

Now let's look at #2. How clumsy is it to write graph search, BGL
style?

--------
package graph

type Edge[V] interface {
Source() V
Target() V
}

type Graph[V, E Edge[V]] interface {
Vertices() []V
OutEdges(V) []E
}

type Color int

type ReadWriteMap[Key, Value] interface {
Get(Key) Value
Set(Key, Value)
}

// Contains callbacks invoked at various points in a graph search.
type GraphSearchVisitor[V, E Edge[V]] interface { ....}


func GraphSearch[V,
E Edge[V],
C ReadWriteMap[V, Color],
Vis GraphSearchVisitor[V, E]](g Graph[V, E],
start V,
colorMap
C,
visitor
Vis) {
...
}
--------

(Some minor differences between this code and the Boost Graph Library:
I have one Graph interface instead of factoring the functionality out
into two; I return slices of vertices and edges instead of iterators;
and I don't parameterize GraphSearch on the graph type, since calls on
the graph are not in inner loops.)

As Garcia et. al. point out, I am forced in writing GraphSearch to
include type parameters V and E in order to establish the associations
among the various interfaces (e.g. the Key type of ReadWriteMap == the
vertex type of the graph). I am also forced to repeat constraints like
"E Edge[V]". This is a bit annoying, but in my opinion it doesn't
rise to the level of requiring a language change. Note also that
calls to GraphSearch see none of this machinery, due to implicit
instantiation:

--------
var g listgraph.Graph = ...
var v listgraph.Vertex = ...
var cm ReadWriteMap[listgraph.Vertex, graph.Color] = ...;
var vis GraphSearchVisitor[listgraph.Vertex, listgraph.Edge] = ...;

graph.GraphSearch(g, v, cm, vs)
--------

Conclusion: based on the evidence so far, type associations do not
provide enough benefit to warrant their addition to my generics
proposal.

NoiseEHC

unread,
Dec 29, 2009, 4:15:29 PM12/29/09
to Jonathan Amsterdam, golang-nuts
What I do not get with generics is this:

Assume a simple code generating generics implementation (for example by
a .go file generating preprocessor which can derive types from the .go
sources which want to use generics) which uses interfaces to constrain
types in the generic definition like C#. Assume that the generic type
information is erased from the generic interfaces in the actual
compilation step.

Stupid example (did not check whether it looks like valid Go):

generic_list.go:
type IList<T> interface {
GetCount() int;
GetItem(int Index) *T;
}
type IValue<T> interface {
GetValue() double;
}
type ArrayList<T> struct {
// default IList<T> implementation
func Add(Item *T);
}
func Sum(L IList<T>) double where T : IValue<T>; // enumerates L and
calls GetValue() on the elements

use_generics.go:
type Test struct {
....
func GetValue() double; ....
}
list := new(ArrayList<Test>);
list.Add(&Test(...));
generic_list.Sum(list);

It is converted to:
type __IList_Test interface {
GetCount() int;
GetItem(int Index) *Test;
}
type __IValue_Test interface {
GetValue() double;
}
type __ArrayList_Test struct {
// default __IList_Test implementation
func Add(Item *Test);
}
func __Sum_Test(L __IList_Test) double;


So the question: what is the thing what is not possible to do with a
generics implementation like this? I mean that most likely there is a
reason why other generics implementations use type hierarchies in
constraints and higher level constructs than this, just I do not get
what that reason is. Could you give some examples which are not possible
with this implementation?

Thanks!


Ian Lance Taylor

unread,
Dec 29, 2009, 4:46:22 PM12/29/09
to NoiseEHC, Jonathan Amsterdam, golang-nuts
NoiseEHC <Nois...@freemail.hu> writes:

> Assume a simple code generating generics implementation (for example
> by a .go file generating preprocessor which can derive types from the
> .go sources which want to use generics) which uses interfaces to
> constrain types in the generic definition like C#. Assume that the
> generic type information is erased from the generic interfaces in the
> actual compilation step.

...

> So the question: what is the thing what is not possible to do with a
> generics implementation like this? I mean that most likely there is a
> reason why other generics implementations use type hierarchies in
> constraints and higher level constructs than this, just I do not get
> what that reason is. Could you give some examples which are not
> possible with this implementation?

Some issues I see with this approach are:

* Debugging is painful, because you are looking at a generated file
rather than the original source code.

* It's complicated to use a generic as a parameter to a generic. This
comes up when you try to have a list of lists.

* The build system is fairly complex, and minor edits to your program
will require changing the build rules to instantiate different
generics.

Ian

Jonathan Amsterdam

unread,
Dec 29, 2009, 4:52:40 PM12/29/09
to golang-nuts
On Dec 29, 4:15 pm, NoiseEHC <Noise...@freemail.hu> wrote:
> What I do not get with generics is this:
>
> Assume a simple code generating generics implementation (for example by
> a .go file generating preprocessor which can derive types from the .go
> sources which want to use generics) which uses interfaces to constrain
> types in the generic definition like C#. Assume that the generic type
> information is erased from the generic interfaces in the actual
> compilation step.
>
> (code omitted)

>
> So the question: what is the thing what is not possible to do with a
> generics implementation like this?

You can't express assignment compatibility with just interfaces. To do
so you need to constrain one type parameter by another. See the
CopyChan2 example in my spec. That turns out to be quite useful.

The Garcia et. al. paper argues that it's harder to describe
relationships between type parameters in this sort of design. But they
don't show that you can't do it, only that's it's a bit uglier.

Of course you can't do metaprogramming a la C++. Take a look at any
modern C++ book to see the wealth of things possible when you allow
metaprogramming.

> I mean that most likely there is a
> reason why other generics implementations use type hierarchies in
> constraints and higher level constructs than this, just I do not get
> what that reason is.

Well, they use type hierarchies because they have type hierarchies.
Because Go doesn't, a lot of machinery goes away.

C# allows you to specify multiple interfaces that a type parameter
must satisfy, but due to Go's structural subtyping, that is
unnecessary as well.

C# allows other sorts of constraints on type parameters. One is for
asserting that the instantiating type has a no-arg constructor. Go
doesn't have constructors, so that goes away.

Another C# constraint lets you assert that the instantiating type is a
value type, or a reference (pointer) type. Asserting the latter would
allow comparisons with nil. Since Go is fairly irregular, you could
imagine a variety of such constraints ("supports equality", "supports
equality with nil", "supports other comparison operators", "supports
range", etc.). For each, you can easily construct generic functions
that are impossible in my (and your) proposal. I chose to leave them
out because I didn't think the added complexity was worth it, and
there are workarounds.

Qtvali

unread,
Dec 29, 2009, 6:01:05 PM12/29/09
to golang-nuts
On Dec 29, 11:15 pm, NoiseEHC <Noise...@freemail.hu> wrote:
> So the question: what is the thing what is not possible to do with a
> generics implementation like this? I mean that most likely there is a
> reason why other generics implementations use type hierarchies in
> constraints and higher level constructs than this, just I do not get
> what that reason is. Could you give some examples which are not possible
> with this implementation?

Example there was not the ultimate complex library using generics, but
rather some simplest example using all features considered important
by authors of this text.

1. Thinking that path, you could use interface{} instead of generics.
Conventions and etc.
2. Relations between your types might be more complex.
3. Statically typed relations allow optimizer to do many optimizations
based on strict knowledge about types.

You should also consider the following:
* Generic BinTreeIterator<BinTree<...>> takes in a BinTree<...>, which
would be some tree, which has "Left" and "Right" branches of each node
or int value.
* When you iterate over BinTree with e := ..., you want element type e
to be int when you assign a value.
* When you write a := BinTreeIterator.getTree() somewhere, you want a
to contain a tree of correct type.
This information, thus, should be known at compile time from this
viewpoint (even if I myself have a proposal, where it's not - rather
very simple proposal in another direction).
* If this type is not known at compile time, you must do runtime
checks everywhere.
* When conventions get complex, it's better to get good compile-time
error with specific contract you did not follow.
* Consider the cases, where contract is more complex - for example you
have a template, which takes in SQL connection as following:
MyContactList<SQLConnection<SQLServerType>>. SQLConnection could be
SQLConnection<Oracle> or SQLConnection<MySQL>. Your class supports
only servers, which support transactions - thus, it would work with
SQLConnection<Oracle>, but not with SQLConnection<MySQL>. This is
complex contract - SQL server might support transactions, but your
driver might still not; newer version of SQL server might support it
even if you thought it doesn't; you might have used this contact list
class in several places, maybe someone of your company created some
code using it, you did develop it for some time and then used it in
your own application - thinking that your application is general
application supporting different kinds of SQL servers (maybe you did
excplicitly write several things differently for MySQL and Oracle);
now you let it to market and some time later get some letter that on
MySQL, all functionality including address books is broken. Then be
happy if this contract is well documented and you have a verbose error
message - but a bug is still there in some version. And this example
was not my wildest fantasy, I could bring very real and much worse
cases as examples ;)

> Thanks!

Qtvali

unread,
Dec 29, 2009, 6:20:43 PM12/29/09
to golang-nuts
> * Consider the cases, where contract is more complex - for example you
> have a template, which takes in SQL connection as following:
> MyContactList<SQLConnection<SQLServerType>>. SQLConnection could be
> SQLConnection<Oracle> or SQLConnection<MySQL>. Your class supports
> only servers, which support transactions - thus, it would work with
> SQLConnection<Oracle>, but not with SQLConnection<MySQL>.

To make this case more clear - suppose that this method does not do
type checks using reflection. It simply uses con.startTransaction.
Imagine that it does not do transaction in all cases, but only when
adding telephone number - an operation, which could use another
database. MyContactList would be visual widget allowing user to change
some kind of contact list used by several applications in your
package. It consists of two tables - contacts and telephone numbers.
Contacts table can be changed by simple queries, but telephone numbers
are ordered and thus need atomic operations. Mostly, contact list does
those simple queries, because it does not need lock. Maybe it's built
even in such way that adding or deleting a telephone number happens
with simple queries. Anyway, when reordering those numbers, other
query from another window could mess things up and thus transaction is
used. Your connection module might have some kind of takeTrasaction
and releaseTransaction methods, which allow takeTransaction called
several times and do commit when release is called as many times - odd
design, but it could be so. Removal of contact relies on constraints,
thus automatically deleting numbers on oracle - in case of mysql,
contacts will be deleted, but numbers stay there.

Now, you might have unit tests for everything - create contact, delete
contact, add number and delete number. Anyway, you don't have unit
test for reordering numbers. Now, when user simply drags a number,
there is a panic and everything will crash.

Popog

unread,
Dec 30, 2009, 1:54:07 AM12/30/09
to golang-nuts
I think someone has suggested this before, I can't remember where, but
what's the problem with creating a new template file-type and
associated paraphernalia?

(Note, this might be similar to or exactly like something NoiseEHC
proposed earlier in this thread.)

The proposal described something along the lines of a new parser
(let's call it "5/6/8t") and two new file-types to house and
instantiate the template code, (let's call them ".goTemplate"s and
".goTemplateInstatiator"s respectively).

How to Use:

1) Write ".goTemplate" files with template code.

2) Write ".goTemplateInstatiator" files. They will import
".goTemplate"s and explicitly instantiate the template code.

3) Run "5/6/8t" on the ".goTemplateInstatiator" files. It will parse
them into ".go" files. "5/6/8t" can start out ignoring most safety and
sanity checks, maybe adding more as development progresses and it gets
smarter.

4) Compile the resulting ".go" files with the rest of your ".go"
files, you get all the errors "5/6/8t" didn't catch.

5) Go fix the errors in your ".goTemplate" files and
".goTemplateInstatiator" files.

6) Goto Step 3

I thought about this for a while and came up with all the problems and
mitigating factors I could think off.

Questions/Problems:

Q: What exactly can I do with templates? What are the restrictions
this proposal imposes?

A: I don't really know yet, I haven't thought much about syntax. The
nice thing is that with this setup, you can do pretty much anything
meta-programming-wise so long as "5/6/8t" is strong enough. This
proposal is basically about liberating the syntax of generics from the
syntax of Go.

Q: How do I use templates in my normal code?

A: Also don't know, like I said: "I haven't thought much about
syntax". One possibility is sort of a function overloading style, but
this would require Go to allow function overloading (which I support),
plus it can be kind of limiting. Another possibility is to make the
identifiers based on the way in which the template was instantiated
(think Vector_float64), but this would lead to some long identifiers.

Q: This is explicit instantiation, I am against this.

A: I actually like implicit instantiation personally, but I'm not sure
it fits Go. IMHO, explicit instantiation is a lot easier to
understand, especially for new programmers. I think we should have
more discussion on this point though, even if the proposal is refused.

Q: This separation of templates from the core language seems kinda
funky.

A: Well, it makes parsing a lot simpler, and the compiler stays just
as fast as it was before.

Q: Even though you haven't said anything about what ".goTemplate"s
look like, I'm assuming writing templates is basically a whole
different language.

A: Well that is a possibility, but most implementations of templates
are pretty syntactically idiosyncratic. However, the logical
separation of templates from the rest of the language means that the
syntax of ".goTemplate"s is significantly less restricted. This means
template syntax could be made similar to Go's syntax (or at the very
least fitting) without complicating the parser too much. Plus this
allows the hardcore meta-programmers to work on "5/6/8t" and get
everything they want/need without affecting the rest of the language.

Q: Why don't you go write a parser yourself?

A: I could write a parser myself, and so could everyone else out
there, but then there wouldn't be a standard spec for ".goTemplate"s.

Q: Haven't you just slowed down compiling of Go by like a billion
times?

A: Not really, the explicit template instantiation means that you only
run (the admittedly slow) "5/6/8t" once. Compile and link are still
just as fast as ever.

Q: Won't "5/6/8t" make huge ".go" files?

A: "5/6/8t" can output large files, but only if you tell it to. If
your ".goTemplate" or ".goTemplateInstatiator" files are written
poorly, overly large files could be generated. However, in the case
where they are not written poorly and huge files are generated, that
just means you have a lot of code. Good thing you had templates,
because otherwise you would have had to have written that huge ".go"
file by hand.

So am I missing something, (other than perhaps Ian's comments, which I
think are relevant to this proposal).

Mike Zraly

unread,
Dec 30, 2009, 6:14:20 AM12/30/09
to Popog, golang-nuts
I suppose this question is more about go than your template proposal,
but here goes anyway:

Q: What about debugging support?  Strictly speaking users would
be debugging the generated .go source, not the .goTemplate files
used to direct their creation.  Is there a way to tell the debugger that the
source is actually from the .goTemplate files, e.g. via the equivalent of
#line and #file directives?

Then there's this:

Q: Won't it be a pain to manage template code that use types parametrized
by one of their parameters, especially in library code?  For example consider
a Graph template with Edge and Vertex type parameters that requires for its
implementation Vectors parametrized by those same types.  The programmer
ends up having to explicitly run your template instantiator for every combination
of types and parameters used in a program.  Is it feasible to write a utility that
parses the .go and .goTemplate files to generates the set of instantiation
commands required, so that it can be used within a Makefile?


NoiseEHC

unread,
Dec 30, 2009, 7:20:21 AM12/30/09
to Ian Lance Taylor, Jonathan Amsterdam, golang-nuts

> Some issues I see with this approach are:
>
> * Debugging is painful, because you are looking at a generated file
> rather than the original source code.
>

I am not sure that you understood my example/question completely
(Jonathan seemed to understand it) again it seems that I cannot express
myself unambiguously. I did not want a text preprocessor generics
implementation, it was just an example to enable us to speak about the
same thing without loosing in the implementation details. Now we have
lost in preprocessor implementation details... :) So the point was that
this generics system can do some type checking but other than that it
can only generate types via simple textual type substitution.
Before you ask: I would like (in my wet dreams) a macro like generics
implementation (and as an extra a "syntax extending" macro system) but
the question was not about macros just type systems.

> * It's complicated to use a generic as a parameter to a generic. This
> comes up when you try to have a list of lists.
>
>

generic_list.go:


type IList<T> interface {
GetCount() int;
GetItem(int Index) *T;
}
type IValue<T> interface {
GetValue() double;
}
type ArrayList<T> struct {

func GetCount() int;
func GetItem(int Index) *T;
func Add(Item *T);
}
func SumMatrix(M IList<IList<T>>) double where T : IValue<T>;

use_generics.go:
type Test struct {
....
func GetValue() double; ....
}

mat := new(ArrayList<ArrayList<Test>>);


list := new(ArrayList<Test>);
list.Add(&Test(...));

mat.Add(list);
generic_list.SumMatrix(mat);

It is converted to:
type __IList_Test interface {
GetCount() int;
GetItem(int Index) *Test;
}

type __IList_IList_Test interface {
GetCount() int;
GetItem(int Index) *__IList_Test;


}
type __IValue_Test interface {
GetValue() double;
}
type __ArrayList_Test struct {

func GetCount() int;
func GetItem(int Index) *Test;
func Add(Item *Test);
}
type __ArrayList_ArrayList_Test struct {
func GetCount() int;
func GetItem(int Index) *__ArrayList_Test;
func Add(Item *__ArrayList_Test);
}
func __SumMatrix_Test(M __IList_IList_Test) double;


Yeah, while __ArrayList_Test implements __IList_Test, if I read
correctly the language spec, __ArrayList_ArrayList_Test does not
implement __IList_IList_Test. In the "proposal" with the macros I
thought that with type erasure of interfaces this "implements" matching
will magically just work but clearly it is not the case.

Of course the interface method signature matching rules could be
loosened to allow using types which implement a given interface in place
of the interface. Did you considered this, and if you did, why did you
rejected from the Go language spec? (I can see performance concerns, but
were there other problems?)

NoiseEHC

unread,
Dec 30, 2009, 8:21:23 AM12/30/09
to Jonathan Amsterdam, golang-nuts

Thanks for the lecture! :)

> You can't express assignment compatibility with just interfaces. To do
> so you need to constrain one type parameter by another. See the
> CopyChan2 example in my spec. That turns out to be quite useful.
>

As I see assignment compatibility is for checking the generic
implementation before instantiating. Another use case can be (I am not
sure) related to instantiating another generics in a generic
implementation. Are there other use cases for assignment compatibility?
I mean that in the preprocessor generics example the generated code
simply will not compile in case the types are not assignment compatible.

> Of course you can't do metaprogramming a la C++. Take a look at any
> modern C++ book to see the wealth of things possible when you allow
> metaprogramming.
>

Ehh, if I have a choice then I would rather choose eternal damnation in
hell instead.... You know there is a reason I would like Go to succeed. :)
(BTW my real macro stuff would allow much fancier metaprogramming)

> Well, they use type hierarchies because they have type hierarchies.
> Because Go doesn't, a lot of machinery goes away.
>

The reason I asked about type systems is Russ Cox's message here:
http://groups.google.com/group/golang-nuts/msg/a8fcc5787490387c

How can those ML structure/signature/functor (whatever they are) be more
powerful than for example C# templates? Am I missing something (other
than that I do not want to learn ML), or is it just what you said: "But
they don't show that you can't do it, only that's it's a bit uglier."?

> C# allows other sorts of constraints on type parameters. One is for
> asserting that the instantiating type has a no-arg constructor. Go
> doesn't have constructors, so that goes away.
>

Actually only having no-arg constructors is a problem to me. Probably
the interface constraints should allow requiring static functions
(package functions) which could return new object instances. It could be
used to implement assignment compatibility (type casting) as well. Have
you thought about it?


Qtvali

unread,
Dec 30, 2009, 8:57:11 AM12/30/09
to golang-nuts
On Dec 30, 8:54 am, Popog <popo...@gmail.com> wrote:
> So am I missing something, (other than perhaps Ian's comments, which I
> think are relevant to this proposal).

Google for golang ctfe. Someone has created some working piece of
code. Then you can say, how nice it is to use.

Ian did already comment that topic - hard to debug, shows error
positions in generated code etc.

Jonathan Amsterdam

unread,
Dec 30, 2009, 10:42:35 AM12/30/09
to golang-nuts
> > You can't express assignment compatibility with just interfaces. To do
> > so you need to constrain one type parameter by another. See the
> > CopyChan2 example in my spec. That turns out to be quite useful.
>
> As I see assignment compatibility is for checking the generic
> implementation before instantiating.

Separate semantic checking is a crucial feature of any reasonable
generic system. It allows compilation errors to appear in a reasonable
place, rather than in the guts of some template instantiation; it
provides checkable documentation of what types are valid
instantiations; and it should speed up compilation, since checking the
body of the generic definition only has to happen once. Every language
except C++ has it, and C++ has been (vainly) trying to add it for
years.

The bad thing is that in the simple form I've adopted, it is very
restrictive -- there are many things you can't say. And to provide
more expressiveness, you seem to need a complicated design like C++
concepts. I claim that the simple way is the right way for Go -- it
lets you express most of the generic types and functions you typically
want to. That is a reasonable topic for discussion: are there good
examples of generic functions that, e.g., would benefit from being
able to write x++ where x is of generic type? I haven't seen any yet.

> How can those ML structure/signature/functor (whatever they are) be more
> powerful than for example C# templates? Am I missing something (other
> than that I do not want to learn ML), or is it just what you said: "But
> they don't show that you can't do it, only that's it's a bit uglier."?

I don't know whether the ML approach is more expressive than the C#
approach. If it only allows you to say "type T in this signature is
the same as type U in this other signature," then I think you can
always express that by repeating a type parameter, as in my graph
search example. I would love to see a proof one way or the other.

Even if it is more expressive, the question is whether the extra
machinery is worth it.

> > C# allows other sorts of constraints on type parameters. One is for
> > asserting that the instantiating type has a no-arg constructor. Go
> > doesn't have constructors, so that goes away.
>
> Actually only having no-arg constructors is a problem to me.

I'm confused. Presumably you're talking about Go, not C#. But Go
doesn't have constructors at all. Or are you equating the zero-
initialization you get from writing new(T) or var x T with a no-arg
constructor, and saying you don't like that? If so, then we are off
the topic of generics and on to the question of whether Go should have
constructors (which it clearly never will, since the designers
obviously considered and rejected the idea).

> Probably the interface constraints should allow requiring static functions
> (package functions) which could return new object instances. It could be
> used to implement assignment compatibility (type casting) as well. Have
> you thought about it?

You are talking about parametrizing on packages as well as types,
which I think over-complicates the design. If you need instances of
generic type to be constructed in a certain way other than the
default, then either the interface constraint should have an Init()
method, or the generic function should accept a factory function as an
(ordinary, non-generic) argument.

Bob Cunningham

unread,
Dec 30, 2009, 2:43:23 PM12/30/09
to Mike Zraly, Popog, golang-nuts
On 12/30/2009 03:14 AM, Mike Zraly wrote:
On Wed, Dec 30, 2009 at 1:54 AM, Popog <pop...@gmail.com> wrote:
I think someone has suggested this before, I can't remember where, but
what's the problem with creating a new template file-type and
associated paraphernalia?

The biggest problem I see with text-based templates is testing the template *as a template*, before instantiating it.  That is, as presently described, this method can only be tested when it is instantiated: A problem with a specific type may not be seen until the template has been in use for a while.

To get past this, we'd need a "template compiler" that can validate the template independently of how it can be instantiated.  Perhaps this can be done by extending Go's parser package (which would be a good place to start anyway).

The main goal of generic programming, as I see it, is to permit programmers to write less code by increasing code re-use by creating abstract operations on arbitrary types (think of generics as a micro version of Design Patterns).  But several assumptions are involved, the most central being that the abstracted code can be checked for some degree of correctness prior to its being instantiated.

If the template cannot be adequately checked prior to use, then you essentially create a situation where each template instantiation combines your new code with a template of unknown quality.  Finding and fixing compile-time errors will require each template user to be very familiar with the template source, which negates some of the idealized benefits of generics.

After the template use correctly compiles, we have the run-time issues.  As others have mentioned, run-time debugging has similar problems: When a run-time bug is found, it may be difficult to correctly partition the fix between the template source and the template use.  Again, the template user will need deep knowledge of the template source.

One or more tools will be needed to permit templates to be trusted to some extent before the first use.  I believe that's why generic implementations are made part of the language, and not implemented only as preprocessing steps.

-BobC


Popog

unread,
Dec 30, 2009, 4:29:05 PM12/30/09
to golang-nuts
On Dec 30, 1:14 am, Mike Zraly <mzr...@gmail.com> wrote:
> I suppose this question is more about go than your template proposal,
> but here goes anyway:
>
> Q: What about debugging support?  Strictly speaking users would
> be debugging the generated .go source, not the .goTemplate files
> used to direct their creation.  Is there a way to tell the debugger that the
> source is actually from the .goTemplate files, e.g. via the equivalent of
> #line and #file directives?

A: I'm don't know how to implement a debugger, nor do I know how Go is
going to implement debugging, so I'm really not sure I can answer this
properly. However, I'm not sure what the opposition to debugging the
generated .go file is, it's debugging normal code, this seems like a
good thing to me.

> Q: Won't it be a pain to manage template code that use types parametrized
> by one of their parameters, especially in library code?  For example
> consider
> a Graph template with Edge and Vertex type parameters that requires for its
> implementation Vectors parametrized by those same types.  The programmer
> ends up having to explicitly run your template instantiator for every
> combination

> of types and parameters used in a program.Is it feasible to write a


> utility that
> parses the .go and .goTemplate files to generates the set of instantiation
> commands required, so that it can be used within a Makefile?

A: If I understand you correctly, the Graph template could specify an
instantiation of the Vector template parametrized by the types
specified. And yes, explicit instantiation would be required, but
could be made easier programatically using the
".goTemplateInstantiator".

Also, my proposed 5/6/8t could be run from a Makefile, so I'm confused
by the later part of your question. Perhaps I should be more clear
though, 5/6/8t does not take command line arguments to understand how
templates are being instantiated. That is the purpose of
".goTemplateInstantiator".

Mike Zraly

unread,
Dec 30, 2009, 5:47:37 PM12/30/09
to Popog, golang-nuts
On Wed, Dec 30, 2009 at 4:29 PM, Popog <pop...@gmail.com> wrote:
On Dec 30, 1:14 am, Mike Zraly <mzr...@gmail.com> wrote:
> I suppose this question is more about go than your template proposal,
> but here goes anyway:
>
> Q: What about debugging support?  Strictly speaking users would
> be debugging the generated .go source, not the .goTemplate files
> used to direct their creation.  Is there a way to tell the debugger that the
> source is actually from the .goTemplate files, e.g. via the equivalent of
> #line and #file directives?

A: I'm don't know how to implement a debugger, nor do I know how Go is
going to implement debugging, so I'm really not sure I can answer this
properly. However, I'm not sure what the opposition to debugging the
generated .go file is, it's debugging normal code, this seems like a
good thing to me.

It's not a huge deal if you have the generated .go files, but these are intermediate
files after all, so you want to be able to map them back to the original .goTemplate
files to make any required changes.  At the very least you want some signal to
the harried programmer that the file he or she is looking at is NOT the source that
needs editing.

I was going to say that adjusting file/line data would help with displaying call stack
source code, but that's not really such a big deal here since the generated .go code
will probably have the same structure and whitespace as the .goTemplate code,
certainly a better match than you get from C/C++ macros or with code generators
like yacc.

> Q: Won't it be a pain to manage template code that use types parametrized
> by one of their parameters, especially in library code?  For example
> consider
> a Graph template with Edge and Vertex type parameters that requires for its
> implementation Vectors parametrized by those same types.  The programmer
> ends up having to explicitly run your template instantiator for every
> combination
> of types and parameters used in a program.Is it feasible to write a
> utility that
> parses the .go and .goTemplate files to generates the set of instantiation
> commands required, so that it can be used within a Makefile?

A: If I understand you correctly, the Graph template could specify an
instantiation of the Vector template parametrized by the types
specified. And yes, explicit instantiation would be required, but
could be made easier programatically using the
".goTemplateInstantiator".

Also, my proposed 5/6/8t could be run from a Makefile, so I'm confused
by the later part of your question. Perhaps I should be more clear
though, 5/6/8t does not take command line arguments to understand how
templates are being instantiated. That is the purpose of
".goTemplateInstantiator".

My apologies, I read the original post too quickly and missed that you were
using the .goTemplateInstantiator files to declare the required template instantiations
rather than the 5/6/8t command-line.  I can see that with this approach you don't
need to change the existing go parser or linker at all, and that is certainly a win.

What I was trying to ask was whether it would be feasible to write a utility that
reads .go and .goTemplate files and generates the .goTemplateInstantiator file(s)
for you, so that if some other person in your development team changes one
of the generic packages you use to rely on additional or different packages
(e.g. changes Graph from using Vector to using List) it doesn't break your build.


Popog

unread,
Dec 30, 2009, 8:43:15 PM12/30/09
to golang-nuts
> It's not a huge deal if you have the generated .go files, but these are
> intermediate
> files after all, so you want to be able to map them back to the original
> .goTemplate
> files to make any required changes.  At the very least you want some signal
> to
> the harried programmer that the file he or she is looking at is NOT the
> source that
> needs editing.

Hmm... Yes this is certainly a concern...

> What I was trying to ask was whether it would be feasible to write a utility
> that
> reads .go and .goTemplate files and generates the .goTemplateInstantiator
> file(s)
> for you, so that if some other person in your development team changes one
> of the generic packages you use to rely on additional or different packages
> (e.g. changes Graph from using Vector to using List) it doesn't break your
> build.

I'm not sure how this change would break the build.

Graph.goTemplate looks something like this (forgive me, I don't know
how to write a graph library)
import Vector;

type GraphTemplate template</*template params go here*/>
{
instantiate Vector</*TPGH*/>;
type GraphContainer</*TPGH*/> Vector</*TPGH*/>;


type Graph</*TPGH*/> struct{/*More stuff goes here */}
/*More stuff goes here */
}
EOF

You make "alpha.goTemplateInstantiator" as follows:
import "Graph";

instantiate GraphTemplate</*template params go here*/>;
/* More stuff */
EOF

Am I missing something?

Qtvali

unread,
Dec 30, 2009, 8:59:45 PM12/30/09
to golang-nuts
On Dec 31, 3:43 am, Popog <popo...@gmail.com> wrote:
> > It's not a huge deal if you have the generated .go files, but these are
> > intermediate
> > files after all, so you want to be able to map them back to the original
> > .goTemplate
> > files to make any required changes.  At the very least you want some signal
> > to
> > the harried programmer that the file he or she is looking at is NOT the
> > source that
> > needs editing.
>
> Hmm... Yes this is certainly a concern...

I think those templates are ugly. Feel like ugly hack.

Anyway - having a Go library, which is able to produce Go source files
from some base of data (in such way that one has methods to add
function, parse some string into this function etc.) would be a nice
library, I think.

NoiseEHC

unread,
Dec 31, 2009, 7:31:31 AM12/31/09
to Jonathan Amsterdam, golang-nuts

Separate semantic checking is a crucial feature of any reasonable
generic system. It allows compilation errors to appear in a reasonable
place, rather than in the guts of some template instantiation; it
provides checkable documentation of what types are valid
instantiations; and it should speed up compilation, since checking the
body of the generic definition only has to happen once. Every language
except C++ has it, and C++ has been (vainly) trying to add it for
years.
  

Yeah, I know the advantages of semantic checking before instantiation. My question was whether assignment compatibility has other uses I do not know about other than supporting separate semantic checking (after your answer I am assuming that it is just for this feature).

So then it seems to me that the type parameters in the generic types are only used to restrict types passed into functions, and avoid casting types returned from functions (I mean compared to the version which is a simple library using only Go interfaces and no generics). The reason I am thinking about it is that it could sidestep the problem of extending the language with constructs of generics if macros could use semantically checked library code and just rewrite them with the actual types. So it would be checked as it is checked now but could be instantiated and inlined if needed (macro could decide, and a future optimizing Go compiler could inline).

Is this "solution" would be too lame or too much like a hack? Or does it loose too much expressiveness to not worth it?

How can those ML structure/signature/functor (whatever they are) be more
powerful than for example C# templates? Am I missing something (other
than that I do not want to learn ML), or is it just what you said: "But
they don't show that you can't do it, only that's it's a bit uglier."?
    
I would love to see a proof one way or the other.
  

Me too!!! :)


Actually only having no-arg constructors is a problem to me.
    
I'm confused. Presumably you're talking about Go, not C#. But Go
doesn't have constructors at all. Or are you equating the zero-
initialization you get from writing new(T) or var x T with a no-arg
constructor, and saying you don't like that? If so, then we are off
the topic of generics and on to the question of whether Go should have
constructors (which it clearly never will, since the designers
obviously considered and rejected the idea).

  

I was talking about generics having constructor constraints in general because I had problems with having only the default constructor in C#. Somehow I managed to project it to Go where it is clearly not applicable (your Init() solution is a solution, I was a little bit dumb...). Now I see that the only reason I am so obsessed with constructors is because in C# I use "readonly" fields all the time and one can initialize them only in constructors. Since Go does not have readonly fields, we can skip this dumb idea.... (And just use Init() in the interface, thanks.)



Jonathan Amsterdam

unread,
Dec 31, 2009, 2:30:01 PM12/31/09
to golang-nuts
> The reason I
> am thinking about it is that it could sidestep the problem of extending
> the language with constructs of generics if macros could use
> semantically checked library code and just rewrite them with the actual
> types. So it would be checked as it is checked now but could be
> instantiated and inlined if needed (macro could decide, and a future
> optimizing Go compiler could inline).

So you want an ordinary go function that is expressed in terms of the
constraint interfaces, for semantic checking, and then you want to
macroexpand in the actual types for speed. That will sort of work, but
not perfectly. Your library function may compile fine, but some
instantiations of it will not. Here's an example from my spec:

func f<T, U>(u U) {var t T = u}

The corresponding function with interfaces is:

func f'(u interface{}) { var t interface{} = u }

which is perfectly legal. But the instantiation f<int, double> is not.

> Is this "solution" would be too lame or too much like a hack? Or does it
> loose too much expressiveness to not worth it?

I find all this talk of macroexpanding, preprocessing and the like to
be pretty depressing. All of those techniques sorta work, at the cost
of obscure error messages, debugging issues, lack of implicit
instantiation, etc. But we should be exploring them as a last resort,
after the Go people definitively say No to generics. I think a more
productive use of our time would be to demonstrate how generics can be
added to the language as cleanly and simply as possible.

roger peppe

unread,
Jan 1, 2010, 8:13:03 AM1/1/10
to Jonathan Amsterdam, golang-nuts
2009/12/24 Jonathan Amsterdam <jbams...@gmail.com>:

>
>> you can't just substitute the original type either, otherwise
>> this:
>>
>> func foo(a 't1, b 't2) 't1 {
>>     var i interface{} = b
>>     return i.('t1)
>>
>> }
>>
>> would incorrectly succeed when 't1 and 't2
>> have the same actual type.
>>
>
> Still confused. Why would it incorrectly succeed in that case? It
> would CORRECTLY succeed!

i guess it depends what external semantics you want from
your generics.

in languages such as haskell, if i have a generic function

foo :: a -> b -> a

and i call it as: foo 3 5
then i know statically and for absolutely sure that
the result must be 3, as foo can't mix up its
type parameters, even if they happen to be instantiated
to the same type.

in Go, currently if i have two variables with differently named
types and i box them into an interface{}, then the types will still
be distinguishable. if we do things your way, then this property
is lost for generic types.

Mike Zraly

unread,
Jan 2, 2010, 9:18:31 PM1/2/10
to Popog, golang-nuts
On Wed, Dec 30, 2009 at 8:43 PM, Popog <pop...@gmail.com> wrote:
[...]

> What I was trying to ask was whether it would be feasible to write a utility
> that
> reads .go and .goTemplate files and generates the .goTemplateInstantiator
> file(s)
> for you, so that if some other person in your development team changes one
> of the generic packages you use to rely on additional or different packages
> (e.g. changes Graph from using Vector to using List) it doesn't break your
> build.

I'm not sure how this change would break the build.

Graph.goTemplate looks something like this (forgive me, I don't know
how to write a graph library)
       import Vector;

       type GraphTemplate template</*template params go here*/>
       {
               instantiate Vector</*TPGH*/>;
               type GraphContainer</*TPGH*/> Vector</*TPGH*/>;


               type Graph</*TPGH*/> struct{/*More stuff goes here */}
               /*More stuff goes here */
       }
EOF

You make "alpha.goTemplateInstantiator" as follows:
       import "Graph";

       instantiate GraphTemplate</*template params go here*/>;
       /* More stuff */
EOF

Am I missing something?

Let me give a concrete example.  Let's use something simpler than a graph.  Consider this simple, non-generic struct for recording data and calculating the median value:

package stat

import "container/vector"
import "sort"

type MedianCalculator struct {
    nums vector.IntVector;
}

func (mc *MedianCalculator) Record(num int) { mc.nums.Push(num) }

func (mc *MedianCalculator) Median() (result float64) {
    len := mc.nums.Len();

    if len == 0 {
        return // TODO: return error
    }

    sort.Sort(&mc.nums); // TODO: don't sort, partition

    if (len % 2) == 1 {
        mid := (len - 1) / 2;
        result = float64(mc.nums.At(mid));
    } else {
        hi := len / 2;
        lo := hi - 1;
        result = (float64(mc.nums.At(lo)) + float64(mc.nums.At(hi))) / 2;
    }

    return;
}

MedianCalculator records int values. Its Median() method return a float64 result to handle averaging the middle two values when there are an even number of values.  MedianCalculator relies on vector.IntVector to store the values.

Now consider a generic version of MedianCalculator that allows you to parametrize the value type.  It might look like this:

package stat

import "container/vector" // assumes updated to support generic vector{T} for any T
import "sort"

type MedianCalculator{T} struct {
    nums vector.Vector{T}
}

func (mc *MedianCalculator{T}) Record(num T) { mc.nums.Push(num) }

func (mc *MedianCalculator{T}) Median() (result float64) {
    // same as non-generic version
}

In the generic version, MedianCalculator has been replaced with MedianCalculator{T}, and vector.IntVector has been replaced with vector.Vector{T}.  Everything else is the same.

If I understand your proposal correctly, to use MedianCalculator{T} I would have something like this in my .go file:

package main
import "stat"
func main() {
    mc := new(MedianCalculatorInt); // note we DON'T use MedianCanculator{int}
    mc.Record(1);
    mc.Record(-3);
    mc.Record(-2);
    print(mc.Median(), "\n");
}

and in the .goTemplateInstantiator file I would have something like this to request instantiation of MedianCalculator for type int under the name MedianCalculatorInt:

import "stat"
instantiate MedianCalculator{int} as MedianCalculatorInt

Upon reading this file your *t command would expand the expand the definition of MedianCalculator{T} for T=int into a source file somewhere, then compile it with *g into an ordinary go object file.  The developer would be responsible for ensuring that it gets linked into the application.

The questions I have are about how to handle generation of the code for vector.Vector{int} used by MedianCalculator{int}:

1. Would your tool be smart enough to make sure that code for vector.Vector{int} also gets generated?

2. If yes, how would your tool avoid duplicating work or code if another package also uses vector.Vector{int}?

3. If no, i.e. if your tool relies on the developer to list dependent generic types in the .goTemplateInstantiator file (which is how I first read your proposal), what happens when the implementation changes to use something other than vector.Vector{int}, say list.List{int}?  Would it be possible for a change in the library implementation to cause a build failure because it requires library users to update .goTemplateInstantiator files to ensure instantiation of code they only use indirectly?

Just trying to understand the implications ...

Popog

unread,
Jan 3, 2010, 5:20:23 AM1/3/10
to golang-nuts
> Upon reading this file your *t command would expand the expand the
> definition of MedianCalculator{T} for T=int into a source file somewhere,
> then compile it with *g into an ordinary go object file. The developer
> would be responsible for ensuring that it gets linked into the application.

First off, my apologies for being unclear, but *t command would expand


the expand the definition of MedianCalculator{T} for T=int into a

source file at a specified or defaulted location. The developer is
then responsible for compiling and linking the generated source file.

*t could also take multiple input files, though I'm not sure if it
would produce multiple output files (one for each input) or a single
file. I could go either way on this one.

> 1. Would your tool be smart enough to make sure that code for
> vector.Vector{int} also gets generated?

1. Yes, the template for MedianCalculator{T} would be able to specify
that it relies on the existence of vector.Vector{T}.


> 2. If yes, how would your tool avoid duplicating work or code if another
> package also uses vector.Vector{int}?

2. Code duplication within a package could easily be handled during
the template expansion check (when a request to expand a template is
processed, just check if you've already expanded it with those
parameters). Code duplication across multiple packages… not gonna be
as easy…

Now if a template did not rely on user defined types when
instantiated, that instantiation could be expanded separately,
compiled, packaged, and placed into a repository. Then, in the
normally generated go file which contains the normally expanded
templates, an import could be inserted to include the library in the
repository.

Unfortunately, this optimization will slow down template expansion (I
don't know how significantly, but it's still a consideration), as it
adds more checks, a compile step, and a pack step. Also, it makes
writing *t more complicated, but note that the compiler is still
untouched.


> 3. If no, i.e. if your tool relies on the developer to list dependent
> generic types in the .goTemplateInstantiator file (which is how I first read
> your proposal), what happens when the implementation changes to use
> something other than vector.Vector{int}, say list.List{int}? Would it be
> possible for a change in the library implementation to cause a build failure
> because it requires library users to update .goTemplateInstantiator files to
> ensure instantiation of code they only use indirectly?

3. I think the answer to #1 makes this question irrelevant, but just
to be as clear as possible: Developers are not required to list
dependent generic types. A change in library implementation (e.g.
switching from lists to vectors) could not cause a build failure
related to template instantiation.

Also, I did some thinking, and I can't think of a reason for two new
file types as opposed to one. Using one would make it much easier to
write a template and instantiate it, because you only need one file.

Additionally, I tried looking into golang-ctfe, because it sounds
kinda like what I'm proposing but http://code.google.com/p/golang-ctfe/
keeps 403ing me.

Popog

unread,
Jan 3, 2010, 6:03:57 AM1/3/10
to golang-nuts
On Jan 3, 12:20 am, Popog <popo...@gmail.com> wrote:
> Now if a template did not rely on user defined types when
> instantiated, that instantiation could be expanded separately,
> compiled, packaged, and placed into a repository. Then, in the
> normally generated go file which contains the normally expanded
> templates, an import could be inserted to include the library in the
> repository.
>
> Unfortunately, this optimization will slow down template expansion (I
> don't know how significantly, but it's still a consideration), as it
> adds more checks, a compile step, and a pack step. Also, it makes
> writing *t more complicated, but note that the compiler is still
> untouched.

Wow, talk about missing the obvious. I never realized you can
import .go files… I feel kinda stupid now… Well that at the very least
means you don't have to compile and pack, so the optimization won't be
slower, but it also completely changes my outlook on templates,
meaning I probably shouldn't have disregarded this:

> Upon reading this file your *t command would expand the expand the
> definition of MedianCalculator{T} for T=int into a source file somewhere,
> then compile it with *g into an ordinary go object file. The developer
> would be responsible for ensuring that it gets linked into the application.

It's probably the way to go.

Popog

unread,
Jan 3, 2010, 5:39:36 PM1/3/10
to golang-nuts
Now I'm really embarrassed. You can't import .go files, I was very
tired when I "figured that out" and failed to realize I had the build
directory and the source directory in the same location and was merely
importing the object files.

So that's the problem with linking them and stuff.

Let's say you have a file Alpha.go in package Alpha that defines a new
type A. Alpha.go also contain functions that use vector{Alpha.A}. You
build the file to instantiate a vector{Alpha.A}. *t is able to expand
the template, but *g is not able to find a definition for Alpha.A
without importing Alpha. However, Alpha can't be built because it
needs to import the template.

So we're back to generating .go files and occasionally object files in
some repository. Which means we're only preventing code duplication
across packages for non-user defined types.

Jonathan Amsterdam

unread,
Jan 4, 2010, 12:35:38 PM1/4/10
to golang-nuts
> >> you can't just substitute the original type either, otherwise
> >> this:
>
> >> func foo(a 't1, b 't2) 't1 {
> >>     var i interface{} = b
> >>     return i.('t1)
>
> >> }
>
> >> would incorrectly succeed when 't1 and 't2
> >> have the same actual type.
>
> > Still confused. Why would it incorrectly succeed in that case? It
> > would CORRECTLY succeed!
>
> i guess it depends what external semantics you want from
> your generics.
>
> in languages such as haskell, if i have a generic function
>
> foo :: a -> b -> a
>
> and i call it as: foo 3 5
> then i know statically and for absolutely sure that
> the result must be 3, as foo can't mix up its
> type parameters, even if they happen to be instantiated
> to the same type.

That's just a consequence of the fact that Haskell does not have an
"any" type like Go's interface{}.

> in Go, currently if i have two variables with differently named
> types and i box them into an interface{}, then the types will still
> be distinguishable. if we do things your way, then this property
> is lost for generic types.

That is not true. My proposal's semantics, after type checking, is
just hygienic substitution of actual types for type parameters, so
nothing could be lost.

roger peppe

unread,
Jan 4, 2010, 1:34:46 PM1/4/10
to Jonathan Amsterdam, golang-nuts
2010/1/4 Jonathan Amsterdam <jbams...@gmail.com>:

>> in languages such as haskell, if i have a generic function
>>
>> foo :: a -> b -> a
>>
>> and i call it as: foo 3 5
>> then i know statically and for absolutely sure that
>> the result must be 3, as foo can't mix up its
>> type parameters, even if they happen to be instantiated
>> to the same type.
>
> That's just a consequence of the fact that Haskell does not have an
> "any" type like Go's interface{}.

actually, haskell does have something similar to Go's interface{} - it's
called Data.Dynamic.

>> in Go, currently if i have two variables with differently named
>> types and i box them into an interface{}, then the types will still
>> be distinguishable. if we do things your way, then this property
>> is lost for generic types.
>
> That is not true. My proposal's semantics, after type checking, is
> just hygienic substitution of actual types for type parameters, so
> nothing could be lost.

if the same type is substituted for two generic type parameters,
then those two generic types will no longer be distinguishable
inside the generically defined function, even though they have
different names there.

Jonathan Amsterdam

unread,
Jan 4, 2010, 1:52:15 PM1/4/10
to golang-nuts
> if the same type is substituted for two generic type parameters,
> then those two generic types will no longer be distinguishable
> inside the generically defined function, even though they have
> different names there.

Okay, I finally understand your point. But I don't think I care about
that. I (and other programmers familiar with C++/Java/Eiffel/C#) are
comfortable with the hygienic macroexpansion semantics. I don't see
what goodness I'm giving up by using that model. (That I can infer
that foo:: a->b -> a, when called as foo 3 5, always returns 3, does
not seem like a particularly valuable property to me.)

NoiseEHC

unread,
Jan 9, 2010, 7:18:39 AM1/9/10
to Jonathan Amsterdam, golang-nuts

> So you want an ordinary go function that is expressed in terms of the
> constraint interfaces, for semantic checking, and then you want to
> macroexpand in the actual types for speed. That will sort of work, but
> not perfectly. Your library function may compile fine, but some
> instantiations of it will not. Here's an example from my spec:
>
> func f<T, U>(u U) {var t T = u}
>
> The corresponding function with interfaces is:
>
> func f'(u interface{}) { var t interface{} = u }
>
> which is perfectly legal. But the instantiation f<int, double> is not.
>
>

The macro could check types programmatically, the real question is
whether it would be usable or not. (It is a rhetorical question, see the
end of this message...)

> I find all this talk of macroexpanding, preprocessing and the like to
> be pretty depressing. All of those techniques sorta work, at the cost
> of obscure error messages, debugging issues, lack of implicit
> instantiation, etc. But we should be exploring them as a last resort,
> after the Go people definitively say No to generics. I think a more
> productive use of our time would be to demonstrate how generics can be
> added to the language as cleanly and simply as possible.
>

I did not notice that we could influence Go authors in the slightest
sense so I would not comment on the most productive use of our time...
:) My goal was in this thread to understand whether macroexpanding could
or could not replace generics (in theory). Now that you did not show an
absolute requirement which cannot be solved with macros I can see this
generics thing much more clearly so thanks for the effort you put into
this thread. Whether Go authors will or will not implement a macro
system is another thing, personally I have some little hope deep in the
corner of my soul that they at least read through this thread so *maybe*
one of them will think about stepping out the usual generics
implementations and do it differently. (A macro system would be a
very-very powerful and orthogonal feature in the language IMHO.
Personally I would like something powerful enough to be able to
implement "yield return" in it.)


NoiseEHC

unread,
Jan 16, 2010, 8:51:57 AM1/16/10
to Ian Lance Taylor, golang-nuts
PING!

Ian Lance Taylor

unread,
Jan 16, 2010, 1:35:48 PM1/16/10
to NoiseEHC, golang-nuts
NoiseEHC <Nois...@freemail.hu> writes:

We did not consider changing method signature matching to permit types
which implement an interface in place of the interface. It would be
difficult to make this work efficiently, because a non-interface value
and an interface value do not look the same at runtime. That means
that the value would have to be converted somewhere, which means that
some sort of function stub would have to be created to do the
conversion when calling the method. As far as I can see, that
function stub would have to be created at runtime--there is no way to
create it statically. Anything which requires runtime code generation
is complex and slow.

Ian

Steven Blenkinsop

unread,
Jan 17, 2010, 1:05:28 AM1/17/10
to golang-nuts
Is manually wrapping functions particularly inefficient?
eg:

func A (a, b interface{foo()}) { ... }
func B (a interface{foo()}){...}

func Wrap() (func(MyInt, MyInt), func(MyInt)) {
wrappedA := func(a, b MyInt) { A(a, b) }
wrappedB := func(a MyInt) { B(a) }

return wrappedA, wrappedB
}
OR
func AWrapped(a, b MyInt) { A(a, b) }
func BWrapped(a MyInt) { B(a) }

*********************************

I was thinking about ML generics in Go. The contents of structures
passed to functors really amount to types, and functions acting on
those types, which really amount to what in Go would be methods. So
what a functor would receive would make sense as types, since they
bring the methods with them. They could then be constrained by
interfaces, or perhaps something like an interface but stronger (like
a generic type that becomes an alias for the passed type as long as
the passed type implements certain features, perhaps just functions,
maybe type compatibility)

type T generic { foo(T), bar() T } // as a type, though it is
inconsistent with other types, so maybe:
generic T int { ... } // must be int derived type
generic T { foo(T), bar() T }

(should point out now that syntaxes are more demonstrative than
suggested)
As for what a functor would be, making it have to be (in) a separate
package seems a bit restrictive, especially for small amounts of
generic code. And changing a package to be able to be defined (as a
functor) within another package seems like a radical change for an
unnecessary generalization. So, I think it should be an entity in and
of itself, which serves as a sandbox for defining generic
"things" (funcs, types...). (this says nothing with regards to actual
implementation, just concepts)

As for what a functor returns, I'm split two ways. Part of me thinks
it would be convenient for it to return a type, which would make
nesting easy:

functor Vector(T) {...; become vector}
var a Vector(Vector(int))

However, this would disallow defining unbound functions.

The other is to simply become an initialized functor, in which types
and functions (and any values those functions use) are defined:

functor Comparisons(Comparable) {...}

Comparisons(MyInt).Max(a, b)

This isn't quite as convenient for types:
var v Collections(Collections(int).Vector).Vector

Perhaps a qualified result would be beneficial (though perhaps
impractical and/or inconsistent):

functor Vector(T) type { become type vector struct{...}; ... }
functor Collections(T) {...} // results in a namespace for its
contents
functor Max(T) func(T)(T) {...}

And, irrespective of the implementation, aliasing is practically a
necessity, since generic names can get quite long:

alias IntMatrix Collections(Collections(int).Vector).Vector

I'm not sure that any of these approaches would provide any advantage
over Jonathan's proposal, except to avoid angle brackets and
association with Java generics ;-) It was more just thinking through
the scenario.

Russ Cox

unread,
Jan 17, 2010, 2:56:27 PM1/17/10
to Steven Blenkinsop, golang-nuts
On Sat, Jan 16, 2010 at 22:05, Steven Blenkinsop <stev...@gmail.com> wrote:
> Is manually wrapping functions particularly inefficient?

I don't know, but the larger problem is that it's not sufficient
to implement what people expect out of generics.

For example, there is no wrapping that lets you turn
container/vector's Vector into its IntVector, because
of the Data method.

Russ

Joe Gregorio

unread,
Jan 26, 2010, 3:05:05 PM1/26/10
to golang-nuts

On Dec 18 2009, 4:08 pm, Russ Cox <r...@golang.org> wrote:
> For many people "generics" means "templates" or "Java generics"
> or "C# generics" or some other thing that essentially boils down
> to a macro system with types as the parameters.  The discussion
> on this thread so far has assumed we want to build something
> equivalent in power to Java's or C#'s generics and has been focusing
> on what the syntax should be.  That's not really interesting.
>
> This paperhttp://www.osl.iu.edu/publications/prints/2003/comparing_generic_prog...
> makes a pretty good argument that the "type parameters" approach
> to generics is fundamentally weak.  I think it would be much more
> interesting to consider how to apply something like ML's module
> system to Go in a way that fits nicely with the rest of the system.
> The paper makes a pretty good case that ML's modules have
> important benefits over C# and Java's generics and even over
> C++'stemplates.

Interesting paper, and I liked how ML moves the pattern of using
low-level templating mechanism for concepts up higher into a language
feature.

I'm not expecting definitive answers, but what are your thoughts on:

1. Providing 'built in' concepts? For example, would Go provide some
concepts such as Numerical, that could only
be satisfied by built in numerical types?

2. Linking some built in concepts to language features? For example,
could
Go provide an Iterable concept that could then be used in for
loops.

Thanks,
-joe

>
> The problem I have trying to apply ML's model to Go is what
> the ideas map to.  A structure feels most like a Go package,
> and a signature could be a newconcept(interface for a package,
> more or less) but then what does a functor return?  It probably
> can't return a new package, but if not it can't be the input to
> another functor, and you do want to be able to write things like
> Vector(Vector(int)).  At the same time, mapping structure to type
> and signature to interface is probably too limiting.  The paper
> makes a good case that much of the verbosity of the non-ML
> systems boils down to not having a structure/signature
> idea to represent a collection of names.
>
> I am skeptical of any proposal that includes the words
> "type erasure".  Reading the papers about Java generics
> suggests that type erasure is more a clumsy hack than a
> model to be emulated.  I think that if the source code says
> Vector(Vector(int)) and all you can see at runtime is Vector,
> that's a serious limitation.  Java made that decision for
> backwards compatibility with a large (at the time) installed
> base.  Whatever Go does, backwards compatibility with
> existing containers should not be a constraint.
>
> Russ

Reply all
Reply to author
Forward
0 new messages