Self referencing interface type "chicken and egg"..

[xiio...@gmail.com]

(has this come up before?)

I was writing an interface for shortest path algorithms and came across an issue  -

type Node interface {

    GetNumberConnections() int

    GetConnection(int) (bool, Node)

    Distance(Node) vectors.Ftype  //    get the distance between 2 nodes

    TotalDistance() vectors.Ftype //    the total distance from the zeroth node

    SetTotalDistance(vectors.Ftype)

    GetParentNode() Node

    SetParentNode(Node)

}

when I try to implement the interface with a "mapnode" struct type - the function :

func (mn mapnode) Distance(mn2 mapnode) vectors.Ftype {

    h1 := mn.parentarray.underlyingmap.array[mn.x][mn.y]

    h2 := mn2.parentarray.underlyingmap.array[mn2.x][mn2.y]

    distance := (h2 - h1)

    return distance * distance

}

 I've abstracted the problem here : https://play.golang.org/p/j8SFhePBPY

The compiler doesn't like this, though if it could be persuaded to allow mapnode as a valid Node interface type there would be no issues. (chicken and egg).

I have a workaround which involves a minor rewrite of my interface avoiding the self reference.. but in general is there a fix for such self references ? Is this something the language designers feel should work..? or plan to fix or ignore

[Danver Braganza]

What you need to do in this instance is change the signature of Distance to

func (mn mapnode) Distance(mn2 Node) vectors.Ftype {

You want to ensure that Distance can be called between ANY two Nodes, no matter what their underlying type is, no just between two Nodes that happen to have the same underlying type.

[Jérôme Champion]

It's not gonna change. You could check the sort package to see how it deals with such problem.

(Instead of having an Interface for a single node, it define an interface for a group of node)

[Matt Harden]

On Sat, Aug 15, 2015 at 2:04 PM <xiio...@gmail.com> wrote:

(has this come up before?)

I was writing an interface for shortest path algorithms and came across an issue  -

type Node interface {

    GetNumberConnections() int

    GetConnection(int) (bool, Node)

    Distance(Node) vectors.Ftype  //    get the distance between 2 nodes

    TotalDistance() vectors.Ftype //    the total distance from the zeroth node

    SetTotalDistance(vectors.Ftype)

    GetParentNode() Node

    SetParentNode(Node)

}

when I try to implement the interface with a "mapnode" struct type - the function :

func (mn mapnode) Distance(mn2 mapnode) vectors.Ftype {

    h1 := mn.parentarray.underlyingmap.array[mn.x][mn.y]

    h2 := mn2.parentarray.underlyingmap.array[mn2.x][mn2.y]

    distance := (h2 - h1)

    return distance * distance

}

 I've abstracted the problem here : https://play.golang.org/p/j8SFhePBPY

The compiler doesn't like this, though if it could be persuaded to allow mapnode as a valid Node interface type there would be no issues. (chicken and egg).

That's not true. The type Distance(mapnode) vectors.Ftype is not the same as Distance(Node) vectors.Ftype. Go does not have subtyping.

I have a workaround which involves a minor rewrite of my interface avoiding the self reference.. but in general is there a fix for such self references ? Is this something the language designers feel should work..? or plan to fix or ignore

No, there's no general fix for this. In this case I think you might be better off with a static type for Node rather than an interface. Another option would be a Graph interface that uses ints to reference nodes:

type Node int

const ZeroNode Node = 0

type Graph interface{

    Connection(Node, int) (Node, bool)

    NumberOfConnections(Node) int

}

func Distance(g Graph, from, to Node) vectors.Ftype

[xiio...@gmail.com]

On Saturday, 15 August 2015 20:14:12 UTC+1, Danver Braganza wrote:

What you need to do in this instance is change the signature of Distance to

func (mn mapnode) Distance(mn2 Node) vectors.Ftype {

You want to ensure that Distance can be called between ANY two Nodes, no matter what their underlying type is, no just between two Nodes that happen to have the same underlying type.

Doesn't work - the mapnode implementation of Distance uses fields and methods not accessible from a Node  interface type

eg errors such as  "mn2.parentarray undefined (type Node has no field or method parentarray)"

 

[Roberto Zanotto]

The problem is that the interface requires to implement a Distance(Node), but you are providing a Distance(mapnode). The method signatures are different, it doesn't matter if map node is in the end a Node or not, you are not implementing the interface correctly. You could try with:

func (mn mapnode) Distance(mn2_ Node) vectors.Ftype {
    mn2 := mn2_.(mapnode)
    

    h1 := mn.parentarray.underlyingmap.array[mn.x][mn.y]

    h2 := mn2.parentarray.underlyingmap.array[mn2.x][mn2.y]

 

    distance := (h2 - h1)

    return distance * distance

}

Let me know if this works.

[xiio...@gmail.com]

On Saturday, 15 August 2015 20:21:31 UTC+1, Roberto Zanotto wrote:

The problem is that the interface requires to implement a Distance(Node), but you are providing a Distance(mapnode). The method signatures are different, it doesn't matter if map node is in the end a Node or not, you are not implementing the interface correctly. You could try with:

func (mn mapnode) Distance(mn2_ Node) vectors.Ftype {
    mn2 := mn2_.(mapnode)
    

    h1 := mn.parentarray.underlyingmap.array[mn.x][mn.y]

    h2 := mn2.parentarray.underlyingmap.array[mn2.x][mn2.y]

 

    distance := (h2 - h1)

    return distance * distance

}

Let me know if this works.

Similar to an answer above -unfortunately no - the Node type doesn't have the necessary fields for the interface implementing function to work. 

[xiio...@gmail.com]

On Saturday, 15 August 2015 20:17:04 UTC+1, Jérôme Champion wrote:

It's not gonna change. You could check the sort package to see how it deals with such problem.

(Instead of having an Interface for a single node, it define an interface for a group of node)

Do you mean this  http://golang.org/pkg/sort/#Interface : "The methods require that the elements of the collection be enumerated by an integer index."

The text sounds similar to my working fix which is replacing the method

Distance(Node) vectors.Ftype

with a

DistanceToConnection(int) vectors.Ftype

that achieves the same thing. Generically I imagine the solution will always be to reference the second Interface type using a getter, not directly. Can't imagine when this might not work. 

 

[Roberto Zanotto]

... that's why I did the type casting in the first line of the function   mn2 := mn2_.(mapnode)

From how you wrote the function the first time, it looked like you wanted a mapnode/mapnode distance, not a mapnode/Node distance. So we are keeping Node in the method signature to satisfy the interface, but we are casting mn2_ Node -> mn2  mapnode inside the function.

[Danver Braganza]

Yep. You're going to have to add more methods to interface Node so that distance between any two nodes can be calculated without using internal implementation details (such as parentarry).

[HaWe]

Hi.
Not sure if this is what you need, but anyway:
https://play.golang.org/p/I8MkbVnEM1

[xiio...@gmail.com]

Duh. Oh sorry. I flash read it, and assumed it was a duplicate of the above, posted concurrently with the other answer.

as far as I can tell - yes it works, but, it ties the mapnode function to a specific interface . problematic for other uses

 

[parais...@gmail.com]

(has this come up before?)

Yes and many times , search for "covariance" in this group. Go doesn't support covariance nor hierarchies between types.

Le samedi 15 août 2015 21:04:34 UTC+2, xiio...@gmail.com a écrit :

[xiio...@gmail.com]

On Saturday, 15 August 2015 22:15:37 UTC+1, parais...@gmail.com wrote:

(has this come up before?)

Yes and many times , search for "covariance" in this group. Go doesn't support covariance nor hierarchies between types.

Le samedi 15 août 2015 21:04:34 UTC+2, xiio...@gmail.com a écrit :

Thanks ! :) 

[Egon]

Do you really need to use interfaces at all? Unless there is a really good reason to use them, don't; they add a lot of complexity in this case.

BTW, here's an A* implementation https://gist.github.com/egonelbre/10578266 that uses interfaces. If I used it in practice, I would remove the interfaces and taylor it to the needs of the application.

+ Egon

[demetri...@gmail.com]

If you need to do this on many types, and need it to be fast, you have two options:

1. Duplicate the code (probably using `go generate`).
2. Use a language with better generic support.  I would recommend Rust, D, or Nim.  Note that cgo bindings can only be done on monomorphized bindings.

Go is good at many things.  Reusable algorithm libraries are not among them.  If you find yourself needing a lot of complex generic algorithms, you may want to consider a better language.  Again, I would recommend Rust, D, or Nim for their speed and safety (be sure not to use `-d=release` with Nim, which disables array bounds checks, and to use `@safe:` at the top of each D file, if you go that route.).

[Egon]

On Sunday, 16 August 2015 06:50:21 UTC+3, demetri...@gmail.com wrote:

If you need to do this on many types, and need it to be fast, you have two options:

If you really need something to be fast, then making the code generic is the last thing you want to do. Generic code makes harder reasoning about optimizations (branch prediction, cache trashing, register spilling) and makes harder taking advantage of the domain-level shortcuts (removing unnecessary parts, LUTs, packing different values into same int). (https://www.youtube.com/watch?v=rX0ItVEVjHc)

+ Egon

[demetri...@gmail.com]

In Go, you are correct. D, Nim, Rust, and C++ compilers generate specialized code for each type.

[Egon]

On Sunday, 16 August 2015 17:41:33 UTC+3, demetri...@gmail.com wrote:

In Go, you are correct.  D, Nim, Rust, and C++ compilers generate specialized code for each type.

Assuming performance is priority, when your data-structures change your algorithm performance characteristics change, hence to account for that you also need to adjust your algorithm to take account those data characteristics. That applies to any language, including languages with generics.

Sure, with generics you might get a faster version of an unoptimized algorithm, but it isn't a magical bullet that solves your optimization (SIMD, hot/cold splitting, pre-fetching, branching,  etc.). Adding generics into that mix makes it much harder to reason about those problems and easier to miss opportunities for optimizations.

+ Egon

[Steven Blenkinsop]

While this is true, this level of optimization is unlikely to take place in the majority of code which could benefit from it if it has to be hand coded each time it is used. More likely, people will choose algorithms that are less suitable in order to save implementation complexity where even a generic version of a more appropriate algorithm would've been a better choice.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Art Mellor]

I made a few tweaks to your playground version that might be what you want:

https://play.golang.org/p/wm-nB5MWyv

[demetri...@gmail.com]

Exactly.  Nim, D, and C++ even allow explicit specialization for special cases.  Of course, I cannot recommend C++ for security reasons.

[Christoph Schunk]

Implemented the A* Search algorithm a while ago: https://github.com/chsc/astar

You put a lot of stuff in your node interface the search algorithm doesn't need to know. Keep Go interfaces simple and minimalistic. 

My implemetation consists of only three methods:

type Node interface {
 NumNeighbours() int
 Neighbour(i int) Node
 Cost(i int) float32
}

Am Samstag, 15. August 2015 21:04:34 UTC+2 schrieb xiio...@gmail.com: