Russ Cox

Sep 16 (20 hours ago)
Re: [go-nuts] How can Go solve a problem that is well served by multiple inheritance?
> In the Eiffel implementation a key aspect to its efficiency is multiple
> inheritance: this allows objects to access things in a way that Go's
> embedding doesn't seem to support.
I don't think this is a key aspect to its efficiency, nor to
its brevity.  It is, however, a key aspect to its multiple
inheritance.

> * Of course, I am not claiming that you can't implement Dijkstra's
> * algorithm in Go. The claim is that you can't take two types, one for
> * directed graphs and one for priority queues, and use them, without
> * rewriting their methods, to produce a version of Dijkstra's algorithm
This question betrays an inheritance-oriented bias: it
assumes that to reuse an algorithm, you have to do it by
inheriting from a type that implements that algorithm.  Go
doesn't buy into that.  Algorithms are code, not types.
They obviously operate on values that have types, and each
algorithm has requirements it places on the types of values
it can operate on, but in the end, an algorithm is not a
type, nor is it embodied by a type.  Algorithms are code, so
it is idiomatic to express them in Go as functions.

Sort is a good example.  There are many kinds of sorting
algorithms, but a very common kind is comparison-based,
meaning that the operations it expects to be able to apply
to the data are to compare two elements at arbitrary indices
and perhaps also swap them.  The Go sort package defines an
interface, sort.Interface, that must be implemented by any
data that wants to submit itself to this kind of sorting
algorithm:

package sort

type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less returns whether the element with index i should sort
// before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}

If your type implements sort.Interface, you can sort what it
represents, by passing it to the sort.Sort function - the
actual algorithm.  We changed the algorithm recently,
actually, and no one noticed, because the details are hidden
behind this simple signature:

func Sort(data Interface)

So far this doesn't look too different than many languages,
because there is no actual state that Sort must maintain
other than the values themselves.  Maybe another language
would choose different methods, but it's about the same.

Heaps are another good example, and where things start to
diverge from inheritance-oriented languages.  Instead of
requiring each element that will be stored in a heap to
inherit from some heap-element type, Go's heap package
defines the interface required of a container in order to
apply the heap algorithms to it:

package heap

type Interface interface {
   sort.Interface
   Push(x interface{})
   Pop() interface{}
}

The container needs to be able to do the comparison
operations that sort requires, and it also needs to be able
to push an element onto the end of the underlying array and
to pop an element from the end.

If your container implements those operations, you can call
the heap algorithm operations:

func Pop(h Interface) interface{}
func Push(h Interface, x interface{})
func Remove(h Interface, i int) interface{}

Remove is the interesting operation here: it requires that
you give it the heap index of the element you want to
remove, not the element itself.

In an inheritance-oriented language, you can pass the
element itself because the element type inherits from a
master heap element type that the heap algorithm updates
with its current index every time it moves within the heap.
That has an implication: you can only put your element into
one heap at a time.  Since you only need this info during
Remove, we decided in Go to let the caller do the tracking
when necessary (and skip it if not).  The most obvious
implementation is to stick an index into the struct being
moved around, like in this code from package time:

func (timerHeap) Swap(i, j int) {
timers[i], timers[j] = timers[j], timers[i]
timers[i].i = i
timers[j].i = j
}

but it's also possible to leave it out (if not calling
Remove) or to do something more general (if you want one
object to be storable in multiple heaps).  In Go there is no
PRIQUEUE_EXTENDED_FIBHEAP_ENTRY to inherit.  This is
especially important if you are building a heap of objects
of a type you don't control, which comes up when writing
Dijkstra's algorithm.  (You could even implement an on-disk
heap using Go's heap package; trying doing that when a disk
block has to inherit from PRIQUEUE_EXTENDED_FIBHEAP_ENTRY!)

Speaking of Dijkstra's algorithm, there's no implementation
in the standard library, so I wrote one.  It expects an
input that satisfies the Graph interface:

package graph

type Graph interface {
// NumVertex returns the number of vertices in the graph.
NumVertex() int

// VertexID returns a vertex ID, 0 <= ID < NumVertex(), for v.
VertexID(v Vertex) int

// Neighbors returns a slice of vertices that are adjacent
// to v in the graph.
Neighbors(v Vertex) []Vertex
}

type Vertex interface {
String() string
}

func ShortestPath(g Graph, start, end Vertex) []Vertex

Here I've decided that a Graph should be able to give each
vertex a dense numeric ID, which the various graph
algorithms can use to identify the vertex.  Note that I am
not requiring a Vertex to be a
PRIQUEUE_EXTENDED_FIBHEAP_ENTRY.  Why should internal
details of the implementation of ShortestPath leak into the
interface required of its callers?

ShortestPath is straightforward:

// ShortestPath uses Dijkstra's algorithm to find the shortest
// path from start to end in g.  It returns the path as a slice of
// vertices, with start first and end last.  If there is no path,
// ShortestPath returns nil.
func ShortestPath(g Graph, start, end Vertex) []Vertex {
d := newDijkstra(g)

// Run Dijkstra's traversal.
d.visit(start, 1, nil)
for !d.empty() {
p := d.next()
if g.VertexID(p.v) == g.VertexID(end) {
break
}
for _, v := range g.Neighbors(p.v) {
d.visit(v, p.depth+1, p)
}
}

// Reconstruct path.
p := d.pos(end)
if p.depth == 0 {
// unvisited - no path
return nil
}
path := make([]Vertex, p.depth)
for ; p != nil; p=p.parent {
path[p.depth-1] = p.v
}
return path
}

The visit and next methods contain calls to container/heap's
heap algorithm functions, but that fact does not leak into
the Graph interface.  The ShortestPath code manages separate
state on the side (the value d of type dijkstra) instead of
requiring that state to be mixed into the Graph that is
passed in.

A maze, of course, is a very specialized kind of graph, in
which each vertex has at most four neighbors drawn from a
fixed set.  It is easy to implement a custom Maze type and
then add the methods to implement graph.Graph.

The maze "solver" is then just a call to ShortestPath:

m := NewMaze(w, h)
path := graph.ShortestPath(m, m.Vertex(0, 0), m.Vertex(w-1, h-1))
fmt.Println(m.PathString(path))

The full code is at:
http://code.google.com/p/rsc/source/browse/rosetta/graph/graph.go
http://code.google.com/p/rsc/source/browse/rosetta/maze/maze.go

You can play with the code by running

goinstall rsc.googlecode.com/hg/rosetta/maze
maze
maze
maze

If you look through the code, the only time there are
conversions is to turn a Vertex into a maze.pos or an
interface{} into a *graph.dpos.  Those are fundamental to
the way you write type-agnostic algorithms in Go: they have
to operate on interface values, and then the implementations
that accept those interfaces need to write a converson
occasionally.  There are two in package graph and three in
maze.  I don't believe that rises to the level of
"extraneous rubbish".

It is easy to get caught in the trap of seeing a piece of
nice code in another language, like this
multiple-inheritance Eiffel shortest path, and then trying
to translate the concepts into Go instead of stepping back
to think about how you'd approach the problem and the
solution from a Go point of view.  Taking an Eiffel point of
view when trying to write a Go program will not produce
nice, idiomatic Go code.  Quite the opposite.  But if you
can avoid the trap, and you come at it thinking about Go
concepts instead of concepts from some other language, I
think you can arrive at an elegant solution.

This makes Go different from many languages: because so many
of today's languages are inheritance-oriented languages, it
is easy to move between them and transliterate code, because
the underlying model is the same.  Go is built on a
different model, so trying to move code from Eiffel or
Python or Java or C# or C++ to Go usually works poorly.  You
have to start over, thinking in Go.

Go's interfaces force you to separate code from data.  You
don't get to mix them like you do in inheritance-oriented
languages.  This is certainly limiting - at the least, it
makes code in inheritance-oriented languages harder to
convert to Go - but it has benefits too.  For example,
because the ShortestPath state is not mixed into the Maze's
Vertex implementation, it is possible for multiple
goroutines to run graph.ShortestPath on the same maze
simultaneously (presumably with different start, end pairs).

It's unfortunate that every time someone asks for
inheritance the answer is "well, there's embedding."
Embedding is useful and a kind of inheritance, but when
people come looking for inheritance, embedding is not the
answer.  The answer is: you're thinking in C++, or in Python
or Java or Eiffel or whatever.  Don't do that.  Think in Go.

Russ