Gonerics - Generics proposal

[Lars Pensjö]

I found this proposal in reddit forum: Idiomatic Generics in Go. It is a solution that can be used already as-is.

General principle is to import from a "magic" address that will replace T with a specified type. E.g. doing:

import "gonerics.io/d/set/int.git"

where the "int" will be used as a type.

If the language would be changed to support this, a new variant of the import statement could be added. E.g. a template import syntax could be:

template "github.com/xxx/set"<int>

This would make the package "set" availble for type "int", with the option to rename it in the same way import packages can be renamed.

Please excuse me if this idea has already been investigated.

[egon]

Yeah, I've proposed a similar approach before, a few years ago; with the addition that the type being replaced must be an interface, and while importing you must explicitly name the interface you are replacing.

Anyways, after writing Go for a while I realized how little use is for generics. They are fun things to do with the language, but most of the time you have only few places in your code where you need it. And if you need it, it's quite easy to generate them from a template.

Of course there are special cases for building up DSL-s e.g. Rx stuff... and this approach doesn't solve it nicely.

+ egon

[Jérôme Champion]

Basically, it's generics at the package level. The trick is neat :)

I don't really like the fact the it doesn't offer a facility to write generic package that are compilable.

It does suffer for cyclic import ( like every method that rewrite package ) : you can't define a type and use it in another generic package. ( I think it's a problem that can't be solved without language support )

It's nice to see there are still ideas about generics being worked on.

[Jesper Louis Andersen]

On Wed, Oct 1, 2014 at 9:26 AM, Jérôme Champion <cham...@gmail.com> wrote:

Basically, it's generics at the package level. The trick is neat :)

I have a hunch a proper solution for generics in Go has to be at the package level. When I saw this, I immediately thought "this is an implementation of a weak form of Standard ML functors":

when we write "package p" in a set of files, we create a new package. This package has a signature, which is the set of its exported symbols. When you import a package `import "../p"` the rule is that any name you refer as p.<N> has to be in the signature of the package. Otherwise, the compile will fail. Furthermore, the types of the signature has to match those of its uses.

Now, any import will require a subset of the signature. Either all of the package, or a proper subset. The principle of substitution holds. If I write

import p "pkg/path/foo"

and subsequently use `p.N`, I can substitute this with

import p "pkg/path/bar"

which is safe, provided the signature subset I use matches: foo and bar exports the same symbols with the same types for the subset I am using in my package. And modularity is all about this substitution principle. I can replace foo with bar as long as they have the same semantics.

A functor is a function at the package level. That is, they are packages with "holes", much like a generic class is a class with "holes" into which we can fill details. So we can write:

package intset = set(ints)

package stringset = set(strings)

for properly constructed packages set, ints, strings. The implementation would handle this by *expansion*, like in C++ templates or the MLton standard ML compiler. In practice, these expansions doesn't hurt much, experience shows.

The problem with regard to compilation speed, however, can't be ignored. I do believe the added benefit of these kinds of constructions far outweigh the added compilation speed, but one has to acknowledge this isn't a flat compilation space anymore. Deeply nested "package compositions/functors" will lead to vastly increased compilation times. Also, it messes with separate compilation since you can't compile the set(·) file in advance unless your linker understands the inlining directives at the package level. Russ Cox's dictum rings true here:

* Either you leave out this construction, slowing down the programmer

* Or you implement composition of packages by indirection of reference, like Java, slowing down the implementation

* Or you implement composition of packages by expansion, like MLton or C++ templates, slowing down the compiler

I much prefer the last option, but do note that in a world where programmers are abundant and compilation times are the limiting factor, the first option is actually more useful.

My hunch is you can pull off the above construction. OCaml has this, and also has a form for structural subtyping like Go, so it seems to be possible to marry the two concepts in a type-safe way. Albeit the language is perhaps not the one with the easiest-to-graph type errors.

--
J.

[egon]

On Wednesday, 1 October 2014 13:39:07 UTC+3, Jesper Louis Andersen wrote:

On Wed, Oct 1, 2014 at 9:26 AM, Jérôme Champion <cham...@gmail.com> wrote:

Basically, it's generics at the package level. The trick is neat :)

I have a hunch a proper solution for generics in Go has to be at the package level. When I saw this, I immediately thought "this is an implementation of a weak form of Standard ML functors":

when we write "package p" in a set of files, we create a new package. This package has a signature, which is the set of its exported symbols. When you import a package `import "../p"` the rule is that any name you refer as p.<N> has to be in the signature of the package. Otherwise, the compile will fail. Furthermore, the types of the signature has to match those of its uses.

Now, any import will require a subset of the signature. Either all of the package, or a proper subset. The principle of substitution holds. If I write

import p "pkg/path/foo"

and subsequently use `p.N`, I can substitute this with

import p "pkg/path/bar"

which is safe, provided the signature subset I use matches: foo and bar exports the same symbols with the same types for the subset I am using in my package. And modularity is all about this substitution principle. I can replace foo with bar as long as they have the same semantics.

A functor is a function at the package level. That is, they are packages with "holes", much like a generic class is a class with "holes" into which we can fill details. So we can write:

package intset = set(ints)

package stringset = set(strings)

for properly constructed packages set, ints, strings. The implementation would handle this by *expansion*, like in C++ templates or the MLton standard ML compiler. In practice, these expansions doesn't hurt much, experience shows.

The problem with regard to compilation speed, however, can't be ignored. I do believe the added benefit of these kinds of constructions far outweigh the added compilation speed, but one has to acknowledge this isn't a flat compilation space anymore. Deeply nested "package compositions/functors" will lead to vastly increased compilation times. Also, it messes with separate compilation since you can't compile the set(·) file in advance unless your linker understands the inlining directives at the package level. Russ Cox's dictum rings true here:

* Either you leave out this construction, slowing down the programmer

* Or you implement composition of packages by indirection of reference, like Java, slowing down the implementation

* Or you implement composition of packages by expansion, like MLton or C++ templates, slowing down the compiler

BTW. regarding boxing vs. expansion; you can implement boxing with expansion... of course the expansion wouldn't be a free lunch...

E.g.

// package stack

type T interface{}

type Stack []T

func (s *Stack) Push(v T) { *s = append(*s, v) }

func (s *Stack) Pop() (r T) {

n := len(*s) - 1

r, *s = *s[n], *s[:n]

return

}

// package stack/boxed

import "stack"

type T interface{}

type Stack struct{ stack.Stack }

func (s *BoxedStack) Push(v T) { s.Stack.Push(v) }

func (s *BoxedStack) Pop() T   { return s.Stack.Pop().(T) }

// and depending how you import

import istack "stack" {T : int}

import bstack "stack/boxed" {T:int}

In bstack case it would specialize only the "type specific interface".

In istack it would specialize the whole package.

[Tad Vizbaras]

Apart from custom collections where else would I need generics for?

I had impression Go is missing many features when I started using it. 

Now after about 18 months using Go I realized that most other languages have way too many useless features, 

corner cases that make code unreadable after 2 weeks (unreadable even by programmer who wrote it).

It is bloatware parade out there.

Go is light on the page. You can even read standard library and understand what is going on. Not that many languages

have such readability.

[egon]

On Wednesday, 1 October 2014 15:04:59 UTC+3, Tad Vizbaras wrote:

Apart from custom collections where else would I need generics for?

Possible use cases:

1. cleaner code:

utility functions for channels (e.g. merge multiple) 

utilty functions for arrays (convert to []interface{})

2. performance optimizations:

Collections

Custom allocators/pools

Matrices, Graphs

Performance Sensitive Algorithms

3. type-safety:

Functional stuff

Non-trivial language extensions:

  e.g. Rx, LINQ, ORM, Logic programming, Event Handlers

Of course whether to do them at all, is a separate discussion. 

my opinion regarding these 3 classes of problems

1. cleaner code - these usually give only marginal improvement to code

2. performance optimization - collections: not having generics means you need to think twice before doing such optimizations; and most of it can be generated. Regarding matrices, graphs, performance sensitive algorithms can make different trade-offs i.e. you probably can allow compilator optimizations, code-size that is not acceptable for "general programs".

3. here, should we be using Go here at all... we are trying to fit a differ model into a language, maybe it's a better approach to create use an embedded language and let them communicate, rather to make a language that does everything.

+ egon

[Tad Vizbaras]

Matrices, graphs, linked lists, rings, pools, double-linked lists, heaps are they all not a "collections" in general sense of the word?

I understand that getting something from current container/ring requires type assertion or type switch, and it is 

only at runtime you get error instead of compiler checking this for you. Yes, it is inconvenience.

I would not like LINQ, ORM baked into the language. This is clearly library material to me. Today we have SQL, tomorrow NoSQL and

day after tomorrow maybe lessSQL or something else. Most ORMs end up tied too much into actual data sources they work on.

[Jonathan Lawlor]

This seems like the tip of an iceberg.  I could imagine a service that stores templates that users can call go gen on with parameters provided by a URL.

[Daniel Skinner]

hey now, that's an interesting thought

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

[David Thomas]

Who was it that came up with the idea of the language not defining an interpretation of a package path and having it just be a string to enable novel tools? Because that really was an awesome idea. 

[Willa Walthall]

import (
intHeap "collections.co/heap?T=int"
strList "collections.co/list?T=string"
)

Could even use a type from a package, as in.

import (
ideaList "collections.co/list?T=github.com/ghthor/journal/idea.Idea"
)

Does anyone know if something like this in the wild yet?

[Andreas Doerr]

Now after about 18 months using Go I realized that most other languages have way too many useless features, 

corner cases that make code unreadable after 2 weeks (unreadable even by programmer who wrote it).

It is bloatware parade out there.

Go is light on the page. You can even read standard library and understand what is going on. Not that many languages

have such readability.

+1

If people would like to use a language with generics, go and pick one of the many choices available. Go does allow the average programmer (and by definition, most programmers are average) to produce clean and readable code, which they even do have a chance to fully comprehend. This is possible to a large degree because of all the features Go does *not* have. Always keep in mind:

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
Antoine de Saint-Exupery

[Robert Melton]

On Thu, Oct 2, 2014 at 3:02 AM, Andreas Doerr <nemo...@gmail.com> wrote:
> If people would like to use a language with generics, go and pick one of the
> many choices available. Go does allow the average programmer (and by
> definition, most programmers are average) to produce clean and readable
> code, which they even do have a chance to fully comprehend. This is possible
> to a large degree because of all the features Go does *not* have.

Herb Sutter recently did a talk about "Back to the Basics! Essentials
of Modern C++ Style" ( http://youtu.be/xnqTKD8uD64 ) and one of his
major refrains was "even if you as an expert can, should you?", made
many points regarding the average programmer and what you should see
in production code (and what you shouldn't). My favorite example in
that regard was the Perfect Forwarding Example (which blew my mind a
little bit): http://youtu.be/xnqTKD8uD64?t=1h15m22s

--
Robert Melton | http://robertmelton.com

[egon]

"A template is just a poor man's text processor." - Mike Acton

https://www.youtube.com/watch?v=rX0ItVEVjHc#t=4276

+ egon

 

[Robert Melton]

That is fantastic Egon -- hadn't gotten to that talk yet.

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

[Eduard Castany]

Go could at least have a magic default interface for numbers that all the numeric types (float64, float32, int, ...) satisfy so we can +-*/ them.

func Add(a , b Number) Number {
return a+b
}

[Jan Mercl]

Consider for example `Add(3.14, 1)`. How to specify the behavior?

-j

[Eduard Castany]

If these are constants then no problem, but otherwise I imagined a compile time error.

[Jesper Louis Andersen]

You would need a way to specify that you have two instances of Number, both being of the same type. Otherwise you end up in coercion silliness, which is just going to introduce errors.

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

--
J.

[Matt Sherman]

This came to mind when I saw the gonerics thing, passing template + params via traditional URL elements. Nice idea.

That said...the remote code generator probably can't evaluate the type you are passing as an argument. So if the remote template assumes a numeric type but you send it something else, it will return non-compilable code.

This is why I am still biased toward local codegen -- it's more visible, the history is in the repo, we can enforce type constraints.

[Jonathan Lawlor]

It should definitely work locally, but a case might be made for splitting the code generator into a different kind of package, instead of living in the same one as the code that uses it.

[Daniel Skinner]

yeah and i wouldn't use query parameters, not sure how that would get checked out by `go get`, but having a server that generated everything necessary for `collections.io/set/string` or `gopkg.in/collections/set/string` via `go generate` and some other magic wouldn't necessarily be a bad thing. Ultimately, I'd personally probably just run the generation locally myself though.

also, +1 egon for the vid link, very interesting QA session

On Thu, Oct 2, 2014 at 2:36 PM, Jonathan Lawlor <jonatha...@gmail.com> wrote:

It should definitely work locally, but a case might be made for splitting the code generator into a different kind of package, instead of living in the same one as the code that uses it.

[Oliver Plohmann]

I had a quick look at gen and liked it. Problem with solutions that generate code is that the code has to re-generated when the "original code" changes. So if you find some smarter way to implement some method provided by gen (faster, less memory inten sive, etc.) or need to fix a bug you need to know the generated code that needs to be re-generated after a change in gen itself. Finding the code that needs to be re-generate can be tedious. And what if the code is in imported third party code?

Regards, Oliver

[Gabriel Aszalos]

What are generics?

[chris dollin]

On 7 October 2014 09:47, Gabriel Aszalos <gabriel...@gmail.com> wrote:
> What are generics?

Speaking very approximately, types with type-shaped holes in them
that you can fill in later.

So it might be a data structure Pair {a T, b U} where T and
U are type parameters. Any actual Pair would have specific
types for a and b.

Or it might be a (family of) function(s) that take(s) a slice of Ts
and deliver(s) a T.

Examples outside Go for this sort of thing include C++'s templates,
Java's generic types, or MLs parametyric polymorphism.

Chris

--
Chris "allusive" Dollin