Archive for September, 2010

Lenses and Listeners in Go.

September 20, 2010

A little while ago, I developed a small experimental graphics package for Go, with the aim of giving full rein to the concurrency of the language and keeping things as modular and “building block”y as possible.

I wanted to allow an application to be structured as many independent agents, each interacting freely with the graphics environment, with independent communication between them.

I haven’t got there yet with the API design (although I’m happy with the way that some things work), but I do particularly like a package I created to solve one problem. It mixes functional style, interfaces and channels in a way that is seems to me to be uniquely “Go-like”. Whether it’s nice or useful I’ll leave you to decide.

Scratches on the wall

Imagine that the screen is a physical blackboard with several people writing on it. Each person can independently make marks on the board, and they can talk to others to help them decide what to write. Others in the room attend to different tasks, writing letters to the outside world, talking amongst themselves and to the people at the blackboard.

With goroutines as people, and talking as communication over a channel, this is how I imagine the graphical environment could be in Go. There is one difficulty, however, and that’s the problem of deadlock. In graphical environments, there are often several elements that reflect one another – for instance, a slider bar might have a textual display of its value, and the value might be used to determine the graphical appearance of some other element.

If each element is represented with a goroutine, then the above setup implies a cyclical dependency. The slider bar can be dragged, the textual display may be edited, and the graphical appearance may be changed as a result of some other action – each of which implies a change to the other two elements.

Naively, we might model this system something like this:

	func SliderElement(setc <-chan float64, getc chan<- float64) {
		var currentValue float64
		for {
			select{
			case currentValue = <-setc:
	
			case m := <-MouseEventChannel:
				currentValue = mousePointToValue(m)
				getc <- currentValue
			}
			drawSlider(currentValue)
		}
	}
			
	func TextElement(setc chan<- string, getc <-chan string) {
		<i>... similar to SliderElement</i>
	}
	
	func GraphicalElement(setc chan <-float64, getc <-chan float64) {
		<i>... also similar to SliderElement</i>
	}
	
	func setup() {
		sliderSet := make(chan float64)
		sliderGet := make(chan float64)
		go SliderElement(sliderSet, sliderGet)
	
		textSet := make(chan string)
		textGet := make(chan string)
		go TextElement(textSet, textGet)
	
		graphicalSet := make(chan float64)
		graphicalGet := make(chan float64)
		go GraphicalElement(graphicalSet, graphicalGet)

		// communications goroutine
		go func() {
			select {
			case v := <-sliderGet:
				textSet <- fmt.Sprint(v)
				graphicalSet <- v
			case v := <-textGet:
				f, err := strconv.Atof(v)
				if err != nil {
					// what now?
					break
				}
				sliderSet <- f
				graphicalSet <- v
			case v := <-graphicalGet:
				textSet <- fmt.Sprint(v)
				sliderSet <- v
			}
		}()
	}

There is are a few problems with this approach, but one show-stopper: it can deadlock. If the communications goroutine happens to be sending on graphicalSet at the same time that the graphical element has decided that it will change, then the two will block forever trying to perform the operation, and the whole thing will hang up. This is fairly unlikely if all the “set” actions are triggered by user mouse events, but not impossible. When independent actions are added to the mix, for example when triggered by a network communication, then it becomes much more likely.

Other problems with the above structure:

  • The number of elements is hard-wired into the communications goroutine. How would we introduce a variable number of graphical elements depending
    on the value?

  • The update speed of one element is linked to the update speed of all of them. If one of the elements is slow to update (for example, the graphical element might be a picture that takes 200ms to redraw), then
    the slider will be sluggish to react.

  • There is no way for the text element to know that the user has entered some invalid text without building knowledge of the acceptable format into it.

The Value of Listening

As one possible solution to this issue, I implemented the “values” package (rog-go.googlecode.com/hg/values). Instead of elements talking directly to one another, they talk to a proxy, a Value, which acts as an intermediary. Any goroutine can set the contents of a value or ask to be notified when the value changes.
The Value type is an interface as follows:

	type Value interface {
		Set(val interface{}) os.Error
		Iter() <-chan interface{}
		Close()
		Type() reflect.Type
	}

To create a new Value, we use values.NewValue:

	v := values.NewValue(0.5)

This creates a new Value holding a single floating point number, 0.5. We can set its contents with Set:

	v.Set(0.6)

Despite the interface{} argument to Set, only a single type of value may be stored, fixed by the initial value passed to NewValue.

	v.Set("hello")		// runtime error

If we want, we can find out that type:

	fmt.Printf("%v\n", v.Type())		// prints "float64"

If we wish to observe changes to the value, we use Iter. This code will start a new goroutine that prints the value each time it changes:

	c := v.Iter()
	go func() {
		for x := range c {
			fmt.Printf("%v\n", x)
		}
	}()

One key property of Value is that Set never waits for the observers to receive the value – in fact, it never blocks. This means that two goroutines that are observing changes to a Value can call Set on that value without risk of deadlock.

There is, however, aother risk: calling Set in response to a value received on the Iter channel will lead to livelock:

	c := v.Iter()
	go func() {
		// this loops forever, printing the same value.
		for x := range c {
			fmt.Printf("%v\n", x)
			c.Set(x)
		}
	}()

As a result, we have a rule: do not call Set in response to a notification of a changed value.

With the primitives we now have, we can join the slider to the graphical element. The code for the Elements is still fairly similar, but the setup() glue becomes much simpler:

	func SliderElement(v Value) {
		c := v.Iter()
		currentValue := <-c.(float64)
		for {
			select{
			case currentValue = <-c:

			case m := <-MouseEventChannel:
				currentValue = mousePointToValue(m)
				v.Set(currentValue)
			}
			drawSlider(currentValue)
		}
	}

	func GraphicalElement(v Value) {
		... similar to SliderElement
	}

	func setup() {
		v := values.NewValue(0.5)
		go SliderElement(v)
		go GraphicalElement(v)
	}

Here we have linked two elements – each can be independently manipulated, but each one always shows the current value. We would like to link in the text element too, but there’s one problem: the text element uses strings, not float64s.

If we could create a value that mirrors the original value, but using a textual representation instead of the original float64 representation, then implementing TextElement would be simple. As it happens (ta da!) the values package makes that quite straightforward.

In focus

“Lens” is a term (probably misborrowed) from functional language terminology. The analogy is the way that light can pass through a glass lens in either direction, bending one way on the way in, and the other on the way out.

I represent a Lens as a pair of functions, one implementing the inverse transformation to the other.

	func stringToFloat(s string) (float64, os.Error) { return strconv.Atof(s) }
	
	func float64ToString(f float64) (string, os.Error)  { return fmt.Sprint(f), nil }
	
	var stringToFloatLens = values.NewLens(stringToFloat, float64ToString)

Despite the analogy, a Go Lens is actually unidirectional.

	x, _ := stringToFloat64Lens.Transform("1.34e99")
	fmt.Printf("%g\n", x.(float64))

To transform in the opposite direction, the Lens can be reversed:

	float64ToStringLens := stringToFloat64Lens.Reverse()
	x, _ := float64ToStringLens.Transform(1.34e99)
	fmt.Printf("%s\n", x.(string))

We can transform the type of a Value using values.Transform and a Lens.Values passed to Set are passed through the lens one way; values received from Iter are passed the other way. Thus we can complete our setup function by adding the third element:

	func setup() {
		v := values.NewValue(0.5)
		go SliderElement(v)
		go GraphicalElement(v)

		sv := values.Transform(v, float64ToStringLens)
		go TextElement(sv)
	}

One more piece completes the toolkit: Lenses can be combined. Suppose, for example, that the Slider value ranges between 0 and 1, whereas the value expected by the graphical element and displayed in the text element varies from -180 to +180.

The values package provides a lens which implements this kind of transformation: UnitFloat2RangedFloat.
Here’s how it might be used:

	func setup() {
		v := values.NewValue(0.5)
		unit2angle := values.UnitFloat2RangedFloat(-180, 180)
		go SliderElement(v)
		go GraphicalElement(v.Transform(unit2angle))
		go TextElement(v.Transform(unit2angle.Combine(float64ToStringLens)))
	}

The observant might note that there are actually two ways of doing this. Without using Combine, we could apply two successive transformations using values.Transform: The two forms are subtly different – values.Transform introduces a new goroutine, and one more buffer element into the channel, whereas Combine does not.

In a subsequent blog post, I plan to talk a little more about the kinds of structures that can be built with this primitive, how it is implemented and performance considerations.

Advertisements