Generics in Go using interface{} and embedding

[Stefan Nilsson]

Here is some code that might offer a bit of consolation to those of you who miss generics in Go. Perhaps the most common use of generics in Java is to define a generic class

public class Stack<E> { ... }

and then use it as a parameterized type:

Stack<String> s = new Stack<String>();

Here is a way to achieve something quite similar in Go. Assume that Stack is a type with Push and Pop methods that operate on elements of interface{} type. Using embedding when can then specialize the type like this:

type StringStack struct {

Stack

}

func (s *StringStack) Push(n string) { s.Stack.Push(n) }

func (s *StringStack) Pop() string   { return s.Stack.Pop().(string) }

The definitions may be a bit verbose, but the code using the specialized type with be clean and type safe.

Here is a complete example: http://play.golang.org/p/bWxN68OzMo

[bryanturley]

Working like that may placate some, I would rather just write StringStack without interfaces because of it's simplicity.
You avoid a number of calls and all runtime type checking then.

This is the real problem with generics.  Things that are as simple as a stack shouldn't need them.
Though you may just be giving an example.

Perhaps the current hard coded generic paradigm is enough.
We just need to add a few more very common ones?
We have slice (array) and channel (specialized queue) and a map builtin, perhaps add one or two types of binary trees?

Keep the list of builtins very small and limited to speed critical well known data structures.  There are really only a handful of them, just many different implementations for those few.
This would keep everything from being implemented in generics and give more flexibility to people who don't like recoding complex but common data structures.

Everything else I can think of I would want to customize in most cases making a generic implementation unsuitable.

I've got a bit of a cold right now so I may be delusional.

[André Moraes]

> This would keep everything from being implemented in generics and give more
> flexibility to people who don't like recoding complex but common data
> structures.

To solve that problem, of repeating things, I try to implement the
structures just like the sort package does.

Of course some things will be too complex to be implemented that way.
In those cases, the CS books comes in handy. :)

--
André Moraes
http://amoraes.info

[Stefan Nilsson]

Yes, the sort package has a very nice generic implementation of a sort algorithm: as a user you describe a two basic primitives (compare and swap) and the sorting algorithm does the rest. This approach seems to work very well for many algorithms.

However, to me it seems less suited when you try to apply it to generic data structures. In that case, the generic datatype interface{} might be a better fit. The generic heap implementation in container/heap is a case in point. Here you get access to the mechanics of a heap by providing four primitives (compare, swap, pop, push). In many cases this is more than you bargained for; frequently you just want a priority queue without having to worry about the fact that it happens to be implemented as a heap. So in this case I've chosen to roll my own implementation (http://code.google.com/p/go-priority-queue/) and forgo the standard library.

[bryanturley]

On Friday, January 4, 2013 5:49:19 AM UTC-6, jonas.m...@gmail.com wrote:

Thanks for sharing this. It's quite clever. I don't recall it coming up in the debates about generics in Go.  It speaks very well of Go (&you!) that no non-orthogonal, complex macro language nor template meta-programming was required to achieve this.

Performance-wise, at least the (*StringStack) Push method gets in-lined (observed using "-gcflags -m"). But not Pop, at least not yet in 6c version 1.03. And of course there is that type assertion that limits performance for small elements in the generic data structure.

It's key that StringStack is a struct not an interface.  But we needn't put a struct inside the struct.  Instead, we can put an interface IStack to the stack in the struct, with similar wrappers, and then even put an interface around the result, an interface-to-a-string-stack IStringStack, implemented using a string-specialized-general-stack-interface (StringIStack), with the general stack interface (IStack) implemented over a general stack (e.g., Stack).   

This way we get implementation hiding (of *both* (1) the wrappers that specialize the type and (2) the underlying general data structure & algorithms)  with a specialized generic data structure, supported by (run-time) type safety. I modified your code to illustrate in http://play.golang.org/p/LkVWkyph75 .

I see that as a shining example of code bloat.  Stacks are not hard to write or fix why do you need to generalize them?

// Prefix I indicates interface, not struct.
Seems a bit like the return of hungarian notation (a bad thing)

s.data[i] = nil // to avoid memory leak
not a leak, just a reference you don't need...

[Kevin Gillette]

The unique part about sort compared to other 'generics in go' workarounds is that it's fully compile-time type-safe; anything that takes an interface{} cannot make those guarantees. In the case of sort, the datastructure (if any) and its needed behaviors are specified through methods acting upon concrete types (all parameters are of type int), and thus the details of the data implementation are entirely hidden away from the algorithm. Many (but presumably not all) algorithms can be designed generically in this way, including some of the examples that have been used to argue why Go needs better support for generics.

[Stefan Nilsson]

I should probably add that the stack was intended merely as an example. But it's still real code. I didn't write it to be clever. It came about when I was fixing a bug related to types and an operand stack.

That said, I believe that many of us have an irrational fear of void*, Object and interface{}. Many of the attempts to avoid these perfectly good language features seem to create more problems than they solve.

[bryanturley]

On Friday, January 4, 2013 3:23:57 PM UTC-6, Stefan Nilsson wrote:

I should probably add that the stack was intended merely as an example. But it's still real code. I didn't write it to be clever. It came about when I was fixing a bug related to types and an operand stack.

That said, I believe that many of us have an irrational fear of void*, Object and interface{}. Many of the attempts to avoid these perfectly good language features seem to create more problems than they solve.

interface {} was designed the avoid the problems of void *.
I wouldn't say some of us have a fear of it, I would say go is designed not to have it.