Generics and how I resolved my use case

[egon]

Well, I'm reimplementing an algorithm called SPEXS (https://github.com/egonelbre/spexs/, from thesis "Pattern Discovery from Biosequences").

That algorithm generalizes over two types: Pattern and Reference. Using only empty interfaces it looks like:

// shortened some parts, actual code is correctly formatted

interface Pattern {}

interface Reference {}

type Pooler interface {

Take() (Pattern, bool)

Put(Pattern)

}

type ExtenderFunc func(p Pattern, ref Reference) Patterns

type FilterFunc func(p Pattern, ref Reference) bool

type FitnessFunc func(p Pattern) float64

type Setup struct {

Ref Reference

Out Pooler; In  Pooler

Extender ExtenderFunc

Extendable  FilterFunc; Outputtable FilterFunc

}

func Run(s Setup) {

for {

p, valid := s.In.Take()

if !valid { return }

extensions := s.Extender(p, s.Ref)

for extended := range extensions {

if s.Extendable(extended, s.Ref) { s.In.Put(extended) }

if s.Outputtable(extended, s.Ref) { s.Out.Put(extended) }

}

}

}

Since there are many possible Extender, Extendable, Outputtable combinations it would be unreasonable to implement a type cast for all the functions (src spxs/  filters.go, extenders.go, fitnesses.go). I know that I could have hidden the type cast inside some function, but the type casts would be quite often, so there was a perfomance loss (~4%) as well. (Just a note that this algorithm can run in the worst case O(n^2*2^k), where k < 30, and n >> k, which means the type cast is called in the worst case w*n^2*2^k, w ~= 5). Also the type checks at compile time are really useful.

First idea, was that when using interfaces I could just do a type alias to my type and copy the files to a separate directory. I moved the Pattern and Reference declaration to separate file "generic.go" and reimplemented it as:

type Pattern *Node

type Reference *UnicodeReference

Ok, this didn't go as well as I thought. Since Node doesn't implement Pattern I can't give it as a parameter to extender and other functions. When declaring those functions using "Pattern", I still wasn't able to do it, since it lost all the methods.

Second idea:

type Pattern struct{ *Node }

type Reference struct{ *UnicodeReference }

Well this didn't go as well either, as I always needed to extract the Node plus constructing this type got confusing at some places.

Finally I just resulted to replacing all the Pattern and Reference in the algorithm with *Pattern and *Reference. And declared in generic.go

type Pattern struct{}

type Reference struct{}

And implemented my Node as Pattern instead. And this worked... although I have some code duplication, then again it's close enough to what I wanted.

Hopefully you aren't yet fed up with generics proposals... so what would have been the minimal features that would have resolved my case: specialized import/include:

specialize "spexs" {

Pattern *Node

Reference *UnicodeReference

}

Which would mean it pulls in spexs package/file with all interface usage of Pattern replaced with *Node and Reference with *UnicodeReference. Also doing a type check whether *Node and *UnicodeReference satisfy those interfaces. This would mean that the generic things must be first written as proper interfaces. Also it makes hard to do obscure things with it.

I haven't thought about all the implications of this way of doing generics, but hopefully it gives some good ideas.

- egon