A Quick Aside

Before I get stuck into this post, I want to quickly mention my last. It got to the front page of Hacker News and stayed there for around a day. I submitted it on a whim and did not expect it to get even the slightest bit of attention. Thank you everybody who upvoted it, I am amazed and humbled that people found it (at least somewhat) interesting.

I fully intend to investigate the issue further and to write a follow up. There were some great comments on the Hacker News thread and on the article itself - leads for further research.

I also want to make it clear that the items listed on my upcoming post are coming, however the posts on that list require a fair bit of work and I want to make sure they’re as good as I want them to be. In order to stick to my promised post/week I need to ‘buffer’ a number of meatier posts, meanwhile I am going to throw out ideas I’ve wanted to express for some time.

The subject of today’s post is one of these things I’ve wanted to write about for a while and by coincidence there was a recent HN furore regarding Jeff Atwood’s latest blog post - Please Don’t Learn to Code - which addresses related issues, so I was motivated to write this now. I will try to pull the threads together.

Why Do I Code?

Growing up I spent a lot of time playing around with BASIC on my ZX Spectrum, and more than anything got a massive kick out of seeing this stuff actually do something, actually working on my computer. It was so satisfying.

Ever since, it has been that kick of seeing something actually come together, actually doing something which has driven my interest in computing. It might sound petty, but this thrill has never quite left me, and I really do think it lies at the heart of the pleasure of the thing. To quote edw519:-

The best part is getting something working for the first time where nothing was there before. For me, this is so exciting that I still I do a “happy dance” every time.

One utterly delightful aspect of programming is how low the barriers are to building things. If you wanted to design and build a car, say, you’d need lots of money and lots of people and a funnelling process from idea to physical reality to achieve your dreams, with plenty of difficult compromises in between. You’d certainly find it incredibly challenging not to mention expensive to try this on your own, to the extent it would be rather mad to try it at all.

Compare this to programming - all you need is a computer - even an ultra-cheap laptop is sufficient, and that combined with the web and all the free material out there is enough to get you from any level to really rather proficient limited only by your attitude and hard work. I can think of nothing else quite like it.

Fred Brooks put it far more eloquently than I ever could:-

The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds castles in the air, from air, creating by exertion of the imagination. … Yet the program construct, unlike the poet’s words, is real in the sense that it moves and works, producing visible outputs separate from the construct itself. … The magic of myth and legend has come true in our time. One types the correct incantation on a keyboard, and a display screen comes to life, showing things that never were nor could be.

Solving abstract problems with few constraints while still actually having an impact on the real world is a large part of the appeal of programming. It’s important not to forget what a miracle this stuff is - we build things which ‘exist’ in what amounts to an imaginary world of electrons travelling around lumps of transmuted sand which somehow do things which people find useful, so useful in fact, that these ghosts in the machine have utterly revolutionised the world and continue to do so at an ever increasing rate.

Programming and Talent

It is my strong conviction that talent and intelligence are the smallest components of the make up of a good programmer. I do believe they make a difference, but are important to a lesser degree than many think.

You need to be able to think logically and be capable of keeping a certain degree of state in your mind, that’s the talent of it, and you need to be bright enough to explore a problem sufficiently to find a solution, which is where the intelligence lies. But these are only pre-requisites. If you have enough of both, then you are going to be able to program (it turns out that a surprising number of people cannot, though to what degree that is talent vs. attitude I dont know.)

Attitude is the really crucial component. The vast size of the subject matter and the vast complexity of the machine in front of you means hubris is the biggest error you can possibly make. You will make mistakes, do stupid things, and misunderstand what the computer is actually doing much of the time. The vital attitude to have in facing this reality is to remain humble. As Dijkstra put it:-

The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague.

A programmer who lacks this humility can be absolutely nightmarish to deal with. Mistakes get brushed under the carpet, code remains an awful unmaintainable mess because ‘it works’ and that’s sufficient (that whole subject is likely to be an entire other ranty post), and things never improve because the first step in improving something is to admit that there’s something which needs improving. You can’t suck less every year without admitted you suck in the first place.

The other, slightly less important, but still critical component of being a good programmer is hard work. Things are always harder than they seem. Any non-trivial problem you’re dealing with will screw you over repeatedly before you solve it, and not until you’ve felt like giving up 3 times will it finally decide to behave. Oh, and the final 10% of the project will take 90% of the time. You just have to keep on going.

This latter point is in fact a lesson I’ve had to learn the hard way with personal projects. I have started several highly ambitious projects, only to hit problems early and give up (‘hey this is meant to be a hobby, this is no fun!’, etc.) - my chess engine project, weak, may be progressing slowly, but it is progressing and I refuse to give up on it.

Another skill which matters rather a lot is the ability to communicate. If you can’t communicate your great idea or the fatal technical flaw in a proposed plan, then no matter how able you are as a developer your voice just won’t be heard. Also, if you can’t communicate well it’s a lot easier to end up in realms of unpleasantness with others, which gets in the way of everything.

Storm in a Teacup

Back to the furore. I strongly believe that programming should be open for all, and new programmers welcomed with open arms. This thing is amazing and nobody has the right to tell anybody that they can’t choose to learn this craft and get that wonderful kick out of making computers actually do stuff. The fact that there has been a big movement to spread coding knowledge is great, the more the merrier I say.

Having said that, I think Jeff has hit on an inconvenient and slightly unpalatable truth which strongly links back to the two crucial characteristics of a good programmer. What we emphatically don’t need are new programmers who believe programming is incredibly easy yet wonder why their spaghetti monster runs so slowly, or managers who learn to write a very simple rails app and therefore get to treat you with less respect because it’s ‘all so easy’. Most of all, we don’t need people thinking developers are fungible commodities, because that simply ain’t so.

What’s needed is humility, commitment, and an understanding that it takes many years to become truly proficient at this craft.

Another uncomfortable truth is that we professional programmers often feel threatened by the idea that all these young whippersnappers might come in and make us look incredibly stupid and redundant. The nightmare scenario of an inexperienced guy coming in and doing in 1 week what took you 4 months is not a pleasant thought.

The solution is to not attach your identity¹ too closely to your code. You are not your job. Personally I’ve found this a very hard lesson and it’s something I still struggle with², but forming this separation is so clearly the answer that it’s worth the struggle.

Try to be the best programmer you can be. Focus on creating solutions to people’s problems because that’s ultimately what matters, but don’t forget that maintainability matters too and code quality informs a lot of the externally observable quality of your solution.

Have fun. Build stuff you’re proud of. And above all else, be nice to other people who are also trying to improve themselves. I know I fail at that often enough myself, and it can sometimes be incredibly difficult, but ultimately we are all idiots, so the best we can do is to try and help each other be a little less stupid.

Notes

1

I reference this post in order to give credit where it’s due. I want to make it clear that I actually strongly dislike the tone of Zed Shaw’s blog post, not to mention many other occasions where he’s, in my opinion, acted in rather a bullying fashion (e.g. this and of course this). He is a great programmer, and his books are equally brilliant, but his behaviour towards others is not.

As I commented on hacker news, my perception of that kind of bullying nastiness put me off working on anything public for a long while. I take responsibility for my lack of productivity, but that kind of attitude certainly didn’t help anything. I don’t think it helps anybody.

2

I don’t want to be too much of a pop psychologist, but I do wonder whether the stereotypical experience of feeling somewhat inadequate at school while finding a means of gaining a sense of value via programming/working with computers binds self worth to your work early on. Of course, this is by no means the experience of all programmers out there, but I do think it is the experience of a fair few, including myself.

In this post I explore what I perceive to be a fundamental issue with object orientation via a type hierarchy.

Apologetic Preamble

I want to make it clear that this post is emphatically not an attack on C# (a language I admire¹), nor is C# the only language to implement type hierarchies (java is a better-known language which takes this approach), rather it’s a criticism of a general trait of the kind of object orientation implemented² by languages like C#, which due to my familiarity with it is the language I use in this post to explore my point.

The Problem

When you write a program using a C#-like language you typically start by modelling your problem as a hierarchical set of classes which represent your domain. You then procede to ‘flesh out’ and expand upon these types with code which actually implements your program.

After a while you inevitably find an exception to the rules of the system you have created - your types turn out not to match the problem in some way. Typically this occurs later after a lot of work has already been done which is now strongly tied to the structure of your type hierarchy, so you are left with a problem - do you hack around the incongruity, usually the quickest solution, or restructure your types to adapt to the new requirement?

If you choose the former your hierarchy not only fails represent the problem anymore, it actively misleads you about it. If you choose the latter, you end up spending a long time yak shaving - working on something which has absolutely nothing to do with the problem itself and is purely a product of the system in which you are writing your program - the very definition of accidental complexity.

A Concrete Example

To explore this problem more concretely, let’s take a look at an actual example.

Note that, whatever example I choose, it’s inevitable that it will not fully capture this problem the way architecting a big project under deadline pressure will. However, exploring actual code is of such value that I think it worth doing regardless.

That said, let’s consider a type hierarchy which represents trades made on financial exchanges:-

class Exchange {
    public string Bic { get; set; }
    public string Name { get; set; }
}

abstract class Security {
    public string Description { get; set; }
    public Exchange Exchange { get; set; }
    public string Isin { get; set; }
}

class Stock : Security {
}

class Bond : Security {
    public DateTime Expiry { get; set; }
}

class Trade {
    public decimal Price { get; set; }
    public decimal Quantity { get; set; }
    public Security Security { get; set; }
}

So far, so good - this seems like a sensible approach and so we go ahead and write a lot of code around this hierarchy.

The code gradually becomes deeply coupled to our type design - we expect all financial securities to possess an ISIN (an international identification number), a description and an exchange which itself possesses a name and a BIC (bank identification code), we expect stocks to possess no extra properties, bonds to possess expiry dates, and trades to possess a security, price and quantity. The client is happy, the system works well and your code is nice and clean.

Suddenly the client demands a change - they are about to trade options and need to bring them into the system. Fine you think, so you come up with a class:-

class Option : Security {
    public bool Call { get; set; }
    public decimal LotSize { get; set; }
    public DateTime Maturity { get; set; }
    public decimal StrikePrice { get; set; }
}

But a problem arises - options are typically not assigned ISINs, and now we have a property which is meaningless for options. We are faced with the dilemma - a lot of the code is now reliant on Isin, and NullReferenceExceptions are getting thrown all over the place because the field isn’t getting populated. Do we remove the Isin field from Security and create a separate classification between physical and derivative securities (or perhaps ISIN-possessing instruments and non-ISIN-possessing instruments) - one containing Isin and one not? Or do we find some other, less salubrious way around the problem?

The client is getting angry now - there’s a hold up, developers are arguing about what to do, and the trading systems needs to be in place by the next day or some P45s are going to be handed out. So it’s decided - quick-fix now, real fix later:-

// Lots of:-
if(security.Isin == null) {
    ...
}

// Not to mention:-
if(security is Option) {
    ...
} else {
    ...
}

// And maybe even some:-
switch(security.GetType().Name) {
    case "Option":
        ...
    case "Stock":
        ...
    ...
}

Our code is suddenly not looking so great. Our type hierarchy now falsely implies that all securities have ISINs, a particular issue for developers new to the project, we have hacks all over the place, maybe not enough (we’re fairly sure we got everything but there are always those nooks and crannies which slip through the test suite), we are forced to add new hacks as we go and confidence in our code is definitely eroded.

Suddenly a new requirement arises - it turns out securities need to refer to traded exchange which might be different for two otherwise identical securities, but our architecture has lumped exchange with securities. We are back to our dilemma again…

An Imperfect Example

Again, I emphasise that the above example is necessarily imperfect, as to practically fit an example of this problem into a blog post necessitates quite some trivialising. That being said, hopefully it makes the point a little more concrete.

An objection here might be that these change requests merely exposed design mistakes made early on in the project whose impact inevitably got magnified down the line as code was written on the assumption that these mistakes were in fact valid. The problem with that argument is to me the problem with the waterfall method for software development - it assumes you know a great deal up front, something which is very rarely the case.

The reality of software development is almost the opposite of that assumed by approaches which require large amounts of upfront structural foundations to be laid. Requirements and facts around your code tends to change constantly and often in utterly unexpected ways, so having a structure up front which lays down brittle laws about your system is setting yourself up to fail.

The brittleness of the laws is the real issue - if their failing didn’t result in hacks or yaks then there wouldn’t be as much of a problem.

Solutions

I hate to state a problem without suggesting solutions, I am after all a programmer, and our job is to solve problems, not just create them.

I am certainly not suggesting that object orientation is somehow fundamentally flawed, nor am I advocating writing code procedurally when it could benefit from the encapsulation, abstraction and de-duplication of an alternative approach purely out of FUD about potential future issues, rather I think that if you are going to write in a language which supports this approach it’s important to consider this issue before committing to representing your problem this way.

Some ideas:-

• There are methods and patterns for separation of concerns and decoupling of related code, including techniques like dependency injection, which may help mitigate this problem to some degree while still using a C#-like language.

• Functional programming is enjoying a great upswing in interest and popularity these days. I wonder whether the stronger type systems of these languages and the greater guarantees about what a function does/does not do (i.e. less likely to produce side-effects, immutable state) might provide a means to more quickly adapt a change to the model at compile- rather than run-time.

• Bottom-up programming in a language like Lisp offers an enormous amount of flexibility in meta-programming and might make downstream changes easier to introduce later in the development process.

• Dynamic programming languages like Python, Ruby and Lisp provide a far less rigid type structure - types don’t necessarily need to be known at compile time, meaning you have a great deal of flexibility to write functions which are less tied to a previously-determined structure than in a statically-typed language.

• Go provides an intriguingly simplified version of static typing where no type hierarchy is permitted to be defined at all, rather you express relations between types through implicit interfaces which define types through what they do rather than what they are. They are implicit in that as soon as you’ve defined what you want, i.e. what methods a type possesses, then any type which possesses those methods implements the interface.

• Smalltalk implements object orientation in quite a different fashion from C#-like languages, with emphasis on passing messages between objects rather than the structure of the classes themselves. This could help reduce the dependency on initial structural decisions.

• (ECMA|Java)script allows you to define relations between objects based on object prototypes rather than static classes, you simply can’t declare static user-defined types at all.

I don’t want to advocate a particular solution above any other, as I am still undecided and exploring these ideas myself, not to mention the fact that a lot of this stuff sits decidedly in the grey area of rather subjective choices where it’s hard to definitely prove one approach is better than another.

I do however think that the brittleness of the upfront type hierarchy is a real issue which needs to be carefully considered before writing a large program and weighed up against other engineering approaches.

Notes

1

I have spent several years working with C#. Overall it’s a fantastic language which has grown ever more fantastic over time. Starting as, frankly, Microsoft Java, it has grown to incorporate generics, better support for functional style programming through a neat lambda syntax, libraries offering standard functional-style methods such as map, filter and fold (select, where and aggregate respectively in C# parlance), a declarative syntax for querying generic collections via LINQ as well as numerous other little features which make it a very nice language to work with. It’s well-engineered and surprisingly ambitious.

2

I say this, rather than just saying ‘I have a problem with object orientation’, as there are different interpretations as to how object orientation should be implemented, and a C#-ish implementation is just one approach - cf. smalltalk.

Goプログラミング言語仕様の翻訳を最新にアップデートしました。
細かい更新箇所は多いのですが、前回の翻訳からの変更点は以下です。

• マップの要素を削除するdelete組み込み関数が追加された。
• rune型(他言語のchar型のようなもの)が追加された。
• init関数内でゴルーチンが起動できるようになった。
• 標準関数が返却するエラー情報は、新たに追加されたerror組み込み型を使用するようになった。

 ※2012/5/9 タイプミスを修正しました。報告いただきありがとうございました。

Okay, so I haven’t updated this blog in quite some time.

I don’t want to become one of those people whose blog consists of very few blog posts, mostly apologising for not blogging more, so I’ll keep this short and sweet and simply announce some posts I’m working on:-

• Why Go? - A post discussing the merits of Go and what makes it different from other programming languages.

• Series: Algorithms - A series of posts on algorithms of interest, with a focus on exploring how you go about actually implementing them in code.

• Series: Go Standard Library - A series of highly indulgent posts exploring Go’s standard libraries and how they are actually implemented in practice, in the vein of Jeff Atwood’s and Scott Hanselman’s recent posts on reading other’s source code.

• Series: Go Internals - A series of yet more indulgent posts exploring Go’s internal implementation details.

• Series: Weak and Chess Engines - A series of posts on the implementation of Weak and chess engines in general.

• General Programming/Personal Topics of Interest - Basically whatever I happen to be thinking about at a given point. I think about programming a lot, and I think it’s time to put it out there, whether it’s coherent or of interest to other geeks out there, or not :-)

I am committing to getting at least one blog post out a week. I intend to fill my blog with exactly the kind of stuff I love reading in other people’s blogs - lots of juicy, no messing about, unix-bearded, hardcore tech detail and geekery with pride.

Sorry Brogrammers, I’ve got nothing for you.

久しぶりの翻訳更新です。
Go言語のインストールの翻訳を更新しました。

いままではGo言語をソースファイルから自分でコンパイルするしかなかったのですが、Version1からバイナリで配布されるようになりました。また、Windowsも正式にサポートされるようになりました。

Oddly appropriate, don't you think?

TL;DR: kylelemons.net/go/rx

The Problem

Before I get too far, let me first summarize the problem.

When developing a Go application, you will most likely find yourself depending on another package, often written by another author. The ease of utilizing such third-party packages with the go tool makes this an even likelier scenario, and it is, in fact, encouraged. Inevitably, however, the author of some package on which you depend will make a change to his package; this could be anything from an innocuous bug fix to a large-scale API reorganization, and you are suddenly left with two choices: stick with the version you have (often by cloning it locally) or bite the bullet and update. This is complicated by the fact that you may both directly and indirectly depend on the same package, which means that both your project and your intermediate dependency need to agree on which of the above choices to take, and in a relatively timely manner.

There have been many proposals and complaints, both on- and offline, with respect to this problem. It’s not a problem that’s unique to Go, either; tools like Apache’s Maven, Ruby’s Bundler, etc all attempt to solve this problem to a greater or lesser degree. It is such a prevalent theme in development that a term, DLL Hell (and the more technically correct term dependency hell), has come into common use to describe it.

Strategies

The most obvious thing to do is to be paranoid about package maintainers, and thus copy your dependencies into your project. If this strategy is sufficient, I highly recommend checking out goven, which will streamline this process (it even rewrites the imports!) for you. I take a different tack because I am lazy and don’t want to have to maintain other people’s code. I also don’t think this strategy simplifies the process of pulling in new changes from upstream, because you still have to update them one at a time until/unless something breaks.

The next obvious thing is to specify somewhere what version you want to check out, in the source code, so that go get knows about it and can do the right thing. This essentially boils down to something like import "path/package/version" (though various proposals suggest using @rev or similar). This is certainly a solution, and I suspect we will see tools emerge that will download source and update it to the proper revisions as a go get alternative. I didn’t choose this solution because this requires rewriting import paths when you update code and it makes it difficult to ensure that there is only a single version of a library built into the same binary, which can cause problems (if there are more, the init() calls will run twice, for one thing). It also doesn’t help with pulling in changes: you still are taking a chance that you’ll break something (sometimes without realizing it) whenever you pull from upstream.

Another reasonable strategy is to version-control the entire (or at least the dependencies within) GOPATH(s). This has the advantage that multiple developers always check out the correct versions, and branches and merges work nicely. A very simple tool along these lines is being developed as gogo, which allows you to version control your dependencies and share them between developers. As long as your version control system doesn’t mind having other version control systems’ (or its own) metadata stored inside it, this will work. The downside of this is that you are storing a lot of redundant data in your vcs, and it still doesn’t address the issue of how to figure out when and if you can update what packages.

Enter `rx`

So, since my ancient pre-goinstall build tool has been obsoleted, I figured I’d try my hand at distilling a reasonable, achievable set of goals out of the sea of requirements and suggestions and turn them into a tool for people to use. If you didn’t guess this from the previous section, the biggest problem that I think I can solve is helping you figure out what dependencies you can update without breaking your world. This can probably work in addition to at least a few of the strategies listed above for a more complete versioning solution, depending on your particular needs. Here are my informal design ideas/goals/requirements/notes:

1. It shouldn’t try to “solve” dependency hell. Making people’s lives easier is enough for now.
2. It should leverage the existing go tool and GOPATH conventions as much as possible.
3. It should be easy to see the versions of packages, and to change the active one.
4. It should be intelligent about updating and notice when an update breaks something else.
5. It should be able to save a “known good” set of versions for easy rollback and sharing.
6. It should be fun to use, and should not get in the way of the developer.

In that vein, I have started work on rx, my prescription for your Go dependency version headaches. It’s starting to approach a few of the the requirements above already. To whet your appetite, here are a few examples of what it can do:

• rx list will show you inter-repository dependencies
• rx tags will show you the what tags are available in a repository
• rx prescribe will update a repository and test its transitive dependents

Each command also has plenty of fun options to play with; rx tags has, for instance, options to only show tags that are up- or downgrades. The structure of the program is strongly reminiscent of the design of the go tool (and, in fact, uses it for a lot of backend logic), and so should be familiar for most Gophers and fit nicely into your existing workflows.

Installation is, of course, rather simple:
go get -u kylelemons.net/go/rx

Here’s a brief example of using rx:

$ rx --rescan list | grep rpc
/<gopath>/src/github.com/kylelemons/go-rpcgen: codec webrpc main main echoservice main main offload wire webrpc
$ rx tags go-rpcgen | egrep v\|HEAD
193746c88dfebdc5462382b93c1038a29496d9af v2.0.0
a6938fa6ec0fb6a63fefab2c462d3cd1102cc477 v1.2.0
bf28cdf3e683dd0919800f6916141c17aa93c36d HEAD
bf28cdf3e683dd0919800f6916141c17aa93c36d v1.1.0
f73c5c8ea85bdfbdc69e6aa24dd90b43c7265c67 v1.0.0
$ rx pre go-rpcgen v2.0.0
ok      github.com/kylelemons/go-rpcgen/codec   0.051s
ok      github.com/kylelemons/go-rpcgen/examples/echo   0.139s
ok      github.com/kylelemons/go-rpcgen/examples/remote 0.019s
ok      github.com/kylelemons/blightbot/bot     0.029s
ok      github.com/kylelemons/go-paxos/paxos    0.053s
$ rx tags go-rpcgen | egrep v\|HEAD
193746c88dfebdc5462382b93c1038a29496d9af HEAD
193746c88dfebdc5462382b93c1038a29496d9af v2.0.0
a6938fa6ec0fb6a63fefab2c462d3cd1102cc477 v1.2.0
bf28cdf3e683dd0919800f6916141c17aa93c36d v1.1.0
f73c5c8ea85bdfbdc69e6aa24dd90b43c7265c67 v1.0.0
</gopath>

There’s not a whole lot here, but you can see that the list command (in its short form) found the repository and listed the (short) names of the packages that exist under it. The --rescan option told it to actually scan my repositories, instead of using the cached dependency graph. The tags command then showed me the interesting tags in the repository (it’s git, so HEAD also shows where it was currently), and then the prescribe command updated it to the latest tag. Notice that the repository’s tests were run, as well as tests for packages that depended on packages in that repository (transitively). They were also built and installed (except binaries, by default), though this isn’t displayed unless you use the -v option.

Expected Use Cases

To help elucidate the problem I’m trying to solve, here are a few use cases that I’d like to support.

Hobbyist Developer

As a single developer, you’ve probably got a single GOPATH into which all of your dependencies are installed alongside your own projects. You freely import between them, and everything generally works. You don’t run go get very often to pull down remote packages, unless you find a bug that has been fixed or you find a new feature in a newer library.

• The rx fetch command will let you fetch the latest changesets without actually applying them.
• The rx tags --up command will show you what tags you can upgrade to.
• The rx prescribe command will allow you to update to a new tag.
• The rx prescribe command automatically builds and tests depenants transitively.
• The rx prescribe command will roll back the update if it turns out to have broken something.

Small Team

As a small team working on a Go project, your concerns are much different from that of a single developer. You want your team members to easily stay in sync with one another, and you will only rarely pull changes in from upstream once you have your project working with a particular dependency.

• The --rxdir flag and RX_DIR environment variable let you version or share an rx configuration.
• The rx cabinet --save command saves the versions of all repositories.
• The rx cabinet --load command reverts/upgrades repositories to their saved state.
• The rx cabinet --export command saves a relocatable cabinet that can be sshared.
• The rx pin command lets you configure what repositories are considered for upgrade.
• The rx auto command will try to upgrade packages automatically, keeping seamless upgrades.

The common theme among these commands is maintaining a cohesive group of dependency versions. When you update a dependency (which we’ve seen that rx prescribe can do automatically), you can save that as a “known good” configuration that you can share, save, and (if things go south) restore later. For packages that are known to misbehave or for the package you’re editing, the rx pin command allows you to specify manually what behavior they should have (never upgrade, always tip, never change, etc). To help with exploring what updates might apply seamlessly, the rx auto command will do the heavy lifting of figuring out which repositories depend on each other and will successively try updates.

Large Project

On a large project, you care about most of the same things as a small team, but there is also a good chance that you are working on multiple versions of your software simultaneously. There is also a good chance that any given developer may have multiple projects on his workstation which are independently versioned.

• The rx cabinet --exclude command (and friends) configure exactly what cabinets track.
• The rx cabinet --diff command shows differences in dependencies between cabinets.
• The advanced rx prescribe optiosn can manage package upgrades auto can’t handle.

The theme here is that the same commands that worked in a small and medium environment continue to work, but that their concepts can be extended (and modified slightly) to accomodate the needs of a larger development team. The larger the team is, the more chances are that there will be multiple branches in play, and rx will need to understand this.

The Catch

There are still problems with this approach. As long as you start with a working project, you should generally be able to keep it working. You may not be able to ever update a package if one of its dependents never comes into line, though, which leads me to the biggest problem with this approach: it doesn’t make it easy to simply install a remote repository that has external dependencies. It’s intended primarily to support development and releasing of e.g. a binary, where your local development environment doesn’t matter to the end user. I’d like for there to be a nice way to import a package’s cabinet file when you’re importing it (so that your version of rx learns about what versions do and don’t work with various dependency versions), but I haven’t fully mapped this out.

Another problem which remains currently unsolved is the requirement to manually update when a dependency’s API changes. It would be nice to have some way for the author of a package to provide a way for dependent packages to fix themselves automatically; a tool like gofix. If this convention were widespread enough, it could vastly simplify the process of updating packages. This is something else about which I am thinking, and I hope that there are good libraries for easily making gofix-like tools in the future as well as a convention for including them in your projects.

Coming Soon

There is a lot of work to do, but I think it’s at the point where the best feedback is feedback from real users who have a real need for a tool like this. The next priorities on my list are:

1. Save and restore global repository state
2. Intelligently run “upgrade” experiments to find what new tags can be seamlessly integrated
3. Support branches and branch switching
4. Clean up and document more of the code

Your feedback, constructive criticism, and pull requests are all greatly appreciated!

P.S. I’m slowly cleaning up my many side-projects and making sure they work with Go 1. I’ll be listing them on kylelemons.net/go as I do, so feel free to e-mail me or find me on IRC if you have a favorite package that you want updated.

If you have written any Go code you have probably encountered the built-in error type. Go code uses error values to indicate an abnormal state. For example, the os.Open function returns a non-nil error value when it fails to open a file.

func Open(name string) (file *File, err error)

The following code uses os.Open to open a file. If an error occurs it calls log.Fatal to print the error message and stop.

    f, err := os.Open("filename.ext")
    if err != nil {
        log.Fatal(err)
    }
    // do something with the open *File f

You can get a lot done in Go knowing just this about the errortype, but in this article we'll take a closer look at error and discuss some good practices for error handling in Go.

The error type

The error type is an interface type. An errorvariable represents any value that can describe itself as a string. Here is the interface's declaration:

type error interface {
    Error() string
}

The error type, as with all built in types, is predeclared in the universe block.

The most commonly-used error implementation is the errors package's unexported errorString type.

// errorString is a trivial implementation of error.
type errorString struct {
    s string
}

func (e *errorString) Error() string {
    return e.s
}

You can construct one of these values with the errors.Newfunction. It takes a string that it converts to an errors.errorStringand returns as an error value.

// New returns an error that formats as the given text.
func New(text string) error {
    return &errorString{text}
}

Here's how you might use errors.New:

func Sqrt(f float64) (float64, error) {
    if f < 0 {
        return 0, errors.New("math: square root of negative number")
    }
    // implementation
}

A caller passing a negative argument to Sqrt receives a non-nil error value (whose concrete representation is an errors.errorString value). The caller can access the error string ("math: square root of...") by calling the error's Error method, or by just printing it:

    f, err := Sqrt(-1)
    if err != nil {
        fmt.Println(err)
    }

The fmt package formats an error value by calling its Error() string method.

It is the error implementation's responsibility to summarize the context. The error returned by os.Open formats as "open /etc/passwd: permission denied," not just "permission denied." The error returned by our Sqrt is missing information about the invalid argument.

To add that information, a useful function is the fmt package's Errorf. It formats a string according to Printf's rules and returns it as an error created by errors.New.

    if f < 0 {
        return 0, fmt.Errorf("math: square root of negative number %g", f)
    }

In many cases fmt.Errorf is good enough, but since error is an interface, you can use arbitrary data structures as error values, to allow callers to inspect the details of the error.

For instance, our hypothetical callers might want to recover the invalid argument passed to Sqrt. We can enable that by defining a new error implementation instead of using errors.errorString:

type NegativeSqrtError float64

func (f NegativeSqrtError) Error() string {
    return fmt.Sprintf("math: square root of negative number %g", float64(f))
}

A sophisticated caller can then use a type assertion to check for a NegativeSqrtError and handle it specially, while callers that just pass the error to fmt.Println or log.Fatal will see no change in behavior.

As another example, the json package specifies a SyntaxError type that the json.Decode function returns when it encounters a syntax error parsing a JSON blob.

type SyntaxError struct {
    msg    string // description of error
    Offset int64  // error occurred after reading Offset bytes
}

func (e *SyntaxError) Error() string { return e.msg }

The Offset field isn't even shown in the default formatting of the error, but callers can use it to add file and line information to their error messages:

    if err := dec.Decode(&val); err != nil {
        if serr, ok := err.(*json.SyntaxError); ok {
            line, col := findLine(f, serr.Offset)
            return fmt.Errorf("%s:%d:%d: %v", f.Name(), line, col, err)
        }
        return err
    }

(This is a slightly simplified version of some actual codefrom the Camlistore project.)

The error interface requires only a Error method; specific error implementations might have additional methods. For instance, the net package returns errors of type error, following the usual convention, but some of the error implementations have additional methods defined by the net.Errorinterface:

package net

type Error interface {
    error
    Timeout() bool   // Is the error a timeout?
    Temporary() bool // Is the error temporary?
}

Client code can test for a net.Error with a type assertion and then distinguish transient network errors from permanent ones. For instance, a web crawler might sleep and retry when it encounters a temporary error and give up otherwise.

        if nerr, ok := err.(net.Error); ok && nerr.Temporary() {
            time.Sleep(1e9)
            continue
        }
        if err != nil {
            log.Fatal(err)
        }

Simplifying repetitive error handling

In Go, error handling is important. The language's design and conventions encourage you to explicitly check for errors where they occur (as distinct from the convention in other languages of throwing exceptions and sometimes catching them). In some cases this makes Go code verbose, but fortunately there are some techniques you can use to minimize repetitive error handling.

Consider an App Engineapplication with an HTTP handler that retrieves a record from the datastore and formats it with a template.

func init() {
    http.HandleFunc("/view", viewRecord)
}

func viewRecord(w http.ResponseWriter, r *http.Request) {
    c := appengine.NewContext(r)
    key := datastore.NewKey(c, "Record", r.FormValue("id"), 0, nil)
    record := new(Record)
    if err := datastore.Get(c, key, record); err != nil {
        http.Error(w, err.Error(), 500)
        return
    }
    if err := viewTemplate.Execute(w, record); err != nil {
        http.Error(w, err.Error(), 500)
    }
}

This function handles errors returned by the datastore.Getfunction and viewTemplate's Execute method. In both cases, it presents a simple error message to the user with the HTTP status code 500 ("Internal Server Error"). This looks like a manageable amount of code, but add some more HTTP handlers and you quickly end up with many copies of identical error handling code.

To reduce the repetition we can define our own HTTP appHandlertype that includes an error return value:

type appHandler func(http.ResponseWriter, *http.Request) error

Then we can change our viewRecord function to return errors:

func viewRecord(w http.ResponseWriter, r *http.Request) error {
    c := appengine.NewContext(r)
    key := datastore.NewKey(c, "Record", r.FormValue("id"), 0, nil)
    record := new(Record)
    if err := datastore.Get(c, key, record); err != nil {
        return err
    }
    return viewTemplate.Execute(w, record)
}

This is simpler than the original version, but the http package doesn't understand functions that return error. To fix this we can implement the http.Handler interface's ServeHTTP method on appHandler:

func (fn appHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    if err := fn(w, r); err != nil {
        http.Error(w, err.Error(), 500)
    }
}

The ServeHTTP method calls the appHandler function and displays the returned error (if any) to the user. Notice that the method's receiver, fn, is a function. (Go can do that!) The method invokes the function by calling the receiver in the expression fn(w, r).

Now when registering viewRecord with the http package we use the Handle function (instead of HandleFunc) as appHandler is an http.Handler (not an http.HandlerFunc).

func init() {
    http.Handle("/view", appHandler(viewRecord))
}

With this basic error handling infrastructure in place, we can make it more user friendly. Rather than just displaying the error string, it would be better to give the user a simple error message with an appropriate HTTP status code, while logging the full error to the App Engine developer console for debugging purposes.

To do this we create an appError struct containing an error and some other fields:

type appError struct {
    Error   error
    Message string
    Code    int
}

Next we modify the appHandler type to return *appError values:

type appHandler func(http.ResponseWriter, *http.Request) *appError

(It's usually a mistake to pass back the concrete type of an error rather than error, for reasons discussed in the Go FAQ, but it's the right thing to do here because ServeHTTP is the only place that sees the value and uses its contents.)

And make appHandler's ServeHTTP method display the appError's Message to the user with the correct HTTP status Code and log the full Error to the developer console:

func (fn appHandler) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    if e := fn(w, r); e != nil { // e is *appError, not os.Error.
        c := appengine.NewContext(r)
        c.Errorf("%v", e.Error)
        http.Error(w, e.Message, e.Code)
    }
}

Finally, we update viewRecord to the new function signature and have it return more context when it encounters an error:

func viewRecord(w http.ResponseWriter, r *http.Request) *appError {
    c := appengine.NewContext(r)
    key := datastore.NewKey(c, "Record", r.FormValue("id"), 0, nil)
    record := new(Record)
    if err := datastore.Get(c, key, record); err != nil {
        return &appError{err, "Record not found", 404}
    }
    if err := viewTemplate.Execute(w, record); err != nil {
        return &appError{err, "Can't display record", 500}
    }
    return nil
}

This version of viewRecord is the same length as the original, but now each of those lines has specific meaning and we are providing a friendlier user experience.

It doesn't end there; we can further improve the error handling in our application. Some ideas:

• give the error handler a pretty HTML template,
• make debugging easier by writing the stack trace to the HTTP response when the user is an administrator,
• write a constructor function for appError that stores the stack trace for easier debugging,
• recover from panics inside the appHandler, logging the error to the console as "Critical," while telling the user "a serious error has occurred." This is a nice touch to avoid exposing the user to inscrutable error messages caused by programming errors. See the Defer, Panic, and Recoverarticle for more details.

Conclusion

Proper error handling is an essential requirement of good software. By employing the techniques described in this post you should be able to write more reliable and succinct Go code.

QR codes are 2-dimensional bar codes that encode arbitrary text strings. A common use of QR codes is to encode URLs so that people can scan a QR code (for example, on an advertising poster, building roof, volleyball bikini, belt buckle, or airplane banner) to load a web site on a cell phone instead of having to “type” in a URL.

QR codes are encoded using Reed-Solomon error-correcting codes, so that a QR scanner does not have to see every pixel correctly in order to decode the content. The error correction makes it possible to introduce a few errors (fewer than the maximum that the algorithm can fix) in order to make an image. For example, in 2008, Duncan Robertson took a QR code for “http://bbc.co.uk/programmes” (left) and introduced errors in the form of a BBC logo (right):

That's a neat trick and a pretty logo, but it's uninteresting from a technical standpoint. Although the BBC logo pixels look like QR code pixels, they are not contribuing to the QR code. The QR reader can't tell much difference between the BBC logo and the Union Jack. There's just a bunch of noise in the middle either way.

Since the BBC QR logo appeared, there have been many imitators. Most just slap an obviously out-of-place logo in the middle of the code. This Disney poster is notable for being more in the spirit of the BBC code.

There's a different way to put pictures in QR codes. Instead of scribbling on redundant pieces and relying on error correction to preserve the meaning, we can engineer the encoded values to create the picture in a code with no inherent errors, like these:

This post explains the math behind making codes like these, which I call QArt codes. I have published the Go programs that generated these codes at code.google.com/p/rsc and created a web site for creating these codes.

Background

For error correction, QR uses Reed-Solomon coding (like nearly everything else). For our purposes, Reed-Solomon coding has two important properties. First, it is what coding theorists call a systematic code: you can see the original message in the encoding. That is, the Reed-Solomon encoding of “hello” is “hello” followed by some error-correction bytes. Second, Reed-Solomon encoded messages can be XOR'ed: if we have two different Reed-Solomon encoded blocks b₁ and b₂ corresponding to messages m₁ and m₂, b₁ ⊕ b₂ is also a Reed-Solomon encoded block; it corresponds to the message m₁ ⊕ m₂. (Here, ⊕ means XOR.) If you are curious about why these two properties are true, see my earlier post, Finite Field Arithmetic and Reed-Solomon Coding.

QR Codes

A QR code has a distinctive frame that help both people and computers recognize them as QR codes. The details of the frame depend on the exact size of the code—bigger codes have room for more bits—but you know one when you see it: the outlined squares are the giveaway. Here are QR frames for a sampling of sizes:

The colored pixels are where the Reed-Solomon-encoded data bits go. Each code may have one or more Reed-Solomon blocks, depending on its size and the error correction level. The pictures show the bits from each block in a different color. The L encoding is the lowest amount of redundancy, about 20%. The other three encodings increase the redundancy, using 38%, 55%, and 65%.

(By the way, you can read the redundancy level from the top pixels in the two leftmost columns. If black=0 and white=1, then you can see that 00 is L, 01 is M, 10 is Q, and 11 is H. Thus, you can tell that the QR code on the T-shirt in this picture is encoded at the highest redundancy level, while this shirt uses the lowest level and therefore might take longer or be harder to scan.

As I mentioned above, the original message bits are included directly in the message's Reed-Solomon encoding. Thus, each bit in the original message corresponds to a pixel in the QR code. Those are the lighter pixels in the pictures above. The darker pixels are the error correction bits. The encoded bits are laid down in a vertical boustrophedon pattern in which each line is two columns wide, starting at the bottom right corner and ending on the left side:

We can easily work out where each message bit ends up in the QR code. By changing those bits of the message, we can change those pixels and draw a picture. There are, however, a few complications that make things interesting.

QR Masks

The first complication is that the encoded data is XOR'ed with an obfuscating mask to create the final code. There are eight masks:

An encoder is supposed to choose the mask that best hides any patterns in the data, to keep those patterns from being mistaken for framing boxes. In our encoder, however, we can choose a mask before choosing the data. This violates the spirit of the spec but still produces legitimate codes.

QR Data Encoding

The second complication is that we want the QR code's message to be intelligible. We could draw arbitrary pictures using arbitrary 8-bit data, but when scanned the codes would produce binary garbage. We need to limit ourselves to data that produces sensible messages. Luckily for us, QR codes allow messages to be written using a few different alphabets. One alphabet is 8-bit data, which would require binary garbage to draw a picture. Another is numeric data, in which every run of 10 bits defines 3 decimal digits. That limits our choice of pixels slightly: we must not generate a 10-bit run with a value above 999. That's not complete flexibility, but it's close: 9.96 bits of freedom out of 10. If, after encoding an image, we find that we've generated an invalid number, we pick one of the 5 most significant bits at random—all of them must be 1s to make an invalid number—hard wire that bit to zero, and start over.

Having only decimal messages would still not be very interesting: the message would be a very large number. Luckily for us (again), QR codes allow a single message to be composed from pieces using different encodings. The codes I have generated consist of an 8-bit-encoded URL ending in a # followed by a numeric-encoded number that draws the actual picture:

The leading URL is the first data encoded; it takes up the right side of the QR code. The error correction bits take up the left side.

When the phone scans the QR code, it sees a URL; loading it in a browser visits the base page and then looks for an internal anchor on the page with the given number. The browser won't find such an anchor, but it also won't complain.

The techniques so far let us draw codes like this one:

The second copy darkens the pixels that we have no control over: the error correction bits on the left and the URL prefix on the right. I appreciate the cyborg effect of Peter melting into the binary noise, but it would be nice to widen our canvas.

Gauss-Jordan Elimination

The third complication, then, is that we want to draw using more than just the slice of data pixels in the middle of the image. Luckily, we can.

I mentioned above that Reed-Solomon messages can be XOR'ed: if we have two different Reed-Solomon encoded blocks b₁ and b₂ corresponding to messages m₁ and m₂, b₁ ⊕ b₂ is also a Reed-Solomon encoded block; it corresponds to the message m₁ ⊕ m₂. (In the notation of the previous post, this happens because Reed-Solomon blocks correspond 1:1 with multiples of g(x). Since b₁ and b₂ are multiples of g(x), their sum is a multiple of g(x) too.) This property means that we can build up a valid Reed-Solomon block from other Reed-Solomon blocks. In particular, we can construct the sequence of blocks b₀, b₁, b₂, ..., where b_i is the block whose data bits are all zeros except for bit i and whose error correction bits are then set to correspond to a valid Reed-Solomon block. That set is a basis for the entire vector space of valid Reed-Solomon blocks. Here is the basis matrix for the space of blocks with 2 data bytes and 2 checksum bytes:

The missing entries are zeros. The gray columns highlight the pixels we have complete control over: there is only one row with a 1 for each of those pixels. Each time we want to change such a pixel, we can XOR our current data with its row to change that pixel, not change any of the other controlled pixels, and keep the error correction bits up to date.

So what, you say. We're still just twiddling data bits. The canvas is the same.

But wait, there's more! The basis we had above lets us change individual data pixels, but we can XOR rows together to create other basis matrices that trade data bits for error correction bits. No matter what, we're not going to increase our flexibility—the number of pixels we have direct control over cannot increase—but we can redistribute that flexibility throughout the image, at the same time smearing the uncooperative noise pixels evenly all over the canvas. This is the same procedure as Gauss-Jordan elimination, the way you turn a matrix into row-reduced echelon form.

This matrix shows the result of trying to assert control over alternating pixels (the gray columns):

The matrix illustrates an important point about this trick: it's not completely general. The data bits are linearly independent, but there are dependencies between the error correction bits that mean we often can't have every pixel we ask for. In this example, the last four pixels we tried to get were unavailable: our manipulations of the rows to isolate the first four error correction bits zeroed out the last four that we wanted.

In practice, a good approach is to create a list of all the pixels in the Reed-Solomon block sorted by how useful it would be to be able to set that pixel. (Pixels from high-contrast regions of the image are less important than pixels from low-contrast regions.) Then, we can consider each pixel in turn, and if the basis matrix allows it, isolate that pixel. If not, no big deal, we move on to the next pixel.

Applying this insight, we can build wider but noisier pictures in our QR codes:

The pixels in Peter's forehead and on his right side have been sacrificed for the ability to draw the full width of the picture.

We can also choose the pixels we want to control at random, to make Peter peek out from behind a binary fog:

Rotations

One final trick. QR codes have no required orientation. The URL base pixels that we have no control over are on the right side in the canonical orientation, but we can rotate the QR code to move them to other edges.

Further Information

All the source code for this post, including the web server, is at code.google.com/p/rsc/source/browse/qr. If you liked this, you might also like Zip Files All The Way Down.

Acknowledgements

Alex Healy pointed out that valid Reed-Solomon encodings are closed under XOR, which is the key to spreading the picture into the error correction pixels. Peter Weinberger has been nothing but gracious about the overuse of his binary likeness. Thanks to both.

Since the biggest problem with transport security is that most sites don't use it, anything that reduces the latency impact of HTTPS is important. Making things faster doesn't just make them faster, it also makes them cheaper and more prevalent. When HTTPS is faster, it'll be used in more places than it would otherwise be.

But, sadly, False Start will be disabled, except for sites doing NPN, in Chrome 20. NPN is a TLS extension that we use to negotiate SPDY, although you don't have to use it to negotiate SPDY, you can advertise http/1.1 if you wish.

False Start was known to cause problems with a very small number of servers and the initial announcement outlined the uncommon scheme that we used to deploy it: we scanned the public Internet and built up a list of problematic sites. That list was built into Chrome and we didn't use False Start for connections to those sites. Over time the list was randomly eroded away and I'd try to address any issues that came up. (Preemptively so in the case of large sites.)

It did work to some extent. Many sites that had problems were fixed and it's a deployment scheme that is worth considering in the future. But it didn't ultimately work well enough for False Start.

Initially we believed that False Start issues were deterministic so long as the TLS Finished and application data records were sent in the same TCP packet. We changed Chrome to do this in the hopes of making False Start issues deterministic. However, we later discovered some HTTPS servers that were still non-deterministically False Start intolerant. I hypothesise that the servers run two threads per connection: one for reading and one for writing. Although the TCP packet was received atomically, thread scheduling could mean that the read thread may or may not be scheduled before the write thread had updated the connection state in response to the Finished.

This non-determinism made False Start intolerance difficult to diagnose and reduced our confidence in the blacklist.

The `servers' with problems were nearly always SSL terminators. These hardware devices terminate SSL connections and proxy unencrypted data to backend HTTP servers. I believe that False Start intolerance is very simple to fix in the code and one vendor suggested that was the case. None the less, of the vendors who did issue an update, most failed to communicate that fact to their customers. (A pattern that has repeated with the BEAST fix.)

One, fairly major, SSL terminator vendor refused to update to fix their False Start intolerance despite problems that their customers were having. I don't believe that this was done in bad faith, but rather a case of something much more mundane along the lines of “the SSL guy left and nobody touches that code any more”. However, it did mean that there was no good answer for their customers who were experiencing problems.

Lastly, it was becoming increasingly clear that we had a bigger problem internationally. Foreign admins have problems finding information on the subject (which is mostly in English) and foreign users have problems reporting bugs because we can't read them. We do have excellent agents in countries who liaise locally but it was still a big issue, and we don't cover every country with them. I also suspect that the distribution of problematic SSL terminators is substantially larger in some countries and that the experience with the US and Europe caused us to underestimate the problem.

In aggregate this lead us to decide that False Start was causing more problems than it was worth. We will now limit it to sites that support the NPN extension. This unfortunately means that it'll be an arcane, unused optimisation for the most part: at least until SPDY takes over the world.

Finite fields are a branch of algebra formally defined in the 1820s, but interest in the topic can be traced back to public sixteenth-century polynomial-solving contests. For the next few centuries, finite fields had little practical value, but all changed in the last fifty years. It turns out that they are useful for many applications in modern computing, such as encryption, data compression, and error correction.

In particular, Reed-Solomon codes are an error-correcting code based on finite fields and used everywhere today. One early significant use was in the Voyager spacecraft: the messages it still sends back today, from the edge of the solar system, are heavily Reed-Solomon encoded so that even if only a small fragment makes it back to Earth, we can still reconstruct the message. Reed-Solomon coding is also used on CDs to withstand scratches, in wireless communications to withstand transmission problems, in QR codes to withstand scanning errors or smudges, in disks to withstand loss of fragments of the media, in high-level storage systems like Google's GFS and BigTable to withstand data loss and also to reduce read latency (the read can complete without waiting for all the responses to arrive).

This post shows how to implement finite field arithmetic efficiently on a computer, and then how to use that to implement Reed-Solomon encoding.

What is a Finite Field?

One way mathematicians study numbers is to abstract away the numbers themselves and focus on the operations. (This is kind of an object-oriented approach to math.) A field is defined as a set F and operators + and · on elements of F that satisfy the following properties:

1. (Closure) For all x, y in F, x+y and x·y are in F.
2. (Associative) For all x, y, z in F, (x+y)+z = x+(y+z) and (x·y)·z = x·(y·z).
3. (Commutative) For all x, y in F, x+y = y+x and x·y = y·x.
4. (Distributive) For all x, y, z in F, x·(y+z) = (x·y)+(x·z).
5. (Identity) There is some element we'll call 0 in F such that for all x in F, x+0 = x. Similarly, there is some element we'll call 1 in F such that for all x in F, x·1 = x.
6. (Inverse) For all x in F, there is some element y in F such that x+y = 0. We write y = −x. Similarly, for all x in F except 0, there is some element y in F such that x·y = 1. We write y = 1/x.

You probably recognize those properties from high school algebra class: the most well-known example of a field is the real numbers, where + is addition and · is multiplication. Other examples are complex numbers and fractions.

A mathematician doesn't have to prove the same results over and over for the real numbers ℝ, the complex numbers ℂ, the fractions ℚ, and so on. Instead, she can prove that a particular result holds for all fields—by assuming only the above properties, called the field axioms. Then she can apply the result by substituting a specific instance like the real numbers for the general idea of a field, the same way that a programmer can implement just one vector(T) and then instantiate it as vector(int), vector(string) and so on.

The integers ℤ are not a field: they lack multiplicative inverses. For example, there is no number that you can multiply by 2 to get 1, no 1/2. Surprisingly, though, the integers modulo any prime p do form a field. For example, the integers modulo 5 are 0, 1, 2, 3, 4. 1+4 = 0 (mod 5), so we say that 4 = −1. Similarly, 2·3 = 1 (mod 5), so we say that 3 = 1/2. After we've proved that ℤ/p is in fact a field, all the results about fields can be applied to ℤ/p. This is very useful: it lets us apply our intuition about the very familiar real numbers to these less familiar numbers. This field is written ℤ/p to emphasize that we're dealing with what's left after subtracting out all the p's. That is, we're dealing with what's left if you assume that p = 0. When you make that assumption, you get math that wraps around at p. These fields are called finite fields because, in contrast to fields like the real numbers, they have a finite number of elements.

For a programmer, the most interesting finite field is ℤ/2, which contains just the integers 0, 1. Addition is the same as XOR, and multiplication is the same as AND. Note that ℤ/p is only a field when p is prime: arithmetic on uint8 variables corresponds to ℤ/256, but it is not a field: there is no 1/2.

What can you do with a field?

The only problem with fields is that there's not a ton you can do with just the field axioms. One thing you can do is build polynomials, which were the original motivation for the mathematicians who pioneered the use of fields in the early 1800s. If we introduce a symbolic variable x, then we can build polynomials whose coefficients are field values. We'll write F[x] to denote the polynomials over x using coefficients from F. For example, if we use the real numbers ℝ as our field, then the polynomials ℝ[x] include x²+1, x+2, and 3.14x² − 2.72x + 1.41. Like integers, these polynomials can be added and multiplied, but not always divided—what is (x²+1)/(x+2)?—so they are not a field. However, remember how the integers are not a field but the integers modulo a prime are a field? The same happens here: polynomials are not a field but polynomials modulo some prime polynomial are.

What does “polynomials modulo some prime polynomial” mean anyway? A prime polynomial is one that cannot be factored, like x²+1 cannot be factored using real numbers. The field ℤ/5 is what you get by doing math under the assumption that 5 = 0; similarly, ℝ[x]/(x²+1) is what you get by doing math under the assumption that x²+1 = 0. Just as ℤ/5 math never deals with numbers as big as 5, ℝ[x]/(x²+1) math never deals with polynomials as big as x²: anything bigger can have some multiple of x²+1 subtracted out again. That is, the polynomials in ℝ[x]/(x²+1) are bounded in size: they have only x¹ and x⁰ (constant) terms. To add polynomials, we just add the coefficients using the addition rule from the coefficient's field, independently, like a vector addition. To multiply polynomials, we have to do the multiplication and then subtract out any x²+1 we can. If we have (ax+b)·(cx+d), we can expand this to (a·c)x² + (b·c+a·d)x + (b·d), and then subtract (a·c)(x²+1) = (a·c)x² + (a·c), producing the final result: (b·c+a·d)x + (b·d−a·c). That might seem like a funny definition of multiplication, but it does in fact obey the field axioms. In fact, this particular field is more familiar than it looks: it is the complex numbers ℂ, but we've written x instead of the usual i. Assuming that x²+1 = 0 is, except for a renaming, the same as defining i² = −1.

Doing all our math modulo a prime polynomial let us take the field of real numbers and produce a field whose elements are pairs of real numbers. We can apply the same trick to take a finite field like ℤ/p and product a field whose elements are fixed-length vectors of elements of ℤ/p. The original ℤ/p has p elements. If we construct (ℤ/p)[x]/f(x), where f(x) is a prime polynomial of degree n (f's maximum x exponent is n), the resulting field has pⁿ elements: all the vectors made up of n elements from ℤ/p. Incredibly, the choice of prime polynomial doesn't matter very much: any two finite fields of size pⁿ have identical structure, even if they give the individual elements different names. Because of this, it makes sense to refer to all the finite fields of size pⁿ as one concept: GF(pⁿ). The GF stands for Galois Field, in honor of Évariste Galois, who was the first to study these. The exact polynomial chosen to produce a particular GF(pⁿ) is an implementation detail.

For a programmer, the most interesting finite fields constructed this way are GF(2ⁿ)—the polynomial extensions of ℤ/2—because the elements of GF(2ⁿ) are bit vectors of length n. As a concrete example, consider (ℤ/2)[x]/(x⁸+x⁴+x³+x+1) . The field has 2⁸ elements: each can be represented by a single byte. The byte with binary digits b₇b₆b₅b₄b₃b₂b₁b₀ represents the polynomial b₇·x⁷ + b₆·x⁶ + b₅·x⁵ + b₄·x⁴ + b₃·x³ + b₂·x² + b₁·x¹ + b₀. To add polynomials, we add coefficients. Since the coefficients are from ℤ/2, adding coefficients means XOR'ing each bit position separately, which is something computer hardware can do easily. Multiplying the polynomials is more difficult, because standard multiplication hardware is based on adding, but we need a multiplication based on XOR'ing. Because the coefficient math wraps at 2, (x²+x)·(x+1) = x³+2x²+x = x³+x, while computer multiplication would choose 110₂* 011₂ = 6 * 3 = 18 = 10010₂. However, it turns out that we can implement this field multiplication with a simple lookup table. In a finite field, there is always at least one element α that can serve as a generator. All the other non-zero elements are powers of α: α, α², α³, and so on. This α is not symbolic like x: it's a specific element. For example, in ℤ/5, we can use α=2: {α, α², α³, α⁴} = {2, 4, 8, 16} = {2, 4, 3, 1}. In GF(2ⁿ) the math is more complex but still works. If we know the generator, then we can, by repeated multiplication, create a lookup table exp[i] = αⁱ and an inverse table log[αⁱ] = i. Multiplication is then just a few table lookups: assuming a and b are non-zero, a·b = exp[log[a]+log[b]]. (That's a normal integer +, to add the exponents, not an XOR.)

Why do we care?

The fact that GF(2ⁿ) can be implemented efficiently on a computer means that we can implement systems based on mathematical theorems without worrying about the usual overflow problems you get when modeling integers or real numbers. To be sure, GF(2ⁿ) behaves quite differently from the integers in many ways, but if all you need is the field axioms, it's good enough, and it eliminates any need to worry about overflow or arbitrary precision calculations. Because of the lookup table, GF(2⁸) is by far the most common choice of field in a computer algorithm. For example, the Advanced Encryption Standard (AES, formerly Rijndael) is built around GF(2⁸) arithmetic, as are nearly all implementations of Reed-Solomon coding.

Code

Let's begin by defining a Field type that will represent the specific instance of GF(2⁸) defined by a given polynomial. The polynomial must be of degree 8, meaning that its binary representation has the 0x100 bit set and no higher bits set.

type Field struct {
    ...
}

Addition is just XOR, no matter what the polynomial is:

// Add returns the sum of x and y in the field.
func (f *Field) Add(x, y byte) byte {
    return x ^ y
}

Multiplication is where things get interesting. If you'd used binary (and Go) in grade school, you might have learned this algorithm for multiplying two numbers (this is not finite field arithmetic):

// Grade-school multiplication in binary: mul returns the product x×y.
func mul(x, y int) int {
    z := 0
    for x > 0 {
        if x&1 != 0 {
            z += y
        }
        x >>= 1
        y <<= 1
    }
    return z
}

The running total z accumulates the product of x and y. The first iteration of this loop adds y to z if the low bit (the 1s digit) of x is 1. The next iteration adds y*2 if the next bit (the 2s digit, now shifted down) of x is 1. The next iteration adds y*4 if the 4s digit is 1, and so on. Each iteration shifts x to the right to chop off the processed digit and shifts y to the left to multiply by two.

To adapt this to multiply in a finite field, we need to make two changes. First, addition is XOR, so we use ^= instead of += to add to z. Second, we need to make the multiply reduce modulo the polynomial. Assuming that the inputs have already been reduced, the only chance of exceeding the polynomial comes from the shift of y. After the shift, then, we can check to see if we've overflowed, and if so, subtract (XOR) out one copy of the polynomial. The finite field version, then, is:

// GF(256) mutiplication: mul returns the product x×y mod poly.
func mul(x, y, poly int) int {
    z := 0
    for x > 0 {
        if x&1 != 0 {
            z ^= y
        }
        x >>= 1
        y <<= 1
        if y&0x100 != 0 {
            y ^= poly
        }
    }
    return z
}

We might want to do a lot of multiplication, though, and this loop is too slow. There aren't that many inputs—only 2⁸×2⁸ of them—so one option is to build a 64kB lookup table. With some cleverness, we can build a smaller lookup table. In the NewField constructor, we can compute α⁰, α¹, α², ..., record the sequence in an exp array, and record the inverse in a log array. Then we can reduce multiplication to addition of logarithms, like a slide rule does.

// A Field represents an instance of GF(256) defined by a specific polynomial.
type Field struct {
    log [256]byte // log[0] is unused
    exp [510]byte
}

// NewField returns a new field corresponding to
// the given polynomial and generator.
func NewField(poly, α int) *Field {
    var f Field
    x := 1
    for i := 0; i < 255; i++ {
        f.exp[i] = byte(x)
        f.exp[i+255] = byte(x)
        f.log[x] = byte(i)
        x = mul(x, α, poly)
    }
    f.log[0] = 255
    return &f
}

The values of the exp function cycle with period 255 (not 256, because 0 is impossible): α²⁵⁵ = 1. The straightforward way to implement Exp, then, is to look up the entry given by the exponent modulo 255.

// Exp returns the base 2 exponential of e in the field.
// If e < 0, Exp returns 0.
func (f *Field) Exp(e int) byte {
    if e < 0 {
        return 0
    }
    return f.exp[e%255]
}

Log is an even simpler table lookup, because the input is only a byte:

// Log returns the base 2 logarithm of x in the field.
// If x == 0, Log returns -1.
func (f *Field) Log(x byte) int {
    if x == 0 {
        return -1
    }
    return int(f.log[x])
}

Mul is where things get interesting. The obvious implementation of Mul is exp[(log[x]+log[y])%255], but if we double the exp array, so that it is 510 elements long, we can drop the relatively expensive %255:

// Mul returns the product of x and y in the field.
func (f *Field) Mul(x, y byte) byte {
    if x == 0 || y == 0 {
        return 0
    }
    return f.exp[int(f.log[x])+int(f.log[y])]
}

Inv returns the multiplicative inverse, 1/x. We don't implement divide: instead of x/y, we can use x · 1/y.

// Inv returns the multiplicative inverse of x in the field.
// If x == 0, Inv returns 0.
func (f *Field) Inv(x byte) byte {
    if x == 0 {
        return 0
    }
    return f.exp[255-f.log[x]]
}

Reed-Solomon Coding

In 1960, Irving Reed and Gustave Solomon proposed a way to build an error-correcting code using GF(2ⁿ). The method interpreted the m message bits as coefficients of a polynomial f of degree m−1 over GF(2ⁿ) and then sent f(0), f(α), f(α²), f(α³), ..., f(1). Any m of these, if received correctly, suffice to reconstruct f, and then the message can be read off the coefficients. To find a correct set, Reed and Solomon's algorithm constructed the f corresponding to every possible subset of m received values and then chose the most common one in a majority vote. As long as no more than (2ⁿ−m)/2 values were corrupted in transit, the majority will agree on the correct value of f. This decoding algorithm is very expensive, too expensive for long messages. As a result, the Reed-Solomon approach sat unused for almost a decade. In 1969, however, Elwyn Berlekamp and James Massey proposed a variant with an efficient decoding algorithm. In the 1980s, Berlekamp and Lloyd Welch developed an even more efficient decoding algorithm that is the one typically used today. These decoding algorithms are based on systems of equations far too complex to explain here; in this post, we will only deal with encoding. (I can't keep the decoding algorithms straight in my head for more than an hour or two at a time, much less explain them in finite space.)

In Reed-Solomon encoding as it is practiced today, the choice of finite field F and generator α defines a generator polynomial g(x) = (x−1)(x−α)(x−α²)...(x−α^n−m). To encode a message m, the message is taken as the top coefficients of a degree n polynomial f(x) = m₀xⁿ⁻¹+m₁xⁿ⁻²+...+m_mx^n−m−1. Then that polynomial can be divided by g to produce the remainder polynomial r(x), the unique polynomial of degree less than n−m such that f(x) − r(x) is a multiple of g(x). Since r(x) is of degree less than n−m, subtracting r(x) does not affect any of the message coefficients, just the lower terms, so the polynomial f(x) − r(x) (= f(x) + r(x)) is taken as the encoded message. All encoded messages, then, are multiples of g(x). On the receiving end, the decoder does some magic to figure out the simplest changes needed to make the received polynomial a multiple of g(x) and then reads the message out of the top coefficients.

While decoding is difficult, encoding is easy: the first m bytes are the message itself, followed by the c bytes defining the remainder of m·x^c/g(x). We can also check whether we received an error-free message by checking whether the concatenation defines a polynomial that is a multiple of g(x).

Code

The Reed-Solomon encoding problem is this: given a message m interpreted as a polynomial m(x), compute the error correction bytes, m(x)·x^c mod g(x).

The grade-school division algorithm works well here. If we fill in p with m(x)·x^c (m followed by c zero bytes), then we can replace p by the remainder by iteratively subtracting out multiples of the generator polynomial g.

for i := 0; i < len(m); i++ {
    k := f.Mul(p[i], f.Inv(gen[0]))  // k = pi / g0
    // p -= k·g
    for j, g := range gen {
        p[i+j] = f.Add(p[i+j], f.Mul(k, g))
    }
}

This implementation is correct but can be made more efficient. If you want to try, run:

go get code.google.com/p/rsc/gf256
go test code.google.com/p/rsc/gf256 -bench Blog

That benchmark measures the speed of the implementation in blog_test.go, which looks like the above. Optimize away, or follow along.

There's definitely room for improvement:

$ go test code.google.com/p/rsc/gf256 -bench ECC
PASS
BenchmarkBlogECC   500000   7031 ns/op   4.55 MB/s
BenchmarkECC      1000000   1332 ns/op  24.02 MB/s

To start, we can expand the definitions of Add and Mul. The Go compiler's inliner would do this for us; the win here is not the inlining but the simplifications it will enable us to make.

for i := 0; i < len(m); i++ {
    if p[i] == 0 {
        continue
    }
    k := f.exp[f.log[p[i]] + 255 - f.log[gen[0]]]  // k = pi / g0
    // p -= k·g
    for j, g := range gen {
        p[i+j] ^= f.exp[f.log[k] + f.log[g]]
    }
}

(The implementation handles p[i] == 0 specially because 0 has no log.)

The first thing to note is that we compute k but then use f.log[k] repeatedly. Computing the log will avoid that memory access, and it is cheaper: we just take out the f.exp[...] lookup on the line that computes k. This is safe because p[i] is non-zero, so k must be non-zero.

for i := 0; i < len(m); i++ {
    if p[i] == 0 {
        continue
    }
    lk := f.log[p[i]] + 255 - f.log[gen[0]]  // k = pi / g0
    // p -= k·g
    for j, g := range gen {
        p[i+j] ^= f.exp[lk + f.log[g]]
    }
}

Next, note that we repeatedly compute f.log[g]. Instead of doing that, we can iterate lgen—an array holding the logs of the coefficients—instead of gen. We'll have to handle zero somehow: let's say that the array has an entry set to 255 when the corresponding gen value is zero.

for i := 0; i < len(m); i++ {
    if p[i] == 0 {
        continue
    }
    lk := f.log[p[i]] + 255 - f.log[gen[0]]  // k = pi / g0
    // p -= k·g
    for j, lg := range lgen {
        if lg != 255 {
            p[i+j] ^= f.exp[lk + lg]
        }
    }
}

Next, we can notice that since the generator is defined as

the first coefficient, g₀, is always 1! That means we can simplify the k = p_i / g calculation to just k = p_i. Also, we can drop the first element of lgen and its subtraction, as long as we ignore the high bytes in the result (we know they're supposed to be zero anyway).

for i := 0; i < len(m); i++ {
    if p[i] == 0 {
        continue
    }
    lk := f.log[p[i]]
    // p -= k·g
    for j, lg := range lgen {
        if lg != 255 {
            p[i+1+j] ^= f.exp[lk + lg]
        }
    }
}

The inner loop, which is where we spend all our time, has two additions by loop-invariant constants: i+1+j and lk+lg. The i+1 and lk do not change on each iteration. We can avoid those additions by reslicing the arrays outside the loop:

for i := 0; i < len(m); i++ {
    if p[i] == 0 {
        continue
    }
    lk := f.log[p[i]]
    // p -= k·g
    q := p[i+1:]
    exp := f.exp[lk:]
    for j, lg := range lgen {
        if lg != 255 {
            q[j] ^= exp[lg]
        }
    }
}

As one final trick, we can replace p[i] by a range variable. The Go compiler does not yet use loop invariants to eliminate bounds checks, but it does eliminate bounds checks in the implicit indexing done by a range loop.

for i, pi := range p {
    if i == len(m) {
        break
    }
    if pi == 0 {
        continue
    }
    // p -= k·g
    q := p[i+1:]
    exp := f.exp[f.log[pi]:]
    for j, lg := range lgen {
        if lg != 255 {
            q[j] ^= exp[lg]
        }
    }
}

The code is in context in gf256.go.

Summary

We started with single bits 0 and 1. From those we constructed 8-bit polynomials—the elements of GF(2⁸)—with overflow-free, easy-to-implement mathematical operations. From there we moved on to Reed-Solomon coding, which constructs its own polynomials built using elements of GF(2⁸) as coefficients. That is, each Reed-Solomon message is interpreted as a polynomial, and each coefficient in that polynomial is itself a smaller polynomial.

Now that we know how to create Reed-Solomon encodings, the next post will look at some fun we can have with them.

i = (data[0]<<0) | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);

i = (data[3]<<0) | (data[2]<<8) | (data[1]<<16) | (data[0]<<24);

i = *((int*)data);

#ifdef BIG_ENDIAN

/* swap the bytes */

i = ((i&0xFF)<<24) | (((i>>8)&0xFF)<<16) | (((i>>16)&0xFF)<<8) | (((i>>24)&0xFF)<<0);

#endif

• applog: Logging with multiple levels, caller details in debug and critical situations and pluggable own logging behavior.
• asserts: Tests which can be used inside of unit tests or at runtime.
• cache: Cache values which will be refreshed on demand.
• cells: A framework for event and behavior based applications.
• identifier: Generate UUIDs and other identifiers.
• mapreduce: Use Googles great algorthim for data processing and aggregating.
• markup: A simple markup language as an alternative to XML.
• monitoring: Keep track of the performance, stay-set variables and dynamically retrieved statuses.
• numerics: Some numerical types, intended to use them e.g. for statistical problems.
• redis: A powerful client for the Redis database.
• sort: A parallel quicksort to use the power of multiple cores.
• state: A generic finite state machine.
• time: Functions to work with times and an internal crontab server.
• util: Some more smaller utilities.
• web: A lean web framework. Especially the combination of REST and JSON is supported.

A hash function for a particular hash table should always be deterministic, right? At least, that's what I thought until a few weeks ago, when I was able to fix a performance problem by calling rand inside a hash function.

A hash table is only as good as its hash function, which ideally satisfies two properties for any key pair k₁, k₂:

1. If k₁ == k₂, hash(k₁) == hash(k₂).
2. If k₁ != k₂, it should be likely that hash(k₁) != hash(k₂).

Normally, following rule 1 would prohibit the use of random bits while computing the hash, because if you pass in the same key again, you'd use different random bits and get a different hash value. That's why the fact that I got to call rand in a hash function is so surprising.

If the hash function violates rule 1, your hash table just breaks: you can't find things you put in, because you are looking in the wrong places. If the hash function satisfies rule 1 but violates rule 2 (for example, “return 42”), the hash table will be slow due to the large number of hash collisions. You'll still be able to find the things you put in, but you might as well be using a list.

The phrasing of rule 1 is very important. It is not sufficient to say simply “hash(k₁) == hash(k₁)”, because that does not take into account the definition of equality of keys. If you are building a hash table with case-insensitive, case-preserving string keys, then “HELLO” and “hello” need to hash to the same value. In fact, “hash(k₁) == hash(k₁)” is not even strictly necessary. How could it not be necessary? By reversing rule 1, hash(k₁) and hash(k₁) can be unequal if k₁ != k₁, that is, if k₁ does not equal itself.

How can that happen? It happens if k₁ is the floating-point value NaN (not-a-number), which by convention is not equal to anything, not even itself.

Okay, but why bother? Well, remember rule 2. Since NaN != NaN, it should be likely that hash(NaN) != hash(NaN), or else the hash table will have bad performance. This is very strange: the same input is hashed twice, and we're supposed to (at least be likely to) return different hash values. Since the inputs are identical, we need a source of external entropy, like rand.

What if you don't? You get hash tables that don't perform very well if someone can manage to trick you into storing things under NaN repeatedly:

$ cat nan.py
#!/usr/bin/python
import timeit
def build(n):
	m = {}
	for i in range(n):
		m[float("nan")] = 1
n = 1
for i in range(20):
	print "%6d %10.6f" % (n, timeit.timeit('build('+str(n)+')',
	    'from __main__ import build', number=1))
	n *= 2

$ python nan.py
     1   0.000006
     2   0.000004
     4   0.000004
     8   0.000008
    16   0.000011
    32   0.000028
    64   0.000072
   128   0.000239
   256   0.000840
   512   0.003339
  1024   0.012612
  2048   0.050331
  4096   0.200965
  8192   1.032596
 16384   4.657481
 32768  22.758963
 65536  91.899054
$

The behavior here is quadratic: double the input size and the run time quadruples. You can run the equivalent Go program on the Go playground. It has the NaN fix and runs in linear time. (On the playground, wall time stands still, but you can see that it's executing in far less than 100s of seconds. Run it locally for actual timing.)

Now, you could argue that putting a NaN in a hash table is a dumb idea, and also that treating NaN != NaN in a hash table is also a dumb idea, and you'd be right on both counts.

But the alternatives are worse:

• If you define that NaN is equal to itself during hash key comparisons, now you have a second parallel definition of equality, to handle NaNs inside structs and so on, only used for map lookups. Languages typically have too many equality operators anyway; introducing a new one for this special case seems unwise.
• If you define that NaN cannot appear as a hash table key, then you have a similar problem: you need to build up logic to test for invalid keys such as NaNs inside structs or arrays, and then you have to deal with the fact that your hash table might return an error or throw an exception when inserting values under certain keys.

The most consistent thing to do is to accept the implications of NaN != NaN: m[NaN] = 1 always creates a new hash table element (since the key is unequal to any existing entry), reading m[NaN] never finds any data (same reason), and iterating over the hash table yields each of the inserted NaN entries.

Behaviors surrounding NaN are always surprising, but if NaN != NaN elsewhere, the least surprising thing you can do is make your hash tables respect that. To do that well, it needs to be likely that hash(NaN) != hash(NaN). And you probably already have a custom floating-point hash function so that +0 and −0 are treated as the same value. Go ahead, call rand for NaN.

(Note: this is different from the hash table performance problem that was circulating in December 2011. In that case, the predictability of collisions on ordinary data was solved by making each different table use a randomly chosen hash function; there's no randomness inside the function itself.)

Go言語のVersion 1 がとうとうリリースされました。

http://blog.golang.org/2012/03/go-version-1-is-released.html

The news, if you hadn’t heard. :)  It’s a big thing with me because I’ve put so much time into using it—well, mostly playing with it.  I do write and maintain some Go programs for work, but most of my time with Go has been spent contributing solutions to Rosetta Code.  I’ve contributed hundreds of Go solutions over the last year or so, and Go has been in the top 10 languages there for some time now.  Recently I’ve tried to review all of the solutions to update them to Go 1, and I’m happy to announce that they (almost) all work with Go 1 now.

I wish I could announce that it represents a large body of idiomatic Go code, available as reference solutions common programming tasks, but I’m afraid it’s not.  Firstly, I’m not sure how idiomatic my code is.  I’ve worked mostly in isolation, and my code almost certainly displays my idiosyncrasies as much as it displays accepted idioms.  Secondly of course, is the nature of of the RC site, which is more a wonderland than reference library.

Still, I’d like to invite people to come and visit.  Browse the existing Go solutions and be amused or enlightened, hopefully both.  But then I’d really like to encourage people to make improvements as they can.  That’s the nature of a wiki, and as I said, since such a large fraction of the Go code is mine, there is certainly much room for the code to be improved.

Next there is the list of existing RC tasks with no Go solution yet.  Most of these are tasks that awkward for me because I don’t have a computer, and can’t freely do things like install software on the computers I do have access to.  If you have or can install up-to-date libraries and software on your computer, some of these tasks should be easy!  Please browse the list and contribute any solutions you can.  A few of them are simply tasks for which I don’t have the knowledge.  For example the HTTP task seemed simple enough, but I don’t know enough to do the HTTPS task.

Finally, if you really enjoy the site, consider contributing a new task that you feel really shows off some feature of Go.  I’ve added just a few, but probably still be designed are some great tasks illuminating interfaces, concurrency, and the varied capabilities of the Go standard package library.

The image and image/color packages define a number of types: color.Color and color.Model describe colors, image.Point and image.Rectangle describe basic 2-D geometry, and image.Image brings the two concepts together to represent a rectangular grid of colors. A separate article covers image composition with the image/draw package.

Colors and Color Models

Color is an interface that defines the minimal method set of any type that can be considered a color: one that can be converted to red, green, blue and alpha values. The conversion may be lossy, such as converting from CMYK or YCbCr color spaces.

type Color interface {
    // RGBA returns the alpha-premultiplied red, green, blue and alpha values
    // for the color. Each value ranges within [0, 0xFFFF], but is represented
    // by a uint32 so that multiplying by a blend factor up to 0xFFFF will not
    // overflow.
    RGBA() (r, g, b, a uint32)
}

There are three important subtleties about the return values. First, the red, green and blue are alpha-premultiplied: a fully saturated red that is also 25% transparent is represented by RGBA returning a 75% r. Second, the channels have a 16-bit effective range: 100% red is represented by RGBA returning an r of 65535, not 255, so that converting from CMYK or YCbCr is not as lossy. Third, the type returned is uint32, even though the maximum value is 65535, to guarantee that multiplying two values together won't overflow. Such multiplications occur when blending two colors according to an alpha mask from a third color, in the style of Porter and Duff'sclassic algebra:

dstr, dstg, dstb, dsta := dst.RGBA()
srcr, srcg, srcb, srca := src.RGBA()
_, _, _, m := mask.RGBA()
const M = 1<<16 - 1
// The resultant red value is a blend of dstr and srcr, and ranges in [0, M].
// The calculation for green, blue and alpha is similar.
dstr = (dstr*(M-m) + srcr*m) / M

The last line of that code snippet would have been more complicated if we worked with non-alpha-premultiplied colors, which is why Color uses alpha-premultiplied values.

The image/color package also defines a number of concrete types that implement the Color interface. For example, RGBA is a struct that represents the classic "8 bits per channel" color.

type RGBA struct {
    R, G, B, A uint8
}

Note that the R field of an RGBA is an 8-bit alpha-premultiplied color in the range [0, 255]. RGBA satisfies the Color interface by multiplying that value by 0x101 to generate a 16-bit alpha-premultiplied color in the range [0, 65535]. Similarly, the NRGBA struct type represents an 8-bit non-alpha-premultiplied color, as used by the PNG image format. When manipulating an NRGBA's fields directly, the values are non-alpha-premultiplied, but when calling the RGBA method, the return values are alpha-premultiplied.

A Model is simply something that can convert Colors to other Colors, possibly lossily. For example, the GrayModel can convert any Color to a desaturated Gray. A Palette can convert any Color to one from a limited palette.

type Model interface {
    Convert(c Color) Color
}

type Palette []Color

Points and Rectangles

A Point is an (x, y) co-ordinate on the integer grid, with axes increasing right and down. It is neither a pixel nor a grid square. A Point has no intrinsic width, height or color, but the visualizations below use a small colored square.

type Point struct {
    X, Y int
}

    p := image.Point{2, 1}

A Rectangle is an axis-aligned rectangle on the integer grid, defined by its top-left and bottom-right Point. A Rectangle also has no intrinsic color, but the visualizations below outline rectangles with a thin colored line, and call out their Min and Max Points.

type Rectangle struct {
    Min, Max Point
}

For convenience, image.Rect(x0, y0, x1, y1) is equivalent to image.Rectangle{image.Point{x0, y0}, image.Point{x1, y1}}, but is much easier to type.

A Rectangle is inclusive at the top-left and exclusive at the bottom-right. For a Point p and a Rectangle r, p.In(r) if and only if r.Min.X <= p.X && p.X < r.Max.X, and similarly for Y. This is analagous to how a slice s[i0:i1] is inclusive at the low end and exclusive at the high end. (Unlike arrays and slices, a Rectangle often has a non-zero origin.)

    r := image.Rect(2, 1, 5, 5)
    // Dx and Dy return a rectangle's width and height.
    fmt.Println(r.Dx(), r.Dy(), image.Pt(0, 0).In(r)) // prints 3 4 false

Adding a Point to a Rectangle translates the Rectangle. Points and Rectangles are not restricted to be in the bottom-right quadrant.

    r := image.Rect(2, 1, 5, 5).Add(image.Pt(-4, -2))
    fmt.Println(r.Dx(), r.Dy(), image.Pt(0, 0).In(r)) // prints 3 4 true

Intersecting two Rectangles yields another Rectangle, which may be empty.

    r := image.Rect(0, 0, 4, 3).Intersect(image.Rect(2, 2, 5, 5))
    // Size returns a rectangle's width and height, as a Point.
    fmt.Printf("%#v\n", r.Size()) // prints image.Point{X:2, Y:1}

Points and Rectangles are passed and returned by value. A function that takes a Rectangle argument will be as efficient as a function that takes two Point arguments, or four int arguments.

Images

An Image maps every grid square in a Rectangle to a Color from a Model. "The pixel at (x, y)" refers to the color of the grid square defined by the points (x, y), (x+1, y), (x+1, y+1) and (x, y+1).

type Image interface {
    // ColorModel returns the Image's color model.
    ColorModel() color.Model
    // Bounds returns the domain for which At can return non-zero color.
    // The bounds do not necessarily contain the point (0, 0).
    Bounds() Rectangle
    // At returns the color of the pixel at (x, y).
    // At(Bounds().Min.X, Bounds().Min.Y) returns the upper-left pixel of the grid.
    // At(Bounds().Max.X-1, Bounds().Max.Y-1) returns the lower-right one.
    At(x, y int) color.Color
}

A common mistake is assuming that an Image's bounds start at (0, 0). For example, an animated GIF contains a sequence of Images, and each Image after the first typically only holds pixel data for the area that changed, and that area doesn't necessarily start at (0, 0). The correct way to iterate over an Image m's pixels looks like:

b := m.Bounds()
for y := b.Min.Y; y < b.Max.Y; y++ {
 for x := b.Min.X; y < b.Max.X; x++ {
  doStuffWith(m.At(x, y))
 }
}

Image implementations do not have to be based on an in-memory slice of pixel data. For example, a Uniform is an Image of enormous bounds and uniform color, whose in-memory representation is simply that color.

type Uniform struct {
    C color.Color
}

Typically, though, programs will want an image based on a slice. Struct types like RGBA and Gray (which other packages refer to as image.RGBA and image.Gray) hold slices of pixel data and implement the Image interface.

type RGBA struct {
    // Pix holds the image's pixels, in R, G, B, A order. The pixel at
    // (x, y) starts at Pix[(y-Rect.Min.Y)*Stride + (x-Rect.Min.X)*4].
    Pix []uint8
    // Stride is the Pix stride (in bytes) between vertically adjacent pixels.
    Stride int
    // Rect is the image's bounds.
    Rect Rectangle
}

These types also provide a Set(x, y int, c color.Color) method that allows modifying the image one pixel at a time.

    m := image.NewRGBA(image.Rect(0, 0, 640, 480))
    m.Set(5, 5, color.RGBA{255, 0, 0, 255})

If you're reading or writing a lot of pixel data, it can be more efficient, but more complicated, to access these struct type's Pix field directly.

The slice-based Image implementations also provide a SubImage method, which returns an Image backed by the same array. Modifying the pixels of a sub-image will affect the pixels of the original image, analagous to how modifying the contents of a sub-slice s[i0:i1] will affect the contents of the original slice s.

    m0 := image.NewRGBA(image.Rect(0, 0, 8, 5))
    m1 := m0.SubImage(image.Rect(1, 2, 5, 5)).(*image.RGBA)
    fmt.Println(m0.Bounds().Dx(), m1.Bounds().Dx()) // prints 8, 4
    fmt.Println(m0.Stride == m1.Stride)             // prints true

For low-level code that works on an image's Pix field, be aware that ranging over Pix can affect pixels outside an image's bounds. In the example above, the pixels covered by m1.Pix are shaded in blue. Higher-level code, such as the At and Setmethods or the image/draw package, will clip their operations to the image's bounds.

Image Formats

The standard package library supports a number of common image formats, such as GIF, JPEG and PNG. If you know the format of a source image file, you can decode from an io.Reader directly.

import (
 "image/jpeg"
 "image/png"
 "io"
)

// convertJPEGToPNG converts from JPEG to PNG.
func convertJPEGToPNG(w io.Writer, r io.Reader) error {
 img, err := jpeg.Decode(r)
 if err != nil {
  return err
 }
 return png.Encode(w, img)
}

If you have image data of unknown format, the image.Decode function can detect the format. The set of recognized formats is constructed at run time and is not limited to those in the standard package library. An image format package typically registers its format in an init function, and the main package will "underscore import" such a package solely for the side effect of format registration.

import (
 "image"
 "image/png"
 "io"

 _ "code.google.com/p/vp8-go/webp"
 _ "image/jpeg"
)

// convertToPNG converts from any recognized format to PNG.
func convertToPNG(w io.Writer, r io.Reader) error {
 img, _, err := image.Decode(r)
 if err != nil {
  return err
 }
 return png.Encode(w, img)
}

Package image/draw defines only one operation: drawing a source image onto a destination image, through an optional mask image. This one operation is surprisingly versatile and can perform a number of common image manipulation tasks elegantly and efficiently.

Composition is performed pixel by pixel in the style of the Plan 9 graphics library and the X Render extension. The model is based on the classic "Compositing Digital Images" paper by Porter and Duff, with an additional mask parameter: dst = (src IN mask) OP dst. For a fully opaque mask, this reduces to the original Porter-Duff formula: dst = src OP dst. In Go, a nil mask image is equivalent to an infinitely sized, fully opaque mask image.

The Porter-Duff paper presented 12 different composition operators, but with an explicit mask, only 2 of these are needed in practice: source-over-destination and source. In Go, these operators are represented by the Over and Src constants. The Over operator performs the natural layering of a source image over a destination image: the change to the destination image is smaller where the source (after masking) is more transparent (that is, has lower alpha). The Src operator merely copies the source (after masking) with no regard for the destination image's original content. For fully opaque source and mask images, the two operators produce the same output, but the Src operator is usually faster.

Geometric Alignment

Composition requires associating destination pixels with source and mask pixels. Obviously, this requires destination, source and mask images, and a composition operator, but it also requires specifying what rectangle of each image to use. Not every drawing should write to the entire destination: when updating an animating image, it is more efficient to only draw the parts of the image that have changed. Not every drawing should read from the entire source: when using a sprite that combines many small images into one large one, only a part of the image is needed. Not every drawing should read from the entire mask: a mask image that collects a font's glyphs is similar to a sprite. Thus, drawing also needs to know three rectangles, one for each image. Since each rectangle has the same width and height, it suffices to pass a destination rectangle `r` and two points sp and mp: the source rectangle is equal to rtranslated so that r.Min in the destination image aligns with sp in the source image, and similarly for mp. The effective rectangle is also clipped to each image's bounds in their respective co-ordinate space.

The DrawMaskfunction takes seven arguments, but an explicit mask and mask-point are usually unnecessary, so the Draw function takes five:

// Draw calls DrawMask with a nil mask.
func Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point, op Op)
func DrawMask(dst Image, r image.Rectangle, src image.Image, sp image.Point,
 mask image.Image, mp image.Point, op Op)

The destination image must be mutable, so the image/draw package defines a draw.Imageinterface which has a Set method.

type Image interface {
    image.Image
    Set(x, y int, c color.Color)
}

Filling a Rectangle

To fill a rectangle with a solid color, use an image.Uniformsource. The ColorImage type re-interprets a Color as a practically infinite-sized Image of that color. For those familiar with the design of Plan 9's draw library, there is no need for an explicit "repeat bit" in Go's slice-based image types; the concept is subsumed by Uniform.

    // image.ZP is the zero point -- the origin.
    draw.Draw(dst, r, &image.Uniform{c}, image.ZP, draw.Src)

To initialize a new image to all-blue:

    m := image.NewRGBA(image.Rect(0, 0, 640, 480))
    blue := color.RGBA{0, 0, 255, 255}
    draw.Draw(m, m.Bounds(), &image.Uniform{blue}, image.ZP, draw.Src)

To reset an image to transparent (or black, if the destination image's color model cannot represent transparency), use image.Transparent, which is an image.Uniform:

    draw.Draw(m, m.Bounds(), image.Transparent, image.ZP, draw.Src)

Copying an Image

To copy from a rectangle sr in the source image to a rectangle starting at a point dp in the destination, convert the source rectangle into the destination image's co-ordinate space:

    r := image.Rectangle{dp, dp.Add(sr.Size())}
    draw.Draw(dst, r, src, sr.Min, draw.Src)

Alternatively:

    r := sr.Sub(sr.Min).Add(dp)
    draw.Draw(dst, r, src, sr.Min, draw.Src)

To copy the entire source image, use sr = src.Bounds().

Scrolling an Image

Scrolling an image is just copying an image to itself, with different destination and source rectangles. Overlapping destination and source images are perfectly valid, just as Go's built-in copy function can handle overlapping destination and source slices. To scroll an image m by 20 pixels:

    b := m.Bounds()
    p := image.Pt(0, 20)
    // Note that even though the second argument is b,
    // the effective rectangle is smaller due to clipping.
    draw.Draw(m, b, m, b.Min.Add(p), draw.Src)
    dirtyRect := b.Intersect(image.Rect(b.Min.X, b.Max.Y-20, b.Max.X, b.Max.Y))

Converting an Image to RGBA

The result of decoding an image format might not be an image.RGBA: decoding a GIF results in an image.Paletted, decoding a JPEG results in a ycbcr.YCbCr, and the result of decoding a PNG depends on the image data. To convert any image to an image.RGBA:

    b := src.Bounds()
    m := image.NewRGBA(image.Rect(0, 0, b.Dx(), b.Dy()))
    draw.Draw(m, m.Bounds(), src, b.Min, draw.Src)

Drawing Through a Mask

To draw an image through a circular mask with center p and radius r:

type circle struct {
    p image.Point
    r int
}

func (c *circle) ColorModel() color.Model {
    return color.AlphaModel
}

func (c *circle) Bounds() image.Rectangle {
    return image.Rect(c.p.X-c.r, c.p.Y-c.r, c.p.X+c.r, c.p.Y+c.r)
}

func (c *circle) At(x, y int) color.Color {
    xx, yy, rr := float64(x-c.p.X)+0.5, float64(y-c.p.Y)+0.5, float64(c.r)
    if xx*xx+yy*yy < rr*rr {
        return color.Alpha{255}
    }
    return color.Alpha{0}
}

    draw.DrawMask(dst, dst.Bounds(), src, image.ZP, &circle{p, r}, image.ZP, draw.Over)

Drawing Font Glyphs

To draw a font glyph in blue starting from a point p, draw with an image.ColorImage source and an image.Alpha mask. For simplicity, we aren't performing any sub-pixel positioning or rendering, or correcting for a font's height above a baseline.

    src := &image.Uniform{color.RGBA{0, 0, 255, 255}}
    mask := theGlyphImageForAFont()
    mr := theBoundsFor(glyphIndex)
    draw.DrawMask(dst, mr.Sub(mr.Min).Add(p), src, image.ZP, mask, mr.Min, draw.Over)

Performance

The image/draw package implementation demonstrates how to provide an image manipulation function that is both general purpose, yet efficient for common cases. The DrawMask function takes arguments of interface types, but immediately makes type assertions that its arguments are of specific struct types, corresponding to common operations like drawing one image.RGBA image onto another, or drawing an image.Alpha mask (such as a font glyph) onto an image.RGBA image. If a type assertion succeeds, that type information is used to run a specialized implementation of the general algorithm. If the assertions fail, the fallback code path uses the generic At and Set methods. The fast-paths are purely a performance optimization; the resultant destination image is the same either way. In practice, only a small number of special cases are necessary to support typical applications.

The Go project takes documentation seriously. Documentation is a huge part of making software accessible and maintainable. Of course it must be well-written and accurate, but it also must be easy to write and to maintain. Ideally, it should be coupled to the code itself so the documentation evolves along with the code. The easier it is for programmers to produce good documentation, the better for everyone.

To that end, we have developed the godoc documentation tool. This article describes godoc's approach to documentation, and explains how you can use our conventions and tools to write good documentation for your own projects.

Godoc parses Go source code - including comments - and produces documentation as HTML or plain text. The end result is documentation tightly coupled with the code it documents. For example, through godoc's web interface you can navigate from a function's documentation to its implementation with one click.

Godoc is conceptually related to Python's Docstring and Java's Javadoc, but its design is simpler. The comments read by godoc are not language constructs (as with Docstring) nor must they have their own machine-readable syntax (as with Javadoc). Godoc comments are just good comments, the sort you would want to read even if godoc didn't exist.

The convention is simple: to document a type, variable, constant, function, or even a package, write a regular comment directly preceding its declaration, with no intervening blank line. Godoc will then present that comment as text alongside the item it documents. For example, this is the documentation for the fmt package's Fprintfunction:

// Fprint formats using the default formats for its operands and writes to w.
// Spaces are added between operands when neither is a string.
// It returns the number of bytes written and any write error encountered.
func Fprint(w io.Writer, a ...interface{}) (n int, err error) {

Notice this comment is a complete sentence that begins with the name of the element it describes. This important convention allows us to generate documentation in a variety of formats, from plain text to HTML to UNIX man pages, and makes it read better when tools truncate it for brevity, such as when they extract the first line or sentence.

Comments on package declarations should provide general package documentation. These comments can be short, like the sortpackage's brief description:

// Package sort provides primitives for sorting slices and user-defined
// collections.
package sort

They can also be detailed like the gob package's overview. That package uses another convention for packages that need large amounts of introductory documentation: the package comment is placed in its own file, doc.go, which contains only those comments and a package clause.

When writing package comments of any size, keep in mind that their first sentence will appear in godoc's package list.

Comments that are not adjacent to a top-level declaration are omitted from godoc's output, with one notable exception. Top-level comments that begin with the word "BUG(who)” are recognized as known bugs, and included in the "Bugs” section of the package documentation. The "who” part should be the user name of someone who could provide more information. For example, this is a known issue from the bytes package:

// BUG(r): The rule Title uses for word boundaries does not handle Unicode punctuation properly.

Godoc treats executable commands somewhat differently. Instead of inspecting the command source code, it looks for a Go source file belonging to the special package "documentation”. The comment on the "package documentation” clause is used as the command's documentation. For example, see the godoc documentation and its corresponding doc.go file.

There are a few formatting rules that Godoc uses when converting comments to HTML:

• Subsequent lines of text are considered part of the same paragraph; you must leave a blank line to separate paragraphs.
• Pre-formatted text must be indented relative to the surrounding comment text (see gob's doc.go for an example).
• URLs will be converted to HTML links; no special markup is necessary.

Note that none of these rules requires you to do anything out of the ordinary.

In fact, the best thing about godoc's minimal approach is how easy it is to use. As a result, a lot of Go code, including all of the standard library, already follows the conventions.

Your own code can present good documentation just by having comments as described above. Any Go packages installed inside $GOROOT/src/pkgand any GOPATH work spaces will already be accessible via godoc's command-line and HTTP interfaces, and you can specify additional paths for indexing via the -path flag or just by running "godoc ."in the source directory. See the godoc documentationfor more details.

Reflection in computing is the ability of a program to examine its own structure, particularly through types; it's a form of metaprogramming. It's also a great source of confusion.

In this article we attempt to clarify things by explaining how reflection works in Go. Each language's reflection model is different (and many languages don't support it at all), but this article is about Go, so for the rest of this article the word "reflection" should be taken to mean "reflection in Go".

Types and interfaces

Because reflection builds on the type system, let's start with a refresher about types in Go.

Go is statically typed. Every variable has a static type, that is, exactly one type known and fixed at compile time: int, float32, *MyType, []byte, and so on. If we declare

type MyInt int

var i int
var j MyInt

then i has type int and jhas type MyInt. The variables i and j have distinct static types and, although they have the same underlying type, they cannot be assigned to one another without a conversion.

One important category of type is interface types, which represent fixed sets of methods. An interface variable can store any concrete (non-interface) value as long as that value implements the interface's methods. A well-known pair of examples is io.Reader and io.Writer, the types Reader and Writer from the io package:

// Reader is the interface that wraps the basic Read method.
type Reader interface {
    Read(p []byte) (n int, err error)
}

// Writer is the interface that wraps the basic Write method.
type Writer interface {
    Write(p []byte) (n int, err error)
}

Any type that implements a Read (or Write) method with this signature is said to implement io.Reader (or io.Writer). For the purposes of this discussion, that means that a variable of type io.Reader can hold any value whose type has a Read method:

    var r io.Reader
    r = os.Stdin
    r = bufio.NewReader(r)
    r = new(bytes.Buffer)
    // and so on

It's important to be clear that whatever concrete value r may hold, r's type is always io.Reader: Go is statically typed and the static type of r is io.Reader.

An extremely important example of an interface type is the empty interface:

interface{}

It represents the empty set of methods and is satisfied by any value at all, since any value has zero or more methods.

Some people say that Go's interfaces are dynamically typed, but that is misleading. They are statically typed: a variable of interface type always has the same static type, and even though at run time the value stored in the interface variable may change type, that value will always satisfy the interface.

We need to be precise about all this because reflection and interfaces are closely related.

The representation of an interface

Russ Cox has written a detailed blog post about the representation of interface values in Go. It's not necessary to repeat the full story here, but a simplified summary is in order.

A variable of interface type stores a pair: the concrete value assigned to the variable, and that value's type descriptor. To be more precise, the value is the underlying concrete data item that implements the interface and the type describes the full type of that item. For instance, after

    var r io.Reader
    tty, err := os.OpenFile("/dev/tty", os.O_RDWR, 0)
    if err != nil {
        return nil, err
    }
    r = tty

r contains, schematically, the (value, type) pair, (tty, *os.File). Notice that the type *os.File implements methods other than Read; even though the interface value provides access only to the Read method, the value inside carries all the type information about that value. That's why we can do things like this:

    var w io.Writer
    w = r.(io.Writer)

The expression in this assignment is a type assertion; what it asserts is that the item inside r also implements io.Writer, and so we can assign it to w. After the assignment, w will contain the pair (tty, *os.File). That's the same pair as was held in r. The static type of the interface determines what methods may be invoked with an interface variable, even though the concrete value inside may have a larger set of methods.

Continuing, we can do this:

    var empty interface{}
    empty = w

and our empty interface value e will again contain that same pair, (tty, *os.File). That's handy: an empty interface can hold any value and contains all the information we could ever need about that value.

(We don't need a type assertion here because it's known statically that w satisfies the empty interface. In the example where we moved a value from a Reader to a Writer, we needed to be explicit and use a type assertion because Writer's methods are not a subset of Reader's.)

One important detail is that the pair inside an interface always has the form (value, concrete type) and cannot have the form (value, interface type). Interfaces do not hold interface values.

Now we're ready to reflect.

The first law of reflection

1. Reflection goes from interface value to reflection object.

At the basic level, reflection is just a mechanism to examine the type and value pair stored inside an interface variable. To get started, there are two types we need to know about in package reflect: Type and Value. Those two types give access to the contents of an interface variable, and two simple functions, called reflect.TypeOf and reflect.ValueOf, retrieve reflect.Typeand reflect.Value pieces out of an interface value. (Also, from the reflect.Value it's easy to get to the reflect.Type, but let's keep the Value and Type concepts separate for now.)

Let's start with TypeOf:

package main

import (
    "fmt"
    "reflect"
)

func main() {
    var x float64 = 3.4
    fmt.Println("type:", reflect.TypeOf(x))
}

This program prints

type: float64

You might be wondering where the interface is here, since the program looks like it's passing the float64variable x, not an interface value, to reflect.TypeOf. But it's there; as godoc reports, the signature of reflect.TypeOf includes an empty interface:

// TypeOf returns the reflection Type of the value in the interface{}.
func TypeOf(i interface{}) Type

When we call reflect.TypeOf(x), x is first stored in an empty interface, which is then passed as the argument; reflect.TypeOf unpacks that empty interface to recover the type information.

The reflect.ValueOf function, of course, recovers the value (from here on we'll elide the boilerplate and focus just on the executable code):

    var x float64 = 3.4
    fmt.Println("value:", reflect.ValueOf(x))

prints

value: <float64 Value>

Both reflect.Type and reflect.Value have lots of methods to let us examine and manipulate them. One important example is that Value has a Type method that returns the Type of a reflect.Value. Another is that both Typeand Value have a Kind method that returns a constant indicating what sort of item is stored: Uint, Float64, Slice, and so on. Also methods on Value with names like Int and Float let us grab values (as int64 and float64) stored inside:

    var x float64 = 3.4
    v := reflect.ValueOf(x)
    fmt.Println("type:", v.Type())
    fmt.Println("kind is float64:", v.Kind() == reflect.Float64)
    fmt.Println("value:", v.Float())

prints

type: float64
kind is float64: true
value: 3.4

There are also methods like SetInt and SetFloat but to use them we need to understand settability, the subject of the third law of reflection, discussed below.

The reflection library has a couple of properties worth singling out. First, to keep the API simple, the "getter" and "setter" methods of Value operate on the largest type that can hold the value: int64 for all the signed integers, for instance. That is, the Int method of Value returns an int64 and the SetInt value takes an int64; it may be necessary to convert to the actual type involved:

    var x uint8 = 'x'
    v := reflect.ValueOf(x)
    fmt.Println("type:", v.Type())                            // uint8.
    fmt.Println("kind is uint8: ", v.Kind() == reflect.Uint8) // true.
    x = uint8(v.Uint())                                       // v.Uint returns a uint64.

The second property is that the Kind of a reflection object describes the underlying type, not the static type. If a reflection object contains a value of a user-defined integer type, as in

    type MyInt int
    var x MyInt = 7
    v := reflect.ValueOf(x)

the Kind of v is still reflect.Int, even though the static type of x is MyInt, not int. In other words, the Kind cannot discriminate an int from a MyInt even though the Type can.

The second law of reflection

2. Reflection goes from reflection object to interface value.

Like physical reflection, reflection in Go generates its own inverse.

Given a reflect.Value we can recover an interface value using the Interface method; in effect the method packs the type and value information back into an interface representation and returns the result:

// Interface returns v's value as an interface{}.
func (v Value) Interface() interface{}

As a consequence we can say

    y := v.Interface().(float64) // y will have type float64.
    fmt.Println(y)

to print the float64 value represented by the reflection object v.

We can do even better, though. The arguments to fmt.Println, fmt.Printf and so on are all passed as empty interface values, which are then unpacked by the fmt package internally just as we have been doing in the previous examples. Therefore all it takes to print the contents of a reflect.Value correctly is to pass the result of the Interface method to the formatted print routine:

    fmt.Println(v.Interface())

(Why not fmt.Println(v)? Because v is a reflect.Value; we want the concrete value it holds.) Since our value is a float64, we can even use a floating-point format if we want:

    fmt.Printf("value is %7.1e\n", v.Interface())

and get in this case

3.4e+00

Again, there's no need to type-assert the result of v.Interface() to float64; the empty interface value has the concrete value's type information inside and Printf will recover it.

In short, the Interface method is the inverse of the ValueOf function, except that its result is always of static type interface{}.

Reiterating: Reflection goes from interface values to reflection objects and back again.

The third law of reflection

3. To modify a reflection object, the value must be settable.

The third law is the most subtle and confusing, but it's easy enough to understand if we start from first principles.

Here is some code that does not work, but is worth studying.

    var x float64 = 3.4
    v := reflect.ValueOf(x)
    v.SetFloat(7.1) // Error: will panic.

If you run this code, it will panic with the cryptic message

panic: reflect.Value.SetFloat using unaddressable value

The problem is not that the value 7.1 is not addressable; it's that v is not settable. Settability is a property of a reflection Value, and not all reflection Values have it.

The CanSet method of Value reports the settability of a Value; in our case,

    var x float64 = 3.4
    v := reflect.ValueOf(x)
    fmt.Println("settability of v:", v.CanSet())

prints

settability of v: false

It is an error to call a Set method on an non-settable Value. But what is settability?

Settability is a bit like addressability, but stricter. It's the property that a reflection object can modify the actual storage that was used to create the reflection object. Settability is determined by whether the reflection object holds the original item. When we say

    var x float64 = 3.4
    v := reflect.ValueOf(x)

we pass a copy of x to reflect.ValueOf, so the interface value created as the argument to reflect.ValueOf is a copy of x, not x itself. Thus, if the statement

    v.SetFloat(7.1)

were allowed to succeed, it would not update x, even though v looks like it was created from x. Instead, it would update the copy of xstored inside the reflection value and x itself would be unaffected. That would be confusing and useless, so it is illegal, and settability is the property used to avoid this issue.

If this seems bizarre, it's not. It's actually a familiar situation in unusual garb. Think of passing x to a function:

f(x)

We would not expect f to be able to modify x because we passed a copy of x's value, not x itself. If we want f to modify x directly we must pass our function the address of x (that is, a pointer to x):

f(&x)

This is straightforward and familiar, and reflection works the same way. If we want to modify x by reflection, we must give the reflection library a pointer to the value we want to modify.

Let's do that. First we initialize x as usual and then create a reflection value that points to it, called p.

    var x float64 = 3.4
    p := reflect.ValueOf(&x) // Note: take the address of x.
    fmt.Println("type of p:", p.Type())
    fmt.Println("settability of p:", p.CanSet())

The output so far is

type of p: *float64
settability of p: false

The reflection object p isn't settable, but it's not p we want to set, it's (in effect) *p. To get to what p points to, we call the Elemmethod of Value, which indirects through the pointer, and save the result in a reflection Value called v:

    v := p.Elem()
    fmt.Println("settability of v:", v.CanSet())

Now v is a settable reflection object, as the output demonstrates,

settability of v: true

and since it represents x, we are finally able to use v.SetFloat to modify the value of x:

    v.SetFloat(7.1)
    fmt.Println(v.Interface())
    fmt.Println(x)

The output, as expected, is

7.1
7.1

Reflection can be hard to understand but it's doing exactly what the language does, albeit through reflection Types and Values that can disguise what's going on. Just keep in mind that reflection Values need the address of something in order to modify what they represent.

Structs

In our previous example v wasn't a pointer itself, it was just derived from one. A common way for this situation to arise is when using reflection to modify the fields of a structure. As long as we have the address of the structure, we can modify its fields.

Here's a simple example that analyzes a struct value, t. We create the reflection object with the address of the struct because we'll want to modify it later. Then we set typeOfT to its type and iterate over the fields using straightforward method calls (see package reflect for details). Note that we extract the names of the fields from the struct type, but the fields themselves are regular reflect.Valueobjects.

    type T struct {
        A int
        B string
    }
    t := T{23, "skidoo"}
    s := reflect.ValueOf(&t).Elem()
    typeOfT := s.Type()
    for i := 0; i < s.NumField(); i++ {
        f := s.Field(i)
        fmt.Printf("%d: %s %s = %v\n", i,
            typeOfT.Field(i).Name, f.Type(), f.Interface())
    }

The output of this program is

0: A int = 23
1: B string = skidoo

There's one more point about settability introduced in passing here: the field names of T are upper case (exported) because only exported fields of a struct are settable.

Because s contains a settable reflection object, we can modify the fields of the structure.

    s.Field(0).SetInt(77)
    s.Field(1).SetString("Sunset Strip")
    fmt.Println("t is now", t)

And here's the result:

t is now {77 Sunset Strip}

If we modified the program so that s was created from t, not &t, the calls to SetInt and SetString would fail as the fields of t would not be settable.

Conclusion

Here again are the laws of reflection:

1. Reflection goes from interface value to reflection object.
2. Reflection goes from reflection object to interface value.
3. To modify a reflection object, the value must be settable.

Once you understand these laws reflection in Go becomes much easier to use, although it remains subtle. It's a powerful tool that should be used with care and avoided unless strictly necessary.

There's plenty more to reflection that we haven't covered — sending and receiving on channels, allocating memory, using slices and maps, calling methods and functions — but this post is long enough. We'll cover some of those topics in a later article.

To transmit a data structure across a network or to store it in a file, it mustbe encoded and then decoded again. There are many encodings available, ofcourse: JSON,XML, Google'sprotocol buffers, and more.And now there's another, provided by Go's gobpackage.

Why define a new encoding? It's a lot of work and redundant at that. Why notjust use one of the existing formats? Well, for one thing, we do! Go haspackages supporting all the encodings just mentioned (theprotocol buffer package is ina separate repository but it's one of the most frequently downloaded). And formany purposes, including communicating with tools and systems written in otherlanguages, they're the right choice.

But for a Go-specific environment, such as communicating between two serverswritten in Go, there's an opportunity to build something much easier to use andpossibly more efficient.

Gobs work with the language in a way that an externally-defined,language-independent encoding cannot. At the same time, there are lessons to belearned from the existing systems.

Goals

The gob package was designed with a number of goals in mind.

First, and most obvious, it had to be very easy to use. First, because Go hasreflection, there is no need for a separate interface definition language or"protocol compiler". The data structure itself is all the package should needto figure out how to encode and decode it. On the other hand, this approachmeans that gobs will never work as well with other languages, but that's OK:gobs are unashamedly Go-centric.

Efficiency is also important. Textual representations, exemplified by XML andJSON, are too slow to put at the center of an efficient communications network.A binary encoding is necessary.

Gob streams must be self-describing. Each gob stream, read from the beginning,contains sufficient information that the entire stream can be parsed by anagent that knows nothing a priori about its contents. This property means thatyou will always be able to decode a gob stream stored in a file, even longafter you've forgotten what data it represents.

There were also some things to learn from our experiences with Google protocolbuffers.

Protocol buffer misfeatures

Protocol buffers had a major effect on the design of gobs, but have threefeatures that were deliberately avoided. (Leaving aside the property thatprotocol buffers aren't self-describing: if you don't know the data definitionused to encode a protocol buffer, you might not be able to parse it.)

First, protocol buffers only work on the data type we call a struct in Go. Youcan't encode an integer or array at the top level, only a struct with fieldsinside it. That seems a pointless restriction, at least in Go. If all you wantto send is an array of integers, why should you have to put it into astruct first?

Next, a protocol buffer definition may specify that fields T.x andT.y are required to be present whenever a value of typeT is encoded or decoded. Although such required fields may seemlike a good idea, they are costly to implement because the codec must maintain aseparate data structure while encoding and decoding, to be able to report whenrequired fields are missing. They're also a maintenance problem. Over time, onemay want to modify the data definition to remove a required field, but that maycause existing clients of the data to crash. It's better not to have them in theencoding at all. (Protocol buffers also have optional fields. But if we don'thave required fields, all fields are optional and that's that. There will bemore to say about optional fields a little later.)

The third protocol buffer misfeature is default values. If a protocol bufferomits the value for a "defaulted" field, then the decoded structure behaves asif the field were set to that value. This idea works nicely when you havegetter and setter methods to control access to the field, but is harder tohandle cleanly when the container is just a plain idiomatic struct. Requiredfields are also tricky to implement: where does one define the default values,what types do they have (is text UTF-8? uninterpreted bytes? how many bits in afloat?) and despite the apparent simplicity, there were a number ofcomplications in their design and implementation for protocol buffers. Wedecided to leave them out of gobs and fall back to Go's trivial but effectivedefaulting rule: unless you set something otherwise, it has the "zero value"for that type - and it doesn't need to be transmitted.

So gobs end up looking like a sort of generalized, simplified protocol buffer.How do they work?

Values

The encoded gob data isn't about int8s and uint16s.Instead, somewhat analogous to constants in Go, its integer values are abstract,sizeless numbers, either signed or unsigned. When you encode anint8, its value is transmitted as an unsized, variable-lengthinteger. When you encode an int64, its value is also transmitted asan unsized, variable-length integer. (Signed and unsigned are treateddistinctly, but the same unsized-ness applies to unsigned values too.) If bothhave the value 7, the bits sent on the wire will be identical. When the receiverdecodes that value, it puts it into the receiver's variable, which may be ofarbitrary integer type. Thus an encoder may send a 7 that came from anint8, but the receiver may store it in an int64. Thisis fine: the value is an integer and as a long as it fits, everything works. (Ifit doesn't fit, an error results.) This decoupling from the size of the variablegives some flexibility to the encoding: we can expand the type of the integervariable as the software evolves, but still be able to decode old data.

This flexibility also applies to pointers. Before transmission, all pointers areflattened. Values of type int8, *int8,**int8, ****int8, etc. are all transmitted as aninteger value, which may then be stored in int of any size, or*int, or ******int, etc. Again, this allows forflexibility.

Flexibility also happens because, when decoding a struct, only those fieldsthat are sent by the encoder are stored in the destination. Given the value

type T struct{ X, Y, Z int } // Only exported fields are encoded and decoded.
var t = T{X: 7, Y: 0, Z: 8}

the encoding of t sends only the 7 and 8. Because it's zero, thevalue of Y isn't even sent; there's no need to send a zero value.

The receiver could instead decode the value into this structure:

type U struct{ X, Y *int8 } // Note: pointers to int8s
var u U

and acquire a value of u with only X set (to theaddress of an int8 variable set to 7); the Z field isignored - where would you put it? When decoding structs, fields are matched byname and compatible type, and only fields that exist in both are affected. Thissimple approach finesses the "optional field" problem: as the typeT evolves by adding fields, out of date receivers will stillfunction with the part of the type they recognize. Thus gobs provide theimportant result of optional fields - extensibility - without any additionalmechanism or notation.

From integers we can build all the other types: bytes, strings, arrays, slices,maps, even floats. Floating-point values are represented by their IEEE 754floating-point bit pattern, stored as an integer, which works fine as long asyou know their type, which we always do. By the way, that integer is sent inbyte-reversed order because common values of floating-point numbers, such assmall integers, have a lot of zeros at the low end that we can avoidtransmitting.

One nice feature of gobs that Go makes possible is that they allow you to defineyour own encoding by having your type satisfy theGobEncoder andGobDecoder interfaces, in a manneranalogous to the JSON package'sMarshaler andUnmarshaler and also to theStringer interface frompackage fmt. This facility makes it possible torepresent special features, enforce constraints, or hide secrets when youtransmit data. See the documentation fordetails.

Types on the wire

The first time you send a given type, the gob package includes in the datastream a description of that type. In fact, what happens is that the encoder isused to encode, in the standard gob encoding format, an internal struct thatdescribes the type and gives it a unique number. (Basic types, plus the layoutof the type description structure, are predefined by the software forbootstrapping.) After the type is described, it can be referenced by its typenumber.

Thus when we send our first type T, the gob encoder sends adescription of T and tags it with a type number, say 127. Allvalues, including the first, are then prefixed by that number, so a stream ofT values looks like:

("define type id" 127, definition of type T)(127, T value)(127, T value), ...

These type numbers make it possible to describe recursive types and send valuesof those types. Thus gobs can encode types such as trees:

type Node struct {
    Value       int
    Left, Right *Node
}

(It's an exercise for the reader to discover how the zero-defaulting rule makesthis work, even though gobs don't represent pointers.)

With the type information, a gob stream is fully self-describing except for theset of bootstrap types, which is a well-defined starting point.

Compiling a machine

The first time you encode a value of a given type, the gob package builds alittle interpreted machine specific to that data type. It uses reflection onthe type to construct that machine, but once the machine is built it does notdepend on reflection. The machine uses package unsafe and some trickery toconvert the data into the encoded bytes at high speed. It could use reflectionand avoid unsafe, but would be significantly slower. (A similar high-speedapproach is taken by the protocol buffer support for Go, whose design wasinfluenced by the implementation of gobs.) Subsequent values of the same typeuse the already-compiled machine, so they can be encoded right away.

Decoding is similar but harder. When you decode a value, the gob package holdsa byte slice representing a value of a given encoder-defined type to decode,plus a Go value into which to decode it. The gob package builds a machine forthat pair: the gob type sent on the wire crossed with the Go type provided fordecoding. Once that decoding machine is built, though, it's again areflectionless engine that uses unsafe methods to get maximum speed.

Use

There's a lot going on under the hood, but the result is an efficient,easy-to-use encoding system for transmitting data. Here's a complete exampleshowing differing encoded and decoded types. Note how easy it is to send andreceive values; all you need to do is present values and variables to thegob package and it does all the work.

package main

import (
    "bytes"
    "encoding/gob"
    "fmt"
    "log"
)

type P struct {
    X, Y, Z int
    Name    string
}

type Q struct {
    X, Y *int32
    Name string
}

func main() {
    // Initialize the encoder and decoder.  Normally enc and dec would be
    // bound to network connections and the encoder and decoder would
    // run in different processes.
    var network bytes.Buffer        // Stand-in for a network connection
    enc := gob.NewEncoder(&network) // Will write to network.
    dec := gob.NewDecoder(&network) // Will read from network.
    // Encode (send) the value.
    err := enc.Encode(P{3, 4, 5, "Pythagoras"})
    if err != nil {
        log.Fatal("encode error:", err)
    }
    // Decode (receive) the value.
    var q Q
    err = dec.Decode(&q)
    if err != nil {
        log.Fatal("decode error:", err)
    }
    fmt.Printf("%q: {%d,%d}\n", q.Name, *q.X, *q.Y)
}

You can compile and run this example code in theGo Playground.

The rpc package builds on gobs to turn thisencode/decode automation into transport for method calls across the network.That's a subject for another article.

Details

The gob package documentation, especially thefile doc.go, expands on many of thedetails described here and includes a full worked example showing how theencoding represents data. If you are interested in the innards of the gobimplementation, that's a good place to start.

• a short introduction into the history,
• the basic features,
• the special combination of elegance and power, and
• Go in the wilderness.

After yesterday's post that advocated using RSA public exponents of 3 or 2¹⁶+1 in DNSSEC for performance, Dan Kaminsky asked me whether there was a potential DoS vector by using really big public exponents.

Recall that the RSA signature verification core is m^e mod n. By making e and n larger, we can make the operation slower. But there are limits, at least in OpenSSL:

/* for large moduli, enforce exponent limit */
if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
        if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
                RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE);
                return -1;
        }
}

So, if n is large, we enforce a limit on e. The values of the #defines are such that for n>3072 bits, e must be less than or equal to 64 bits. So the slowest operations happen with an n and e of 3072 bits. (The fact that e<n is enforced earlier in the code.)

So I setup *.bige.imperialviolet.org. This is a perfectly valid and well signed zone which happens to use a 3072-bit key with a 3072-bit public exponent. (I could probably have slowed things down more by picking a public exponent with lots of 1s in its binary representation, but it's just a random number in this case.) One can resolve records 1.bige.imperialviolet.org, 2.bige.imperialviolet.org, … and the server doesn't have to sign anything because it's a wildcard: a single signature covers all of the names. However, the resolver validates the signature every time.

On my 2.66GHz, Core 2 laptop, 15 requests per second causes unbound to take 95% of a core. A couple hundred queries per second would probably put most DNSSEC resolvers in serious trouble.

So I'd recommend limiting the public exponent size in DNSSEC to 2¹⁶+1, except that people are already mistakenly using 2³²+1, so I guess that needs to be the limit. The DNSSEC spec limits the modulus size to 4096-bits, and 4096-bit signatures are about 13 times slower to verify than the typical 1024-bit signatures used in DNSSEC. But that's a lot less of a DoS vector than bige.imperialviolet.org, which is 2230 times slower than normal.

RSA public operations are much faster than private operations. Thirty-two times faster for a 2048-bit key on my machine. But the two operations are basically the same: take the message, raise it to the power of the public or private exponent and reduce modulo the key's modulus.

What makes the public operations so much faster is that the public exponent is typically tiny, while the private exponent should be the same size as the modulus. One can actually use a public exponent of three in RSA, and clearly cubing a number should be faster than raising it to the power of a 2048-bit number.

In 2006, Daniel Bleichenbacher (a fellow Googler) gave a talk at the CRYPTO 2006 rump session where he outlined a bug in several, very common RSA signature verification implementations at the time. The bug wasn't nearly as bad as it could have been because it only affected public keys that used a public exponent of three and most keys used a larger exponent: 2¹⁶+1. But the fact that a slightly larger public exponent saved these buggy verifiers cemented 2¹⁶+1 as sensible default value for the public exponent.

But there's absolutely no reason to think that a public exponent larger than 2¹⁶+1 does any good. I even checked that with Bleichenbacher before writing this. Three should be fine, 2¹⁶+1 saved some buggy software a couple of times and any larger is probably a mistake.

Because of that, when writing the Go RSA package, I didn't bother supporting public exponents larger than 2³¹-1. But then several people reported that they couldn't verify some DNSSEC signatures. Sure enough, the DNSKEY records for .cz and .us are using a public exponent of 2³²+1.

DNSSEC is absolutely the last place to use large, public exponents. Busy DNS resolvers have to resolve tens or hundreds of thousands of records a second; fast RSA signature verification is big deal in DNSSEC. So I measured the speed impact of various public exponent sizes with OpenSSL (1.0.1-beta3):

So a public exponent of 2³²+1 makes signature verification over four times slower than an exponent of three. As DNSSEC grows, and DNSSEC resolvers too, that extra CPU time is going to be a big deal.

It looks like the zones using a value of 2³²+1 are just passing the -e flag to BIND's dnssec-keygen utility. There's some suggestion that -e used to select 2¹⁶+1 but silently changed semantics in some release.

So today's lesson is don't pass -e to dnssec-keygen! The default of dnssec-keygen is 2¹⁶+1 and that's certainly safe. The .com zone uses a value of three and I think that's probably the best choice given the CPU cost and the fact that the original Bleichenbacher bug has been long since fixed.

The development of the language Go is going at a fast pace, hence an updated version of Super-short guide to gettinq q.

Get the latest version (called weekly) of Go:

1. Get Go: hg clone -u release https://go.googlecode.com/hg/ go Note the directory you have downloaded it to and set add its bin directory to your PATH: PATH=$PWD/go/bin.

2. Update Go to the latest weekly: cd go; hg pull; hg update weekly

3. Compile Go: cd src, you should now sit in go/src. And compile: ./all.bash

Install missing commands (gcc, sed, bison, etc.) if needed.

The latest Go is now installed. You should now have the go-tool, this is the central interface to all Go program building tasks.

$ go
Go is a tool for managing Go source code.

Usage: go command [arguments]

The commands are:

build       compile packages and dependencies
clean       remove object files
doc         run godoc on package sources
fix         run go tool fix on packages
....
....
lost more

If you can not run go, check your PATH.

Install Go DNS and set GOPATH

The GOPATH variable specifies (among things) where your Go code lives. Using the go tool does bring a few requirements to the table in how to layout the directory structure.

1. Create toplevel directory (~/g) for your code: mkdir -p ~/g/src
2. Set GOPATH to this toplevel directory: export GOPATH=~/g
3. Get dns: cd ~/g/src; git clone git://github.com/miekg/dns.git
4. Compile it: cd dns; go build
5. Compile and install the examples, there is a helper Makefile here, but it just calls go multiple times: cd ex; make
6. Look in $GOPATH/bin for the binaries, in this setup that will be ~/g/bin
7. Query with q: ~/g/bin/q mx miek.nl (or add ~/g/bin to your $PATH too)
8. Report bugs

When we announced forward secrecy for Google HTTPS we noted that “we hope to support IE in the future”. It wasn't that we didn't want to support IE, but IE doesn't implement the combination of ECDHE with RC4. IE (or rather, SChannel) does implement ECDHE with AES on Vista and Windows 7, but I only wanted to make one change at a time.

With the release of MS12-006 a month ago to address the BEAST weakness in TLS 1.0's CBC design, we've now made ECDHE-RSA-AES128-SHA our second preference cipher. That means that Chrome and Firefox will still use ECDHE-RSA-RC4-SHA, but IE on Vista and Windows 7 will get ECDHE now. This change also means that we support ECDHE with Safari (at least on Lion, where I tried it.)

Modern ELF systems can randomize the address at which shared libraries are loaded. This is generally referred to as Address Space Layout Randomization, or ASLR. Shared libraries are always position independent, which means that they can be loaded at any address. Randomizing the load address makes it slightly harder for attackers of a running program to exploit buffer overflows or similar problems, because they have no fixed addresses that they can rely on. ASLR is part of defense in depth: it does not by itself prevent any attacks, but it makes it slightly more difficult for attackers to exploit certain kinds of programming errors in a useful way beyond simply crashing the program.

Although it is straightforward to randomize the load address of a shared library, an ELF executable is normally linked to run at a fixed address that can not be changed. This means that attackers have a set of fixed addresses they can rely on. Permitting the kernel to randomize the address of the executable itself is done by generating a Position Independent Executable, or PIE.

It turns out to be quite simple to create a PIE: a PIE is simply an executable shared library. To make a shared library executable you just need to give it a PT_INTERP segment and appropriate startup code. The startup code can be the same as the usual executable startup code, though of course it must be compiled to be position independent.

When compiling code to go into a shared library, you use the -fpic option. When compiling code to go into a PIE, you use the -fpie option. Since a PIE is just a shared library, these options are almost exactly the same. The only difference is that since -fpie implies that you are building the main executable, there is no need to support symbol interposition for defined symbols. In a shared library, if function f1 calls f2, and f2 is globally visible, the code has to consider the possibility that f2 will be interposed. Thus, the call must go through the PLT. In a PIE, f2 can not be interposed, so the call may be made directly, though of course still in a position independent manner. Similarly, if the processor can do PC-relative loads and stores, all global variables can be accessed directly rather than going through the GOT.

Other than that ability to avoid the PLT and GOT in some cases, a PIE is really just a shared library. The dynamic linker will ask the kernel to map it at a random address and will then relocate it as usual.

This does imply that a PIE must be dynamically linked, in the sense of using the dynamic linker. Since the dynamic linker and the C library are closely intertwined, linking the PIE statically with the C library is unlikely to work in general. It is possible to design a statically linked PIE, in which the program relocates itself at startup time. The dynamic linker itself does this. However, there is no general mechanism for this at present.

"Go is miles ahead of C++ and Java in terms of expressibility and close in terms of performance. It is also relatively simple and has a straightforward interaction with Linux system calls."

"The main drawback is also its strength - the garbage collector. vtocc has made spot optimizations to minimize most of the adverse effects of Go’s stop-the-world gc. At this point, we are trading some amount of performance for greater creativity and efficiency at lower layers. unless you’re trying to max out on qps for your servers, you should see acceptable performance from vtocc. Also, go’s garbage collector is being improved. So, this should only get better over time. Go’s existing mark-and-sweep garbage collector is sub-optimal for systems that use large amounts of static memory (like caches). In the case of vtocc, this would be the row cache. To alleviate this, we intend to use memcache for the time being. If the gc ends up addressing this, it should be fairly trivial to switch to an in-memory row cache. Note that the row cache functionality is not fully ready yet."

/home/themue/projects
        /go
                /bin
                ...
                /test
        /own
                /pkg
                /src
        /3rdparty
                /pkg
                /src

GOPATH=$HOME/projects/3rdparty:$HOME/projects/own

• The location for the binaries is ok. Here the standard $PATH should point to this directory too with PATH=$PATH:$HOME/projects/go/bin.
• The other way is that you've got a directory like $HOME/bin for all your private binaries and scripts and it's already in your $PATH. In this case you can set GOBIN=$HOME/bin before installing the Go SDK. In this case after the compilation the Go binaries get installed in your $HOME/bin.

Just a brief note that I'll be at RSA 2012 in San Francisco at the end of the month and will be speaking with several others about certificate revocation. (tech-106, Tuesday, 1pm.).

If you want to chat and don't manage to grab me then, drop me an email. (agl at imperialviolet.org if you didn't already know.)

Due to the new go tool (long story), I've renamed godns to dns. This means the github repo is also somewhere else.

godns installed itself as dns so code using it does not need to be changed.

Let my start by apologizing for the noisy duplicate posts. I know that people using RSS software to read this blog got a whole bunch of old posts shown as new yesterday, and the same thing happened again just now. I made some mistakes while moving the blog from one platform to another, which caused the first burp, and then I had to fix the mistakes, which caused the second burp. But it's done, and there won't be another batch of duplicates waiting for you tomorrow.

I've moved this blog off of Blogger onto App Engine, running on a custom app written in Go. The down side is that I had to implement functionality that Blogger used to handle for me, like generating the RSS feed, and that's both extra work and a chance to make mistakes, which I took full advantage of. The up side, however, is that it makes it significantly easier for me to automate the writing and publishing of posts, and to create posts with a computational aspect to the content. I'll be blogging in the coming months about both the new setup, which has some interesting technical aspects behind it (I can edit live posts in a real text editor, for one thing), and about other topics that can make use of the computation.

For now, though, it's just the same content on a new server. Enjoy.

When a browser connects to an HTTPS site it receives signed certificates which allow it to verify that it's really connecting to the domain that it should be connecting to. In those certificates are pointers to services, run by the Certificate Authorities (CAs) that issued the certificate, that allow the browser to get up-to-date information.

All the major desktop browsers will contact those services to inquire whether the certificate has been revoked. There are two protocols/formats involved: OCSP and CRL, although the differences aren't relevant here. I mention them only so that readers can recognise the terms in other discussions.

The problem with these checks, that we call online revocation checks, is that the browser can't be sure that it can reach the CA's servers. There are lots of cases where it's not possible: captive portals are one. A captive portal frequently requires you to sign in on an HTTPS site, but blocks traffic to all other sites, including the CA's OCSP servers.

If browsers were to insist on talking to the CA before accepting a certificate, all these cases would stop working. There's also the concern that the CA may experience downtime and it's bad engineering practice to build in single points of failure.

Therefore online revocation checks which result in a network error are effectively ignored (this is called “soft-fail”). I've previously documented the resulting behaviour of several browsers.

But an attacker who can intercept HTTPS connections can also make online revocation checks appear to fail and so bypass the revocation checks! In cases where the attacker can only intercept a subset of a victim's traffic (i.e. the SSL traffic but not the revocation checks), the attacker is likely to be a backbone provider capable of DNS or BGP poisoning to block the revocation checks too.

If the attacker is close to the server then online revocation checks can be effective, but an attacker close to the server can get certificates issued from many CAs and deploy different certificates as needed. In short, even revocation checks don't stop this from being a real mess.

So soft-fail revocation checks are like a seat-belt that snaps when you crash. Even though it works 99% of the time, it's worthless because it only works when you don't need it.

While the benefits of online revocation checking are hard to find, the costs are clear: online revocation checks are slow and compromise privacy. The median time for a successful OCSP check is ~300ms and the mean is nearly a second. This delays page loading and discourages sites from using HTTPS. They are also a privacy concern because the CA learns the IP address of users and which sites they're visiting.

On this basis, we're currently planning on disabling online revocation checks in a future version of Chrome. (There is a class of higher-security certificate, called an EV certificate, where we haven't made a decision about what to do yet.)

Pushing a revocation list

Our current method of revoking certificates in response to major incidents is to push a software update. Microsoft, Opera and Firefox also push software updates for serious incidents rather than rely on online revocation checks. But our software updates require that users restart their browser before they take effect, so we would like a lighter weight method of revoking certificates.

So Chrome will start to reuse its existing update mechanism to maintain a list of revoked certificates, as first proposed to the CA/Browser Forum by Chris Bailey and Kirk Hall of AffirmTrust last April. This list can take effect without having to restart the browser.

An attacker can still block updates, but they have to be able to maintain the block constantly, from the time of revocation, to prevent the update. This is much harder than blocking an online revocation check, where the attacker only has to block the checks during the attack.

Since we're pushing a list of revoked certificates anyway, we would like to invite CAs to contribute their revoked certificates (CRLs) to the list. We have to be mindful of size, but the vast majority of revocations happen for purely administrative reasons and can be excluded. So, if we can get the details of the more important revocations, we can improve user security. Our criteria for including revocations are:

1. The CRL must be crawlable: we must be able to fetch it over HTTP and robots.txt must not exclude GoogleBot.
2. The CRL must be valid by RFC 5280 and none of the serial numbers may be negative.
3. CRLs that cover EV certificates are taken in preference, while still considering point (4).
4. CRLs that include revocation reasons can be filtered to take less space and are preferred.

For the curious, there is a tool for fetching and parsing Chrome's list of revoked certificates at https://github.com/agl/crlset-tools.

When people need a list of root certificates, they often turn to Mozilla's. However, Mozilla doesn't produce a nice list of PEM encoded certificates. Rather, they keep them in a form which is convenient for NSS to build from: https://mxr.mozilla.org/mozilla/source/security/nss/lib/ckfw/builtins/certdata.txt?raw=1.

Several people have written quick scripts to try and convert this into PEM format, but they often miss something critical: some certificates are explicitly distrusted. These include the DigiNotar certificates and the misissued COMODO certificates. If you don't parse the trust records from the NSS data file, then you end up trusting these too! There's at least one, major example of this that I know of.

(Even with a correct root file, unless you do hard fail revocation checking you're still vulnerable to the misissued COMODO certificates.)

So, at the prodding of Denton Gentry, I've open-sourced a tool for converting NSS's file to PEM format: extract-nss-root-certs. (At the time of writing it requires a 6g built from the weekly or current tree (hg -r weekly), not the release tree. A few of the APIs have changed since the last Go release was done. This will be resolved when Go 1.0 is released.)

A problem I’ve had for a long while has been the fear of looking stupid. It’s held back projects, study, blog posts (you can see this from the sparseness of this blog), and more generally things I’ve wanted to do which risk looking stupid - translated: worthwhile things.

Ironically this fear has often been self-fulfilling as I’ve ran through the familiar cycle of publicly promising to do something → fearing looking stupid since this thing is tough and I’ve hit up on a brick wall → engaging in endless procrastination → end up looking stupid for not having made progress on said thing.

This is all highly applicable to programming. Computers are so ridiculously complicated that there will always be something to defeat you, the field so wide that there will always be something you don’t know about, or even if you do know something relatively deeply there is always something (actually many things) which will crop up to surprise you (C sharpies should read Eric Lippert’s blog to bring this point home).

A curious aspect of our craft is how quickly you can find yourself in a situation where your particular problem is a unique enough combination of factors for you to be out there on your own at least in some regard or another. That is enough to make the most hardened, experienced developer insecure and is yet another factor in my own battle with the stupid.

Another consequence of this fear is that, since it’s really impossible to improve at something without questioning whether you have the best approach to the problem at hand (and thus risking looking stupid for having got something wrong), you end up less great than you could potentially be.

In terms of programming this fear stands in the way of better code. Without considering whether your code might be suboptimal (and therefore you possibly looking stupid), you end up almost definitely ensuring your code will be suboptimal. This is not unconnected to the only valid measure of code quality.

Clearly a big factor in all of this is pride, especially when you consider future employability, and especially when you have a name which is globally unique over the whole of the internet (the intersection of people with forename of Lorenzo and people with surname of Stoakes, rather than the more common Stokes, is small).

Fuck pride. Fuck not doing things you want to do because you might end up looking stupid, fuck getting stuck on a problem and not bringing the awesome power of crowdsourcing to bear on it.

Expect some stupidity going forward, but also intelligence as I work hard on fixing my stupidity, little-by-little. Sucking a little less each year.

Announcing FP

The tool for DNS fingerprinting is fpdns, which is Perl based. In recent times development seems to have picked up, but a little competition never hurt anyone, so I wrote fp in Go. Fp is also a fingerprint program for DNS servers. Its aim is to be more readable then fpdns is (was?). And make it more easy to add new server types.

Help needed!

Do you have some old(er) nameserver laying around that can be queried? Does your (sick) mind know of a few extra evil queries that can be sent to nameservers? If so, please contact me: query@evilquery.nl. I want to get to a point where fp sends about 10 queries that can be used to identify a server.

Fingerprint

A fingerprint in fp looks like this:

.,CH,TXT,QUERY,NOERROR,qr,aa,tc,RD,ra,ad,cd,z,1,0,0,0,DO,4097,NSID

It has 20 fields, which are:

1. Domain name, . in this example;
2. Class, CH here;
3. Type, TXT here;
4. Opcode, QUERY;
5. Rcode, NOERROR;
6. Query response, qr, lowercase means false (not set), uppercase means true;
7. Authoritative, aa, lowercase. Thus not set here;
8. Truncated, tc, not set;
9. Recursion Desired, RD, uppercase, thus set;
10. Recursion Available, ra;
11. Authenticated Data, ad;
12. Checking Disabled, cd;
13. Zero, z;
14. Question section length, 1 here;
15. Answer section length, 0;
16. Authoritative section length, 0;
17. Additional section length, 0;
18. DNSSEC OK, DO (uppercase, thus set);
19. UDP bufsize, set to 4097;
20. NSID, uppercase: request NSID (or NSID was set).

These fingerprints are also used in creating the DNS queries that are send to nameserver(s) being tested.

A full nameserver fingerprint consists out of multiple of these fingerprints. Right now fp fires off 3 queries to test a server, so each nameserver fingerprint must also consist out of 3 fingerprints. The nameserver fingerprint of BIND9 looks like:

# BIND9 fingerprints
.,CH,TXT,QUERY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,1,DO,4096,NSID
auThoRs.bInD.,CH,TXT,QUERY,NOERROR,QR,AA,tc,rd,ra,ad,cd,z,1,15,1,0,do,0,nsid
bind.,NONE,SOA,NOTIFY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,0,do,0,nsid

When fp is extended with an extra fingerprint, this BIND9 fingerprint also needs to get an extra fingerprint.

Trying it yourself

As said, Currently fp only uses three queries, but this is expected to be increased in the near future. In the data directory, the file q holds the fingerprints of the queries to ask. Currently it looks like this:

# These are the queries that we ask the nameserver being identified
#
# The order is important, as the data files of the known nameservers are compared
# in this order.
.,CH,TXT,QUERY,NOERROR,qr,aa,tc,RD,ra,ad,cd,z,1,0,0,0,DO,4097,NSID
auThoRs.bInD.,CH,TXT,QUERY,NOERROR,qr,aa,tc,rd,ra,ad,cd,z,1,0,0,0,do,0,nsid
bind.,NONE,SOA,NOTIFY,NOERROR,qr,AA,tc,RD,ra,ad,cd,Z,1,0,0,0,do,0,nsid

A local run looks like this (this is abbreviated):

% ./fp @localhost
Server type     Diffs       Fingerprint         Recevied
Bind9   0 .,CH,TXT,QUERY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,1,DO,4096,NSID .,CH,TXT,QUERY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,1,DO,4096,NSID
Bind9   0 auThoRs.bInD.,CH,TXT,QUERY,NOERROR,QR,AA,tc,rd,ra,ad,cd,z,1,15,1,0,do,0,nsid auThoRs.bInD.,CH,TXT,QUERY,NOERROR,QR,AA,tc,rd,ra,ad,cd,z,1,15,1,0,do,0,nsid
Bind9   0 bind.,NONE,SOA,NOTIFY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,0,do,0,nsid bind.,NONE,SOA,NOTIFY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,0,do,0,nsid
        =
Differences:    0

Nsd3    2 .,CH,TXT,QUERY,NOERROR,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,1,DO,4096,nsid .,CH,TXT,QUERY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,1,DO,4096,NSID
Nsd3    3 auThoRs.bInD.,CH,TXT,QUERY,NOERROR,QR,aa,tc,rd,ra,ad,cd,z,1,0,0,0,do,0,nsid auThoRs.bInD.,CH,TXT,QUERY,NOERROR,QR,AA,tc,rd,ra,ad,cd,z,1,15,1,0,do,0,nsid
Nsd3    6 .,CLASS0,TYPE0,NOTIFY,NXDOMAIN,QR,AA,tc,RD,ra,ad,cd,z,0,0,0,0,do,0,nsid bind.,NONE,SOA,NOTIFY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,0,do,0,nsid
            =
Differences:    11

What do you see here? On the left the nameserver type we're testing, then a number. This number represent the number of differences with the stored fingerprint for this server. When this number is zero, it means the reply from the unknown server is an exact match with one of the stored fingerprints. In general, the lower the number, the more exact the hit was. For bind9 in the example above, the accumulated number of differences is zero. This indicates the server is probably a BIND9 server.

For nsd3 the story is completely different. The accumulated number of differences is 11, so this server probably isn't a NSD3 server.

Report

With, -report fp will just show the fingerprint of a nameserver. If the server is positively identified, the finger print can be added to fp:

% ./fp -report @localhost
# Fingerprint of <Nameserver> <version>
# Supplied by <Name> on <Date>
#
.,CH,TXT,QUERY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,1,DO,4096,NSID
auThoRs.bInD.,CH,TXT,QUERY,NOERROR,QR,AA,tc,rd,ra,ad,cd,z,1,15,1,0,do,0,nsid
bind.,NONE,SOA,NOTIFY,REFUSED,QR,aa,tc,RD,ra,ad,cd,z,1,0,0,0,do,0,nsid

For those who didn’t know, I have quit my job at a hedge fund to work at a startup - Rulemotion (website under construction). Exciting! Scary! Awesome! All at the same time :-)

I don’t move until early March, at which I point I am sure I shall blog some more about what I’m getting up to there/what we are all about.

Already looking to be an interesting year, this!

Get the latest version (called weekly) of Go:

1. Get Go: hg clone -u release https://go.googlecode.com/hg/ go Note the directory you have downloaded it to and set $GOROOT to it: export GOROOT=$PWD/go. Add the GOROOT bin directory to your path: PATH=$PATH:$GOROOT/bin

2. Update Go to the latest weekly: cd $GOROOT; hg pull; hg update weekly

3. Compile Go: cd $GOROOT/src ; ./all.bash

   Install missing commands (gcc, sed, bison, etc.) if needed.

The latest Go is now installed.

Install GoDNS

1. Get GoDNS: cd ~; git clone git://github.com/miekg/godns.git
2. Compile it: cd godns; make ; make install
3. Compile the examples; cd examples; make ; make install
4. Query with q: q mx miek.nl
5. Report bugs

In January 2007 I posted an article on my web site titled “Regular Expression Matching Can Be Simple And Fast.” I intended this to be the first of three; the second would explain how to do submatching using automata, and the third would explain how to make a really fast DFA. These were inspired by my work on Google Code Search.

Today, the fourth article in my three-part series is available, accompanied by source code (as usual). This one describes how Code Search worked.

(See the original post for background.)

Everyone seems to have settled on 1/n-1 record splitting as a workaround for the BEAST attack in TLS 1.0 and SSLv3. Briefly: 1/n-1 record splitting breaks CBC encrypted records in two: the first with only a single byte of application data and the second with the rest. This effectively randomises the IV and stops the attack.

The workaround which OpenSSL tried many years ago, and which hit significant issues, was 0/n record splitting. It's the same thing, but with the first record being empty. The problem with it was that many stacks processed the empty record and returned a 0-byte read, which higher levels took to mean EOF.

1/n-1 record splitting doesn't hit that problem, but it turns out that there's a fair amount of code out there that assumes that the entire HTTP request comes in a single read. The single byte record breaks that.

We first implemented 1/n-1 record splitting in Chrome 15 but backed off after only a couple of days because logging into several large sites broke. But that did motivate the sites to fix things so that we could switch it on in Chrome 16 and it stuck that time.

Opera also implemented it around this time, but I think Chrome took the brunt of the bug reports and it's time consuming dealing with them. Myself and a colleague have been emailing and phoning a lot of sites and vendors while dealing with upset users and site admins. Chrome certainly paid a price for moving before Firefox and IE but then we're nice like that.

Thankfully, this week, Microsoft released a security update which implements 1/n-1 record splitting in SChannel and switches it on in IE. (Although it defaults to off for other users of SChannel, unlike NSS.) Now the sites which broke with Chrome 16 are also broken in a patched IE and that takes some pressure off us. In a few weeks, Firefox 10 should be released and then we'll be about as good as we're going to get.

After taking the brunt with Chrome 16, there is one case that I'm not going to fight: Plesk can't handle POST payloads that don't come in a single read. Chrome (currently) sends POSTs as two writes: one for the HTTP headers and a second for the POST body. That means that each write is split into two records and Plesk breaks because of the second split. IE and Firefox send the headers and body in a single write, so there's only a single split in the HTTP headers, which Plesk handles.

Chrome will start merging small POST bodies into the headers with Chrome 17 (hopefully) and this will fix Plesk. Also, merging as Firefox and IE do saves an extra packet so it's worthwhile on its own. Once again, anything that's mostly true soon becomes an unwritten rule on the Internet.

It's worth contrasting the BEAST response to the renegotiation attack. The BEAST workaround caused a number of problems, but it worked fine for the vast majority of sites. The renegotiation fix requires that very nearly every HTTPS site on the Internet be updated and then that browsers refuse to talk to unpatched servers.

I'd bet that we'll not manage to get enough patched servers for any browser to require it this side of 2020. Unpatched servers can still disable renegotiation to protect themselves, but it's still not hard to find major sites that allow insecure renegotiation (www.chase.com was literally the second site that I tried).

“Off the record” is, unfortunately, an overloaded term. To many it's feature in gTalk and AOL IM which indicates that the conversation isn't logged. However, to crypto folks it's a protocol for secure chat.

(In fact, resoloving the ambiguity is on the EFF's wish list.)

Pidgin has been my chat client of choice for some time because it's pretty fully featured and supports OTR via a plugin. However, I just don't trust it from a security point of view. The latest incident was only a couple of weeks ago: CVE-2011-3919.

So, I implemented otr in Go, as well as an XMPP library and client. It's an absolutely minimal client (except for OTR support) and implements only what I absolutely need in a client.

But it does mean that the whole stack, including the TLS library, is implemented in a memory safe language. (On the other hand, pretty much everything in that stack, from the modexp function to the terminal handling code was written by me and has never really been audited. I'm a decent programmer but I'm sure there are some howlers of security issues in there somewhere.)

“Nothing is so strong as gentleness, nothing so gentle as real strength”
- St. Francis de Sales

Go Gopher

As 2011 makes its way out and 2012 takes its place, it’s time for a bit of reflection and a bit of looking forward. I haven’t been writing software professionally for particularly long, but I have written software in a number of languages (everything from Pascal to Python), and I think we can all agree that none of the usual suspects are particularly ideal. If you’re like me, you hunker down with your favorite set of language features and write your code in as much isolation as possible, so that you can work around or ignore whatever problems your language and/or environment cause you. You probably have some tools lying around to help you do various things for which the language or your editor/environment aren’t well-equipped. You probably don’t even realize all of the things that bother you about the language after awhile, because it’s the norm: every programmer has to deal with them, it just comes with the territory. Please note: I will be comparing Go to other languages extensively in this blog post; do not take it to be an indictment of them or even, really, as reasons to not use them. I’m simply giving my opinion on their differences and why I personally find that Go is a more suitable language for my development. I have used all of the languages that I discuss and will continue to use them when their particular strengths are required.

Let’s start with Python. I loved my time writing Python, because I felt like I could be really productive. I created a library that my team and I could use to replace huge pieces of boilerplate with a few lines of very terse but legible code. I used just about every new, shiny feature of Python on which I could get my grubby little hands: I used context objects, generators, fancy inheritance and especially I abused the data model in ways that now make me cringe. My code was a pleasure to read and even more of a pleasure to write. It got the job done with a really small amount of code, and my team and managers loved me for how productive I was and how productive I was making my team. What I knew somewhere in the back of my mind but didn’t tell anyone was how horribly painful it was to debug the code written this way. My code reviewers were able to read the code and admit that it looked right, see that the test cases were comprehensive enough and verify that I was covering all of the requirements, but I doubt that they had any idea what was really going on behind-the-scenes or how brittle some of the libraries could be. Since I had written one of the libraries myself and knew most of the nuances of the Python features employed, I was able to debug problems with the library (or my use of it) with relative ease. Unfortunately, it often meant tracing through many layers and scrutinizing pieces of code with a fine-toothed comb to find all of the places where Python was secretly calling (or not calling) out to other pieces of code. Often, it was simply a matter of hiding yet another __special__ function to an object to handle a new use case (for those of you familiar with C++ and the Rule of 3, there needs to be a Python Rule of 17 or something…) that wasn’t already covered. The rest of the team pretty much just used my example code as a template and never ran into these issues, but if they’re still using this particular library I really hope that it’s not causing them more problems than it solved. I’m not even going to get into the various issues that flimsy duck-typing and non-static typing can cause, often a long time after the offending code is written… What remains clear to me is that Python (and langauges like it) are not suitable for large-scale development without very strict adherence to a style guide which precludes almost all of what I described above, and to me that would just take all of the fun out of it.

That, however, is Python, and is the price you expect to pay for such a dynamic language. Even lower-level languages like C and Pascal have their issues. Don’t get me wrong, I absolutely love C and feel like I am a deus intra machinam whenever I write it; I still think it’s the first programming language that a student should learn, and that they shouldn’t be able to move to a higher- or lower-level language until they’ve mastered it. The problem with these languages, especially C, is that you have to take such care when writing and reviewing any significant amount of code that verifying that the code is correct, robust, and has no memory leaks is the next closest thing to impossible. The boilerplate and the bookkeeping that have to be done before you even get to the meat of your application or algorithm are tedious and error-prone in the worst way. There are certainly situations in which such lower-level languages are the only language that can solve your problem, whether it be for performance, real-time/deterministic execution or bare metal proximity reasons, but they just aren’t the most suitable languages for large-scale development.

I’ve also done a bit of graphical (read: drag-and-drop, flow chart) programming, which is interesting to say the least. I won’t go into much detail here, except to say that from my limited exposure, it seems best suited as a special-purpose tool for small- to medium-scale logic at best, and should probably not be used when there are more than a few developers on a particular piece of “code.” It’s fun at first, but the limitations show up fast, and after awhile it seems more tedious, repetitive, and limiting than anything else.

Go even has an adorable mascot

Enter Go. It is a new programming language by pretty much any definition, despite having been in development at Google since 2007 and as an open source project since 2009. It’s a compiled, statically typed, garbage collected language with some cool primitives for concurrency. Despite being compiled and statically typed, it has a very dynamic feel. The syntax has some concise shortcuts to minimize repetition and variable typing. The presence of closures, a garbage collector, and a fairly expansive standard library also contribute to its dynamic feel. These things, coupled with the clarity and explicit nature of Go source code, all help make Go one of the best general purpose languages that I have ever used. I won’t be providing code directly (this blog post is long enough already), but many of the links I provide will be to the documentation or to the relevant portions of the Go Tour, where you can play with the features yourself.

We look forward to the first long-term stable release of the Go standard library and compilers sometime early this year: Go version 1. I’ve been convinced for awhile now that Go is a production-ready language, but in my mind this piece is really the last thing left barring wider adoption. There are some exciting language changes leading up to this Go 1 release, and I am really excited to see what gets done after it is finished. To date, the fast pace at which Go has evolved (both the language and the standard libraries) has posed a challenge for third-party library maintainers, who often have to maintain both a “release” branch of their code and a “weekly” branch due to the rate at which the weekly branch progresses and the relatively high percentage of Go users who are doing their development at (or beyond) the “weekly” branch to take advantage of the new, shiny features or to get the latest bug fixes. With Go 1 this should change, and the number of libraries available to use with a single command (more on that later) will be able to grow even faster.

Why Go?

Compared to most languages in use today, Go was designed with many programmers, concurrent systems, and large-scale problems in mind. Some languages, like C, were simply not designed at a time where multicore and multiprocessor systems were in broad deployment. Some languages, like Python, weren’t originally intended to scale well onto multiple cores and have been slow to adopt strategies for utilizing such resources. Many languages to this day don’t have networking libraries which work predictably and have a clean, understandable API. Programs written in many languages, especially those with operator overloading, require in-depth knowledge of both the architecture of the program itself and the libraries in use in order to be able to understand the code well. Go attempts to address all of these problems and more; in my opinion, it does so brilliantly.

Two of the first things you will hear most people talk about when you hear about Go are channels and goroutines. They’re certainly two of the “shiniest” features of the language, and are the reasons why I tried out Go back in late 2009. They’re far from the biggest reasons why I think you should try Go, but they’re as good a place as any to start.

Channels and Goroutines

These two features are inspired by Hoare’s Communicating Sequential Processes (CSP). A goroutine (similar to a coroutine) is a function that runs independently of the calling function. They’re similar to threads in that a scheduler manages which ones are running at any given time, but they are much lighter-weight than their operating system counterparts. In fact, a Go application with many thousands of goroutines can run comfortably on a single operating system thread.

Channels are a data type in Go which allows for simple, clear communication between goroutines. They are first-class values that have a data type associated with them. Any value of the associated type can be sent over the channel and then received from the channel, usually by another goroutine. They can be passed into functions and goroutines, stored in objects, even sent through other channels.

In most programming languages, when you have multiple threads that need to share data or communicate, you arrange to do so via the use of mutual exclusion locks (mutexes). At first glance, it seems simple: before you access the data you lock it, and when you’re done you unlock it. It gets more complicated very quickly, of course. In Go, a mutex (while available) is not the preferred solution to most problems. As stated in Effective Go, the slogan has become:
Do not communicate by sharing memory; instead, share memory by communicating.Thus instead of using a mutex to protect a shared, global object, you either pass the object around (changing ownership as you do) or you maintain a single owner and all other goroutines access the object by sending requests to that goroutine.

Using these two tools, it turns out to be quite easy to implement solutions to a problem that make logical sense and that very closely reflect the way we might solve the problem in our head. Small, focused pieces of code are concerned with specific aspects of the solution, and are either given their input via the usual way (function parameters) or continually from channels (they also have the same alternatives available for their output). Ownership of data is clear, communication is explicit, the code is highly legible. Such designs are also often easy to unit test; simulating the input and verifying the output via channels is straightforward and very common.

Closures and Deferred Functions

One of the many features of Go that makes it have a very dynamic feel are closures. Like lambdas in python or blocks in ruby, a function can be declared as a local variable or even passed as a literal to a function. All local variables in scope at the closure declaration are also in scope within the closure. They’re powerful tools for functional-style APIs and can be a really fun alternative to (or improvement upon) callbacks. They are also commonly executed directly as a goroutine.

In addition to the “go” directive that runs a function in its own goroutine, Go also has a “defer” directive. When a function (or closure) call is preceded by the “defer,”, the call is evaluated but not executed until just before the function returns. Multiple deferred calls will be executed in reverse order. This turns out to be a very powerful tool for using any object or API which requires cleanup: as soon as you create it or lock it, you can defer the cleanup or unlock. This makes it very easy to spot when you forgot to close a file descriptor or (should you find yourself using one) unlocking a mutex.

These two features provide the ability to confine relevant code all in the same place, which in turn makes reading, debugging, and maintaining the code easier. This is a common theme, and I think was at or near the top of the Go designers’ priority list when designing the language. The concepts are simple, orthogonal, and flexible without sacrificing readability, debuggability, or maintainability.

Interfaces

Interfaces in Go are a welcome twist on a familiar concept. Typically, in a language like Java, interfaces must be explicitly declared by any implementing class. This, of course, means that adding a new interface requires modifying (and having access to modify) all classes that you plan to use in values of that interface type. The paradigm in Go is reversed: instead of defining an interface and declaring all of the objects that satisfy it, the interface is defined and any object which could satisfy the interface can implicitly be used as a value of the interface. This also provides a useful tool, the empty interface, which acts as a container for any possible value (similar to Java’s Object, from which all classes are derived) because all values satisfy it.

In contrast to interfaces in other languages (for instance, in Java), Go interfaces are often very small, and contain one or just a few methods. Because of the presence of such small interfaces in the standard library, they have naturally given rise to some common, idiomatic function names and signatures. Possibly the best examples of these from the standard library are the io.Reader and io.Writer interfaces. Because of the prevalence of objects which implement these two interfaces, stringing together producers and consumers of a data stream is often reminiscent of a unix pipeline. It is simple, for instance, to open a file, unzip it, decrypt its contents, and stream it directly to an HTTP client because all of these interfaces satisfy or consume the above interfaces. Even Go’s version of the old favorite printf can write to any object which satisfies the io.Writer interface, which gives rise to the very concise web-based version of “Hello, World!” in Go.

Simplicity and Explicitness

Some of the best features of Go are, unlike those listed above, not something you’ll find listed in the specification. They probably stem from the guiding philosophy behind its design more than anything else. I think that the simplicity, orthogonality, and explicitness of the features of the Go language make it a prime candidate for a teaching language, especially at the middle- or high-school level.

First, the features of Go are simple and minimal. The entire language specification fits in 45 printed pages. By contrast, the C++ specification clocks in at 750 pages and Javascript has nearly 250. It is short enough that an average programmer can actually read it, understand it, and internalize it in its entirety. This turns out to be quite an asset in a large project setting with multiple developers, each of whom will have a slightly different coding style and may utilize a different different set of features. Being able to understand all of the language features in use, their nuances, and their side effects turns out to be easy in Go when it could be a nearly impossible task in many others.

Second, the features of Go are designed to be orthogonal to one another. When you understand two concepts independently, you understand them together. I have already given one example of this: deferred function calls. If you understand defer (e.g. that it doesn’t make the call immediately, that it evaluates arguments at the defer site, and that it is executed after any subsequent defer calls as the function returns) and you understand closures (that any local variables are in scope, etc), you already understand what happens if you defer a call to a function literal. Compare this to my Python anecdotes earlier, and you’ll find that this is not as ubiquitous a quality as you might expect. There are also a fair number of C++ and Java features that interact non-orthogonally and require some more in-depth understanding (hence the 750-page C++ specification).

Ease of Development

This one is more difficult to quantify. I have found, qualitatively, that writing Go is easier and more fun than pretty much any other language I have used to date. Dynamic languages like Python and Ruby are fun to learn and are fun languages with which to experiment, but I have found that the amount of time spent debugging them (especially when it’s somebody else’s code) takes almost all of the fun out of large project and multi-developer situations. By contrast, languages like C and C++ (and to a somewhat lesser extent, Java) are more painful to write up front but have well-established tools that make analyzing and debugging them a much more pleasant experience. Until I tried Go, I accepted this as the nature of the beast. You just had to to choose. With Go, however, I think the designers managed to strike a balance.

On the development side, I have found that it is easy to translate designs into code. As I mentioned previously, channels and goroutines make it easy to implement your design in pieces that all connect together and communicate. The lack of verbose syntaxes for declarations and the implicit nature of interfaces reduce the amount of arguably unnecessary up-front work. The simplicity of the type system lets you (or forces you to) focus on the implementation instead of fixating on design patterns or type hierarchies. The lack of certain features in the language like operator overloading, destructors, exceptions, and the like all force code to be explicit. An oft-quoted mailing list post by Andrew Gerrand states that “[in] Go, the code does exactly what it says on the page.” Error handling, function calls, math, map/slice access and inter-goroutine communication all look exactly like what they are. When examining a function in isolation, it is a relatively small feat to understand the side-effects of a given statement, which makes the debugging process much more pleasant than in some other languages in which the simplest statement like “a+b” could potentially have unlimited side effects.

Outside of the code itself, there are many benefits to the Go programming language. The standard library is very complete, cohesive, and easy to understand. The third party package ecosystem is nurtured by the Go team, and the standard distribution includes an application called “goinstall” (soon to be bundled into a “go” meta-command) by means of which a package hosted in any web-accessible Git, Mercurial, or Subversion repository can be installed (and any such dependencies, ad infinitum) with a single command. By default, such installations are anonymized and aggregated on a package dashboard, which shows the most- and most-recently installed packages as well as their build status as of the latest release. The standard distribution also includes a formatting tool called “gofmt” which knows how to format a piece of source code according to “Go style,” which reduces or eliminates the need for unproductive debating within a project about things like brace placement or whitespace around operators. There is also a tool called “gofix” which contains modules to automatically fix up any mechanical changes that have been made to the standard library or language between releases (for instance, changing function names, package imports or method signatures) where possible. The last of the tools that I will mention is “godoc,” which is similar to pydoc or javadoc. It uses the comments in the source to provide easily accessible documentation both on the command-line and from a web browser. All of these tools add up to make even the experience of development that doesn’t involve code production as easy as possible.

Summary

Go is an industrial-strength programming language for solving industrial-sized problems. There are many features that I haven’t even touched upon, like the fact that Go is now the third runtime on Google App Engine, which could probably fill another equally long blog post. If you read this far, I hope you at least take the time to take the Go tour or peruse the language specification. Keep an eye out for future projects or tools where you might be able to try out a new language. You may not like it, it may not be accepted in your place of work, or it may simply not be adequate for your needs, but I think that it has the potential to make significant waves in the software industry and I encourage everyone (even if you’ve never programmed before in your life) to give it a shot.

It’s been a long time since I’ve updated this blog, and a completely crazy past few months, so I hope to rectify the former by using the latter as the basis for this post :)

I turned 30 this September, and the force of switching from the deferring-friendly 20’s (‘I can achieve these things, don’t worry, I’m still young’) to the ‘oh shit I’m an adult now’ 30’s has hit harder than I expected (in fact, to be honest, I didn’t expect it at all).

So what’s happened? Well in my personal life, I finally did something about my weight issue and lost ~3.5 stone (~50lb, ~23kg).

In my intellectual/geek life I committed to the open Stanford AI course and completed it with a 98.7% average*, and wrote notes for the purposes of actual applying the course to real things (the notes are not yet fully complete, however I do plan to finish that later), which has really helped with my recently very low intellectual confidence.

Two fundamental things have changed - firstly I’ve got organised about things (for weight loss - food diary, for study - committed, realistic work schedule), secondly and far more importantly, I’ve stopped beating myself up quite as badly about everything. Beating yourself up like that makes you incapable of doing anything since you feel constantly bad about whatever it is you’re doing, and thus reticent to do it, which means you don’t improve/change anything, which means you beat yourself up more, etc. - a vicious, vicious cycle.

Another thing to note here is the amazing usefulness of timeboxing. The past week I have got more hacking done in a week than I have for hundreds of weeks prior.

So what about resolutions? Over the coming year I plan to contribute considerably more to go, and build weak into a fully-fledged chess engine (though I can make no guarantees to its eventual strength) and I intend to work on improving my algorithmic and computer science fundamentals knowledge. On the final bit - I plan to enter the google code jam and blog about the experience, though I don’t expect or predict any sort of performance, it’s more of a motivation and point of focus.

Happy New Year!

* I’m not boasting here. I fell considerably below the performance of many other participants and wish I’d been more careful with many of the answers. Also I realised how rusty I am at this stuff. Also I couldn’t stand to carry on attending the meetup I was attending given how erudite, intelligent and informed the other people were compared to me.

As both of my faithful readers can see, my blog postings have dropped significantly. I’ve been posting my random little comments on Google+ instead.

Which leads me to the following. There is a hard-core group of people who only use free software. I’m not quite that hard-core, but in practice I do use only free software, except perhaps for some binary drivers in the kernel (I don’t actually know whether the systems I’m running use binary drivers or not, and I’m not hard-core enough to find out).

I’ve seen some people argue that if you are serious about using free software, you should also only use Internet services which are themselves free software. For example, you should not use Facebook or Google+, because the software used to run those services is not free.

I don’t agree with that argument. The key goal of free software is that I always have the right to change the software that I am running. When I use an Internet service like Google+, I am not running the software. Even if I had a copy of the software, I would not be able to run it, because I don’t have enough servers. And even if I had enough servers, it would be useless for me to run the software, because I don’t have the data. And there is no way to grant me access to the data, because that would violate the reasonable privacy choices of everybody else using the service.

When it comes to a service like Google+, whether the software is free is not important. Releasing the software would not give me any more freedom than I already have. Google+ is only interesting when many people are operating out of a single shared data base, and that data base must have privacy safeguards to ensure that it is not copied.

What matters with Google+ is not the software, but the data. It is important that I be able to retrieve all my data associated with Google+, and that I be able to retrieve it in a way that makes it possible to use with other software. That is, I should be able to retrieve my posts, my comments on other people’s posts, my list of followers, my photos, etc. And I should be able to plug them into some other software service if I so choose.

In fact Google+ does have a set of APIs which permit me to retrieve my data. I haven’t verified that all Google+ data is available via the APIs, but all the obvious stuff seems to be available. Given those APIs, it should be possible for me to move all my data to some other service which provides te required APIs itself.

So I personally don’t see any reason why even a hard-core free software supporter should avoid using a service like Google+. This isn’t to say that it wouldn’t be nice if Google freed up the software and accepted patches from outside users. It’s just that that is not a critical part of freedom to use software.

My name is Patrick Crosby and I'm the founder of a company called Numerotron. We recently released StatHat. This post is about why we chose to develop StatHat in Go, including details about how we are using Go.

StatHat is a tool to track statistics and events in your code. Everyone from HTML designers to backend engineers can use StatHat easily, as it supports sending stats from HTML, JavaScript, Go, and twelve other languages.

You send your numbers to StatHat; it generates beautiful, fully-embeddable graphs of your data. StatHat will alert you when specified triggers occur, send you daily email reports, and much more. So instead of spending time writing tracking or reporting tools for your application, you can concentrate on the code. While you do the real work, StatHat remains intensely vigilant, like an eagle in its mountaintop nest, or a babysitter on meth.

Here's an example of a StatHat graph of the temperature in NYC, Chicago, and San Francisco:

(click to enlarge)

Architecture Overview

StatHat consists of two main services: incoming statistic/event API calls and the web application for viewing and analyzing stats. We wanted to keep these as separate as possible to isolate the data collection from the data interaction. We did this for many reasons, but one major reason is that we anticipate handling a ton of automated incoming API HTTP requests and would thus have different optimization strategies for the API service than a web application interacting with humans.

The web application service is multi-tiered. The web server processes all requests and sends them to an interactor layer. For simple tasks, the interactor will handle generating any necessary data. For complex tasks, the interactor relies on multiple application servers to handle tasks like generating graphs or analyzing data sets. After the interactor is finished, the web server sends the result to a presenter. The presenter responds to the HTTP request with either HTML or JSON. We can horizontally scale the web, API, application servers, and databases as the demand for services grows and changes over time. There is no single point of failure as each application server has multiple copies running. The interactor layer allows us to have different interfaces to the system: http, command line, automated tests, mobile API. StatHat uses MySQL for data storage.

Choosing Go

When we designed StatHat, we had the following check list for our development tools:

• same programming language for backend and frontend systems
• good, fast HTML templating system
• fast start-up, recompilation, testing for lots of tinkering
• lots of connections on one machine
• language tools for handling application-level concurrency
• good performance
• robust RPC layer to talk between tiers
• lots of libraries
• open source

We evaluated many popular and not-so-popular web technologies and ended up choosing to develop it in Go.

When Go was released in November 2009, I immediately installed it and loved the fast compilation times, goroutines, channels, garbage collection, and all the packages that were available. I was especially pleased with how few lines of code my applications were using. I soon experimented with making a web app called Langalot that concurrently searched through five foreign language dictionaries as you typed in a query. It was blazingly fast. I put it online and it's been running since February, 2010.

The following sections detail how Go meets StatHat's requirements and our experience using Go to solve our problems.

Runtime

We use the standard Go http package for our API and web app servers. All requests first go through Nginx and any non-file requests are proxied to the Go-powered http servers. The backend servers are all written in Go and use the rpc package to communicate with the frontend.

Templating

We built a template system using the standard template package. Our system adds layouts, some common formatting functions, and the ability to recompile templates on-the-fly during development. We are very pleased with the performance and functionality of the Go templates.

Tinkering

In a previous job, I worked on a video game called Throne of Darkness that was written in C++. We had a few header files that, when modified, required a full rebuild of the entire system, 20-30 minutes long. If anyone ever changed `Character.h`, he would be subject to the wrath of every other programmer. Besides this suffering, it also slowed down development time significantly.

Since then, I've always tried to choose technologies that allowed fast, frequent tinkering. With Go, compilation time is a non-issue. We can recompile the entire system in seconds, not minutes. The development web server starts instantly, tests complete in a few seconds. As mentioned previously, templates are recompiled as they change. The result is that the StatHat system is very easy to work with, and the compiler is not a bottleneck.

RPC

Since StatHat is a multi-tiered system, we wanted an RPC layer so that all communication was standard. With Go, we are using the rpc package and the gob package for encoding Go objects. In Go, the RPC server just takes any Go object and registers its exported methods. There is no need for an intermediary interface description language. We've found it very easy to use and many of our core application servers are under 300 lines of code.

Libraries

We don't want to spend time rewriting libraries for things like SSL, database drivers, JSON/XML parsers. Although Go is a young language, it has a lot of system packages and a growing number of user-contributed packages. With only a few exceptions, we have found Go packages for everything we have needed.

Open source

In our experience, it has been invaluable to work with open source tools. If something is going awry, it is immensely helpful to be able to examine the source through every layer and not have any black boxes. Having the code for the language, web server, packages, and tools allows us to understand how every piece of the system works. Everything in Go is open source. In the Go codebase, we frequently read the tests as they often give great examples of how to use packages and language features.

Performance

People rely on StatHat for up to the minute analysis of their data and we need the system to be as responsive as possible. In our tests, Go's performance blew away most of the competition. We tested it against Rails, Sinatra, OpenResty, and Node. StatHat has always monitored itself by tracking all kinds of performance metrics about requests, the duration of certain tasks, the amount of memory in use. Because of this, we were able to easily evaluate different technologies. We've also taken advantage of the benchmark performance testing features of the Go testing package.

Application-Level Concurrency

In a former life, I was the CTO at OkCupid. My experience there using OKWS taught me the importance of async programming, especially when it comes to dynamic web applications. There is no reason you should ever do something like this synchronously: load a user from the database, then find their stats, then find their alerts. These should all be done concurrently, yet surprisingly, many popular frameworks have no async support. Go supports this at the language level without any callback spaghetti. StatHat uses goroutines extensively to run multiple functions concurrently and channels for sharing data between goroutines.

Hosting and Deployment

StatHat runs on Amazon's EC2 servers. Our servers are divided into several types:

• API
• Web
• Application servers
• Database

There are at least two of each type of server, and they are in different zones for high availability. Adding a new server to the mix takes just a couple of minutes.

To deploy, we first build the entire system into a time-stamped directory. Our packaging script builds the Go applications, compresses the CSS and JS files, and copies all the scripts and configuration files. This directory is then distributed to all the servers, so they all have an identical distribution. A script on each server queries its EC2 tags and determines what it is responsible for running and starts/stops/restarts any services. We frequently only deploy to a subset of the servers.

More

For more information on StatHat, please visit stathat.com. We are releasing some of the Go code we've written. Go to www.stathat.com/srcfor all of the open source StatHat projects.

To learn more about Go, visit golang.org.

This article was written by Reinaldo Aguiar, a software engineer from the Search team at Google. He shares his experience developing his first Go program and launching it to an audience of millions - all in one day!

I was recently given the opportunity to collaborate on a small but highly visible "20% project": the Thanksgiving 2011 Google Doodle. The doodle features a turkey produced by randomly combining different styles of head, wings, feathers and legs. The user can customize it by clicking on the different parts of the turkey. This interactivity is implemented in the browser by a combination of JavaScript, CSS and of course HTML, creating turkeys on the fly.

Once the user has created a personalized turkey it can be shared with friends and family by posting to Google+. Clicking a "Share" button (not pictured here) creates in the user's Google+ stream a post containing a snapshot of the turkey. The snapshot is a single image that matches the turkey the user created.

With 13 alternatives for each of 8 parts of the turkey (heads, pairs of legs, distinct feathers, etc.) there are more than than 800 million possible snapshot images that could be generated. To pre-compute them all is clearly infeasible. Instead, we must generate the snapshots on the fly. Combining that problem with a need for immediate scalability and high availability, the choice of platform is obvious: Google App Engine!

The next thing we needed to decide was which App Engine runtime to use. Image manipulation tasks are CPU-bound, so performance is the deciding factor in this case.

To make an informed decision we ran a test. We quickly prepared a couple of equivalent demo apps for the new Python 2.7 runtime (which provides PIL, a C-based imaging library) and the Go runtime. Each app generates an image composed of several small images, encodes the image as a JPEG, and sends the JPEG data as the HTTP response. The Python 2.7 app served requests with a median latency of 65 milliseconds, while the Go app ran with a median latency of just 32 milliseconds.

This problem therefore seemed the perfect opportunity to try the experimental Go runtime.

I had no previous experience with Go and the timeline was tight: two days to be production ready. This was intimidating, but I saw it as an opportunity to test Go from a different, often overlooked angle: development velocity. How fast can a person with no Go experience pick it up and build something that performs and scales?

Design

The approach was to encode the state of the turkey in the URL, drawing and encoding the snapshot on the fly.

The base for every doodle is the background:

A valid request URL might look like this: http://google-turkey.appspot.com/thumb/20332620

The alphanumeric string that follows "/thumb/" indicates (in hexadecimal) which choice to draw for each layout element, as illustrated by this image:

The program's request handler parses the URL to determine which element is selected for each component, draws the appropriate images on top of the background image, and serves the result as a JPEG.

If an error occurs, a default image is served. There's no point serving an error page because the user will never see it - the browser is almost certainly loading this URL into an image tag.

Implementation

In the package scope we declare some data structures to describe the elements of the turkey, the location of the corresponding images, and where they should be drawn on the background image.

var (
    // dirs maps each layout element to its location on disk.
    dirs = map[string]string{
        "h": "img/heads",
        "b": "img/eyes_beak",
        "i": "img/index_feathers",
        "m": "img/middle_feathers",
        "r": "img/ring_feathers",
        "p": "img/pinky_feathers",
        "f": "img/feet",
        "w": "img/wing",
    }

    // urlMap maps each URL character position to
    // its corresponding layout element.
    urlMap = [...]string{"b", "h", "i", "m", "r", "p", "f", "w"}

    // layoutMap maps each layout element to its position
    // on the background image.
    layoutMap = map[string]image.Rectangle{
        "h": {image.Pt(109, 50), image.Pt(166, 152)},
        "i": {image.Pt(136, 21), image.Pt(180, 131)},
        "m": {image.Pt(159, 7), image.Pt(201, 126)},
        "r": {image.Pt(188, 20), image.Pt(230, 125)},
        "p": {image.Pt(216, 48), image.Pt(258, 134)},
        "f": {image.Pt(155, 176), image.Pt(243, 213)},
        "w": {image.Pt(169, 118), image.Pt(250, 197)},
        "b": {image.Pt(105, 104), image.Pt(145, 148)},
    }
)

The geometry of the points above was calculated by measuring the actual location and size of each layout element within the image.

Loading the images from disk on each request would be wasteful repetition, so we load all 106 images (13 * 8 elements + 1 background + 1 default) into global variables upon receipt of the first request.

var (
    // elements maps each layout element to its images.
    elements = make(map[string][]*image.RGBA)

    // backgroundImage contains the background image data.
    backgroundImage *image.RGBA

    // defaultImage is the image that is served if an error occurs. 
    defaultImage *image.RGBA

    // loadOnce is used to call the load function only on the first request.
    loadOnce sync.Once
)

// load reads the various PNG images from disk and stores them in their
// corresponding global variables.
func load() {
    defaultImage = loadPNG(defaultImageFile)
    backgroundImage = loadPNG(backgroundImageFile)
    for dirKey, dir := range dirs {
        paths, err := filepath.Glob(dir + "/*.png")
        if err != nil {
            panic(err)
        }
        for _, p := range paths {
            elements[dirKey] = append(elements[dirKey], loadPNG(p))
        }
    }
}

Requests are handled in a straightforward sequence:

1. Parse the request URL, decoding the decimal value of each character in the path.
2. Make a copy of the background image as the base for the final image.
3. Draw each image element onto the background image using the layoutMap to determine where they should be drawn.
4. Encode the image as a JPEG
5. Return the image to user by writing the JPEG directly to the HTTP response writer.

Should any error occur, we serve the defaultImage to the user and log the error to the App Engine dashboard for later analysis.

Here's the code for the request handler with explanatory comments:

func handler(w http.ResponseWriter, r *http.Request) {
    // Defer a function to recover from any panics.
    // When recovering from a panic, log the error condition to
    // the App Engine dashboard and send the default image to the user.
    defer func() {
        if err := recover(); err != nil {
            c := appengine.NewContext(r)
            c.Errorf("%s", err)
            c.Errorf("%s", "Traceback: %s", r.RawURL)
            if defaultImage != nil {
                w.Header().Set("Content-type", "image/jpeg")
                jpeg.Encode(w, defaultImage, &imageQuality)
            }
        }
    }()

    // Load images from disk on the first request.
    loadOnce.Do(load)

    // Make a copy of the background to draw into.
    bgRect := backgroundImage.Bounds()
    m := image.NewRGBA(bgRect.Dx(), bgRect.Dy())
    draw.Draw(m, m.Bounds(), backgroundImage, image.ZP, draw.Over)

    // Process each character of the request string.
    code := strings.ToLower(r.URL.Path[len(prefix):])
    for i, p := range code {
        // Decode hex character p in place.
        if p < 'a' {
            // it's a digit
            p = p - '0'
        } else {
            // it's a letter
            p = p - 'a' + 10
        }

        t := urlMap[i]    // element type by index
        em := elements[t] // element images by type
        if p >= len(em) {
            panic(fmt.Sprintf("element index out of range %s: "+
                "%d >= %d", t, p, len(em)))
        }

        // Draw the element to m,
        // using the layoutMap to specify its position.
        draw.Draw(m, layoutMap[t], em[p], image.ZP, draw.Over)
    }

    // Encode JPEG image and write it as the response.
    w.Header().Set("Content-type", "image/jpeg")
    w.Header().Set("Cache-control", "public, max-age=259200")
    jpeg.Encode(w, m, &imageQuality)
}

For brevity, I've omitted several helper functions from these code listings. See the source code for the full scoop.

Performance

This chart - taken directly from the App Engine dashboard - shows average request latency during launch. As you can see, even under load it never exceeds 60 ms, with a median latency of 32 milliseconds. This is wicked fast, considering that our request handler is doing image manipulation and encoding on the fly.

Conclusions

I found Go's syntax to be intuitive, simple and clean. I have worked a lot with interpreted languages in the past, and although Go is instead a statically typed and compiled language, writing this app felt more like working with a dynamic, interpreted language.

The development server provided with the SDK quickly recompiles the program after any change, so I could iterate as fast as I would with an interpreted language. It's dead simple, too - it took less than a minute to set up my development environment.

Go's great documentation also helped me put this together fast. The docs are generated from the source code, so each function's documentation links directly to the associated source code. This not only allows the developer to understand very quickly what a particular function does but also encourages the developer to dig into the package implementation, making it easier to learn good style and conventions.

In writing this application I used just three resources: App Engine's Hello World Go example, the Go packages documentation, and a blog post showcasing the Draw package. Thanks to the rapid iteration made possible by the development server and the language itself, I was able to pick up the language and build a super fast, production ready, doodle generator in less than 24 hours.

Download the full app source code (including images) at the Google Code project.

Special thanks go to Guillermo Real and Ryan Germick who designed the doodle.

(I don't have comments on this blog, but you can comment on my Google+ post.)

Ben Laurie and I have been working on a longer term plan for improving the foundations of the certificate infrastructure on which most Internet transport security is based on these days. Although Chrome has public key pinning for some domains, which limits the set of permitted certificates, we don't see public key pinning as a long term solution (and nor was it ever designed to be).

For the 10 second summary of the plan, I'll quote Ben: “certificates are registered in a public audit log. Servers present proofs that their certificate is registered, along with the certificate itself. Clients check these proofs and domain owners monitor the logs.”. I would add only that anyone can check the logs: the certificate infrastructure would be fully transparent.

We now have an outline of the basic idea and will be continuing to flesh it out in the coming months, hopefully in conjunction with other browser vendors.

But I thought that, at the outset, it would be helpful to describe some of the limitations to the design space, as I see them:

No side-channels

As I've previously described, side-channels occur when a browser needs to contact a server other than the immediate destination in order to verify a certificate. Revocation checking with OCSP is an example of a side-channel used today.

But in order to be effective, side-channels invariably need to block the certificate verification until they complete, and that's a big problem. The Internet isn't fully connected. Captive portals, proxies and firewalls all mean that the only thing you can really depend on talking to is the immediate destination server. Because of this, browsers have never been able to make OCSP lookups blocking, and therefore OCSP is basically useless for security.

And that's not to mention the privacy, performance and functionality issues that arise from needing side-channels. (What happens when the side-channel server goes down?)

So our design requires that the servers send us the information that we require. We can use side-channels to check up on the logs, but it's an asynchronous lookup.

It's not opt-in, it's all-in

SSL Stripping is a very easy and very effective attack. HSTS prevents it and is as easy to deploy as anything can be for HTTPS sites. But, despite all this, and despite a significant amount of evangelism, take up has been very limited, even by sites which are HTTPS only and the subject of attacks.

While HSTS really has to be opt-in, a solution to the certificate problem doesn't. Although our scheme is incrementally deployable, the eventual aim is that it's required for everybody. Thankfully, since certificates have to be renewed there's an obvious means to incrementally deploy it: require it for certificates issued after a certain date. Although an eventual hard requirement is still needed, it's a lot less of a problem.

It's easy on the server operator

Since the aim is to make it a requirement for all servers, we've sacrificed a lot in order to make it very easy on the server operator. For most server operators, their CA will probably take care of fetching the audit proofs, meaning there's no additional work at all.

Some initial designs included short-lived log signatures, which would have solved the revocation problem. (Revocation would simply be a matter of instructing the logs to stop signing a given certificate.) However, this would have required server operators to update their audit proofs on a near-daily basis. After discussions it became clear that such a requirement wouldn't be tenable for many and so we reluctantly dropped it.

We are also sacrificing decentralisation to make things easy on the server. As I've previously argued, decentralisation isn't all it's cracked up to be in most cases because 99.99% of people will never change any default settings, so we haven't given up much. Our design does imply a central set of trusted logs which is universally agreed. This saves the server from possibly having to fetch additional audit proofs at runtime, something which requires server code changes and possible network changes.

There are more valid certificates than the one that's currently serving

Cheap virtual hosting and EC2 have made multi-homed services common. Even small to medium scale sites have multiple servers these days. So any scheme that asserts that the currently serving certificate is the only valid certificate will run into problems when certificates change. Unless all the servers are updated at exactly the same time, then users will see errors during the switch. These schemes also make testing a certificate with a small number of users impossible.

In the end, the only real authority on whether a certificate is valid is the site itself. So we don't rely on external observations to decide on whether a certificate is valid, instead to seek to make the set of valid certificates for a site public knowledge (which it currently isn't), so that the site can determine whether it's correct.

It's not easy to do

We believe that this design will have a significant, positive impact on an important part of Internet security and that it's deployable. We also believe that any design that shares those two properties ends up looking a lot like it. (It's no coincidence that we share several ideas with the EFF's Sovereign Keys.)

None the less, deployment won't be easy and, hopefully, we won't be pushing it alone.

As announced on the Google Security Blog, Google HTTPS sites now support forward secrecy. What this means in practice is two things:

Firstly, the preferred cipher suite for most Google HTTPS servers is ECDHE-RSA-RC4-SHA. If you have a client that supports it, you'll be using that ciphersuite. Chrome and Firefox, at least, support it.

Previously we were using RSA-RC4-SHA, which means that the client (i.e. browser) picks a random key for the session, encrypts it with the server's public key and sends it to the server. Since only the holder of the private key can decrypt the session key, the connection is secure.

However, if an attacker obtains the private key in the future then they can decrypt recorded traffic. The encrypted session key can be decrypted just as well in ten years time as it can be decrypted today and, in ten years time, the attacker has much more computing power to break the server's public key. If an attacker obtains the private key, they can decrypt everything encrypted to it, which could be many months of traffic.

ECDHE-RSA-RC4-SHA means elliptic curve, ephemeral Diffie-Hellman, signed by an RSA key. You can see a previous post about elliptic curves for an introduction, but the use of elliptic curves is an implementation detail.

Ephemeral Diffie-Hellman means that the server generates a new Diffie-Hellman public key for each session and signs the public key. The client also generates a public key and, thanks to the magic of Diffie-Hellman they both generate a mutual key that no eavesdropper can know.

The important part here is that there's a different public key for each session. If the attacker breaks a single public key then they can decrypt only a single session. Also, the elliptic curve that we're using (P-256) is estimated to be as strong as a 3248-bit RSA key (by ECRYPT II), so it's unlikely that the attacker will ever be able to break a single instance of it without a large, quantum computer.

While working on this, Bodo Möller, Emilia Kasper and I wrote fast, constant-time implementations of P-224, P-256 and P-521 for OpenSSL. This work has been open-sourced and submitted upstream to OpenSSL. We also fixed several bugs in OpenSSL's ECDHE handling during deployment and those bug fixes are in OpenSSL 1.0.0e.

Session Tickets

The second part of forward secrecy is dealing with TLS session tickets.

Session tickets allow a client to resume a previous session without requiring that the server maintain any state. When a new session is established the server encrypts the state of the session and sends it back to the client, in a session ticket. Later, the client can echo that encrypted session ticket back to the server to resume the session.

Since the session ticket contains the state of the session, and thus keys that can decrypt the session, it too must be protected by ephemeral keys. But, in order for session resumption to be effective, the keys protecting the session ticket have to be kept around for a certain amount of time: the idea of session resumption is that you can resume the session in the future, and you can't do that if the server can't decrypt the ticket!

So the ephemeral, session ticket keys have to be distributed to all the frontend machines, without being written to any kind of persistent storage, and frequently rotated.

Result

We believe that forward secrecy provides a fairly significant benefit to our users and we've contributed our work back to OpenSSL in the hope that others will make use of it.

Generics in Go - A proposal for Generic Types in the Go language

I won’t bore you with the details here; read the PDF for those. Here are some examples to whet your appetite.

A somewhat comprehensive example:

// Package gen provides some example generic functionality.
package gen

// Generic types for this package
type Value generic
type Result generic
type ReduceFunc func(Result, Value) Result

// Tern is the ternary operator: Tern(cond,t,f) == (cond?t:f)
func Tern(cond bool, t, f Value) Value {
  if cond {
    return t
  }
  return f
}

// Reduce returns the result of running the ReduceFunc on each successive value
// in list along with the last result.
func (red ReduceFunc) Reduce(r0 Result, list ...Value) Result {
  for _, v := range list {
    r0 = red(r0, v)
  }
  return r0
}

// Check strips out the os.Error return from a function call for use inline.
func Check(val Value, err os.Error) Value {
  if err != nil {
    panic(err)
  }
  return val
}

Using that package:

package main

import (
  "fmt"
  "gen"
  "strconv"
)

func main() {
  add := gen.ReduceFunc(func(x0 int, x1 string) int {
    return x0 + gen.Check(strconv.Atoi(x1))
  })

	nums := os.Args[1:]
  fmt.Printf("Sum of your %s: %v\n",
    "number" + gen.Tern(len(nums)==1, "", "s"),
    add.Reduce(0, os.Args))
}

Everybody’s favorite generic interface:

type Value generic
type Equaler interface {
  Equals(other Value) bool
}

// Integer implements Equaler.
type Integer int
func (i Integer) Equals(j Integer) bool {
	return i == j
}

// Compile-time check.
var _ Equaler = Integer(0)

// Search returns the index of the first element for which list[idx].Equal(val)
// returns true.
func Search(list []Equaler, val Value) int {
  for i, v := range list {
    if v.Equal(val) {
      return i
    }
  }
  return -1
}

The proposal’s source can be found on github.

The Go Authors went on to produce lots of libraries, new tools, and reams of documentation. They celebrated a successful year in the public eye with a blog post last November that concluded "Go is certainly ready for production use, but there is still room for improvement. Our focus for the immediate future is making Go programs faster and more efficient in the context of high performance systems."

Today is the second anniversary of Go's release, and Go is faster and more stable than ever. Careful tuning of Go's code generators, concurrency primitives, garbage collector, and core libraries have increased the performance of Go programs, and native support for profiling and debugging makes it easier to detect and remove performance issues in user code. Go is also now easier to learn with A Tour of Go, an interactive tutorial you can take from the comfort of your web browser.

This year we introduced the experimental Go runtime for Google's App Engine platform, and we have been steadily increasing the Go runtime's support for App Engine's APIs. Just this week we released version 1.6.0 of the Go App Engine SDK, which includes support for backends (long-running processes), finer control over datastore indexes, and various other improvements. Today, the Go runtime is near feature parity with - and is a viable alternative to - the Python and Java runtimes. In fact, we now serve golang.org by running a version of godoc on the App Engine service.

While 2010 was a year of discovery and experimentation, 2011 was a year of fine tuning and planning for the future. This year we issued several "release" versions of Go that were more reliable and better supported than weekly snapshots. We also introduced gofix to take the pain out of migrating to newer releases. Furthermore, last month we announced a plan for Go version 1 - a release that will be supported for years to come. Work toward Go 1 is already underway and you can observe our progress by the latest weekly snapshot at weekly.golang.org.

The plan is to launch Go 1 in early 2012. We hope to bring the Go App Engine runtime out of "experimental" status at the same time.

But that's not all. 2011 was an exciting year for the gopher, too. He has manifested himself as a plush toy (a highly prized gift at Google I/O and other Go talks) and in vinyl form (received by every attendee at OSCON and now available at the Google Store).

And, most surprisingly, at Halloween he made an appearance with his gopher girlfriend!

Photograph by Chris Nokleberg.

This post might be about a worker synchronization idiom—whatever an idiom is.  I don’t know.  Is it a way to solve a common problem in a particular language?  I don’t even know if idioms are good or bad.

Anyway, suppose you have a data structure and you want to let multiple workers concurrently read from it and, each doing things slightly differently, compute independent results.  The workers all need to see the entire data structure, but that’s okay because the data isn’t changing during this read and compute phase.  The results need to be combined and reduced.  When all the results are in and reduced, the result is used to update the shared data structure.  Then it all needs to be repeated for some number of iterations.  Is this common?  Are there physical simulations or stochastic algorithms that are like this?  I would think so.

I know, it’s not sounding like idiomatic Go.  It’s communicating by sharing memory.  But still, if it’s a common thing and there’s a way to do it in the language, isn’t that an idiom?  (Maybe it’s a bad idiom.  Then, I’ve heard people say all idioms are bad.  Maybe it’s a good idiom for doing a bad thing…)  Sometimes though, you have an existing algorithm and you want to follow it, even if it does communicate by sharing memory.

The important feature of the algorithm seemed to be the checkpoints (or barriers or whatever) that separate the phases.

Initialization | processing | update | processing | update | …

• Initialization is a single thread that sets up the shared data.
• Processing involves multiple concurrent workers, and can only start after initialization is complete.
• Update is a single thread again and can only start after all workers rendezvous.
• The next iteration of processing can only start after the update is complete.

It’s not too hard, and surely, like exercise #69 (it seems to be #70 now) there must be lots of ways to do it.  Before showing my complete program though, I tried reducing it to a minimal program that would show the just synchronization without the clutter of everything else.  It was at that point that the problem struck me as analogous to a horse race.

Initialization is like getting the track groomed and everything all set up.  It has to happen without the horses running around.  There is just one track.  It is shared.  To keep the horses from starting, there is a gate that holds them.  They all wait at the gate until the gate opens and lets them run.  Then they all begin to run concurrently.  They finish at different times and some data is recorded.  At some point, the gates must close in preparation for the next race.

package main

import (
    "fmt"
    "math/rand"
    "sync"
    "time"
)

var horses = []string{"pie", "biscuit", "lap", "derpy"}

const nRaces =  4

var startSignal, gates sync.WaitGroup
var finish = make(chan string, len(horses))

func main() {
    startSignal.Add(1)
    for _, name := range horses {
        go horse(name)
    }

    places := make([]string, len(horses))

    for r := 1; r <= nRaces; r++ {
        gates.Add(len(horses))
        startSignal.Done()
        gates.Wait()
        startSignal.Add(1)

        for i := range horses {
            places[i] = <-finish
        }
        fmt.Println("race", r, places)
    }
}

func horse(horseName string) {
    rnd := rand.New(rand.NewSource(time.Nanoseconds()))
    for {
        // wait for start signal
        startSignal.Wait()
        gates.Done()

        // do something
        time.Sleep(9e7+rnd.Int63n(2e7))

        // return result
        finish <- horseName
    }
}

Example output:

race 1 [lap derpy biscuit pie]
race 2 [derpy pie biscuit lap]
race 3 [biscuit derpy lap pie]
race 4 [biscuit derpy pie lap]

It seems a little clunky and mousetrap-like, but I think that might just be the nature of communicating by sharing memory. Results are gathered with a channel in the usual way, and then I use two WaitGroups to implement the latch mechanism of the starting gate. startSignal is binary and is a 1 to N broadcast. All of the horses wait on it to fall to zero, implementing the starting gates opening. Then there is the problem of setting it back to 1 for the start of the next race. It needs to be done before the first horse finishes, or else the horse will find the gate open and begin to run again. It cannot be done immediately on the next line of code however, because that leads to the gate snapping shut before some of the horses have had a chance to leave. The solution was a a separate WaitGroup, this one used in the more common N to 1 mode indicating when each goroutine has completed the step of the horse leaving the gate.

Finally now, the fun program. It’s still just a toy problem, but I coded up an ant colony solution” of the knight’s tour problem as described by Philip Hingston and Graham Kendall. It was fun to reproduce their results and get the same number for cumulative production rate. (Although I couldn’t figure out what they were doing to get the .09 number for mean production rate.

package main

import (
    "fmt"
    "math/rand"
    "sync"
    "time"
)

const boardSize = 8
const nSquares = boardSize * boardSize
const completeTour = nSquares - 1
const cycles = 27000

// pheromone representation read by ants
var tNet = make([]float64, nSquares*8)

// row, col deltas of legal moves
var drc = [][]int{{1, 2}, {2, 1}, {2, -1}, {1, -2},
    {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}

// get square reached by following edge k from square (r, c)
func dest(r, c, k int) (int, int, bool) {
    r += drc[k][0]
    c += drc[k][1]
    return r, c, r >= 0 && r < boardSize && c >= 0 && c < boardSize
}

// struct represents a pheromone amount associated with a move
type rckt struct {
    r, c, k int
    t       float64
}

func main() {
    // waitGroups for ant release clockwork
    var start, reset sync.WaitGroup
    start.Add(1)
    // channel for ants to return tours with pheromone updates
    tch := make(chan []rckt)

    // create an ant for each square
    for r := 0; r < boardSize; r++ {
        for c := 0; c < boardSize; c++ {
            go ant(r, c, &start, &reset, tch)
        }
    }

    // accumulator for new pheromone amounts
    tNew := make([]float64, nSquares*8)

    // map for collecting set of complete tours
    allUnique := make(map[string]int)
    tbuf := make([]byte, 2+completeTour) // for building map key

    // heading
    fmt.Println("Board size:", boardSize)
    fmt.Println("Cycles per repeat:", cycles)
    fmt.Println("          Unique                        Production   Cumm.")
    fmt.Println("        complete     Cumm.      Total   rate         prod.")
    fmt.Println("Repeat     tours    unique   attempts   this repeat  rate")

    // each iteration is a "repeat" as described in the paper
    for repeat := 1; ; repeat++ {
        unique := make(map[string]int) // complete tours this repeat

        // initialize board
        for r := 0; r < boardSize; r++ {
            for c := 0; c < boardSize; c++ {
                for k := 0; k < 8; k++ {
                    if _, _, ok := dest(r, c, k); ok {
                        tNet[(r*boardSize+c)*8+k] = 1e-6
                    }
                }
            }
        }

        // each iteration is a "cycle" as described in the paper
        for i := 0; i < cycles; i++ {
            // evaporate pheromones
            for i := range tNet {
                tNet[i] *= .75
            }

            reset.Add(nSquares) // number of ants to release
            start.Done()        // release them
            reset.Wait()        // wait for them to begin searching
            start.Add(1)        // reset start signal for next cycle

            // gather tours from ants
            for i := 0; i < nSquares; i++ {
                tour := <-tch
                // accumulate complete tours
                if len(tour) == completeTour {
                    tbuf[0] = byte(tour[0].r)
                    tbuf[1] = byte(tour[0].c)
                    for i, m := range tour {
                        tbuf[i+2] = byte(m.k)
                    }
                    key := string(tbuf)
                    unique[key] = 1
                    allUnique[key] = 1
                }
                // accumulate pheromone amounts from all ants
                for _, move := range tour {
                    tNew[(move.r*boardSize+move.c)*8+move.k] += move.t
                }
            }

            // update pheromone amounts on network, reset accumulator
            for i, tn := range tNew {
                tNet[i] += tn
                tNew[i] = 0
            }
        }

        // print statistics
        //  fmt.Println("          Unique                        Production   Cumm.")
        //  fmt.Println("        complete     Cumm.       Total   rate         prod.")
        //  fmt.Println("Repeat     tours    unique    attempts   this repeat  rate")
        fmt.Printf("%6d %9d %9d %10d   %6.4f       %6.4f\n",
            repeat, len(unique), len(allUnique), repeat*cycles*nSquares,
            float64(len(unique))/float64(cycles*nSquares),
            float64(len(allUnique))/float64(repeat*cycles*nSquares))
    }
}

func printTour(tour []rckt) {
    seq := make([]int, nSquares)
    for i, sq := range tour {
        seq[sq.r*boardSize+sq.c] = i + 1
    }
    last := tour[len(tour)-1]
    r, c, _ := dest(last.r, last.c, last.k)
    seq[r*boardSize+c] = nSquares
    fmt.Println("Move sequence:")
    for r := 0; r < boardSize; r++ {
        for c := 0; c < boardSize; c++ {
            m := seq[r*boardSize+c]
            if m > 0 {
                fmt.Printf(" %3d", seq[r*boardSize+c])
            } else {
                fmt.Print("    ")
            }
        }
        fmt.Println()
    }
}

type square struct {
    r, c int
}

func ant(r, c int, start, reset *sync.WaitGroup, tourCh chan []rckt) {
    rnd := rand.New(rand.NewSource(time.Nanoseconds()))
    tabu := make([]square, nSquares)
    moves := make([]rckt, nSquares)
    unexp := make([]rckt, 8)
    tabu[0].r = r
    tabu[0].c = c

    for {
        // cycle initialization
        moves = moves[:0]
        tabu = tabu[:1]
        r := tabu[0].r
        c := tabu[0].c

        // wait for start signal
        start.Wait()
        reset.Done()

        for {
            // choose next move
            unexp = unexp[:0]
            var tSum float64
        findU:
            for k := 0; k < 8; k++ {
                dr, dc, ok := dest(r, c, k)
                if !ok {
                    continue
                }
                for _, t := range tabu {
                    if t.r == dr && t.c == dc {
                        continue findU
                    }
                }
                tk := tNet[(r*boardSize+c)*8+k]
                tSum += tk
                // note:  dest r, c stored here
                unexp = append(unexp, rckt{dr, dc, k, tk})
            }
            if len(unexp) == 0 {
                break // no moves
            }
            rn := rnd.Float64() * tSum
            var move rckt
            for _, move = range unexp {
                if rn <= move.t {
                    break
                }
                rn -= move.t
            }

            // move to new square
            move.r, r = r, move.r
            move.c, c = c, move.c
            tabu = append(tabu, square{r, c})
            moves = append(moves, move)
        }

        // compute pheromone amount to leave
        for i := range moves {
            moves[i].t = float64(len(moves)-i) / float64(completeTour-i)
        }

        // return tour found for this cycle
        tourCh <- moves
    }
}

Output:

Board size: 8
Cycles per repeat: 27000
          Unique                        Production   Cumm.
        complete     Cumm.      Total   rate         prod.
Repeat     tours    unique   attempts   this repeat  rate
     1    176027    176027    1728000   0.1019       0.1019
     2    172491    348518    3456000   0.0998       0.1008
     3    201836    550354    5184000   0.1168       0.1062
     4    104574    654928    6912000   0.0605       0.0948
     5    117130    772058    8640000   0.0678       0.0894
...
    95    193387  12424890  164160000   0.1119       0.0757
    96     37647  12462537  165888000   0.0218       0.0751
    97    121887  12584424  167616000   0.0705       0.0751
    98    145072  12729496  169344000   0.0840       0.0752
    99    162658  12892154  171072000   0.0941       0.0754
   100    206599  13098753  172800000   0.1196       0.0758

There is no chance that Edward de Vere, the Earl of Oxford, wrote the plays attributed to William Shakespeare.

That said, I found the movie Anonymous to be reasonably watchable, although I thought many of Vanessa Redgrave’s scenes as the older Queen Elizabeth were ridiculous. But since the movie claims (perhaps as a joke) to be seriously advocating the position that Oxford wrote the plays, I was surprised that they did such a poor job of supporting the theory.

Oxford was shown as being tutored at length on topics other than poetry. He traveled abroad, he intrigued at court. When would he have had time to write the plays and the sonnets? The movie essentially presents Oxford as being mysterious gifted by the ability to write; he speaks of continual voices in his head. That could happen to anybody, and perhaps describes the real Shakespeare–if anybody could have written Shakespeare’s plays, then why not Shakespeare himself?

Oxford is shown as using the plays to support his court intrigues. Is it possible to imagine Shakespeare, with his clear vision of humanity, thinking that he could achieve such ends through his plays? One of the strongest examples of that in the movie was the suggestion that it was odd that Shakespeare portrayed Richard III as a hunchback, but even I know that Richard III was popularly (and probably falsely) considered to be a hunchback long before Shakespeare’s time.

Of course it’s conceivable if unlikely that somebody else wrote Shakepeare’s plays. But the undercurrent of the Oxford theory has always been that a member of the nobility would be more likely as the playwright than a commoner. But this reverses reality. The nobility were highly trained from birth in their roles in society. They were busy people with lots to do. It was far less likely that an earl could write the plays than a member of the middle class. As far as I know only one member of the English nobility ever achieved any note as an author: Lord Dunsany, who lived much later.

The movie did have a couple of nice (non-Shakespearean) lines, one of which, by the Ben Jonson character, was simply the truth: the only reason future ages remember the people who lived then was because they were alive when Shakespeare was writing.

One of the key benefits of the Go runtime, apart from working in a fantastic language, is that it has high performance. Go applications compile to native code, with no interpreter or virtual machine getting between your program and the machine.

Making your web application fast is important because it is well known that a web site's latency has a measurable impact on user happiness, and Google web search uses it as a ranking factor. Also announced in May was that App Engine would be leaving its Preview status and transitioning to a new pricing model, providing another reason to write efficient App Engine applications.

To make it easier for Go developers using App Engine to write highly efficient, scalable applications, we recently updated some existing App Engine articles to include snippets of Go source code and to link to relevant Go documentation.

• Best practices for writing scalable applications
• Managing Your App's Resource Usage

Among the improvements are the ability to inspect goroutines and to print native Go data types, including structs, slices, strings, maps, interfaces, and channels.

To learn more about Go and GDB, see the Debugging with GDB article.

After writing my last post, I again worked my arse off this week to study both the Stanford AI and ML classes in a less crunchy fashion than the week before. Unfortunately the crunch avoidance did not come to pass and I was up until 3am this morning (well, 2am if you take into account the clocks going back :-) cramming on AI.

Since I actually want to learn about AI (and apply it to weak) I am not finding this cramming aspect of the study particularly beneficial. In my experience, cramming simply wears you out and gets you ready for a given short-term task (e.g. homework, later exams) before the information you’ve learned largely plops out of your brain.

For that reason, and for the sake of keeping this doable, I’ve decided to drop the machine learning course and focus fully on AI. There is an irony in that - I have found the AI work to be considerably more involved and challenging than machine learning (that’s not a comment on the relative quality of one course vs. the other by the way), however a. AI is of more relevance to what I want to do, and b. focusing on one thing reduces the stressful feeling of distraction that maintaing another course which requires homework, etc. brings.

I am still very interested in machine learning, so I might very well go over the machine learning course material at a later date. Additionally, the AI course contains some cross-over material so I won’t do entirely without.

Another aspect is that I would like to maintain my notes to a better standard than I have (and which more time would allow me to achieve), rather than having to rush them out because of time constraints. There are almost certainly better notes for the course out there, however there is nothing quite like having a set of notes to refer to you which you’ve written in your own style and to your own tastes. Not invented here syndrome, perhaps!

Meta-Blog Tediousness

On an entirely different subject, you may have noticed I’ve deleted a number of posts. This is because I felt they were of little value and often quite negative. This blog is meant to be a diary of where I’m at in my tech life, and yes that involves both positive and negative, however there is nothing more tedious than wading through either rather mediocre technical posts, or moany personal ones. I’d like to maximise the chances of me (and to some degree others of course :-) actually enjoying reading this blog.

I can only apologise to those few whose comments have consequently been deleted from this site. Hopefully you can understand why I’ve done it.

The lure of Sprint was too strong to pass up, but ultimately ended in letdown and abandon.

Sprint's pitch was simple. Where else can you get an all you can eat data plan and ample minutes for $75.00 including the government’s taxation scheme that Karl Marx would be proud of? Done. Sign me up.

Choosing a phone for Sprint's network was not as easy. They offer three compelling choices.

First, you can speak random thoughts of consciousness in a Sprint store, and if a customer has pressed the Siri button on the display model iPhone 4s, you'll likely get verbal confirmation to choose it.

For those flirting with escape from Jobs’ utopia, the gorilla glass encased false god of Android is eager to entice, with a Samsung Galaxy S II. Like a hollywood celeb it's light weight and beautiful. 

But for some, age brings truth, hence the third option, a year old Samsung Nexus S anointed with the purity of plain Gingerbread. I chose this option.

Despite the sweetness of Gingerbread, there is nothing tasty about Samsung’s Nexus S. Extremely poor antennas for wifi, 3g and 4g? Check. A battery that can’t last ½ day with light to moderate use? Check. Screen jitter while scrolling through your twitter feed? Check.

Needless to say the phone went back to the Sprint store. This left two choices left. The iPhone 4s and the Galaxy S II. I opted with the Galaxy S II.

The Galaxy S II represents everything that is right and wrong about Android, the device manufacturers, and the carriers.

On the Galaxy S II, gone is the jerky scrolling of the Nexus S. The screen is vibrant and huge. Samsung retained its use of a plastic enclosure, yet improved its sturdiness, a move that makes the device feel better quality. The antennas are dramatically better, resulting in greater wifi availability and improved call quality.

Unfortunately, the battery still sucks. And Samsung managed to load the device up with crap ware that you cannot delete from the application menu.

To mitigate the battery life, I bought a few chargers to plant at strategic locations at home, in the car and at the office. And most of the crap ware can be stashed in a folder on the desktop. This uncluttered  things enough to pass inspection.

Just as I was getting used to the device, and on the last day of my free trial, Sprint dropped the mother of all bombs. They announced the ending of the unlimited data plan. Furthermore, current users would not be grandfathered in, and thus would be subject to huge data overage charges.

This triggered my immediate cancellation of the Sprint plan.

The data plan was the only reason why I went to Sprint in the first place. With Sprint customers faced a trade-off. You received unlimited data for a unreliable network that has poor coverage in rural areas.

With their latest decision, there is no tradeoff, and therefore no logical reason why anyone whould choose Sprint over another network.

I leveraged the "winback" program AT&T offers customers who made the transgression of choosing another carrier. They put you back on the program exactly as you left it at no charge. 

So here I am, back with AT&T using a feature phone with nothing but time to ponder my next move.

Do I wait three weeks for Samsung’s Galaxy Nexus that boasts Ice Cream Sandwich, Google’s new OS? Do l let lust get the best of me, and choose a Windows Phone 7, with the Mango update, knowing I'll likely be ultiamtely dissapointed with its feature incompleteness? Or do I return to utopia with an iPhone 4s?

The reality is that in this temporal existence, utopia doesn’t exist and there is no perfect phone. Therefore, I’m sticking with my wife’s old feature phone.

Am currently attempting to do both the Stanford AI and Machine Learning courses at once. My brain is melting.

I’m keeping my ongoing rough notes on github, I’m writing them in markdown so they render relatively nicely there.

I have realised that, if I am actually going to see both courses through to the end, I am going to have to put everything else on hold until they’re done.

Luckily, they both pertain to greater or lesser degrees to weak so its not entirely a pause on other projects. Also, I might choose to hack on weak from time-to-time since I am chomping at the bit to get it moving.

In an ordinary employer-employee relationship with a large company, the employer has most of the power. When any individual employee seeks a higher wage, he or she has no leverage; for a large company to lose a single employee makes little difference. In the U.S., unions have been a way for employees to get more leverage. The large company can not ignore the effect of many employees working together.

However, many people dislike unions, because unions are only effective when the union members work together. Many people feel that this takes away individual rights, as indeed it does.

It recently occurred to me that there is a different way to look at the issue. Think of the union as a company itself, a special sort of company which operates as a monopsony. When you join the employer, you are actually joining two companies: the employer and the company which provides employees to the employer. The union company and the regular company have a tight relationship, but this is no different from an ordinary monopsony supplier situation, such as is widely found in, e.g., the automotive business. Union companies tend to be more democratic than most companies, but this is not a fundamental difference.

One can of course have multiple union companies providing labor to the parent company. However, it is perfectly reasonable for the parent company to negotiate only with union companies for labor, rather than with individuals. After all, only in exceptional situations would a company purchase non-labor supplies from an individual. Why should labor be any different? Thus the “closed shop” has a clear support: it’s a matter of efficiency for the parent company.

This perspective may remove some of the traditional complaints against unions. They are replaced by a different issue, which is that every employee has two loyalties. However, in reality we all have multiple loyalties in our lives—to our families, our sports teams, etc.

Try thinking of the matter this way the next time you feel angry about unions. They are just doing what regular companies do.

As Andrew said, there are many different ways of approaching this.  Following Rog’s comment to my last post, I tried a new version.  This one starts a goroutine for each URL fetched, but manages to get by with only a single channel communication per URL.  Is it better?  Hard to say.  For the dummied data set, of course none of this matters.  “Better” would make much more sense in the context of a real problem.

Anyway, one more way:

type request struct {
    url   string
    depth int
}

type result struct {
    req  *request
    body string
    urls []string
    err  os.Error
}

func Crawl(url string, depth int, f Fetcher, maxWorkers int) {
    // resCh is the only channel used.
    // one result will be sent for each url fetched,
    // and this is the only synchronization needed.
    resCh := make(chan *result)

    // fetch function literal fetches a single url and
    // returns the result on resCh.
    fetch := func(req *request) {
        body, urls, err := f.Fetch(req.url)
        resCh <- &result{req, body, urls, err}
    }

    // initial condition is that a fetch is started on the top url,
    // the url is noted as having been seen, the fetch is noted as
    // outstanding, and there is otherwise no backlog of requests.
    go fetch(&request{url, depth})
    seen := map[string]bool{url: true}
    outstanding := 1
    var backlog []*request

    for outstanding > 0 {
        // block and wait for a result.  print results when it arrives,
        // and then one less request is known to be outstanding.
        res := <-resCh
        if res.err != nil {
            fmt.Println(res.err)
        } else {
            fmt.Printf("found: %s %q\n", res.req.url, res.body)
        }
        outstanding--

        // check if any urls in the result need to be crawled.
        if res.req.depth <= 1 {
            continue // at depth limit
        }
        for _, u := range res.urls {
            if seen[u] {
                continue // don't fetch the same url twice
            }
            // at this point we know this is a new url we want
            // to crawl.  mark it as seen and prepare a request.
            seen[u] = true
            req := &request{u, res.req.depth - 1}

            // if we are under the concurrency limit, start a
            // fetch immediately.  otherwise backlog it.
            if outstanding < maxWorkers {
                go fetch(req)
                outstanding++
            } else {
                backlog = append(backlog, req)
            }
        }

        // after handling a result, it is possible that it
        // resulted in no new requests, but that there was
        // an existing backlog.  with that oustanding request
        // done, we can pick one request off the backlog.
        if len(backlog) > 0 && outstanding < maxWorkers {
            go fetch(backlog[len(backlog)-1])
            backlog = backlog[:len(backlog)-1]
            outstanding++
        }
    }
}

As long as I’ve been programming, I’ve often found it helpful to sketch little diagrams to help me puzzle out programs. I’ve been known to draw plain old flowcharts for example, sometimes to the amusement of others. In my object oriented days, I assembled a few very elaborate object hierarchy diagrams, because they seemed a crucial foundation for the elaborate programs based on them. Thankfully none of these are in the pile of scratch paper on my desk currently (or posted on my wall!)

Programming in Go, a type of diagram I have occasionally found useful though, is one showing communication between goroutines. I put a goroutine name in a box and draw a vertical line down from it, vaguely suggesting a sequential process. I represent channels as horizontal lines that go from one vertical line to another. Then I annotate the diagram with whatever I think is relevant. I’ve found pencil and paper best for doing this. Anytime I’ve tried using drawing or diagramming software I’ve wasted huge amounts of time and ultimately not been pleased with the result. For showing examples here, I’m resorting to ASCII art! For exhibit 1, here’s a diagram of Andrew Gerrand’s solution to exercise 64 in A Tour of Go.

                                         one per url to be fetched!
                                                 +---------------+
+------+ url                       (url string) +---------------+|
| main |--------------------------------------->| crawler.fetch |+
+------+                                        +---------------+
|                 n = workers                                   |
|                  +-------------+                              |
|                 +-------------+|                              |
|                 | crawler.run |+                              |
|                 +-------------+                               |
|                               | c.req      string      c.req  |
|                               |-range-----------------------<-|
|                               |                               |
| c.res     *result      c.res  |
|-range-----------------------<-|
|                               |

Note that while lines representing channels go from one vertical line to another, There is a line from the main box to the crawler.fetch box. This doesn’t represent a channel, but data passed as a parameter at the invocation of the goroutine. Without that, it’s not obvious where crawler.fectch gets its data. I put an annotation about this data in parentheses reminiscent of function call syntax.

When there are multiple instances of a goroutine, I use a shadowed box and put an annotation above the box saying something about how many instances are created or are running.

The main annotation for a channel is its type, which I always put above line near the middle. Channel communication generally goes in one direction, which is shown with an arrow on the channel line. If you can arrange goroutines so that communication goes from right to left on the diagram, then the arrows look like send and receive communication operations. I’ve found it useful to annotate both ends of the channel lines with the name of the channel in that goroutine. In this case both ends use the same variable name, so it might seem a little redundant, but I think that’s helpful information.

So, here’s another. This is Rog’s solution.

                                            one per url fetched!
                                                 +-----------+
+------+                           {url string} +-----------+|
| main |--------------------------------------->| "fetcher" |+
+------+                                        +-----------+
|                                                           |
| limiter <-         struct{}, 10                 <-limiter |
|------------------------>>>>>------------------------------|
|                                                           |
|                                                           |
| rc                         result                      r  |
|-range---------------------------------------------------<-|

The fetcher goroutine here happens to be an anonymous function literal. I put “fetcher” in quotes to show that fetcher isn’t really the name of the function in the source code, but is just kind of a descriptive name used in the diagram. Also, the data supplied from the main goroutine is not passed as a parameter but as a free variable to the closure so I used brace brackets, kind of suggestive of the literal.

The limiter channel poses a problem for my diagramming scheme because data goes from left to right. Arrows on the channel line cutely suggestive of channel syntax don’t work because they would go the wrong way. In fact I used to draw them the wrong way, but as I got more used to reading Go code, I found this disturbing. Here I’m experimenting with just putting the channel operators in their correct relation to the channel names and then putting a bold sort of arrow under the channel type. (I’m making this all up as I go along, you see…)

So how does Rog’s approach compare to Andrew’s from this perspective? At a glance it seems nicer because it uses fewer goroutines. Rate limiting is done by putting tokens in a buffered channel and Andrew’s “worker” goroutines are not needed. If you look at the amount of channel communication going on however, it’s about the same. In each case there are two channel communications per url fetched. Really I’m not sure we can do better for a rate limited algorithm.

Can we do worse? Always! For a great example, I offer my previous blog post. Diagrams aren’t even needed to notice the difference in the amount of channel communication going on. I’m having all my concurrent goroutines do a bunch of concurrency stuff that can be avoided with a different algorithm.

A shocking recommendation appeared on Go Nuts recently to “avoid concurrency as much as possible.” This heresy was immediately challenged. The clarification is that of course you use concurrency when you have to, but only when you have to. Synchronization is expensive. If you don’t have to share something, don’t! If there’s a way to avoid sharing something, do it.

Anyway, back to the two diagrams presented above.  There is one thing that bothers me.  There is a separate goroutine created for each individual url.  Is that really necessary?  Looking at all the solutions presented in the Go Nuts thread, they all do this.  My sad solution of the previous post does this.  Goroutines are pretty cheap, true, but still I understand there’s a 4k stack, and who knows what else it takes to get one started.  It seems a lot of churn.

Is there a solution with a diagram like this? It would still have two channel communications per url, but no separate goroutine per url, just main and a small constant number of worker goroutines.

+------+                                         n = workers
| main |                                          +----------+
+------+                                         +----------+|
|                                                | "worker" |
|                                                +----------+
|                                                           |
| reqCh <-              *request                    <-reqCh |
|------------------------->>>>>-----------------------------|
|                                                           |
|                                                           |
|  resCh               *result                       resCh  |
|<--------------------------------------------------------<-|
|                                                           |

Well yes. Here is one example:

type request struct {
    url   string
    depth int
}

type result struct {
    req  *request
    body string
    urls []string
    err  os.Error
}

func Crawl(url string, depth int, f Fetcher, workers int) {
    reqCh := make(chan *request)
    resCh := make(chan *result)
    for i := 0; i < workers; i++ {
        go func() {
            for r := range reqCh {
                body, urls, err := f.Fetch(r.url)
                resCh <- &result{r, body, urls, err}
            }
        }()
    }

    seen := map[string]bool{url: true}
    backlog := []*request{&request{url, depth}}
    outstanding := 1
    for outstanding > 0 {
        var res *result
        for len(backlog) > 0 {
            // feed backlog to reqCh until a result arrives.
            select {
            case reqCh <- backlog[len(backlog)-1]:
                backlog = backlog[:len(backlog)-1]
            case res = <-resCh:
                goto gotResult
            }
        }
        res = <-resCh // no backlog.  block until result arrives.
    gotResult:
        outstanding--
        if res.err != nil {
            fmt.Println(res.err)
        } else {
            fmt.Printf("found: %s %q\n", res.req.url, res.body)
        }
        if res.req.depth > 1 {
            for _, u := range res.urls {
                if !seen[u] {
                    seen[u] = true
                    outstanding++
                    backlog = append(backlog,
                        &request{u, res.req.depth - 1})
                }
            }
        }
    }
}

The magic is all in using a select statement. We need main to be handling data in both directions depending on what data is available. That’s exactly what select does.

These communication diagrams don’t describe algorithms. They don’t even suggest them. They do however give you a synopsis of goroutines and channel communication, and this may prompt you to consider alternatives. Is everything in the diagram needed? Can you solve the problem with less?

Today we released version 1.5.5 the Go App Engine SDK. You can download it from the App Engine downloads page.

This release includes changes and improvements to the App Engine APIs and brings the supporting Go tool chain to release.r60.2 (the current stable release). Also included in this release are the godoc, gofmt, and gofix tools from the Go tool chain. They can be found in the root directory of the SDK.

Some changes made in this release are backwards-incompatible, so we have incremented the SDK api_version to 3. Existing apps will require code changes when migrating to api_version 3.

The gofix tool that ships with the SDK has been customized with App Engine-specific modules. It can be used to automatically update Go apps to work with the latest appengine packages and the updated Go standard library. To update your apps, run:

    /path/to/sdk/gofix /path/to/your/app

The SDK now includes the appengine package source code, so you can use the local godoc to read App Engine API documentation:

    /path/to/sdk/godoc appengine/datastore Get

Important note: We have deprecated api_version 2. Go apps that use api_version 2 will stop working after 16 December 2011. Please update your apps to use api_version 3 before then.

See the release notes for a full list of changes. Please direct any questions about the new SDK to the Go App Engine discussion group.

I can’t resist. The difficulty level of the exercise is similar to much of what I’ve posted on this blog and I just want to talk about it.

For any of you who don’t regularly follow the Go Blog or Go Nuts, I’m talking about the final exercise, #69, of the recently published A Tour of Go. This is a perfect little introduction to the language that starts with the most basic elements of the language and progresses through some of the best and most interesting elements of the language. There are exercises along the way. The first exercises are easy, then they become more challenging. I believe most people new to Go will find the final exercise in particular to be a satisfying challenge. If you haven’t taken the tour yet, I encourage you to do so and to attempt the exercises, especially #69, the subject of my post here.

Done? Good. :) Of the two TODO items, “Don’t fetch the same URL twice” is easy to add.  One quick and dirty solution is to replace the Crawl function with the following,

func Crawl(url string, depth int, fetcher Fetcher) {
    c2(url, depth, fetcher, map[string]bool{url: true})
}

func c2(url string, depth int, fetcher Fetcher, m map[string]bool) {
    // TODO: Fetch URLs in parallel.
    if depth <= 0 {
        return
    }
    body, urls, err := fetcher.Fetch(url)
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Printf("found: %s %q\n", url, body)
    for _, u := range urls {
        if !m[u] {
            m[u] = true
            c2(u, depth-1, fetcher, m)
        }
    }
    return
}

This works, but some people might not like a couple of things here. It introduces a new function, c2, and c2 has a fourth parameter. Do you agonize about the clutter of another function or the overhead of pushing another parameter on the stack? There are other ways to do it. You could make the map a package variable. Bad idea. I won’t even show it. An excellent and popular technique is a recursive closure:

func Crawl(url string, depth int, fetcher Fetcher) {
    m := map[string]bool{url: true}
    var c2 func(string, int)
    c2 = func(url string, depth int) {
        // TODO: Fetch URLs in parallel.
        if depth <= 0 {
            return
        }
        body, urls, err := fetcher.Fetch(url)
        if err != nil {
            fmt.Println(err)
            return
        }
        fmt.Printf("found: %s %q\n", url, body)
        for _, u := range urls {
            if !m[u] {
                m[u] = true
                c2(u, depth-1)
            }
        }
        return
    }
    c2(url, depth)
}

Alternatively, you could use a struct and a method:

func Crawl(url string, depth int, fetcher Fetcher) {
    c := &crawlHistory{fetcher, map[string]bool{url: true}}
    c.c2(url, depth)
}

type crawlHistory struct {
    fetcher Fetcher
    m       map[string]bool
}

func (c *crawlHistory) c2(url string, depth int) {
    // TODO: Fetch URLs in parallel.
    if depth <= 0 {
        return
    }
    body, urls, err := c.fetcher.Fetch(url)
    if err != nil {
        fmt.Println(err)
        return
    }
    fmt.Printf("found: %s %q\n", url, body)
    for _, u := range urls {
        if !c.m[u] {
            c.m[u] = true
            c.c2(u, depth-1)
        }
    }
    return
}

Which of these forms appeal to you is likely to depend on what other languages you know. If you know a language with closures, you probably like the first one. If your experience is object oriented, the second probably looks good to you. It really doesn’t matter.

One elegant little change that can be made to the second version is to embed Fetcher in crawlHistory. Remove the field name from Fetcher so that the struct definition reads simply

type crawlHistory struct {
    Fetcher
    m map[string]bool
}

The call to Fetch can now be written

    body, urls, err := c.Fetch(url)

Embedding wasn’t covered in the tour, but that’s okay because we’re not going to complete this exercise without a couple of other things that weren’t covered in the tour.

Next on the TODO list is fetching URLs in parallel. We’re going to start multiple goroutines and let them crawl different urls found on the page. A pretty big thing not covered in the tour is that concurrent map access is not safe without synchronization. That means these multiple goroutines need to access to the map one at a time. If we don’t serialize access to the map, we risk wrong answers or even corrupt memory and a crash.

Also not covered is that fmt.Println should be synchronized as well. It turns out that we have no guarantee from the operating system even that output from multiple threads won’t get interleaved.

Finally, covered so subtly that you probably missed it is that a Go program terminates when main terminates, without waiting for other goroutines. (Take another look at the output of example 61.) We will start goroutines to crawl urls found on the page, but then we need to do something to wait for them to complete.

So we’re going to need lots of synchronization to do this exercise! The tour did mention the sync package, and there is stuff there to do the job, but we can do the exercise easily without the sync package so I won’t go into it just yet. Go channels, as shown in the tour, represent a very general purpose mechanism that easily handle all of the synchronization needs for this exercise.

The pattern I use for serializing access to the shared resources—the map and fmt.Println—uses channels with capacity=1. One channel is created for a resource that is to be shared and this one channel is passed to all goroutines that want to access the resource. When a goroutine wants to access the resource, it must take (some reference to) the resource from the channel, use the resource, and then return the resource to the channel. It’s like the salt shaker on the table. Only one person uses it at a time, and otherwise it sits in a place where everyone can reach it.

The pattern I use to wait for goroutine completion is that if a function launches goroutines, it must also create a channel for them to report completion. It counts the number of goroutines it launches, then waits for exactly that many completion reports.

Simple enough? Here’s the code:

// struct renamed crawlShared to reflect that it provides access to
// things that are shared across goroutines (the goroutines being
// instances of c2, specifically.)
type crawlShared struct {
    Fetcher     // embedded for Fetch method.

    // the "salt shaker" pattern:  a channel holds the shared map
    mapAccess   chan map[string]bool

    // about the same pattern, except that there is nothing obvious
    // to put in the channel.  instead, a boolean value is used as
    // a token.  the value is ignored.  all that matters is the
    // presence or absence of the token in the channel.
    printAccess chan bool
}

func Crawl(url string, depth int, fetcher Fetcher) {
    c := &crawlShared{
        fetcher,
        make(chan map[string]bool, 1),
        make(chan bool, 1),
    }

    // put the salt shaker on the table.  that is, put the map
    // in the channel, making it available to goroutines.
    c.mapAccess <- map[string]bool{url: true}

    // same with the token to serialize printing
    c.printAccess <- true

    // run goroutine to crawl top level url.
    // since we are starting exactly one goroutine here, we wait
    // for a single completion report.  receipt means that all
    // lower levels have also completed and it is safe to return
    // --and allow the caller to return, in this case, main().
    done := make(chan bool)
    go c.c2(url, depth, done)
    <-done
}

func (c *crawlShared) c2(url string, depth int, pageDone chan bool) {
    // the function has multiple return points.  all of them must
    // report goroutine completion by sending a value on pageDone.
    if depth <= 0 {
        pageDone <- true
        return
    }

    body, urls, err := c.Fetch(url)
    if err != nil {
        // here's how to print:
        // take the token (waiting for it if it's not there.)
        <-c.printAccess
        // do whatever you need to do while other goroutines are
        // excluded from printing.
        fmt.Println(err)
        // put the token back, allowing others to print again.
        c.printAccess <- true

        pageDone <- true
        return
    }

    // same sequence of steps to print found message
    <-c.printAccess
    fmt.Printf("found: %s %q\n", url, body)
    c.printAccess <- true

    // "found" means the url was fetched without error and that urls
    // on the fetched page are collected in the slice "urls."
    // synchronization to crawl these urls in parallel is implemeted
    // with the uDone channel.  create the channel, count the number of
    // goroutines started, then wait for exactly that many completions.
    uDone := make(chan bool)
    uCount := 0

    // salt shaker pattern for map access:  get the map from
    // the channel, and then hold it while iterating over urls.
    // this works with the assumption that all of the operations here
    // take trivial time compared to the relatively lengthy time
    // to fetch a url.  other than map access (which is what we need
    // exclusive access for!) the only operations are iterating over
    // a string slice, incrementing an integer, and starting
    // a goroutine.  these all run very fast so it is reasonable and
    // best to hold "the lock" that is, exclusive map access, while
    // running through this loop.
    m := <-c.mapAccess
    for _, u := range urls {
        if !m[u] {
            m[u] = true
            uCount++
            go c.c2(u, depth-1, uDone)
        }
    }
    c.mapAccess <- m

    // wait for the number of goroutines started just above.
    for ; uCount > 0; uCount-- {
        <-uDone
    }

    // and finally, report completion of this level
    pageDone <- true
}

So that’s kind of the safety scissors version. I think it shows a correct solution while introducing a minimum of concepts that were not covered in the tour.

I’ll leave you with this alternative that uses a few more tricks. The tricks require greater knowledge of the language and libraries, but make for code that is both more concise and faster. This version dispenses with the struct by going back to the recursive closure, trades printAccess for a little trick with the log package, trades mapAccess for a sync.Mutex, and replaces all the done channels with a single sync.WaitGroup. With the waitGroup there is no longer any need to run the first call to c2 as a goroutine, mm, and there’s a defer statement in there too.

import (
    "log"
    "os"
    "sync"
)

var fmt = log.New(os.Stdout, "", 0)

func Crawl(url string, depth int, fetcher Fetcher) {
    m := map[string]bool{url: true}
    var mx sync.Mutex
    var wg sync.WaitGroup
    var c2 func(string, int)
    c2 = func(url string, depth int) {
        defer wg.Done()
        if depth <= 0 {
            return
        }
        body, urls, err := fetcher.Fetch(url)
        if err != nil {
            fmt.Println(err)
            return
        }
        fmt.Printf("found: %s %q\n", url, body)
        mx.Lock()
        for _, u := range urls {
            if !m[u] {
                m[u] = true
                wg.Add(1)
                go c2(u, depth-1)
            }
        }
        mx.Unlock()
    }
    wg.Add(1)
    c2(url, depth)
    wg.Wait()
}

Oh, and without the fmt package, there’s a line in fakeFetcher.Fetch that now has to read

    return "", nil, os.NewError("not found: " + url)

My open source chess engine project, Weak, is progressing well as I build up the absolute fundamentals.

As discussed in the readme, the current approach is to get to the point where the engine can play legal (against a subset of the rules of chess), random, moves. Once this is implemented then I will slowly improve the engine until it gets to the point where it can actually play competitive chess.

In pursuit of this, I have been taking full advantage of the amazing power of the internet to provide information on any subject you can possibly think of, no matter how niche, and the best resource I have found so far is the rather excellent chess programming wiki.

As a guide to how to proceed, I have been working through the getting started section of the wiki, starting with the board representation, which is arguably the most fundamental choice in the design of a chess engine.

I have chosen to use a bitboard representation. Bitboards work by assigning 64-bit values to each piece type, where each bit of each value indicates whether a piece of the type in question is present on a certain square of the board. Representing the board this way permits the use of bitwise logic to interact with different board positions + due to the ease with which processors can perform these operations, analysis can be performed efficiently (in theory, at least).

Here is the actual board data structure:-

struct board {
  uint64_t pawns, rooks, knights, bishops, queen, king;
};

The engine stores separate instances of this for white and black.

I have chosen to map board positions to bit positions as follows:-

bit = rank * 8 + file

E.g.:-

Index of E1 = 0 * 8 + 4 = 4

Index of H3 = 2 * 8 + 7 = 23

Over the coming week I hope to actually bring the engine to the point where it can play a game :)

Forgive the sparseness of this post, I would have liked to put some more graphics + effort into it, however I am so ridiculously busy at the moment with this + my other projects that I simply do not have the time!

This is something that I wrote up internally, but which Chris Palmer suggested would be useful to post publicly for reference. It presents some, somewhat artificial, axis on which I believe that all proposed solutions to addressing weaknesses in the current certificate ecosystem fall. By dividing the problem into those decisions, I hope to make the better solutions clearer.

Axis 1: Private vs public signing

At the moment we have private signing. A CA can sign a certificate and tell nobody about it and the certificate is still valid. This is the reason that we have to go crawl the Internet in order to figure out how many intermediate CA certs there are.

In public signing, certificates aren't valid unless they're public.

There are degrees of how public schemes are. Convergence is a public scheme: certificates have to be visible to the notaries, but it's a lot less public than a scheme where all certificates have to be published. And published where? Highly public schemes imply some centralisation.

Private schemes don't protect us from CAs acting in bad faith or CAs which have been compromised. Public schemes help a lot in these cases, increasingly so the more public they are. Although a certificate might be valid for a short time, evidence of misbehavior is recorded. Public schemes also allow each domain to monitor all the certificates for their domain. Fundamentally, the only entity that can answer the question of whether a certificate is legitimate is the subject of the certificate itself. (See this tale of a Facebook certificate.)

Private schemes have the advantage of protecting the details of internal networks (i.e. not leaking the name www.corp.example.com).

Axis 2: Side channels or not

Revocation checking which calls back to the CA is a side channel. Convergence notaries are too. OCSP stapling is not, because the server provides the client with everything that it needs (assuming that OCSP stapling worked).

Side channels which need to be a hard fail are a problem: it's why revocation checking doesn't actually work. Private networks, hotel networks and server downtime are the issues. Side-channels are also a privacy and performance concern. But they're easier on the server operator and so more likely to be deployed.

In the middle are soft-fail side-channels. These offer limited protection because the connection proceeds even when the side-channel fails. They often queue the certificate up for later reporting.

Axis 3: Clocks or not

OCSP with nonces doesn't need clock sync. OCSP with time stamps does.

Keeping clocks in sync is a problem in itself, but it allows for short lived statements to be cached. It can also be a useful security advantage: Nonces require that a signing key be online because it has to sign a constant stream of requests. With clocks, a single response can be served up repeatedly and the key kept largely off-line. That moves the online key problem to the clock servers, but that's a smaller problem. A compromised clock server key can be handled by querying several concurrently and picking the largest cluster of values.

Examples

OCSP today is {private,side-channel,clock}. The 'let's fix OCSP' solutions are typically {private,side-channel,no-clock} (with an option for no-side-channel). Convergence is {mostly-public,side-channel,no-clock}.

I think the answer lies with {public,no-side-channel,clock}, but it's a trek to get there. Maybe something for a future post.

I wrote previously that Brocade had released a firmware update for their ServerIron SSL terminators which fixed an incompatibility with False Start. However, it now appears that they didn't fix the underlying issue, rather they special cased Chrome's current behaviour.

Sadly, due to Chrome implementing a workaround for the BEAST attack, their special casing doesn't work anymore and breaks Chrome 15.

So, if you run a Brocade ServerIron you should contact me ASAP. I'll be adding sites running this hardware to the False Start blacklist for Chrome 15 to allow Brocade to release another firmware update.

“Dining Savages” is another toy problem from The Little Book of Semaphores.  Quoting from the PDF,

A tribe of savages eats communal dinners from a large pot that
can hold M servings of stewed missionary1. When a savage wants to
eat, he helps himself from the pot, unless it is empty. If the pot is
empty, the savage wakes up the cook and then waits until the cook
has refilled the pot.

So…the pot is a shared integer.  Sure you could make one special place in memory and do synchronization stuff to control access to it, but that’s not the Go way.  In Go, we share by communicating—in this case, that means we pass the integer around.  We pass it around by passing it through channels.  One channel I call potHolder. It’s a buffered channel with capacity=1. It’s a place to put the pot. Let all of the savages access the pot holder and the result is that any of them can pick up the pot, take from it, (decrement the int) and then return the pot to the pot holder. If a savage finds it empty, he uses another channel to give it to the cook.

package main

import (
    "log"
    "os"
    "rand"
    "sync"
    "time"
)

var fmt = log.New(os.Stdout, "", log.Lmicroseconds)

const (
    potCap             = 5
    nSavages           = 3
    nServingsPerSavage = 4
    cookTime           = 2e8
    avgEatTime         = 1e8
)

type pot int

func main() {
    rand.Seed(time.Nanoseconds())

    fillReq := make(chan pot)
    go cook(fillReq)

    potHolder := make(chan pot, 1)
    potHolder <- pot(0)
    var s sync.WaitGroup
    s.Add(nSavages)
    for i := 1; i <= nSavages; i++ {
        // savages wander into camp at random intervals
        time.Sleep(rand.Int63n(cookTime) / nSavages)
        go savage(i, potHolder, fillReq, &s)
    }
    s.Wait()
}

func savage(i int, potHolder, fillReq chan pot, s *sync.WaitGroup) {
    // some savages eat faster than others
    eatTime := avgEatTime/2 + rand.Int63n(avgEatTime)

    for s := 0; s < nServingsPerSavage; s++ {
        fmt.Println("savage", i, "hungry!")
        pot := <-potHolder
        if pot == 0 {
            fmt.Println("savage", i, "finds empty pot and wakes cook")
            fillReq <- pot
            pot = <-fillReq
        }
        fmt.Println("savage", i, "eating")
        potHolder <- pot - 1
        // time passes while eating
        time.Sleep(eatTime)
    }
    fmt.Println("savage", i, "happy")
    s.Done()
}

func cook(fillReq chan pot) {
    for {
        fmt.Println("cook sleeping")
        <-fillReq
        fmt.Println(`cook grumbles "i'm cooking"`)
        time.Sleep(cookTime) // time passes while cooking
        fmt.Println(`cook mutters "here, ya ungrateful savages"`)
        fillReq <- potCap
    }
}

The algorithm here is almost exactly the same as Downey’s, and yet Downey’s explanation includes a mutex, semaphores, rendezvous, and a “scoreboard pattern.” Is it really that hard? I think mostly the wording is hard. In general, I find the wording of Go easier.

Go also helps by holding related things together. A mutex is a thing that synchronizes access to some data object. They are separate and the declaration of the mutex generally has no dependence on the declaration of the data object. You’re on your own to use some coding convention to hold them together. A Go channel on the other hand is typed. A channel can fulfill the synchronization role of a mutex, but is typed consistent with the data object.

This simple pattern I use when I translate a mutex-based algorithm into Go is to create a buffered channel of capacity=1 to hold the data object.

mutex.wait() (with no reference to the data object being controlled) in Downey’s pseudocode becomes pot := <-potHolder in my code. It’s so nice to not have to worry about where the data object is, what it is called, or who else might be messing with it.  The synchronization operation (channel receive) serves up the data object and hands it to you!  It’s synchronization and communication.

The channel savages use for communicating with the cook is not buffered and is also not in a select statement on either end. Both send and receive are therefore blocking, which makes this an example of a rendezvous. The term is used to describe synchronous communication between threads. Synchronous means that a savage goroutine will be at the line fillReq <- pot at the same time that the cook goroutine is at the line <-fillReq. Which ever goroutine arrives at its line first will block and wait for the other goroutine to arrive at its line. Data is then exchanged through the channel and both goroutines can proceed.

Why do we even care? Well, we don’t strictly need to know the term rendezvous, but in this case it is nice to know that the communication operation is blocking. It lets us use the same channel for communication in both ways. Once the savage has handed over the pot to the cook, he stands there ready to take the pot back with the same hand, so to speak. This only works because the pot is guaranteed to be in complete possession of the cook before the savage can attempt to take it back again.

This guarantee comes from the Go memory model specification which defines the concept “happens before” which provides guarantees such as this about the order of events in Go’s concurrent environment. The document says for example, “A send on a channel happens before the corresponding receive from that channel completes.” This is comforting, but then very interestingly it says, “A receive from an unbuffered channel happens before the send on that channel completes.” Here is the guarantee of synchronous communication. It’s saying that once the savage starts handing the pot over, that the cook getting the pot out of the channel happens before the the savage is free to do anything else. That is, before the next line of savage code attempts to take the pot back.

I was recently thinking about my college studies of nuclear warfare. At the time it seemed like a relevant topic, and I took two courses on it. Like everything, the more you look into it the more complex it gets. The depth of the thinking in nuclear warfare planning was both impressive and appalling.

One of the more interesting cases was driven by the fear of a Soviet invasion of Western Europe. In retrospect we know there was never a danger of that, but at the time it was a real concern. The western strategists feared that in a conventional war, the Soviet tanks would rapidly rout the smaller European armies. The use of nuclear weapons, or at least their potential use, was an obvious way to counter this threat.

However, most of the nuclear weapons were in the U.S. It was clear that no U.S. president would launch nuclear weapons at the Soviet Union in order to forestall an invasion of Europe. The U.S. promised to support Europe, but if the war actually started, a nuclear attack on the U.S.S.R. could only end in a nuclear counter-attack on the U.S. That would never happen. England and France had a few nuclear weapons, but would their leaders really launch them, knowing that they would face certain death in the overwhelming nuclear counter-attack? A bold and calculating leader of the Soviet Union might be willing to risk that nobody would take the nuclear option, and be willing to gamble that they would win a conventional war (again, this was the fear of the U.S. and Europe, the Soviet Union knew perfectly well that they could not win such a war). How could the U.S. and Europe use nuclear weapons as a credible deterrent to a conventional invasion?

The answer was, as I said, both impressive and appalling. NATO distributed low-yield nuclear weapons throughout Europe (they even had nuclear landmines). In the event of an invasion, complete control over the weapons was handed over to local commanders. The decision to use nuclear weapons would not be in the hands of an elected leader far from the war zone. It would be in the hands of a local colonel facing the immediate loss of his command. The Soviet Union might gamble (so the thinking went) on the reactions of a few political leaders they could study closely. They would never gamble on the reactions of several hundred local military commanders. Although the weapons were relatively low-yield, the expectation was that once a war went nuclear, the only thing that would stop it from escalating would be a quick complete cessation of hostilities.

This is a nice example of achieving your goal by explicitly giving up your ability to act rationally.

In a Go-nuts discussion a while back, Dmitry Vyukov mentions in passing,

Btw, it’s possible to implement Barber Shop with only channels in a
quite idiomatic way (IMHO):

seats := make(chan *Customer, 4) // 4 seats

func (self *Customer) EnterShop() bool {
select {
case seats <- self:
default: return false
}
…
}

The Barber Shop problem to which he refers has a Wikipedia page and is also covered in “The Little Book of Semaphores.”  If you’re not familiar with the problem, I encourage you to go read the WP entry at least, then look at Dmitry’s code snippet.  He’s using a buffered channel as a data structure that conveniently has safe concurrent access already built in.  The elements of the channel represent the waiting room seats in the barber shop.  Each one can hold one customer.  Customers can contend for the seats, but the language will see to it that there is never more than one customer per seat.  The barber can attend to them in order, and more customers can seat themselves only as waiting room seats become available.  This solution has no mutexes or semaphores, just a single Go channel.

The technique is nice and is really just that simple.  The rest of this post takes a closer (if pedantic) look.

So it’s nice, but it hasn’t been mentioned yet what real-world problems this might apply to. The buffered channel represents a thread-safe FIFO queue. That should certainly have wide applicability. The opening paragraph of the WP article says it’s “inter-process communication and synchronization problem between multiple operating system processes.” Well wahoo, that covers a lot of territory. Thankfully, the problem as usually stated is much narrower. The specifics are usually start something like,

• There are a number of “customer” processes which can run concurrently.
• There is one “barber” process which runs concurrently with customer processes.
• The barber process can do some unit of useful work “haircut” for customer processes.
• There is a fixed capacity FIFO queue that customer processes must use to get the barber process to perform the haircut.

So in other words, it’s a job queuing system. Now we’re getting somewhere. Additional details are usually specified or implied:

• The customer process “gets the barber to perform the haircut” by enqueueing some data object. The data object represents a command for the barber process to perform the haircut work unit for that customer.
• The barber process performs the action of executing the haircut command; that is, it does the work.
• The barber executes only one command at a time and processes it to completion before accepting the next command.
• If the queue is empty and the barber is not executing a command, the barber sleeps. That is, the barber process enters some sort of idle state.
• If a customer process enqueues a haircut command when the barber is sleeping, the barber wakes.
• In the awake state, and while there are haircut commands enqueued, the barber sequentially takes a command and executes it.
• If a customer process attempts to enqueue a haircut command when the queue is already full, the attempt fails. The customer process handles this failure in some graceful way, but does not wait for a space in the queue.

This describes a mechanism—a concurrent algorithm—enabling concurrent processes to ask a single, shared, sequential worker process to perform a specified work unit for them, presumably something they can’t do for themselves.  This is much more specific, and yet there are still loose ends unspecified.  Notice most problem descriptions say nothing about a haircut “command” and yet certainly this is the meaning of a customer sitting in a chair.  Notice also most problem descriptions gloss over any distinction between the customer process, a customer data object, and the haircut command.  What are these things, what creates or instantiates them, what is their lifetime?  These kinds of issues are important in the real world.  Often you don’t get to pick the answers, but rather they are fixed for your application.  A toy program that makes one set of assumptions may not be easily adapted to a different set of constraints.

Without thinking about these things too hard just yet, here is a complete program written around Dimitry’s code snippet.

package main

import (
    "fmt"
    "sync"
)

const (
    nWaitingRoomChairs = 2
    nCustomers         = 10
)

type customer int

var seats = make(chan customer, nWaitingRoomChairs)

func (c customer) enterShop() bool {
    select {
    case seats <- c:
    default:
        fmt.Println(c, "no cut")
        return false
    }
    return true
}

var wg sync.WaitGroup

func main() {
    go barber()
    wg.Add(nCustomers)
    for i := customer(1); i <= nCustomers; i++ {
        go customerGr(i)
    }
    wg.Wait()
}

func barber() {
    for {
        c := <-seats
        fmt.Println(c, "cut")
        wg.Done()
    }
}

func customerGr(c customer) {
    if !c.enterShop() {
        wg.Done()
    }
}

You can see Dmitry’s code in lines 15-25; everything else there is just to complete a working program. I’ll explore specifics of what creates what in an expanded program, but first I want to simplify this one a bit. Barber Shop problem statements often specify the “enterShop” method, but in the simple program above, it looks rather pointless. It is only called from the customerGr function, so all the code from enterShop could just be included in customerGr. The customer type then is left with no methods, and it was just an int anyway, so I think this type can be dispensed with altogether. Here’s the simplified version:

package main

import (
    "fmt"
    "sync"
)

const (
    nWaitingRoomChairs = 2
    nCustomers         = 10
)

var wg sync.WaitGroup
var wr = make(chan int, nWaitingRoomChairs)

func main() {
    go barber()
    wg.Add(nCustomers)
    for i := 1; i <= nCustomers; i++ {
        go customer(i)
    }
    wg.Wait()
}

func barber() {
    for {
        c := <-wr
        fmt.Println(c, "cut")
        wg.Done()
    }
}

func customer(i int) {
    select {
    case wr <- i:
    default:
        fmt.Println(i, "no cut")
        wg.Done()
        return
    }
}

That version may or may not be enough to get credit on a homework assignment, but it certainly doesn’t answer all the questions you might have.  I’ll present an expanded version now that is instrumented with lots of print statements to better show the goroutine interactions.  To make things clear regardless of how the scheduler schedules goroutines, I’ll add some time.Sleeps to simulate events at random times and to simulate work getting done.

package main

import (
    "log"
    "os"
    "rand"
    "sort"
    "sync"
    "time"
)

var fmt = log.New(os.Stdout, "", log.Lmicroseconds)

const (
    nWaitingRoomChairs = 2
    nCustomers         = 10
    avgCutTime         = 1e8
    shopOpenTime       = 10e8
)

type haircutCommand struct {
    customerId int
    cutDone    chan bool
}

func main() {
    rand.Seed(time.Nanoseconds())

    fmt.Println(nWaitingRoomChairs, "chairs in the waiting room")
    wr := make(chan *haircutCommand, nWaitingRoomChairs)

    go barberGr(wr)

    fmt.Println(nCustomers, "customers will arrive")
    arrivals := make([]float64, nCustomers)
    for i := range arrivals {
        arrivals[i] = rand.Float64()
    }
    sort.Float64s(arrivals)

    var wg sync.WaitGroup // wait for each customer goroutine to finish
    wg.Add(nCustomers)

    shopT0 := time.Nanoseconds()
    for i, arrivalTime := range arrivals {
        delay := int64(arrivalTime*shopOpenTime) -
            (time.Nanoseconds() - shopT0)
        if delay > 0 {
            time.Sleep(delay)
        }
        go customerGr(i+1, wr, &wg)
    }

    wg.Wait()
}

func barberGr(wr chan *haircutCommand) {
    var napStart int64
    for {
        if len(wr) == 0 {
            napStart = time.Nanoseconds()
            fmt.Println("no customers.  barber sleeps")
        }
        cmd := <-wr
        if napStart > 0 {
            fmt.Println("barber wakes.  nap:",
                time.Nanoseconds()-napStart)
            napStart = 0
        }
        fmt.Printf("barber begins cutting customer %d's hair\n",
            cmd.customerId)
        time.Sleep(avgCutTime/2 + rand.Int63n(avgCutTime))
        fmt.Printf("barber finishes customer %d\n", cmd.customerId)
        cmd.cutDone <- true
    }
}

func customerGr(i int, wr chan *haircutCommand, wg *sync.WaitGroup) {
    fmt.Println("customer", i, "arrives looking shaggy")
    defer wg.Done()
    cutDone := make(chan bool)
    select {
    case wr <- &haircutCommand{i, cutDone}:
    default:
        fmt.Println("customer", i, "sees full shop and goes away")
        return
    }
    fmt.Println("customer", i, "takes a seat")
    <-cutDone
    fmt.Println("customer", i, "leaves looking neat")
}

A couple of changes are in the general interest of code clean up. I serialize output, just to be safe, with the log package. Also main() now declares wr and wg, which were formerly package variables, and passes them to functions as needed.

I add avgCutTime and shopOpenTime to the package level const list. These values are in nanoseconds rather than simulated barber shop minutes or hours. This is convenient for passing to time.Sleep of course, and really it’s just the ratios of the these numbers in the const list that affect the output. (It’s interesting to play with them.)

I define haircutCommand as a struct type. This change illustrates the distinction I mentioned earlier between the customer object and the request for a haircut. I still represent the customer object simply as an int, although it’s easy to see that it could be a reference to some other object, potentially with fields and methods and such. The haircutCommand contains the customer object and also the bookkeeping needed to execute the command. In this case it is a channel for signaling completion of the haircut.

Within main(), one significant change is construction of the slice arrivals. I want to simulate customers arriving at random independent times, so I have main fill a slice with uniformly distributed values and then sort them to get the times at which to simulate customers arriving. main() then sequences customers by starting goroutines as indicated by the arrivals array. Doing it this way, the goroutnes are not started all at once but are staged. There will never be a time when nCustomers instances of customerGr will all be running at once.

The barber goroutine now prints a message when it sleeps. Before, this wasn’t really clear. We could read the code and see that the barber would block on the channel read, but there was no indication of this in the output. We can also now see where we could add code that might do something associated with sleeping, like maybe spinning down a disk drive and starting it back up again.

The customer goroutine creates a new cutDone channel and handles the interaction between this channel and the WaitGroup.

Within a toy program like this, it’s hard to maintain a distinction between what you are trying to demonstrate and the mechanism you are using to demonstrate it. The WaitGroup, for example, is there to keep the program from terminating before all the goroutines have completed. This seems pretty clearly part of the demonstration mechanism so I’d rather not have it integrated with either the customer object (which can otherwise be demonstrated as just an int) or the haircut command object. Still, the barber, as part of the job queuing system being demonstrated, needs to signal when the cut is complete. This is more properly done with a separate mechanism then, the cutDone channel.

Sadly, I’m leaving the distinction between the demonstrator and the demonstrated a bit muddled in the the case of the barber and the customer goroutines. Originally, we had the enterShop method, which was clearly something being demonstrated. But really, it’s just the select statement. I think it’s enough to just observe that that’s where the job queuing happens. The other thing being demonstrated there is waiting for work unit completion. Again, it’s just a single statement. Other than those two statements, customerGr is concerned with the simulation, printing messages and doing stuff with the WaitGroup.

How about the barber goroutine, where is the distinction between demonstrator and demonstrated there? Interestingly, everything there is something being demonstrated. Even the print statements can be considered placeholders for more practical functions, perhaps named enterSleepState, restoreCapabilitesAfterSleeping, and doUnitOfMeaningfulWork.

Breaking apart customerGr and barberGr into these pieces is way too much work to do for this blog post, but it should be clear by now how to do it, should you need to for some real job queuing problem, or some real homework problem.

Phew. Having had a break I have got over my mini-crisis/burnout and feel ready to get back into the wonderful world of coding.

I haven’t been keeping this blog wonderfully updated, nor have I been making great progress on my projects. So, to address this, I have refocused and committed to working on 2 projects in particular (as well as study, see below) - go, an excellent systems programming language from google, which I humbly hope to contribute to further, and weak, a chess engine I am building from scratch.

An aside - yes, lorix is being put on the sidelines. I do intend to come back to it, however it is just far too much work for me to be able to reasonably work on it at the moment. I have deleted its github page for now; however I will restore it when I get back to working on it. There is a certain irony in that I talked about my track record on promises in the lorix post, however I did say that I was not making any promises. You were warned! :-) Astute readers will note that I am in fact promising things here, however I do very much intend to keep these promises as I am very focused on these projects. Ahem!

I have also committed to following the Stanford AI and Machine Learning courses, both of which I am studying on the advanced track (i.e. voluntarily doing homework + exams). I am also studying (principally algorithmic/data structure) fundamentals with the high bar of being able to pass a google interview at some point in the future. Note this is a theoretical bar - this is no comment on whether I do or do not actually intend to attempt to execute that in practice, or whether I am in fact at all capable of mashing a keyboard let alone writing an efficient program :-)

So a busy, busy boy. I also intend to update this blog far more frequently. Translation - I intend to actually update this blog from time-to-time :-)

Weak

Weak is a chess engine, i.e. a program which plays chess. I intend to start with a very naive approach, then gradually reduce the naivety throughout until it is as efficient as I can make it. The guiding principles of weak are - a. strong play (as strong possible) and b. an obsessive focus on optimisation at all points in the code. As a result of point b, I am writing weak in C (and perhaps assembly where necessary).

Yes, I know, in many ways this seems a perfect fit for go; however, I intend weak to be as much an exercise in learning C and low-level optimal programming as just a chess engine project. As I want to absolutely control performance throughout, I want to use a language which is as close to the metal as possible. Go is an absolutely brilliant language (y’know, so much so that I’m actually trying to contribute to it), however it is still young and it takes away some control.

In general, I don’t intend to defend my programming choices on practicality grounds; this is as much a learning project as it is just a straight up coding project. I intend to, at some point, take a look at GPGPU programming with an eye to expanding weak’s capabilities. For now, however, that is merely conjecture.

I suspect that an eye towards optimisation from day 1 will have an overall positive impact on performance, as all the little optimisations add up. The endlessly paraded ‘premature optimisation is the root of all evil’ Knuth quote is somewhat misleading I think - algorithmic optimisation matters throughout, and it’s difficult to go back on poor performance choices if they are littered throughout your code and underlie everything. Having said that, I intend to steer clear of silly micro-optimisations, and also intend to profile ruthlessly to avoid guessing where performance issues arise from.

Looking Forward

I will be writing a series of blog posts as I progress with the various projects, both as a diary for myself and somewhere I can point interested people at. Turning 30 has given me a real focus on what I want to pursue, and I am very much committed to following it. What makes me considerably more confident about these goals compared to previous ones is that I’ve established a ‘head fake’ - I only permit myself to change my mind about what I pursue once a year at my birthday; in between I focus on the projects I have set for myself. This reduces procrastination and uncertainty and ensures I work hard on projects without the inevitable self-doubt and worry affecting things.

Thai Duong and Juliano Rizzo today demoed an attack against TLS 1.0's use of cipher block chaining (CBC) in a browser environment. The authors contacted browser vendors several months ago about this and so, in order not to preempt their demo, I haven't discussed any details until now.

Contrary to several press reports, Duong and Rizzo have not found, nor do they claim, any new flaws in TLS. They have shown a concrete proof of concept for a flaw in CBC that, sadly, has a long history. Early reports of the problem date back nearly ten years ago and Bard published two papers detailing the problem.

The problem has been fixed in TLS 1.1 and a workaround for SSL 3.0 and TLS 1.0 is known, so why is this still an issue?

The workaround (prepending empty application data records) is perfectly valid according to the protocol but several buggy implementations of SSL/TLS misbehaved when it was enabled. After Duong and Rizzo notified us, we put the same workaround back into Chrome to see if the state of the Internet had improved in the years since the last attempt. Sadly it was still infeasible to implement this workaround and the change had to be reverted.

Use of TLS 1.1 would also have solved the issue but, despite it being published in 2006, common SSL/TLS libraries still don't implement it. But even if there was widespread deployment of TLS 1.1, it wouldn't have helped avoid problems like this. Due to a different, common bug in SSL 3.0 implementations (nearly 12 years after SSL 3.0 was obsoleted by TLS 1.0), browsers still have to perform SSL 3.0 downgrades to support buggy servers. So even with a TLS 1.1 capable browser and server, an attacker can trigger a downgrade to SSL 3.0 and bypass the protections of TLS 1.1.

Finally, the CBC attacks were believed to be largely theoretical but, as Duong and Rizzo have pointed out today, that's no longer the case.

Initially the authors identified HTML5 WebSockets as a viable method of exploiting the CBC weakness but, due to unrelated reasons, the WebSockets protocol was already in the process of changing in such a way that stopped it. The new WebSockets protocol shipped with Chrome 14 but several plugins have been found to offer features that might allow the attack to be performed.

Duong and Rizzo confirmed that the Java plugin can be used, but Chrome already blocks the execution of Java by default. Other plugins, if installed, can be disabled on the about:plugins page if the user wishes.

The attack is still a difficult one; the attacker has to have high-bandwidth MITM access to the victim. This is typically achieved by being on the same wireless network as the victim. None the less, it's a much less serious issue than a problem which can be exploited by having the victim merely visit a webpage. (Incidentally, we pushed out a fix to all Chrome users for such a Flash bug only a few days ago.)

Also, an attacker with MITM abilities doesn't need to implement this complex attack. SSL stripping and mixed-scripting issues are much easier to exploit and will take continued, sustained effort to address. Duong and Rizzo have highlighted this fact by choosing to attack one of the few HSTS sites.

Thanks to an idea suggested by Xuelei Fan, we have another workaround for the problem which will, hopefully, cause fewer incompatibility problems. This workaround is currently being tested on the Chrome dev and beta channels but we haven't pushed it on the stable channel yet. Since we don't really know if the fix will cause problems it's not something that we want to drop on people without testing. The benefit of a fix to Chrome's TLS stack is also limited as Chrome already uses the newer WebSockets protocol and it doesn't fix problems in plugins.

If it turns out that we've misjudged something we can quickly react, thanks to Chrome's auto-update mechanism.

It's also worth noting that Google's servers aren't vulnerable to this problem. In part due to CBC's history, Google servers have long preferred RC4, a cipher that doesn't involve CBC mode. Mention has also been made of Chrome's False Start feature but, since we don't believe that there are any vectors using Chrome's stack, that's immaterial.

Russ Cox wrote a very popular post on the Go-Nuts list recently in a thread titled “How can Go solve a problem that is well served by multiple inheritance?”  From a complex discussion of Dijkstra’s shortest path algorithm, multiple inheritance, constrained genericity, and generic types, Russ cut away nonsense to show how “generic” algorithms can be written with clarity in Go using interfaces.  I put generic in quotes there because Russ wrote this long post without ever using the word generic once.  The word is loaded, of course, with preconceptions from other languages which is a good reason to avoid the word in the context of Go, but just as a word in the English language, I think it describes well this style of programming that Go interfaces enable.  It’s a style that separates code from data, allowing the same piece of code to work with a whole class (English language definition) of different types of data.

Of special interest to me, the original post was prompted by a Rosetta Code task, Maze Solving.  I’ll come back to this task later, but first I’ll point out a few other RC tasks that I think are relevant.  One that popped in my mind as I was reading Russ’s post is Parametric Polymorphism.  This is a fancy computer science term and so to complete the RC task in Go I did a bit of homework first.  For a little insight into the task author’s thinking, I checked the original implementation languages.  Haskell, OCaml, and C++.  Uh huh.  Then I followed the Wikipedia links in search of some consensus on the meaning of the term and how I might interpret the concepts within Go.

Wading through all that, my conclusion seemed simple.  A parameter is an input to a function.  Parameter polymorphism is when a parameter can be of different types.  That makes it an interface type in Go.  You can pass objects of different concrete types to the function, and the function will access them generically through a common interface.  We can do that.

The task description suggests implementing a container type, a tree specifically, and a map function that traverses the tree.  Most language examples on the page managed this much, but the task also says to “write … a short bit of code that uses [the parametric type].”  This I found lacking or at least not obvious in most of the examples.  Further, it seemed to me that to really illustrate polymorphism, you should show that this “bit of code” working on multiple types, and thus that you need to actually implement more than one type.  “Poly” as a word prefix, anyone?  So, as I’ve done often on RC, I wrote more than other people wrote.  My example goes a bit farther than others, perhaps farther than the task author was thinking, but as far as I felt was necessary to fully demonstrate the task.

package main

import "fmt"

func average(c intCollection) float64 {
    var sum, count int
    c.mapElements(func(n int) {
        sum += n
        count++
    })
    return float64(sum) / float64(count)
}

func main() {
    t1 := new(binaryTree)
    t2 := new(bTree)
    a1 := average(t1)
    a2 := average(t2)
    fmt.Println("binary tree average:", a1)
    fmt.Println("b-tree average:", a2)
}

type intCollection interface {
    mapElements(func(int))
}

type binaryTree struct {
    // dummy representation details
    left, right bool
}

func (t *binaryTree) mapElements(visit func(int)) {
    // dummy implementation
    if t.left == t.right {
        visit(3)
        visit(1)
        visit(4)
    }
}

type bTree struct {
    // dummy representation details
    buckets int
}

func (t *bTree) mapElements(visit func(int)) {
    // dummy implementation
    if t.buckets >= 0 {
        visit(1)
        visit(5)
        visit(9)
    }
}

I wanted to offer “average” as an example of a generic algorithm. It is my “bit of code” for this task that is parameterized. Everyone knows the algorithm: add up all all the numbers and divide by how many there are. The generic part is that it doesn’t matter where the numbers are stored or how they are organized. All that matters is that you can get them.

Reviewing this RC task inspired me to update another, Knuth Shuffle.  The minimal task requirement is to shuffle an integer array, and so that’s what my initial implementation did.  At the time (January 2011) I didn’t bother with the “if possible, an array of any type” because hey, Go doesn’t do generics, right?  Oh, but this algorithm is so easy to write generically.

Unlike the algorithm for computing averages, this one does have some constraints about the way data is organized.  Specifically, the shuffle doesn’t really make sense unless data is organized in some kind of sequence.  It’s enough to assume that data can be indexed with an integer.  What else is needed?  The number of elements is handy; also the algorithm needs to swap data elements.  The easy way to specify this is by index.  It turns out that’s enough!  Here is what’s needed of a collection:

type shuffler interface {
    Len() int      // number of things in the collection
    Swap(i, j int) // swap the two things indexed by i and j
}

And here’s the algorithm, written generically, parametrically polymorphized, or jargon free–as a simple Go function that uses an interface.

func shuffle(s shuffler) {
    for i := s.Len() - 1; i >= 1; i-- {
        j := rand.Intn(i + 1)
        s.Swap(i, j)
    }
}

As a little aside here, note that shuffler is a subset of sort.Interface. I didn’t have to carefully craft that, or even think about it as I wrote my code, but it kind of makes sense that shuffling and sorting might have similar requirements. Really sorting just has one more, the Less method, which pays attention to the values of the elements. It kind of makes sense that shuffling doesn’t care about the values. A consequence of this is that any type you might happen to have made sortable by ensuring that it implements sort.Interface is automatically shufflable with the shuffle function and interface above. The author of Go’s sort package didn’t have to do anything special to make this possible. You with your sortable type didn’t have to do anything beyond implementing the sort interface, and yet just by including the code above for shuffle and shuffler, you can shuffle anything that you can sort. That’s reusable code.

A number of RC tasks are like Parametric Polymorphism in that they cite a computer science term and ask for examples of it. Constrained Genericity was one I enjoyed finding. I didn’t know the term, but it was plain that Go interfaces do exactly what the task asks for. Abstract type is another one. After puzzling out all the text of the task description and the WP article on the term you can finally say, “huh. So it’s just an interface.”

Returning to the Maze Solving task on RC and the “how multiple inheritance” thread on Go-Nuts, Dijkstra’s shortest path algorithm was held up as a solution and the discussion followed. One comment I liked was the observation that Dijkstra’s algorithm is overkill for the problem—it is designed for weighted graphs, and the maze problem on RC is an equal-weight problem.  Simple breadth-first search would be a fine choice.  (I might code it up soon, as after all the attention from Go-Nuts, no one has bothered to submit a solution to RC.)

Another comment I liked was that even for Dijkstra’s algorithm, a heap-based version is likely overkill.  The observation was that the set of candidate end-points under consideration at any time is likely far smaller than the number of vertices, and that a simple linear search of the candidates is likely sufficient.  Indeed I found this to be true.

I was sure I had coded up Dijkstra’s algorithm fairly recently but when I searched the RC site, I couldn’t find my code.  I finally realized I had coded it not for RC, but for Project Euler.  I located my code then, and sure enough, it used linear search.  The graph for that problem was an 80×80 grid and my program gave the answer (the minimal path from corner to corner) in 13ms.  My comments included a note that I wanted to use container/heap but had problems.  Now with a higher Go-Fu belt, I went back and added the heap optimization.  New run time?  13ms.  In the Go-Nuts thread, a 10k x 10k grid was cited.  Maybe then it would matter.  Not for 80×80 though, and certainly not for 8×11 or whatever one cares to show for the RC task.

Um, so, speaking of Project Euler, sorry for spamming people with password protected blog posts.  No one complained, but someone probably should have.  Anyway, I moved them to a separate wordpress.com blog, linked to at the top of this one.  My Dijkstra code was done for problem 83, now at (still password protected) http://gopeuler.wordpress.com/2011/09/20/pe-83/

A few months back I described DNSSEC authenticated HTTPS in Chrome. This allows sites to use DNSSEC, rather than traditional, certificates and is aimed at sites which currently use no HTTPS, or self-signed certificates. Since Chrome 14 is now stable, all Chrome users now have this experimental feature.

(Also, the serialisation format has been documented.)