Statically typed generic data structures in Go

I gave a talk at the Go Boston meetup last night and figured I should write it up and put it here.

The second thing everyone says when they read up on Go is "There are no generics!".

(The first thing people say is "There are no exceptions!")

Both are only mostly true,  but we're only going to talk about generics today.

Go has generic built-in data structures - arrays, slices, maps, and channels. You just can't create your own new type, and you can't create generic functions. So, what's a programmer to do? Find another language?

No. Many, possibly even most, problems can be solved with the built-in data structures. You can write pretty huge applications just using maps and slices and the occasional channel. There may be a tiny bit of code duplication, but probably not much, and certainly not any tricky code.

However, there definitely are times when you need more complicated data structures. Most people writing Go solve this problem by using Interface{}, the empty interface, which is basically like Object in C# or Java or void * in C/C++.  It's a thing that can hold any type... but then you need to type cast it to get at the actual type. This breaks static typing, since the compiler can't tell if you make a mistake and pass the wrong type into something that takes an Interface{}, and it can't tell until runtime if a cast will succeed or not.

So, is there any solution? Yes. The inspiration comes from the standard library's sort package. Package sort can sort a slice of any type, it can even sort things that aren't slices, if you've made your own custom data structure. How does it do that? To sort something, it must support the methods on sort.Interface. Most interesting is Less(i, j int). Less returns true if the item at index i in your data structure is Less than the object at index j in your data structure. Your code has to implement what "Less" means... and by only using indices, sort doesn't need to know the types of objects held in your data structure. 

This use of indices to blindly access data in a separate data structure is how we'll implement our strongly typed tree. The tree structure will hold an index as its data value in each node, and the indices will index into a data structure that holds the actual objects. To make a tree of a new type, you simply implement a Compare function that the tree can use to compare the values at two indices in your data structure. You can use whatever data structure you like, probably a slice or a map, as long as you can use integers to reference values in the data structure.

In this way we separate the organization of the data from the storage of the data. The tree structure holds the organization, a slice or map (or something custom) stores the data. The indices are the generic pointers into the storage that holds the actual strongly typed values.

This does require a little code for each new tree type, just as using package sort requires a little code for each type. However, it's only a few lines for a few functions, wrapping a tree and your data. 

You can check out an example binary search tree I wrote that uses this technique in my github account

https://github.com/natefinch/tree

or go get the runnable sample tree:

go get github.com/natefinch/treesample

This required only 36 lines of code to make the actual tree structure (including empty lines and comments).

In some simple benchmarks, this implementation of a tree is about 25% faster than using the same code with Interface{} as the values and casting at runtime.... plus it's strongly typed.

Be not afraid.

The ultimate goal of terrorism is not carnage, it is fear. Go to work, love your family, enjoy life. Be not afraid. This is our best weapon against terrorism.

My thoughts go out to the victims of Boston Marathon bombing and their families. I don't know any of them, but we are all Bostonians and Americans in spirit.

Go is for Open Source

The Go programming language is built from the ground up to implicitly encourage Go projects to be open source. If you want your project not only to contribute to open source, but to encourage other people to write open source code, Go is a great language to choose.

Let's look at how Go does this. These first two points are overly obvious, but we should get them out of the way.

The language is open source

You can go look at the source code for the language, the compilers, and the build tools for the language. It's a fully open source project. Even though a lot of the work is being done by Google engineers, there are hundreds of names on the list of contributors of people who are not Google employees.

The standard library is open source

Want to see high quality example code? Look at the code in the standard library. It has been carefully reviewed to be of the best quality, and in canonical Go style. Reading the standard library is a great way to learn the best ways to use and write Go.

Ok, that's great, but what about all the code that isn't part of Go itself?

The design of Go really shows its embrace of open source in how third party code is used in day to day projects.

Go makes it trivial to use someone else's code in your project

Go has distributed version control built-in from the ground up. If you want to use a package from github, for example, you just specify the URL in the imports, as if it were a local package:

import (
    "bytes" // std lib package
    "github.com/fake/foo" // 3rd party package
)

You don't have to go find and download fake/foo from github and put it in a special directory or anything. Just run "go get github.com/fake/foo". Go will then download, build, and install the code, so that you can reference it... nicely stored in a directory defined by the URL, in this case $GOPATH/src/github.com/fake/foo. Go will even figure out what source control system is used on the other side so you don't have to (support for git, svn, mercurial, and bazaar).

What's even better is that the auto-download happens for anyone who calls "go get" on your code repository. No more giving long drawn-out installation instructions about getting half a dozen 3rd party libraries first. If someone wants your code, they type "go get path.to/your/code", and Go will download your code, and any remote imports you have (like the one for github above), any remote imports that code has, etc, and then builds everything.

The fact that this is available from the command line tools that come with the language makes it the de facto standard for how all Go code is written. There's no fragmentation in the community about how packages are stored, accessed, used, etc. This means zero overhead for using third party code, it's as easy to use as if it were built into the Go standard library.

Sharing code is the default

Like most scripting languages (and unlike many compiled languages), using source code from another project is the default way to use third party code in Go. Go creates a monolithic executable during its build, so there are no DLLs to create and distribute in the way you often see with other compiled languages. In theory you could distribute the compiled .a files from your project for other people to link to in their project, but this is not encouraged by the tooling, and I've personally never seen anyone do it.

All Go code uses the same style

Have you ever gone to read the source for a project you'd like to contribute to, and had your eyes cross over at the bizarre formatting the authors used? That almost never happens with Go. Go comes with a code formatting tool called gofmt that automatically formats Go code to the same style. The use of gofmt is strongly encouraged in the Go community, and nearly everyone uses it. Most text editors have an extension to automatically format your code with gofmt on save, so you don't even have to think about it. You never have to worry about having a poorly formatted library to work with... and in the very rare situation where you do, you can just run it through gofmt and you're good to go.

Easy cross platform support

Go makes it easy to support multiple platforms. The tooling can create native binaries for any popular operating system from the same source on a single machine. If you need platform-specific code, it's easy to specify code that only gets compiled for a single platform, by simply appending _<os> to a file name .e.g path_windows.go will only be compiled for builds targeting Windows.

Built-in documentation and testing

Go comes with a documentation generator that spits generates HTML or plain text from minimally formatted comments in the code. It also comes with a standard testing package that can run unit tests, performance benchmarks, and runnable example code. Because this is all available in the standard library and with the standard tools, nearly everyone uses it... which means it's easy to look at the documentation for any random Go package, and easy check if the tests pass, without having to go install some third party support tool. Because it's all standardized, several popular websites have popped up to automate generating (and hosting) the documentation for your project, and you can easily run continuous integration on your package, with only a single line in the setup script - "language: go".

Conclusion

Everything about Go encourages standardization and openness... which not only makes it possible to use other people's code, it makes it easy to use other people's code. I hope to see Go blossom as a language embraced by the open source community, as they discover the strengths that make it uniquely qualified for open source projects.

What I love about Go

The best things about Go have nothing to do with the language.

Single Executable Output

Go compiles into a single executable that runs natively on the target OS. No more needing to install java, .net, mono, python, ruby, whatever. Here's your executable, feel free to run it like a normal person.  And you can target builds for any major OS (windows, linux, OSX, BSD).

One True Coding Style

GoFmt is a build tool that formats your source code in the standard Go format. No more arguing about spacing or brace matching or whatever. There is one true format, and now we can all move on... and even better, many editors integrate GoFmt so that your code can be automatically formatted whenever you save.

Integrated Testing

Testing is integrated into the language. Name a file with the suffix _test.go and it'll only build under test. You run tests simply by running "go test" in the directory. You can also define runnable example code with output that is checked at test time.  This example code is then included in the documentation (see below)... now you'll never have examples in documentation with errors in them.  Finally, you can have built-in benchmarks that are controlled by the go tool to automatically run enough iterations to get a significant result, displayed in number of operations per second.

Integrated Documentation

HTML documentation is built into the language. No need for ugly HTML in your source or weirdly formatted comments. Plaintext comments are turned into very legible documentation, and see above for examples that actually run and can have their output tested as a part of the tests.

DVCS

Support for distributed version control is built into the language. Want to reference code from a project on github?  Just use the url of the project as the import path in your code, e.g. import "github.com/jsmith/foo"   When you build your code it'll get downloaded and built automatically.

Want to get a tool written in go?  From the command line type "go get github.com/jsmith/bar" - go will download the source, build it, and install the executable in your path.  Now you can run bar.

Any git, SVN, mercurial, or bazaar repository will work, but all the major public source code sites are supported out of the box - github, bitbucket, google code, and launchpad.

Other Cool Stuff

Debugging with gdb
Integrated profiling tools
Easy to define custom includes per targeted OS/architecture (simple _windows will only build if targetting windows)
Integrated code parsers and lexers.

Do you even care about the actual language anymore?  I wouldn't.  But just in case:

• C-like
• Garbage Collected
• Statically typed
• ...but with type inference so you're not typing boilerplate all the time: a := "my string"
• Implicit interfaces - if a type has the methods of an interface, it implements the interface
• Pointers but no pointer arithmetic (thank god)
• First class functions
• No exceptions
• ...but multiple returns from a single function so you don't have to overload return types
• Everything is UTF8 (both strings and source code.. yes you can have Θ as a variable name now)
• Highly performant asynchronous code that is trivial to write
• A deep standard library that does most of the boring stuff for you

gocog

I recently got very enamored with Go, and decided that I needed to write a real program with it to properly get up to speed. One thing came to mind after reading a lot on the Go mailing list: a code generator.

I had worked with Ned Batchelder at a now-defunct startup, where he developed cog.py. I figured I could do something pretty similar with Go, except, I could do one better - Go generates native executables, which means you can run it without needing any specific programming framework installed, and you can run it on any major operating system. Also, I could construct it so that gocog supports any programming language embedded in the file, so long as it can be run via command line.

Thus was born gocog - https://github.com/natefinch/gocog

Gocog runs very similarly to cog.py - you give it files to look at, and it reads the files looking for specially tagged embedded code (generally in comments of the actual text). Gocog extracts the code, runs it, and rewrites the file with the output of the code embedded.

Thus you can do something like this in a file called test.html:

<html>
<body>
<!-- [[[gocog
print "<b>Hello World!</b>"
gocog]]] -->
<!-- [[[end]]] -->
</body>
</html>

if you run gocog over the file, specifying python as the command to run:

gocog test.html -cmd python -args %s -ext .py

This tells gocog to extract the code from test.html into a  file with the .py extension, and then run python <filename> and pipe the output back into the file.

This is what test.html looks like after running gocog:

<html>
<body>
<!-- [[[gocog
print "<b>Hello World!</b>"
gocog]]] -->
<b>Hello World!</b>
<!-- [[[end]]] -->
</body>
</html>

Note that the generator code still exists in the file, so you can always rerun gocog to update the generated text.  

By default gocog assumes you're running embedded Go in the file (hey, I wrote it, I'm allowed to be biased), but you can specify any command line tool to run the code - python, ruby, perl, even compiled languages if you have a command line tool to compile and run them in a single step (I know of one for C# at least).

"Ok", you're saying to yourself, "but what would I really do with it?"  Well, it can be really useful for reducing copy and paste or recreating boilerplate. Ned and I used it to keep a schema of properties in sync over several different projects. Someone on Golang-nuts emailed me and is using it to generate boilerplate for CGo enum properties in Go.

Gocog's sourcecode actually uses gocog - I embed the usage text into three different spots for documentation purposes - two in regular Go comments and one in a markdown file.  I also use gocog to generate a timestamp in the code that gets displayed with the version information.

You don't need to know Go to run Gocog, it's just an executable that anyone can run, without any prerequisites.  You can download the binaries of the latest build from the gocog wiki here: https://github.com/natefinch/gocog/wiki

Feel  free to submit an issue if you find a bug or would like to request a feature.

Go Win Stuff

No, not contests, golang (the programming language), and Win as in Windows.

Quick background - Recently I started writing a MUD in Go for the purposes of learning Go, and writing something that is non-trivial to code.  MUDs are particularly suited to Go, since they are entirely server based, are text-based, and are highly concurrent and parallel problems (which is to say, you have a whole bunch of people doing stuff all at the same time on the server). 

Anyway, after getting a pretty good prototype of the MUD up and running (which was quite fun), I started thinking about using Go for some scripty things that I want to do at work. There's a bit of a hitch, though... the docs on working in Windows are not very good.  In fact, if you look at golang.org, they're actually non-existent.  This is because the syscall package changes based on what OS you're running on, and (not surprisingly) Google's public golang site is not running on Windows.

So, anyway, a couple notes here on Windowy things that you (I) might want to do with Go:

Open the default browser with a given URL:

import (
    "syscall/exec"
) 

func OpenBrowser(url string) {
    exec.Command("rundll32", "url.dll", "FileProtocolHandler", url)
}

Example of a wrapper for syscall's Windows Registry functions:

import (
    "syscall"
)

func ReadRegString(hive syscall.Handle, subKeyPath, valueName string) (value string, err error) {
    var h syscall.Handle
    err = syscall.RegOpenKeyEx(hive, syscall.StringToUTF16Ptr(subKeyPath), 0, syscall.KEY_READ, &h)
    if err != nil {
        return
     }
     defer syscall.RegCloseKey(h)

    var typ uint32
    var bufSize uint32

    err = syscall.RegQueryValueEx(
              hKey,
              syscall.StringToUTF16Ptr(valueName),
              nil,
              &typ,
              nil,
              &bufSize)
    if err != nil {
        return
    }

    data := make([]uint16, bufSize/2+1)

    err = syscall.RegQueryValueEx(
              hKey,
              syscall.StringToUTF16Ptr(valueName),
              nil,
              &typ,
              (*byte)(unsafe.Pointer(&data[0])),
              &bufSize)
    if err != nil {
        return
    }

    return syscall.UTF16ToString(data), nil
}

Mite Away Quick Strips and Robbing

So, yesterday I put Mite Away Quick Strips on my hives.  The first treatment I'd ever put on them. It was a little sad, but like I said in my last post, I don't want to lose my hives.  I went to check on them this morning and saw a lot of dead bees in front of the hives.  I was freaked out - certain the mite away was killing my bees.  I opened the hives and looked inside - the bees looked pretty much ok.  There were some scratched honey cappings around, so I'm pretty sure the dead bees are from robbing, not from the mite away.  And luckily, it wasn't very successful robbing.  As far as I can tell, it was fairly short lived robbing, since neither hive seems to have lost any honey, but I would recommend that if you use the 1/2" overhang of the top brood box when you use mite away, that you cover the overhangs with bee-proof hardware cloth, and probably reduce your entrance with it as well, so that you don't let the robbing even start.

Alcohol Wash

So, since I was going to put a treatment on my hives for the first time, I wanted to at least have a scientifically accurate account of how well it worked.  At the WCBA meeting a couple weekends ago, Ken Warchol showed everyone how to do an alcohol wash to count varroa mites.

This is a pretty good description of it on this site: http://scientificbeekeeping.com/sick-bees-part-11-mite-monitoring-methods/

Here's my description based on what Ken said:

Take a pint or quart mason jar (preferably wide mouth), fill it with about 8 ounces of rubbing alcohol.  Take a frame of brood, triple check that the queen is not on it, and sweep about 100 nurse bees into the jar (you can guess at first by sorta filling it to the 4 ounce line with bees).  The alcohol kills the bees and the mites, and causes the mites to fall off.

Take the jar inside and dump it in a larger vessel, and fill with water.  Swirl the bees around a bunch to make sure the mites don't get caught in them.  Scoop out the bees with something that won't also scoop out the mites (like a slotted spoon).  Now you should see the mites floating in the water (very small brown dots).  Now count the mites and the bees.  Infestation counts are based on number of mites per 100 bees (a percent, really), so you can just divide the number of mites by the number of bees.


Ken said that if you have 8 or more mites per 100 bees, you should treat with Mite Away Quick Strips.
Here's the results from my two hives:

Lefty: 18 mites / 196 bees  (9% infestation)
Righty: 9 mites / 268 bees (3% infestation)

(Yes, I have two hives, next to each other, so that's how they're named).

I was shooting for 100 bees each, but this was my first time, so I went a bit overboard... but more bees just means a more accurate count anyway.

This shows I should treat Lefty, and might not need to bother treating Righty... but since it's my first time doing the test, I'm not 100% confident that I didn't somehow mess up the test on Righty, and Ken said it looked like it needed treating, so I figure I should just do it.  I don't like it, but I don't want to lose my hives either.

Penzey's

Jennifer, Lily, and I went to Penzey's spices in Arlington recently.  The place is amazing - the spices all smell at least twice as good as the stuff in the grocery store, usually like 10 times better.  I had bought Vietnamese Cassia Cinnamon from them before, and it made the most amazing apple pies.  You could definitely tell which pie was made with grocery store cinnamon and which one with the good stuff.   Their prices are pretty good, which means a little more expensive than grocery store, but not by a huge amount - maybe $1 or 2 more.   If you buy spices in the bags you see above, their prices are actually pretty comparable to the grocery store's (those glass jars aren't cheap).

We can't wait to try out the chili powders, and everything else we got. It's going to be a tasty year.

How to Fix Your HP dv8t's Wifi in 2 minutes

I bought an HP dv8t laptop a year and a half ago. I bought it because it had the specs I wanted (mostly) for the cheapest price.  In hindsight, that may have been a clue.  I haven't had very good luck with it.  The right click button stopped working fairly early on (I configured the lower right section of the touchpad to act as right click, so I can at least work around that).  Then, randomly, the wifi would turn off sometimes. I figured I was just hitting the "turn the wifi off" button by accident, since it seemed to always happen when I picked up the laptop. then it started happening more and more and more, until it as happening when I knew I was no where near the wifi button.

You see, the dv8t has a bunch of touch sensitive buttons in a strip above the function keys.  The kind that you don't have to push, just touch.  Buttons for volume, mute, play, pause, skip, etc ....and turning the wifi on and off.

Side Rant:
Why the hell do laptop makers think they need a quick access way to turn on and off the wifi?  Who the hell turns the wifi off on their laptop so often, they need a dedicated button for it?

Well, since I don't use the button, I could just disable it, right? There must be some setting in the software to disable this button, right?  Nope.  Not even a little.  No settings for it or the other touch sensitive buttons at all.  Fantastic.

I googled the problem - here's how far I got before I knew this was not just me:

So,  looked up how to fix it.  HP was, of course, zero help.  The suggestions for new drivers etc had been tried and discarded by many forum goers, who were, naturally, quite pissed off.  Turns out this is a very widespread problem that HP itself hadn't been able to fix even when people returned their laptops for repair multiple times. HP just stopped producing this line of laptops (and another line with a similar touch sensitive bar that also had problems).

Turns out that the root of the problem is static electricity.  The touch sensitive buttons are capacitive, and use the electrical signal from your body to know when to turn on and off.  They evidently aren't shielded or grounded well enough, so just random static electric fields can cause them to trigger.  There are a couple youtube videos about how to fix it... but it's a little involved, using aluminum tape and kapton tape to ground the ribbon that connects the touch strip to the rest of the computer.  It looked like a hassle, honestly.

I figured... the only button I actually use on that stupid bar is the mute button, and I've been getting by with software controls since 1995.  So, instead of trying tp fix the thing, I'd just unplug it.  Turns out, that's actually really easy.

You have to remove the speaker cover so that you can pop out the bar with the touch buttons.  To do that you just need to unscrew 6 screws from the bottom of the laptop.  The screws are all marked with an arrow next to them like this:

These are the screws you are looking for

Remove the battery and unplug the laptop.  We don't want any electrocutions.  There are two of these screws on the back outside edges of the bottom of the laptop, and 4 under the battery.  Remove them, making sure the laptop is unplugged as well as having the battery out. 

Once that's done, flip the laptop  back over and pop out the speaker cover up by the screen.  I had to use a small screw driver to get under the edge of it, but trust me, it'll pop up.  Then pop up the top of the touch sensitive bar closest to the screen.  You'll see a 1/2 inch ribbon cable connected to the underneath of it. Just disconnect it and tuck it underneath the bar.  Snap the bar back in and the speaker cover back in, and put the screws back.  You're done. 

I still catch myself cringing when I pick up the laptop or hit the keyboard harder than usual... it's so ingrained in me now that any false move I make will turn off the wifi... it'll take some time for me to get used to the wifi actually staying on.