Thank, I feel I can work with this :)
On Sat, Oct 20, 2018 at 10:58 AM roger peppe <rogpe...@gmail.com> wrote:
> 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.
>
First, am I concluding correctly, that you are thus also doubting the dual
implementation property of the contracts design as it stands? If you do,
that's fair and probably not a fight I want to get into :)
To answer your question: I handwavily put that under the same "operator"
headline of a) (lord, all of this would be so much easier with a formal
type system. That was the intention of a) - restrict the set of
type-constructors we have to talk about to func). An extremely simple way
would be
type A = interface { … }
type R = interface { … }
func G(a func() []A) *R
and at the call site
var x []CA
var y *CR
_y := G(func() []A {
var out []A
for _, a := range x {
out = append(out, a)
}
return a
})
if _y != nil {
tmp := (*_y).(CR)
y = &tmp
}
For the full argument, we'd also need that the compiler is able to
recognize and reverse these patterns. There are ways to do this
transformation that make this reversal simpler (if you transform
slice-accesses in the parametric function into method calls and generate
appropriate wrappers, the reverse transformation becomes simply inlining
and the trivial devirtualization), but I'm too lazy to write them down now.
For the record, I'm fully aware of the problems with this approach
<https://blog.merovius.de/2018/06/03/why-doesnt-go-have-variance-in.html>
in general. However, the big advantage we have here is that we can ignore
type-safety. This is an internal optimization after the type-checking pass
that has already guaranteed that what we're doing is safe. Which is pretty
much the crux of b) - being able to ignore type-safety allows us to do
abhorrent, reflect/unsafe based things that we wouldn't want to do in the
language proper but which allows us to just assume any co-/contravariance
we need.
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.
>
It may be a big assumption - but that's not what c) is about. c) is the
lemma "assuming we have this proof, no matter where it came from". d) is
then the lemma that at least the cases resulting from b) fall within that
"limited set of cases" :) So, for clarity: Is this your only problem with
c)? Because then I'm going to assume we are discussing d).
Again, I agree with you that, *in general*, obtaining this proof is
non-trivial. But we don't have to care about the general case, we only have
to care about the case where the function resulted from our self-devised
generic rewrites, which gives us a very good idea of how these functions
look and what to look out for.
Note, that if we *absolutely* had to, we could even add a fast-path to
whatever heuristic we come up with by keeping the information from b)
around (e.g. in a special `//go:` directive - or just a
`map[FuncDecl]ParametricFuncDecl`). As long as we don't *solely* rely on
that, this wouldn't weaken the overall argument. But I'm pretty sure that
the fact that we know what transformations we did in b) makes writing this
heuristic easy(ish).
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?
>
See the corresponding paragraph for b). If you do the copy-variant of
transformation, you'd have to pattern-match for such loops (which is still
possible and cheap to do). Apart from that, it's just regular
devirtualization - e.g. inlining and replacing `x.(T)` either with `x` or
with `panic`, depending on the known concrete type of x.
I don't think devirtualization is very hard - even in the completely
general case. There aren't many operations where interfaces are special,
pretty much only type-assertions and type-switches, both of which are easy
enough to transform. Apart from that, you should pretty much be able to do
the transformation even on the AST level (though naming).
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.
