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.