foo::bar

Blogs and RSS are cooler than ever

Tripping on Go: bloxorz

The Go language

Go is a fast, statically typed, compiled, garbage-collected language. It was designed and developed to make working in a modern environment (multicore processors, networked systems, massive computation clusters) more productive, lightweight and pleasant.

Three blue gophers

A basic bloxorz solver

After a short intro and a few samples on the golang website, nothing beats coding when it comes to learning a programming language. Something not too trivial but not too complex neither, and preferably fun.

A bloxorz solver seemed appropriate. It’s a simple, yet addictive game where you move a rectangular block around squares on a floating platform, following certain rules. Well, just try it!

I didn’t bother taking into account all the fancy terrain variations like soft squares (where the block must be lying rather than standing up), switches, bridges and other puzzling tricks. For the exercise, a plain terrain will do.

Blocks

Let’s start with a Block. The Block is a simple struct.

type Block struct {
    ax, ay, bx, by int
}

Provided x and y vectors, it is able to move around, or more exactly, to create a new block based on its current position and the vectors.

// Create a new Block moved relative to this Block
// according to the given vectors.
func (block Block) move(dx, dy int) *Block

move is a function that applies to a Block, takes 2 int arguments and returns a pointer to a (new) Block.

BFS, channels and goroutines

For each candidate solution, we must retain the path followed as a list. And we’ll also need a queue for our breadth-first search (BFS). But there are no lists nor queues per se in Go. To me, that’s the most surprising part of Go: unlike in other languages, there is little built-in support for collections. More on that later.

Leveraging channels, each time the BFS runs into a solution, we send it to a channel. A channel can be seen as a pipe, for communication purpose. As the saying go(es):

Do not communicate by sharing memory; instead, share memory by communicating.

Sending data to a channel is as easy as this:

// Found a solution
solution <- newPath

The caller (here, a unit test) can simply call the Solve function with a channel and wait for one or more solutions on the channel. Since we’re mainly interested in the (or one of the) optimal solutions with the smallest number of moves, we’ll read the first one and be done with it.

// Create a channel for the solution(s)
solutionChan := make(chan Path)
// Solve the terrain
go Solve(terrain, solutionChan)
// Wait for the first solution and print it
solution := <-solutionChan
fmt.Printf("%s first solution in %d moves: %s\n",
    name, len(solution)-1, solution.String())

The call is made in a goroutine, with the invocation go Solve. A goroutine is a function executing concurrently with other goroutines in the same address space. The language authors did not want to call them threads, coroutine or processes because of the inaccurate connotations they convey. They are not threads - several goroutines can be multiplexed on a single thread.

The combination of channels and goroutine is one of the powerful Go constructs.

The actual iterative BFS solving function works with a Terrain, a pointer to a Queue and our solution channel. The queue is initialized with a single path containing the start block.

func solveIter(terrain Terrain, queue *lang.Queue, solution chan Path)

No rocket science for the rest, only an exercise to get acquainted with the language. Note: there are certainly things that leave to be desired, for instance, methods on Path are partly on a *Path and partly on Path. While technically correct, this is not consistent. And I’m sure I should be closing my channels somewhere, but my attempts lead to dreaded deadlock error messages at compile time.

Illustration of Bloxorz

Pros and Cons

I like:

I don’t like:

C, Pascal, and modern design

Being a C-family language with significant input from Pascal makes Go exquisite. It might not be to your liking. But don’t let the “C” part fool you. There is no pointer arithmetic and the syntax looks more like Pascal than C. The syntax includes changes from C aimed at keeping code concise and readable.

Go is not object-oriented in the usual sense. There is no type hierarchy:

A type automatically satisfies any interface that specifies a subset of its methods, which allows to reduce bookkeeping. Types can satisfy many interfaces at once, without the complexities of traditional multiple inheritance. Interfaces can be added after the fact if a new idea comes along - without annotating the original types. Because there are no explicit relationships between types and interfaces, there is no type hierarchy to manage.

Noteworthy:

Idioms and style

Idioms are important in Go. The documentation often refers to Go idioms and that’s a good thing. 16 mentions of “idiom” on the “Effective Go” page. Unified style is encouraged by the use of the formatting command go fmt.

Collections

As mentioned before, the limited built-in collections came as a big surprise. One of those “this can’t be” moment, followed by “I must have missed something”, before you realise it is as intended. Arrays, slices and maps are all you get. You can implement a Set with a map, a few wrapper/helper methods and maybe an empty interface.

EDIT 2014-03-01: In Go, “a channel is just a simple thread-safe FIFO”. If you don’t need peek/poll operations, like it is the case here, a channel will do. There’s more than one way to skin a cat. Thank you Martin for your comment.

Generics

Generics are missing, for better or for worse. All things considered, it’s wiser not to have them rather than adding an ill-designed incarnation of them. Actually not a deal breaker. The worst implication is probably the limited support for collections and the possible heavy use of the empty interface interface {} to satisfy your needs. UPDATE: Generics are now available in Go 1.18.

Errors

Go makes it easy to report an error without overloading an error value and to treat it:

if value, err := MySqrt(i); err != nil {
    fmt.Println("Error!"")
} else {
    fmt.Println("It's ok!")
}

Yet I don’t find it more readable nor more zen than exception handling. But that’s ok.

The defer construct however is interesting.

func CopyFile(dstName, srcName string) (written int64, err error) {
    src, err := os.Open(srcName)
    if err != nil {
        return
    }
    defer src.Close()

    dst, err := os.Create(dstName)
    if err != nil {
        return
    }
    defer dst.Close()

    return io.Copy(dst, src)
}

Where to start