As I said, I don't really understand why we disagree here - or what we are
even disagreeing about. So let me make my claim as precise as possible, in
the hope that it at least helps me understand which particular part you are
disagreeing with. I claim:
a) w.l.o.g. we can ignore operators (including
index-expressions/range/select/…) for now, with the understanding that any
program using operators on a type-parameter to a generic function can be
transformed into an equivalent program using methods instead. In practice
this is a bit hairy and as discussed ad nausea the obvious
interface-definitions are not equivalent to the operators (given that they
allow different sets of types), but for the semantic of a specific program
that doesn't matter.
b) Any program using functions with type-parameters can be transformed into
an equivalent program without such functions. The simplest way to do that
transformation is to replace a generic function
func F(type A, R someContract) (a A) R { … }
by (assuming A, R are not used in the package - otherwise rename)
type A = interface { /* methods that someContract requires of A */ }
type R = interface { /* methods that someContract requires of R */ }
func F(a A) R { … }
and by replacing any concrete call
var a CA
var r CR = F(CA, CR)(a)
with
var a CA
var r CR = F(a).(CR)
(and similarly for passing around a fully instantiated version of F)
c) Given a function
func F(a A) R { … }
with A, R interface types and concrete types CA, CR implementing A and R
respectively and assuming every return statement of F can be proven to
return a value of dynamic type CR, we can create a devirtualized version of
F with the signature
func CF(CA) CR
such that for any a, the expression `F(a).(CR)` is equivalent to `CF(a)`
and the expression `F(a)` is equivalent to `R(CF(a))`.
(and similarly for the func value CF when passing it around)
d) Any replacement resulting from the transformation in b) fulfills the
requirement for c) - that is, the type-parameters get turned into
interface-types and it is provable that any return statement has a
consistent static (and hence dynamic) type CR. This is guaranteed by the
type-checker for generic functions.
e) Thus, following the transformation for b) with the transformation for c)
(restricted to the image of b) is equivalent to full template-style
expansion of all generic functions for all possible sets of static types
they are instantiated with in a given program.
Now, to me, all of a) to e) seem fairly clear. There are bits and pieces
that need to be expanded to work around details of scoping and naming and
everything and a full formal proof is hard, given a lack of a formal type
system for Go. But overall, this seems fair to me. If there is any specific
step you disagree with, that would be helpful to understand why we can't
agree.
Now, with that, we'd have a reduction proof that generics can't actually
perform better than the equivalent program using interfaces. The algorithm
to determine if devirtualization is possible (in c) is equivalent to the
type-checker of generic functions. And an algorithm that, given a list of
generic functions and a list of instantiations and calls to that function,
decides which of these should get a specialized version generated, can
*also* take a list of candidate-functions for devirtualization and calls to
those functions and decide which of these functions get devirtualized.
Note, that I'm not saying *any* function using interfaces can be
devirtualized - for my claim, it's only necessary that every function in
the image of transformation b) can be devirtualized. This is why I'm so
confused by your examples - you keep constructing functions with interface
arguments that are not in the image of b), saying that they can't be
devirtualized or that the question of whether they can is undecidable. But
that doesn't actually matter. Worst case, we have to be able to determine
whether a function taking interfaces is in the image of b), which I think
is pretty easy - we basically only need to determine whether, for any
interface-type returned, the static type in the return statement is
consistent (for arguments, we can get around that by renaming if need be).
However, I'm also saying that if we use this view and instead of
implementing a heuristic for "are parametric functions compiled
instantiated or generic" we view these steps separately and first implement
generics completely via virtual calls (interfaces) and then implement a
heuristic for devirtualization, we get a higher payoff. Because in practice
there *will* be some function that would benefit from that heuristic that
are *not* parametric functions. A good example is `fmt.Fprint*`, which
would definitely be considered a candidate for devirtualization, as it
*could* be in the image of b). i.e. by doing the two-step thing, we
essentially answer the question of "when to use contracts and when to use
interfaces": `func Fprint(io.Reader, ...interface{})` is equivalent
semantically to `func Fprint(type R io.Reader) (R, ...interface{})` - but
under this view, it also generates the same code. So there no longer is an
advantage to use type-parameters except where needed (e.g. for consistency
in Max) and the answer truly becomes "if you can, use interfaces".
The last possibly helpful illustration of what I'm trying to argue is, that
all of this is *essentially* simply the "dual implementation principle".
The dual implementation principle states, that it should be possible to
compile any parametric function either by compile-time or by run-time
substitution. That's exactly what I'm saying: The transformation in b) is
*exactly* the run-time substitution extreme in the implementation spectrum.
And full template-expansion in e) is *exactly* the compile-time
substitution extreme in the implementation spectrum. And thus,
devirtualization is exactly the "compiler optimization" answer to the
generics dilemma.
On Fri, Oct 19, 2018 at 1:22 PM roger peppe <rogpe...@gmail.com> wrote:
> On Fri, 19 Oct 2018 at 12:04, roger peppe <rogpe...@gmail.com> wrote:
>
>> The algorithm to do it is quite straightforward:
>> https://play.golang.org/p/subnLkSSxdI
>>
>
> On reflection, that ParamType hack won't work correctly with
> types.Identical. This should work better:
> https://play.golang.org/p/iswgf7mr8ht
>
>>
--
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
