Abstract Libraries in Go | Hacker News Reader

Abstract Libraries in Go

austingwalters.com

28 pointslettergram49 comments

Declaring Data as interface{} allows a struct to initialize Data, and therefore a node in this graphing library can store anything (including another graph). This is probably one of the most important characteristics of Go

What? The void pointer has been around since at least the seventies. Ok, Go adds introspection by storing the type in a fat pointer. But...

and is why it is part of the reason Go cannot be considered object-oriented [5].

A don't see what this has to do with anything. Pre-generics Java, you'd do the same thing by making a field store Object (the superclass of every class). This also provides introspection like Go's interfaces. Then the Java folks concluded that generics are much nicer :).

tl;dr This form of genericity is provided by nearly any OO or imperative language. And in fact it points out a shortcoming in Go: it doesn't support parametric polymorphism.

> tl;dr This form of genericity is provided by nearly any OO or imperative language. And in fact it points out a shortcoming in Go: it doesn't support parametric polymorphism.

OTOH the feature demonstrated here is discriminated unions, he's actually storing different types in the two nodes and is correct that most statically-typed languages don't have good ways to nicely handle that case (at least when the typeset is open, many languages handle the closed case nicely[0]).

Not that Go handles it nicely of course, as you would in Java you have to use a cast/type assertion at every fetch, and that operation may fail at runtime. So you end up with

    val = heap.Pop(key).(*MyType)

which may fault at runtime much like Java's

    val = (MyType) heap.pop(key)

    val, ok = heap.Pop(key).(*MyType)
    if !ok {
        // handle failure
    }

versus

    try {
        val = (MyType) heap.pop(key)
    } except (ClassCastException e) {
        // handle failure
    }

[0] http://en.wikipedia.org/wiki/Tagged_union

Void* and java's object both support that idiom, at least to the degree to does. Actually, I'm having trouble thinking of a static language that doesn't support it at least as well as go.

> Void* and java's object both support that idiom

I may be mistaken, but IIRC C-style casting from a (void *) provides no correctness guarantees, you may well end up with complete garbage unless you took care to explicitly check your union. And dynamic_cast requires RTTI.

So the idiom is supported in the loosest possible sense, there's no language-provided safety.

> at least as well as go.

Yes, I think that's a point of contention and I edited my comment to expand on it: I really, really don't think Go supports this use case nicely.

> I may be mistaken, but IIRC casting from a (void *) provides no correctness guarantees, you may well end up with complete garbage unless you took care to explicitly check your union.

Right. In fact, in C (NB: not C++) you don't even have to cast, as the compiler allows it as an (extremely unsafe) automatic conversion :)

Languages that support algebraic data types have a much better solution. You can explicitly declare which types can occur and it can be "A or B". It's called ADTs and it's the real solution to these problems.

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

> Languages that support algebraic data types have a much better solution.

Which I mentioned in my original comment…

> You can explicitly declare which types can occur and it can be "A or B". It's called ADTs and it's the real solution to these problems.

Well no actually, an ADT is a single type with multiple data-divergent constructors (although GADT may fit the bill, maybe with datakinds, I've yet to understand those).

In `data List a = Nil | Cons a (List a)`, the only type is List. Which is why I specifically noted that a closed set was necessary for tagged unions. There are languages which safely[0] handle actual type unions (genuine type coproducts), they are much rarer than types supporting simple tagged unions. IIRC, /u/munificent did a post on that for his magpie language although I don't remember if he ever implemented it. David Pierce's Whiley also seems to use type unions[1]

[0] an important discriminant, C has unions but they're not memory — let alone type — safe.

[1] http://whiley.org/2013/07/31/understanding-why-union-types-a...

OTOH the feature demonstrated here is discriminated unions,

He is storing interface{}, which is a fat pointer (a tuple of the pointer and type pointer).

I don't see what is revolutionary and how most statically typed languages don't handle that case. Sure, in Java the type pointer is stored in the actual instance and not in a fat pointer, but it doesn't make a difference in data structure design.

You can do the same abstraction in Java, C++, and C#. Which covers probably 90% of the statically-typed languages out there.

Edit: note on the last Java example: an if statement with instanceof look prettier ;).

> Edit: note on the last Java example: an if statement with instanceof look prettier ;).

Sure, and an if or switch on .(type) in go probably looks better as well.

> switch on .(type)

For anyone wondering

    switch val := heap.Pop(key).(type) {
    case (*MyType):
        // We're all good
    default:
        // Didn't get a (*MyType)
    }

Let's dissect [5] in the above:

> Is Go an object-oriented language? Yes and no. Although Go has types and methods and allows an object-oriented style of programming, there is no type hierarchy.

Classless prototype languages like JavaScript and Self also lack explicit type hierarchies, and they are still considered object-oriented.

> The concept of “interface” in Go provides a different approach that we believe is easy to use and in some ways more general.

There was a OO ML language called Moby [1] that had something similar. Just because the objects were structural didn't mean they weren't objects, though encapsulated communication (calling another object's private methods in the proper scope) is definitely more complicated.

> There are also ways to embed types in other types to provide something analogous—but not identical—to subclassing. Moreover, methods in Go are more general than in C++ or Java: they can be defined for any sort of data, even built-in types such as plain, “unboxed” integers. They are not restricted to structs (classes).

You mean like extension methods in C#?

> Also, the lack of type hierarchy makes “objects” in Go feel much more lightweight than in languages such as C++ or Java.

They are basically claiming that Go is not C++ or Java, not that Go is not object-oriented, of which the design space is much broader.

In my opinion, there is nothing interesting in Go, and it doesn't seem like a language I would want to use.

[5] http://golang.org/doc/faq#Is_Go_an_object-oriented_language

[1] http://cs.uchicago.edu/files/tr_authentic/TR-2003-10.pdf

> There was a OO ML language called Moby [1] that had something similar.

OCaml uses a structural object system (alongside the nominative type system it inherited from ML)

[0] http://en.wikipedia.org/wiki/OCaml

They are pretty contemporary, from the 2003 Moby paper:

> The main differences stem from a fundamental design choice: OCAML’s design emphasizes the expressiveness of the object-type system, whereas MOBY’s design emphasizes the expressiveness of the class system. OCAML uses row polymorphism [R´em94] to support extensible object types, whereas MOBY uses structural subtyping. OCAML’s approach has two advantages: it is backward compatible with ML’s Hindley-Milner type inference, and one can get the effect of mytype by the use of recursive type variables. The cost of providing mytype is that OCAML’s classes are less flexible than MOBY’s. Specifically, if a method is public in an OCAML class, it cannot be hidden from either class clients or object clients of a deriving class, as required for the soundness of mytype. In addition, if a method is hidden from object clients in a class, it cannot be made public by a deriving class. The former restriction means that the class hierarchy determines an object-type hierarchy. These restrictions, along with the fact that OCAML does not have public fields, limit one’s ability to use the module system to implement friends via package scope in two ways. First, it is not possible to reveal inherited protected methods or fields to the friend functions, and any method that a class reveals to its friends must also be revealed to any client outside the module (assuming that the class is exported).

> In my opinion, there is nothing interesting in Go, and it doesn't seem like a language I would want to use.

I take it you're a C/C++ developer ? As a ruby developer, go got my interest like other compiled languages could not, and the reason for that has be pointed out by Rob Pike in his keynote at gophercon[1] : productivity.

I'm used to a certain pace of development with interpreted languages that compiled languages just can't match. And well, time is money, I'll use a "slower to write with" language only on critical piece of software where something else won't do. Go has been a perfect fit, here : it allows to do more heavy processing while still being acceptably fast to develop.

Other than that, its main advantage is what it has been created for to begin with : concurrency. It's a core concept, meaning you can express it with simple syntax (with goroutines and channels) and that you don't have to fear hitting limits (goroutines are not threads exactly, go do its best to map them on available threads, as much as there are cores, and you can thus have ten of thousands of goroutines running concurrently with no problem).

There are probably languages that go further on concurrency, like erlang, but go is just the perfect balance between ease of learning, speed to develop, ease of implementing concurrent code and speed of execution.

[1] http://confreaks.com/videos/3419-gophercon2014-opening-day-k...

C#, which is faster than Go with better features (parametric polymorphism, classes, interfaces, the works).

Go's support for concurrency is nothing very novel and has nothing to do with its language design. Green threads have been around forever, and many platforms support thread pools.

"C# is faster than Go" do you have some links to prove that statement ? I'm really interested because in all the benchmarks I saw, C# seemed much more slower.

I haven't seen any head to head comparisons about Go, I just know that C# is generally faster than the JVM (on Windows at least, not Mono), while Go is known to be slower than Java. If you have something that says otherwise, it would be nice to see.

Also, I think .NET can optimize generic class instantiations (one advantage in forgoing type erasure), but I'm not sure.

C# is a very good language. It's also ridiculously huge. There are so many language features, you could use a new one in every class and not run out until you'd rewritten Windows.

I worked in C# for a decade, and I still have to go look up how some of the features work. Try getting new people up to speed in the language... you'll still be teaching them language features years into their careers.... I know because I did it.

It's not a bad language, it's just that it suffers from feature bloat, like many things Microsoft does, and that makes for code that is very difficult to maintain.

> ten of thousands of goroutines running concurrently with no problem

You have been able to spawn tens of thousands of native threads (on Linux) no problem for a long time. (Though the memory management for stacks can be a pain, so the fact that Go automates this through stack growth is nice.)

> I'm used to a certain pace of development with interpreted languages that compiled languages just can't match.

You have never worked with an incremental compiler, have you?

I mostly work in Java, using Eclipse. I make a change to the code, i hit control-R, the test runs immediately. The pace is no slower than with an interpreted language.

In fact, Java also offers hotswap (even more extensively with JRebel). So if you are running an app, changes you make can be live nearly immediately, in a running app.

Yes, I was not thinking of java (nor any other jit compiler) saying that, but more specifically of C and C++.

Also note, in those, it's not especially the building part that annoys me (running tests can just be as long, even in interpreted languages), but more the high verbosity of code you have to write (again, not speaking of java, here).

> I'm used to a certain pace of development with interpreted languages that compiled languages just can't match.

Haskell using Yesod matches the workflow of interpreted languages. When the development server is running, anytime you save a file it instantly recompiles the file so that the change is immediately reflected.

> Moreover, methods in Go are more general than in C++ or Java: they can be defined for any sort of data, even built-in types such as plain, “unboxed” integers. They are not restricted to structs (classes).

This doesn't quite mean what it sounds like it means for those familiar with extension methods or typeclasses, because you cannot define methods on ints in Go: http://play.golang.org/p/CuBT11_uF3

Presumably what it means is that you can wrap built-in types in a local "type" wrapper and then implement methods on that. (That's not what I would call a "plain, unboxed integer" in the FAQ language, but this is a semantic quibble.)

Anyhow, Go has nothing like the extension methods in C#: the closest thing you can do is to wrap external types in a "type" wrapper and implement methods on that, but this is not as general of a solution as it requires callers to perform the wrapping of individual values before calling the method.

So, I think the key thing here is unboxed. You can write methods on values whose in-memory representation is the same as an int. It performs in all ways like an int (you can do arithmetic operations on it, etc). It's not boxed, the way other languages would require it to be in order to have methods.

C# extension methods are just syntactic sugar.

  public static int WordCount(this String str)

Yes, this means that you can now do this:

  string foo = "howdy partner!"
  int count = foo.WordCount()

Is that really any better than this?

  string foo = "howdy partner!"
  int words = WordCount(foo)

The only reason this is useful in C# is because it doesn't support bare functions, all methods have to be on an object. In Go, this is not a problem, you can have bare methods.

Also, extension methods, in practice (and I have a lot of practice with them), are a pain in the butt... because they're magic additional methods on a class that only exist if you include the right project... which means if you try to copy some logic, some of the functionality will not compile in the new location until you figure out what projects to include in the new spot. That's still requiring work by the caller, except that it's much less obvious what you need to do to get it to work.

In contrast, Go's type definitions are 100% clear and obvious, and there's never a question where the functionality is coming from. That clarity makes a huge difference when you're trying to understand the code.

Of course, you'd never actually do that for most C# extension methods in Go, it's ridiculous to make a new type just to make it look like you're calling methods on that type. You'd just write a bare function like a normal person:

  package count
  func Words(s string) int {}

  // elsewhere
  foo := "Howdy Partner!"
  words := count.Words(foo)

Where extension methods really shine is with generic classes and structures, you can define methods over arbitrary generic bindings; e.g. a method over List of int. Of course that isn't a problem in Go.

And even then, its all about the intellisense.

Intellisense is a good point. If you already have the variable there, getting the free "list of stuff I can do with this" can be pretty handy.

I don't see what the difference is between having to hunt for the class that implements an extension method and having to hunt for the newtype wrapper. Seems like the same thing.

Also, extension methods don't involve any boxing.

In the last few months I've been drifting toward the idea that parametric polymorphism is in fact enough for everything, and subtype polymorphism isn't needed at all. If you have subtype and parametric polymorphism in the same language, designing software becomes way too complicated. For example, look at this bullshit:

    public static <T extends Comparable<? super T>> void sort(List<T> list)

There's no good reason why a simple concept, like sorting, must have a hugely complicated type that involves inheritance, F-bounded polymorphism and wildcards. It should be replaced with this:

    public static <T> void sort(List<T> list, Comparator<T> comparator)

You can use that idea to replace pretty much all uses of subtype polymorphism with parametric polymorphism. The notion of interface inheritance, like "inheriting from" the interface Comparator<T>, is also unnecessary, because you can use a record type containing first-class functions instead. I wrote it up in more detail here: http://lambda-the-ultimate.org/node/4950

That was the goal of the C++ STL. Some may argue it goes too far, other opinions suggest it doesn't go too far enough; however I think most people can agree that you need typeclasses/traits/concepts et al. if you don't want to be doomed to passing different data structure manipulation functions to every call, as in your replacement example, or else resort to underspecifying the requirements of your type parameters and experiencing compiler messages from Hell.

I'm hoping that some system like Scala's implicit arguments or Agda's instance arguments could ease the burden of passing stuff around. I don't know if that's enough for most realistic use cases, though.

There's another complication. For operations that make sense on only some types, it makes sense to pass around the implementation of the operations, because it also acts as a type constraint. But for operations that make sense on all types, like Java's equals/hashCode/toString (and possibly also comparison), I suppose it's better to make them overridable for each type, as a special case in the language.

In the last few months I've been drifting toward the idea that parametric polymorphism is in fact enough for everything, and subtype polymorphism isn't needed at all.

Also relevant reading in this context: Haskell Antipattern: Existential Typeclass

http://lukepalmer.wordpress.com/2010/01/24/haskell-antipatte...

While I think Go is great and interfaces are great, the author didn't mention that you need to include the type as an additional annotation when reading the variable, so this isn't really great.

An example from his own github repo:

  dcurrent = heap.Pop(n).(*D_Node)

So if you are using multiple types, you need to keep track of that, or do more boilerplate in a type switch to pull out what you want, or use reflection, so it's really not quite as elegant as it may seem.

Yeah noticed that too. Was just talking to a co-worker the other day about how static types are sometimes, and they were saying how any sufficiently large code base written by average developers will have more and more things like that (void*) casts and so on. So then type safety kind of goes out of the window.

For languages like Go you look at static types from 2 sides - 1) it is there for safety and reliability (so in this case if it couldn't be circumvented it would that way) or 2) it is there to speed things up. Then Go is like a faster Python but casting things left and right erasing types will make the code blow up.

So taking the second approach, I don't see it as terribly. But maybe someone coming from Java or Haskell might be really offended by that line of code.

A minor nitpick - it's still type safe in Go, you can check the type of what's in interface{} and convert the value to that type. You'll never have to worry about getting complete garbage out. However, it's not pretty, and the boxing to and from interface{} is not free.

In order to catch up with language, I also decided to write a Graph library in Go[1]. Since this seems to be a quite common application, is there any more mature, bigger project implementing these same ideas? A similar concept in the Python community is python-graph[2].

[1] https://github.com/ichinaski/grapho

[2] https://code.google.com/p/python-graph/

There are dozens (if not dozens of dozens) of graph-manipulation libraries in python, but the most full-featured one is probably networkx.

The best part of this article is the (single) comment.

> Robert Seaton says: March 6, 2014 at 11:13 pm I wanted to comment, but had nothing to say, so I googled computational complexity jokes. Except there are none. So here you have it. The first joke about computational complexity ever written: “Hey, man, is there something wrong with your mom? Because I graphed her weight and she’s growing faster than a busy beaver function.”

New to Go still, what kind of caution should one take when using interface{} to store data in structs? It seems to be a catch-all sort of type, I've read how cluttered some code can get when using it (I think it was an HN post related to math in Go, and type-checking against an interface{} type).

Thanks

A general rule of thumb: don't use `interface{}` unless you have to. With respect to performance, it isn't free. And with respect to type safety, it isn't safe. (It is however memory safe when casting, unlike C's `void *`.)

The key is that an `interface{}` is an interface with exactly 0 methods. Since all types in Go have at least 0 methods, any type satisfies `interface{}`. Resorting to using an `interface{}` type is akin to dynamic typing. All of your type errors get pushed to runtime and you lose any performance benefits you might get from the compiler knowing the type of your data.

Russ Cox goes into great detail on the representation of interface values.[1]

I wrote a blog post a while back on conveniently writing parametric functions in Go using reflection.[2] (Here, "convenience" is a relative term.)

[1] - http://research.swtch.com/interfaces

[2] - http://blog.burntsushi.net/type-parametric-functions-golang

Is there a chance ty or a similar implementation will make it into Go core? What do you think about Go designers being generally averse to the idea of parametric polymorphism?

> Is there a chance ty or a similar implementation will make it into Go core?

I hope not! It was purely an experiment. There are significant draw backs, particularly with respect to performance.

One could reasonably argue that writing parametric functions with reflection should be hard, so as to discourage users from resorting to it too easily.

> What do you think about Go designers being generally averse to the idea of parametric polymorphism?

I think the jury is still out. Russ Cox laid out the essential trade offs given to them: 1) slow programmers 2) slow programs or 3) slow compiler. There's a lot of wiggle room in there (what do you mean by "slow"?), but my sense is that they're still looking for a trade off they're happy with.

In my experience with the Go community, there isn't a ton of internal complaining about the lack of generics. It's certainly brought up now and then, but it doesn't seem to put people off too much. Now, obviously this could just be confirmation bias, but if the Go community keeps growing despite the lack of generics, it may be difficult to justify generics in the future. (i.e., People will live with the first trade off.)

My expectation is that they'll end up giving us something that'll make it easier to work around the lack of generics, but I don't know about getting actually full-on generics. Honestly, I don't want them - they make it way too easy to make overly complex code.... much like class inheritance. I've been developing for 14 years and can count on one hand the number of times I needed something like a tree or graph. Certainly, if you're working on scientific or mathematic projects, you may use them every day of the week, but if so, maybe Go isn't the right language for you, and honestly, it doesn't have to be everything to everyone.

I'm skeptical that trees and graphs are the only thing generics are good for, but, I've published research with open source software written in Go.[1] I've also done it for Haskell.[2] I just try not to pigeonhole languages and learn as much as I can about different paradigms. In my experience, they all have something useful to offer beyond trees and graphs.

[1] - https://github.com/BurntSushi/cablastp

[2] - https://github.com/ndaniels/mrfy

This is bit nitpicking, but in Go comments are usually done with two slashes followed by a space. See this for example: http://golang.org/src/pkg/bytes/buffer.go

This is good practice in your own packages as well, as online tools such as GoDoc rely that your code is commented right.

I wander why not start a comment text without a function name? i.e. "reads something" instead of "Read reads something". Can't GoDoc easily extract function names from the code?

starting comment with function name will much easier run `godoc` with `grep` command.

    $ godoc regexp | grep parse

"If all the doc comments in the package began, "This function...", `grep` wouldn't help you remember the name. But because the package starts each doc comment with the name, you'd see something like this, which recalls the word you're looking for."

Effective Go - http://golang.org/doc/effective_go.html#commentary

But, this is against the spirit of go, I mean in the sense that go is typed, to avoid exactly this kind of type ambiguity. and that is why you don't have generic functions ...

>Declaring Data as interface{} allows a struct to initialize Data, and therefore a node in this graphing library can store anything (including another graph). This is probably one of the most important characteristics of Go.

"Declaring Data as Object allows a class to initialize Data, and therefore a node in this graphing library can store anything (including another graph). This is probably one of the most important characteristics of Java." - Probably someone before 2004, when Java programmers hadn't yet realized that using the most general type to do anything is a terrible idea

Reply on news.ycombinator.com