Home About RSS

Tripping on Go: bloxorz

The Go language

Go is a fast, statically typed, compiled, garbage-collected language that feels like a dynamically typed, interpreted 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.

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 prefarably 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 exervice, 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 method 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 suprising (and maybe disappoitning) part of Go: unlike in other languages, there is little built-in support for collections. More on that later.

Leveraging the presence of channels, each time the BFS runs into a solution, we send it to a channel. A channel can be seen as a pipe, for commmunication purpose. As they say in their slogan:

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 interrested 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.

solutionChannel := make(chan Path)
go Solve(terrain, solutionChannel)

solution := <-solutionChannel
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 invokation 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.

Pros and Cons

I like:

I don’t like:

C, Pascal, and modern design

Chirashi sushi, Wikipedia

Being a C-family language with significant input from Pascal makes Go exquisite. It’s like eating chirashi sushi. 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.

Simple programming model

The limited amount of concepts makes it easy for Go to fit in your head. There is no steep learning curve. It’s not like, say, Scala.

Concurrency

Concurrency is at the heart of Go and makes concurrent programming easy (or easier).

Fast

If Ken Block was a developer, Go is what he would probably use for his gymkhana.

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. That ought to count for something. Unified style is encouraged by the use of the formatting command go fmt.

Collections

As mentionned 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 that’s just the way it is. Sigh.

Arrays, slices and map are all you’ll get. You can implement a Set with a map, a few wrapper/helper methods and maybe an empty interface. Fair enough, but why would I want to spend time on that?

There’s a doubly linked list that didn’t fit the bill for my Path so I ended up rolling my own Tail, Contains and friends myself. Again, not the most productive thing to do even though we’re not talking about a great amount of work.

And for the queue, I borrowed from hishboy, but relying on “some lib found on the internet” for such a trivial purpose, no matter how good and carrefully designed it is, seems like a poor man’s solution.

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.

Exceptions

No support for exceptions neither, but the justification does not hold the water IMO.

We believe that coupling exceptions to a control structure, as in the try-catch-finally idiom, results in convoluted code. It also tends to encourage programmers to label too many ordinary errors, such as failing to open a file, as exceptional.

So try-catch-finally would be more convoluted than, say, checking a possible error return code of each call that would fit in a try block? Nah, I don’t buy it.

I would also argue that a failure to open a file, in itself, does not have to be handled on the spot. What would you do instead in Go ? Check an error code, log it and… use panic? Or return? Rather, a throws FileNotFoundException as in Java does not imply you have no clue of what you are doing.

Well, it might be the case with a poor or a beginner programmer, but a poor programmer will also fail to check return codes properly. Again, I’m not convinced.

Throwing an exception may simply indicate that there’s nothing you can do about it if it happens, and that it is not your responsibility to act upon it. Probably the caller will be able to display an error message in a Swing component, or send an HTTP error code with some JSON to its client. Often, it is none of your concerns.

On the bright side, 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)
}

Too bad the unpretty if err != nil { return } ruins the days.

Where to start

© Youri Ackx 2007-2024 ・ Powered by Hugo ・ Mentions légales ・ Déclaration vie privée