On Sun, Oct 21, 2018 at 2:03 PM roger peppe <rogpe...@gmail.com> wrote:
> Yes. The draft proposal says "generic functions, rather than generic
> types, can probably be compiled using an interface-based approach. That
> will optimize compile time, in that the package is only compiled once, but
> there will be some run-time cost.". I don't think this is possible as
> stated. I don't even know what it means to compile a generic type, as types
> themselves aren't compiled - unless they're talking about compiling methods
> on generic types, in which case I don't see how they differ from generic
> functions.
>
> I do believe it's possible to avoid generating code for every possible set
> of type parameters to a generic function. There's a continuum of
> efficiency. At one end, we *could* generate code for each possible set of
> type parameters (giving efficient code but binary bloat), and at the other,
> I think it's possible to generate a function containing reflect-based code
> that will work on all possible type parameters (*) but is comparatively
> very slow.
>
To me, it seems that you are contradicting yourself here. To clarify: To
me, an "interface-based approach" and "reflect-based code" essentially
comes down to exactly the same thing: We pass run-time type information to
the function which then unpacks that to do the actual work. Tomato Potahto
;)
(and FWIW "compiling a type", I believe, refers to generating a
reflect.rtype/runtime._type at compile time and embedding it in the binary.
So, if you have `type Foo(T) struct { x T }`, an interface-based
compilation would just generate one run-time type of the form `type Foo
struct { x interface{} }`, whereas a static approach would create e.g.
`type Foo(int) struct { x int }`, `type Foo(string) struct { x string }`,
etc)
But, I guess, I'm fine to agree to disagree at that point then - if you
think a purely run-time/reflect/interface/… approach is impossible, I can't
argue with that :)
Somewhere in the middle, is probably a happy medium: perhaps something like
> "generate a version of the function for all types with the same size and
> pointer map".
>
> (*) some things aren't currently possible, like iterating over maps in
> O(1) space, but it's likely they can be solved in time.
>
> 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
>>
>
> Your code here assumes that x is known at the call site. That's not a
> valid general assumption. The function might be well be generating the
> slice on every call.
>
> var y *CR
>> _y := G(func() []A {
>> var out []A
>> for _, a := range x {
>> out = append(out, a)
>>
>
> Making a copy of the slice isn't valid in general either, as the slice
> might legitimately alias some other slice elsewhere in the program. When G
> mutates the slice, it's important that the elements that it mutates are the
> same ones as in the slice originally returned by the function.
>
> By way of example, think about how your transformation could work on this
> code: https://play.golang.org/p/_nfS2rEJIJy
>
>
>> }
>> 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.
>>
>
> I don't understand why you think the compiler needs to be able to
> recognize and reverse these patterns.
>
> 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.
>>
>
> I don't think it's possible to assume co-/contravariance even with unsafe,
> because the runtime representation of interface values really is different
> from that of concrete values. The only way of doing this would be to make
> all values in the program the same size, which is indeed the approach taken
> by many languages, so []byte would have exactly the same layout as
> []io.Reader, for example. I don't think this is an acceptable approach for
> Go though.
>
> 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.
>>
>
> Originally you claimed that "the analysis [of the exact set of possible
> types that a type parameter can be] for interfaces is [...] *exactly as
> hard *[as that for generic type-parameterized functions]".
>
> As I understand it, this means that you're claiming that taking some
> arbitrary piece of Go code that uses interfaces and determining the exact
> set of possible dynamic types that those interfaces can be is *exactly as
> hard* as taking a generic function and determining the set of possible
> types it can be called with. I guess I must be misinterpreting you here,
> because it's quite easy to see that if I have a method Foo:
>
> type T struct {
> I interface { A() }
> }
> func (t *T) Foo() {
> t.I.A()
> }
>
> then it's only possible to know what types t.I can be by knowing where all
> possible references there might be to t.I in the entire program and knowing
> what dynamic types it might be set to. This is the problem solved by Guru's
> "pointsto" query - it's slow and hard and inaccurate (to do it right, you
> really have to trace reflect-based code too).
>
> 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).
>>
>
> Ah, I *think* I see where you might be coming from now. You're thinking
> that the compiler could do some kind of Go-to-Go transformation for generic
> functions so that they looked exactly as if they'd been written using
> interfaces, and then later transform that back into devirtualized calls.
> Even if it were possible in general (I'm fairly sure it's not), I don't see
> why anyone would want to take such an indirect approach when it's quite
> possible for the compiler to compile to an intermediate format that
> preserves all the information needed and decide how to generate the code
> based on that.
>
>
--
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.
