FAQ
Whenever the topic of generics in Go is brought up, people link
to http://research.swtch.com/generic . There the trilemma given is you have
to pick one of:

1. (The C approach.) Leave them out. This slows programmers. But it
adds no complexity to the language.
2. (The C++ approach.) Compile-time specialization or macro
expansion. This slows compilation. It generates a lot of code, much of it
redundant, and needs a good linker to eliminate duplicate copies. The
individual specializations may be efficient but the program as a whole can
suffer due to poor use of the instruction cache. I have heard of simple
libraries having text segments shrink from megabytes to tens of kilobytes
by revising or eliminating the use of templates.
3. (The Java approach.) Box everything implicitly. This slows
execution. Compared to the implementations the C programmer would have
written or the C++ compiler would have generated, the Java code is smaller
but less efficient in both time and space, because of all the implicit
boxing and unboxing. A vector of bytes uses significantly more than one
byte per byte. Trying to hide the boxing and unboxing may also complicate
the type system. On the other hand, it probably makes better use of the
instruction cache, and a vector of bytes can be written separately.
But Go itself has two genericish types: slice and map. How do those work to
get around the trilemma? I assume it only compiles in support for the types
you end up using. So if you have a map[IdNumber]*UserObject in your source
that gets baked into your binary, but if not then not. Couldn't that work
just as well for other types?

Suppose we had code like

type T generic

func Sum([]T numbers) total T {
     for _, value := numbers {
         total += value
     }
     return total
}

func main() {
     sliceInts := []int { 1, 2, 3, 4, 5 }
     sliceFloats := []float64 { 1.0, 2.0, 3.0, 4.0 }
     var totalInt int = Sum(sliceInts)
     var totalFloat float64 = Sum(sliceFloat)
}

Then it would just compile in the two versions of Sum, just like (I assume)
you have however many versions of map compiled in.

What's the main problem with this approach? Is it just that the number of
copies of Sum would grow out of control? It's not so bad in this case, but
you get an explosion as you add more generic types with things like

type A generic
type B generic

func Map(f func(A) B, as []A) []B {
     bs := make([]B, len(as))
     for i := range as {
         bs[i] := f(as[i])
     }
     return bs
}

Then again, are we really convinced that answer 1 to the trilemma is really
the best answer? ISTM that the whole point of the trilemma is that all
three options have their downsides…

--
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+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

  • Michael Jones at May 26, 2013 at 6:42 am
    I don't see the "explosion" as a problem. I want every combination of code
    I use to be instantiated.

    On Sat, May 25, 2013 at 8:30 PM, Carl Johnson wrote:

    Whenever the topic of generics in Go is brought up, people link to
    http://research.swtch.com/generic . There the trilemma given is you have
    to pick one of:

    1. (The C approach.) Leave them out. This slows programmers. But it
    adds no complexity to the language.
    2. (The C++ approach.) Compile-time specialization or macro
    expansion. This slows compilation. It generates a lot of code, much of it
    redundant, and needs a good linker to eliminate duplicate copies. The
    individual specializations may be efficient but the program as a whole can
    suffer due to poor use of the instruction cache. I have heard of simple
    libraries having text segments shrink from megabytes to tens of kilobytes
    by revising or eliminating the use of templates.
    3. (The Java approach.) Box everything implicitly. This slows
    execution. Compared to the implementations the C programmer would have
    written or the C++ compiler would have generated, the Java code is smaller
    but less efficient in both time and space, because of all the implicit
    boxing and unboxing. A vector of bytes uses significantly more than one
    byte per byte. Trying to hide the boxing and unboxing may also complicate
    the type system. On the other hand, it probably makes better use of the
    instruction cache, and a vector of bytes can be written separately.
    But Go itself has two genericish types: slice and map. How do those work
    to get around the trilemma? I assume it only compiles in support for the
    types you end up using. So if you have a map[IdNumber]*UserObject in your
    source that gets baked into your binary, but if not then not. Couldn't that
    work just as well for other types?

    Suppose we had code like

    type T generic

    func Sum([]T numbers) total T {
    for _, value := numbers {
    total += value
    }
    return total
    }

    func main() {
    sliceInts := []int { 1, 2, 3, 4, 5 }
    sliceFloats := []float64 { 1.0, 2.0, 3.0, 4.0 }
    var totalInt int = Sum(sliceInts)
    var totalFloat float64 = Sum(sliceFloat)
    }

    Then it would just compile in the two versions of Sum, just like (I
    assume) you have however many versions of map compiled in.

    What's the main problem with this approach? Is it just that the number of
    copies of Sum would grow out of control? It's not so bad in this case, but
    you get an explosion as you add more generic types with things like

    type A generic
    type B generic

    func Map(f func(A) B, as []A) []B {
    bs := make([]B, len(as))
    for i := range as {
    bs[i] := f(as[i])
    }
    return bs
    }

    Then again, are we really convinced that answer 1 to the trilemma is
    really the best answer? ISTM that the whole point of the trilemma is that
    all three options have their downsides…

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.



    --
    Michael T. Jones | Chief Technology Advocate | mtj@google.com | +1
    650-335-5765

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Ziad Hatahet at May 26, 2013 at 7:15 am

    On Sat, May 25, 2013 at 8:30 PM, Carl Johnson wrote:

    Suppose we had code like

    type T generic

    func Sum([]T numbers) total T {
    for _, value := numbers {
    total += value
    }
    return total
    }


    The other issue is that Go does not have operator overloading, or a
    typeclass-like system. How would you specify that you want your Sum()
    function to only run on number types, for instance?

    --
    Ziad

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Carl Johnson at May 26, 2013 at 7:31 am
    Today, if you try to use + on types that don't support it you get a compile time error. I imagine the same compile time error would arise if you attempted to say, pass a slice to Sum.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Michael Jones at May 26, 2013 at 12:42 pm
    Surely so. In any scenario, an attempt to instantiate something that is
    incompatible is a compile-time error, "ouch: you can't do that with me."

    On Sun, May 26, 2013 at 12:31 AM, Carl Johnson wrote:

    Today, if you try to use + on types that don't support it you get a
    compile time error. I imagine the same compile time error would arise if
    you attempted to say, pass a slice to Sum.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.


    --
    Michael T. Jones | Chief Technology Advocate | mtj@google.com | +1
    650-335-5765

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Minux at May 26, 2013 at 7:28 am

    On Sunday, May 26, 2013, Carl Johnson wrote:

    Whenever the topic of generics in Go is brought up, people link to
    http://research.swtch.com/generic . There the trilemma given is you have
    to pick one of:

    1. (The C approach.) Leave them out. This slows programmers. But it
    adds no complexity to the language.
    2. (The C++ approach.) Compile-time specialization or macro
    expansion. This slows compilation. It generates a lot of code, much of it
    redundant, and needs a good linker to eliminate duplicate copies. The
    individual specializations may be efficient but the program as a whole can
    suffer due to poor use of the instruction cache. I have heard of simple
    libraries having text segments shrink from megabytes to tens of kilobytes
    by revising or eliminating the use of templates.
    3. (The Java approach.) Box everything implicitly. This slows
    execution. Compared to the implementations the C programmer would have
    written or the C++ compiler would have generated, the Java code is smaller
    but less efficient in both time and space, because of all the implicit
    boxing and unboxing. A vector of bytes uses significantly more than one
    byte per byte. Trying to hide the boxing and unboxing may also complicate
    the type system. On the other hand, it probably makes better use of the
    instruction cache, and a vector of bytes can be written separately.
    But Go itself has two genericish types: slice and map. How do those work
    to get around the trilemma? I assume it only compiles in support for the
    types you end up using. So if you have a map[IdNumber]*UserObject in your
    source that gets baked into your binary, but if not then not. Couldn't that
    work just as well for other types?
    there is only one copy of code for slices and maps, unlike the C++ case.
    of course, the compiler provides some help so that the type is passed
    to the runtime code for slice/map.

    read golang.org/src/pkg/runtime/slice.c and hashmap.c for details.
    Suppose we had code like

    type T generic

    func Sum([]T numbers) total T {
    for _, value := numbers {
    total += value
    }
    return total
    }

    func main() {
    sliceInts := []int { 1, 2, 3, 4, 5 }
    sliceFloats := []float64 { 1.0, 2.0, 3.0, 4.0 }
    var totalInt int = Sum(sliceInts)
    var totalFloat float64 = Sum(sliceFloat)
    }

    Then it would just compile in the two versions of Sum, just like (I
    assume) you have however many versions of map compiled in.

    What's the main problem with this approach? Is it just that the number of
    copies of Sum would grow out of control? It's not so bad in this case, but
    you get an explosion as you add more generic types with things like

    type A generic
    type B generic

    func Map(f func(A) B, as []A) []B {
    bs := make([]B, len(as))
    for i := range as {
    bs[i] := f(as[i])
    }
    return bs
    }

    Then again, are we really convinced that answer 1 to the trilemma is
    really the best answer? ISTM that the whole point of the trilemma is that
    all three options have their downsides…
    before we find a beautiful solution, answer 1 is the safest choice
    so that we are not locked to a solution that we don't like.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Rémy Oudompheng at May 26, 2013 at 7:30 am

    On 2013/5/26 Carl Johnson wrote:
    Whenever the topic of generics in Go is brought up, people link to
    http://research.swtch.com/generic . There the trilemma given is you have to
    pick one of:
    (The C approach.) Leave them out. This slows programmers. But it adds no
    complexity to the language.
    (The C++ approach.) Compile-time specialization or macro expansion. This
    slows compilation. It generates a lot of code, much of it redundant, and
    needs a good linker to eliminate duplicate copies. The individual
    specializations may be efficient but the program as a whole can suffer due
    to poor use of the instruction cache. I have heard of simple libraries
    having text segments shrink from megabytes to tens of kilobytes by revising
    or eliminating the use of templates.
    (The Java approach.) Box everything implicitly. This slows execution.
    Compared to the implementations the C programmer would have written or the
    C++ compiler would have generated, the Java code is smaller but less
    efficient in both time and space, because of all the implicit boxing and
    unboxing. A vector of bytes uses significantly more than one byte per byte.
    Trying to hide the boxing and unboxing may also complicate the type system.
    On the other hand, it probably makes better use of the instruction cache,
    and a vector of bytes can be written separately.

    But Go itself has two genericish types: slice and map. How do those work to
    get around the trilemma? I assume it only compiles in support for the types
    you end up using. So if you have a map[IdNumber]*UserObject in your source
    that gets baked into your binary, but if not then not. Couldn't that work
    just as well for other types?
    The trilemma is about principles, but concrete implementations may
    freely mix the three of them. Also, "compile types" may not mean
    anything, since Go doesn't have generic functions. Maps and slices are
    not generic types, but primitive constructors of Go's type algebra,
    which is slightly different.

    Go mixes the three approches.

    1. The C approach: Go does not allow you to write type-parameterised
    code. So there is no question about instantiating anything.

    2. The C++ approach: the compiler generates specific code for slice
    indexing, reslicing. But since these are only a couple of
    instructions, does it actually qualify as instantiating?

    3. The Java approach: maybe not quite, but a reflective approach. Maps
    and channels are pointers to a single structure type, with functions
    (map assignment, map access) that are compiled only once: they use
    type information to dynamically change behaviour. Type safety is
    enforced by the compiler.

    In Go 1.1, the map implementation uses a mix of 2 and 3: a specialized
    implementation is used for a few common cases (templating by C
    preprocessor), and the generic, "reflective" code is used for the
    rest.

    Slices and channels only need to know about type size, so the amount
    of genericity is very limited.
    A few slice primitives also use type information append(a, b...) for
    example, and use shared code for all types, but this is not so
    relevant as it's mostly a wrapper around memmove.

    Rémy.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Robert Johnstone at May 26, 2013 at 3:37 pm
    The problem of providing specialized container classes is more restricted
    than the general case. This is even more true when those containers are
    built-in. Most "methods" are inlined, so code explosion isn't an issue.
    The allowed operations on the containers can be restricted. There is
    little interaction with other components of the language. Issues of
    dealing with operators does not appear.

    I think the main lesson is that generics are simpler when the problem
    domain is restricted.


    On Saturday, 25 May 2013 23:30:12 UTC-4, Carl Johnson wrote:

    Whenever the topic of generics in Go is brought up, people link to
    http://research.swtch.com/generic . There the trilemma given is you have
    to pick one of:
    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.
  • Carl Johnson at May 27, 2013 at 12:11 am

    On Sunday, May 26, 2013 5:37:43 AM UTC-10, Robert Johnstone wrote:
    The problem of providing specialized container classes is more restricted
    than the general case. This is even more true when those containers are
    built-in. Most "methods" are inlined, so code explosion isn't an issue.
    The allowed operations on the containers can be restricted. There is
    little interaction with other components of the language. Issues of
    dealing with operators does not appear.

    I think the main lesson is that generics are simpler when the problem
    domain is restricted.
    That's a good point. Go's existing "generish" types (slice, map, and I
    can't believe I forgot to list channel before) are much simplified by the
    fact that they're not trying to do everything. It's a good 80-20 (or 90-10
    or whatever) solution.

    For operator overloading, there's an obvious restriction to make -- only
    use it for real math-like operations, not weird hacks like cout << -- but
    it's a cultural restriction that's hard to enshrine programmatically.

    For generics, you could have a general precept like, "Only use generics for
    container types," but again it's not clear to me how you could enforce that
    programmatically.

    --
    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+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedMay 26, '13 at 3:30a
activeMay 27, '13 at 12:11a
posts9
users6
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase