On Fri, 19 Oct 2018 at 22:41, Axel Wagner <axel.wagner...@googlemail.com>
wrote:
> 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:
>
Thanks. A bit more precision makes things easier.
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.
>
Yup, let's ignore operators for now.
> 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)
>
That transformation might be valid for the simple case you have there,
where there's a single parameter of exactly the interface type, but generic
functions allow much more than that. You can have types that include the
generic types as a component too. To take one simple example, how would
your transformation work with a function that looks like this?
func G(type A R someContract)(a func()[]A) *R
In general, I believe the representation of generic values *must* be the
same as that of the concrete values in other non-generic parts of the
program because both can alias each other. This precludes boxing
implementations of generics such as you're describing there.
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)
>
"assuming every return statement of F can be proven to return a value of
dynamic type CR". This is a big assumption, and can only be done with flow
analysis and then only in a limited set of cases. For cases where you can't
prove it, you can't make devirtualized version of F. Also, you have the
same issue with higher order types as with the previous transformation. For
example, try to apply this devirtualization transformation to G (phrased in
terms of interface types, not generics) above?
The fact that neither b) or c) are feasible in general means that the rest
of your points don't follow, as far as I can see.
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.
