Sunday, 12 May 2013

Go: Interfaces and Type Assertion

Hot on the heals of my last post, I feel I have to share a little trick I just discovered about type assertions. While it is documented within the language specs I handn't really seen anyone talk about this in a formal manner until coming across a post in the Go mailing list.

In the pursuit of implementing Scheme-like functional behaviour in Go in order to solve some exercises in SICP I discovered a problem: Scheme is dynamically typed and it's internal data structures (cons, list) allow for mixed types. While this is obviously handy it creates some problems, most important of which is type safety. Thankfully, Go provides an awesome way to handle this: an empty interface.

Go's implementation of interfaces is awesome. It might be a bit foreign to those who come from other languages with interfaces, like Java, where you have to specifically state that an object implements an interface. No so in Go. If you want an object to implement an interface just implement it. Objects can then be used anywhere that accepts that interface. You don't need to explicitly state anything. An object either implements an interface or it doesn't. However, that's not what this post is about. No, this is about type assertions and the empty interface.

An empty interface is just that: Empty. That means that any type matches an interface because the empty interface has no requirements, no functions to implement. You could think of the empty interface as a generic type but I think that's misleading. Interfaces are interfaces and types are types. And this leads us to what I want to talk about. Implementing a list type which accepts multiple types, all at once:

type List []interface{}

We've created a slice type which accepts variables of any type. As I've already stated, the empty interface doesn't have any requirements so every type implements its interface, which is why we can use it like this. What's truly brilliant, is that we can use all the slice operations on this new type just like regular slices like ranging through the slice or creating sub-slices. This absolves us from even creating a constructor. If you want to simply create a list of integers do:

l := List{1, 2, 3, 4}

Fan-freakin-tastic, I say! So we've created a list type that behaves like it's dynamically typed. The icing on the cake is that we don't even need to create a custom String() function for our List type, even with nested Lists!

This is great and all except that Go isn't dynamically typed. So, what happens if we create a list of integers and try to add them up? Well, since an interface{} isn't a type, and we try to use the + operator on it, the compiler will fail with an error. So, how can we get around this? Type assertions. We can assert that an element in the list is of a specific type by using a type assertion:

l[0].(int)

But, there's a problem with that. We don't know what type we might have and we can't guarantee what we've received is what we expect. If we assert that an element in the list is a specific type, and we're wrong, our program will panic and, if not caught, will crash our program. And this, finally, is what I've been wanting to talk about. Thanks to our intrepid Go developers, functions can have multiple return types. In the case of type assertions, we can check to see if the assertion succeeded, which suppresses the panic if we're wrong. So let's write an Accumulate function which performs an operation on our list:

type Operation func(int, int) int

func (l List) Accumulate(f Operation) interface{} {
res := 0
for _, v := range(l) {
if i, ok := v.(int); ok {
res = f(res, i)
continue
}
if lst, ok := v.(List); ok {
res = f(res, lst.Accumulate(f).(int))
}
}
return res
}

Voila! Now, you'll notice that I've cheated a bit where I assert that the value returned by Accumulate is an integer on line 11, after I test whether the current item in the list is another list. Since I know that Accumulate can only ever return an integer I can be safe in that assumption even though Accumulate returns another empty interface. I could have just made Accumulate return an integer and avoided the type assertion completely but the point was to create a function which could accept and return any type. We might want to be able to concatenate strings or operate on floats. However, I cheated a bit in the implementation details for simplicity's sake. Obviously, if you wanted to write an Accumulate function which accepts lists containing many types different types you'd have to do a bit more work to test what type you received back.

Thankfully, there's another way you can test what type a variable is. If you need your function to accept many different types, you can use an assertion switch. In my case, I didn't need to go that far because I knew I was only dealing with integers and lists of lists. However, I'll show you an example of what it might look like:

func (l List) Accumulate2(f Operation) interface{} {
var res interface{} for _, v := range(l) { switch t := v.(type) { case int: if res == nil { res = 0 } res = f(res.(int), t) case List: if i, ok := t.Accumulate2(f).(int); ok { res = f(res.(int), i) } } } return res
}

And that, as they say as that! Strictly speaking, you'd have to do a heck of a lot more work if you were to add more types. For one, what would happen if there were strings mixed with ints? Or even floats and bytes? This function only really works if all the elements are of the same type or if elements are other lists. If, though, you do need to wrestle with mixed types in a single list you might need to rethink the problem you're trying to solve!

Hopefully, this has provided you with another tool to add to your toolbox, as it did for me. For the complete source code, go here.

Saturday, 4 May 2013

Data as Procedures

* Updated: Made the example a little more idiomatic and used a more intuitive type for differentiating between the numerator and denominator. Thanks to the excellent comments/suggestions! *

It has been a long while since my last post. Having a stressful full-time job, two kids under the age of five, and all the other fun and foibles that come along with life has been a natural distraction. Hopefully, I can get back into the swing of things again but I make no promises!

I've begun reading Structure and Interpretation of Computer Programs. It has proved, thus far, to be truly enlightening and I feel the need to talk about my first revelation, of a sorts. Coming from a primarily imperative based background, functional programming is somewhat foreign to me. For example, the concept of data as procedures came as truly mind boggling. Even the book pokes fun at the reader about it! I have only ever known data as container constructs. In C and Go these would be structs and in C++ and Java, classes. However, through the use of closures you can do away with data structures and use procedures instead.

SICP uses the example of representing a rational number. A rational number consists of a numerator and a denominator and we normally write them as a faction (i.e. 3/4). In essence, they're a number pair and you could represent them as a structure quite easily:


type RationalNumber struct {
numerator, denominator int

}


You would then create constructor and selector procedures to operator on the data structure. Nothing new here. However, there is a way to do away with the data structure. First we'll create the constructor. This is the hard part:


type Fraction func(bool) int

func NewFraction(n, d int) Fraction {
return func(z bool) int {
if z == true {
return n
}
return d
}
}


Utilizing a closure, we create a function which returns a function containing our data. To make this a little more idiomatic Go we've made the return function it's own type. If we supply this function with a value of true it returns the numerator and if we supply false it returns the denominator.

The rest becomes trivial. We just create our selectors to accept the closure as a parameter and tell it what we want to return:


func Numerator(f Fraction) int {
return f(true)
}

func Denominator(f Fraction) int {
return f(false)
}


Voila! We've just represented data without using a data structure! Colour me impressed! In a language like Scheme the implementation is a lot cleaner looking. Because Go emphasis type-safety we have to do define a lot of data types making thing look a lot more complicated than they really are.

Full source code for this example can be found here. Click run to see it in action.


If you want a more thorough, professional explanation I highly encourage you to read SICP yourself. If you want a PDF you can find a link on the Wikipedia page.