language: covariance support

[gopherbot]

by justin@fathomdb.com:

Go does not support contravariance, specifically

type Iterator interface {
  Next() interface{}
}

is not satisfied by

func (s*WidgetList) Next() *Widget

---

Supporting contravariance would:

* Reduce the complexity of the language for the programmer (people assume things are
contravariant, covariance is more nuanced).

* Enable good collection classes to be implemented, which would likely either reduce the
need for generics or point the way.

* Should not be slower to compile than a call to Next().(*Widget).  It may actually be
faster, by allowing better caching.

* Be reasonable in terms of implementation difficulty.



I couldn't find a bug tracking this, so I'm opening this one!

[gopherbot]

Comment 1 by justin@fathomdb.com:

Hmmm... I think I actually reversed covariant & contravariant here.  Looks like I can't
edit the bug either.  Mods: feel free to fix - sorry!

[cznic]

Comment 2:

AFAICT the fact that Go interface is defined _only_ by the signatures of its methods is
intentional. The benefits of the magic implicit conversion are small compared to the
complication it would introduce to the language complexity. Also, it would be
particularly harmful for tooling. Nowadays, to find an interface satisfying method of a
type even REs can be used.
#WAI

[gopherbot]

Comment 3 by justin@fathomdb.com:

Funny: I see this as simplifying the language.  Implicit conversion is done elsewhere,
so I find it inconsistent that it is not done for interface return types.  I recognize
that it is different, but it is not different on first sight (i.e. you have to think to
realize why it would not be this way).
I also think the way to get better tooling is perhaps to discourage the use of Regexes,
rather than hobbling the language to cater to things we should really be discouraging :-)
More seriously though, which tools would it break?

[minux]

Comment 4:

how could adding a feature simplifying the language?
Have you considered how to implement it? When does the conversion take place?

[ianlancetaylor]

Comment 5:

Extremely unlikely to ever happen.  The simplicity of method matching is a feature of
the language.  Moreover, I see no way to efficiently implement this feature.  In the
general case it requires dynamic code generation during interface conversions.

Labels changed: added release-none, languagechange.

Status changed to WorkingAsIntended.

[gopherbot]

Comment 6 by justin@fathomdb.com:

Adding a feature can simplify the language if it becomes more coherent, and thus you
don't need to document the inconsistency.  Consider { the set of integers except for
seven (because seven includes the word even but is not even, and this has caused some
people using regexes to think that seven is even) }; add { seven } and you have a
simpler set :-)
Semantic arguments aside, the bigger win is in a simpler language & runtime: e.g. a rich
collections library becomes possible.  So even if the go language itself did become more
complicated, it can still be simpler for go programmers.
In terms of implementation: doesn't Go's dynamic interface table building make this even
easier than it would be in other languages?  Specifically: we match the method as normal
(by name); if the return types are the same or bitwise-assignable then no problem;
otherwise we build a shim function that calls the method and performs the (verified
typesafe) cast.  We could also do it at each call-site, this would avoid runtime code
generation, but I think this would be sub-optimal.
Is there a specific problem you're alluding to?  Would this e.g. be the first place that
we runtime generate code?
If runtime code generation is a no-go for go, there may be other approaches we could
take (e.g. insert a generic shim function into the itable, which then looks up the
actual method call and the cast and performs them without code generation; we could
memoize the info it needs in the itable)

[gopherbot]

Comment 7 by justin@fathomdb.com:

Thanks for fixing the title!
Perhaps we could leave this open while we discuss possible efficient implementations? 
This seems a more productive forum than the endless discussions on generics!
Is dynamic code generation out of the question?  (Can you post a link to why?)
Any thoughts on the shim method?

[ianlancetaylor]

Comment 8:

Dynamic code generation is always a problem for compiled languages on modern systems,
because it requires memory that is both writable and executable.  That is considered
verboten these days, because it is exactly what malware needs.
I don't see how you can do the conversion at each call site, because when you convert
one interface type to another there is no call site.

[gopherbot]

Comment 9 by justin@fathomdb.com:

OK, I like the 'maximal security' approach.  It's fairly contrary to the way every other
language is going, but it seems a good practice.
I'm not sure what you mean by "when you convert one interface type to another there is
no call site" - perhaps you can provide a quick one-line example if you think it's
important.  Anyway, I think the shim is the way to go, as casting on every interface
call is going to be really expensive.
To expand on the shim approach, currently we do this on an interface call:
s.tab->fun[0](s.data)
Instead, we could change every interface call to do this:
shim(s.tab, 0, s.data)
We would also need to add some extra data to the itable, specifically an array of
convert_to types per method.
So shim would do this (warning, pseudo-code):
shim(table, index, data) {
fn = table->fun[index]
v = fn(data)
convert_to = table->convert_to[index]
if (convert_to) {
 v = convert(v, convert_to)
}
return v
}
I think that would work, but would be slow (we pay for another method dispatch whether
or not we use it).
We could inline the shim function; this would be the equivalent of doing the conversion
at each call site.  But we're still paying the convert_to lookup whether or not we need
it, hence it would be slow.
Instead, we can insert the shim into the itable, but we would always need a shim,
because the signature is different from a struct method.
If we could steal a register or two on interface calls, we could get around this.  If we
have multiple shim functions, encoding index (shim_0, shim_1, shim_2...), then we only
need one register.
I hope this makes the shim idea clearer!  I don't see this as being particularly
expensive, particularly if it enables smaller code.

[ianlancetaylor]

Comment 10:

type Iterator interface {
    Next() interface{}
}
func F(e interface{}) interface{} {
    if i, ok := e.(Iterator); ok {
        return i
    }
    return nil
}
type S struct {}
func (s S) Next() *S {
    return nil
}
func main() {
    F(S{})
}
Now in F we have a type that supports Iterator, using covariant returns.  So the
interface conversion needs to somehow add code that will convert between *S and
interface{}, so that calls to the method will return interface{} as they must.

[gopherbot]

Comment 11 by justin@fathomdb.com:

Thank you for the example.
I'm not sure I see where this example causes problems for the shim approach, though.  My
mental model for an interface pointer is that it is an (itable,  data) pair.  (My model
comes from here: http://research.swtch.com/interfaces)
Throughout, data will point to s, our instance of S.  You will have two itables:
itable(S, interface{}) and itable(S, Iterator).
[ I know that itable(S, interface{}) will actually be optimized out, but I think we can
ignore that... ]
When you call Next() on S you invoke S::Next, which returns *S.
You can't call Next() through interface{}
When you call Next() on (itable(S, Iterator), s), you go through the type-casting stub /
thunk (that's my suggestion, anyway).  It calls the real method (S::Next) and then
converts the return value to the target type as stored in the itable(S, Iterator), in
this case interface{}.
The only change is that we must build the itable(S, Iterator) to generate that thunk and
build the table of required target types.
I believe it doesn't matter that we are building itable(S, Iterator) from
(itable(S,iterator{}), s), because building the itable uses S, not interface{}.
So I'm sorry, but I don't see what you're saying...  Where have I gone wrong here?

[remyoudompheng]

Comment 12:

I don't understand how this can be useful. You should write a document explaining the
intended usage and proposed implementation strategy.

[ianlancetaylor]

Comment 13:

Who creates the "type-casting stub / thunk"?  It won't be created when the method is
written, because that code doesn't know about the interface.  It won't be created when
the interface is created, because that code doesn't know about S.next.  It won't be
created when the code is compiled to convert the empty interface to Iterator, because
that code also doesn't know about S.Next.
You suggest that the thunk is created when building the itable(S, Iterator), but that
itable is built only at runtime.  At compile time we don't know that the itable is
needed.

[gopherbot]

Comment 14 by justin@fathomdb.com:

remyoudompheng: Definitely!  But it seems that right now iant is telling me that it just
can't work, so I'd love to figure out whether I'm barking up the wrong tree before
spending the time to write up a document, if the response is just going to be "that
won't work because of X".
iant: The thunk would be inserted at runtime, as part of the itable creation process. 
If runtime code generation isn't allowed, then we would have to share a single
pre-generated thunk.  This requires that (1) we know the method return types, (2) we can
convert between arbitrary types and (3) we change the invocation for an interface method
to pass any extra required parameters.   reflect.Method includes Type, so I think #1 is
OK.  I think #2 is OK now that we have #4047.  I believe #3 is doable as well, ideally
by putting those extra parameters in specific registers so we don't have to thunk
methods that don't require type conversion.  The complexity of #3 would really depend on
the code generator (which I'm not that familiar with).
It seems to me there are different questions:
1) Can this be done at all, even theoretically?
2) Can this be done with a stub/thunk which we substitute in to methods that need
type-conversion as part of building the itable?
3) Can this still be done if runtime code generation is not allowed?
4) Do we want to do this? (What is the benefit?  What is the cost?)
I'm having difficulty keeping track of where we are in the discussion!  I think that the
questions can only be answered in order, because each depends on the previous one. 
Where do you think we are?

[ianlancetaylor]

Comment 15:

Passing extra parameters in registers penalizes every interface method call in order to
support this feature.  That sounds like a bad tradeoff.
To answer your questions:
1) There may be a way to do it.  I don't know of one, but there may be a way.
2) I don't know.
3) Maybe.  Runtime code generation is absolutely off the table.
4) I don't think we want to do this even if it can be done.