proposal: spec: generics: Anonymous generic aggregate types

[rvolosatovs]

I decided to implement some common functional programming primitives in Go2 and immediately was faced with a drawback of the design. Given:

func Map[F, T any](f func(F) T, vs ...F) []T

I would like to write an idiomatic "table" test like this:

func TestMap(t *testing.T) {
    for _, tc := range []struct[F, T any] {
        Name     string
        Func     func(F) T
        Values   []F
        Expected []T
    }{
        {
            Name:     "strconv.Itoa",
            Func:     strconv.Itoa,
            Values:   []int{1, 2, 3},
            Expected: []string{"1", "2", "3"},
        },
        {
            Name:     "append string",
            Func:     func(s string) string { return s+"test" },
            Values:   []string{"1", "2", "3"},
            Expected: []string{"1test", "2test", "3test"},
        },
    } {
        t.Run(tc.Name, func(t *testing.T) {
            if ret := fungo.Map(tc.Func, tc.Values...); !reflect.DeepEqual(ret, tc.Expected) {
                t.Errorf(`Got:
%v

Expected:
%v`,
                    ret, tc.Expected)
            }
        })
    }
}

Which does not work.

What actually works is this: (from https://github.com/rvolosatovs/fungo/blob/13515ac078aa5099896ec57bbb7ad050e996c653/fungo_test.go2)

type MapTestCase[F, T any] struct {
    Name     string
    Func     func(F) T
    Values   []F
    Expected []T
}

func runMapTest[F, T any](t *testing.T, tc MapTestCase[F, T]) bool {
    return t.Run(tc.Name, func(t *testing.T) {
        if ret := fungo.Map(tc.Func, tc.Values...); !reflect.DeepEqual(ret, tc.Expected) {
            t.Errorf(`Got:
%v

Expected:
%v`,
                ret, tc.Expected)
        }
    })
}

func TestMap(t *testing.T) {
    for _, tc := range []MapTestCase[int, string]{
        {
            Name:     "strconv.Itoa",
            Func:     strconv.Itoa,
            Values:   []int{1, 2, 3},
            Expected: []string{"1", "2", "3"},
        },
    } {
        runMapTest(t, tc)
    }
    for _, tc := range []MapTestCase[string, string]{
        {
            Name:     "append string",
            Func:     func(s string) string { return s+"test" },
            Values:   []string{"1", "2", "3"},
            Expected: []string{"1test", "2test", "3test"},
        },
    } {
        runMapTest(t, tc)
    }
}

Observations:

1. Current type Name[<parameters>] struct{...} syntax does not support anonymous structs. A workaround could be to define a type TestCase[<parameters>] struct{...} right above the loop, but anonymous struct is cleaner IMO. Note that type declaration within a function does not work in go2go tool atm, but I assume that is a temporary thing.
2. ~Currently go2go tool requires the type to be instantiated for range, that means that in order to test this, multiple loops would be required, which is not desirable.~

Proposal:

1. Allow struct[<parameters>]{...} syntax for definition of anonymous structs (or better refactor the proposed syntax to type Name struct[<parameters>] {...} for consistency). This also concerns anonymous functions etc.
2. ~Allow range over generic structs as seen above~

[ianlancetaylor]

Allow struct[]{...} syntax for definition of anonymous structs (or better refactor the proposed syntax to type Name struct[] {...} for consistency)

There's no obvious reason why structs should be special in permitted type parameters, when other types don't. Why not permit type parameters for the other aggregate types?

Allow range over generic structs as seen above

I don't think this can be implemented. You are relying on type inference when calling fungo.Map. If we can make that call in a loop over a slice of parameterized structs, we have to instantiate fungo.Map separately each time through the loop. But the current proposal only supports instantiation at compile time. So we would have to break up the loop. While we could do that for this particular example, we couldn't do it if the slice of parameterized structs were passed by another function in a different package. So this seems impossible.

[rvolosatovs]

FTR, ended up with following structure: https://github.com/rvolosatovs/fungo/blob/c21e889863bfa3f241f0522a8633ecbfad33027c/fungo_test.go2

Once go2go supports type declaration within function scope and anonymous generic functions are supported as well, this is "good enough" in my opinion

[bcmills]

In the handful of statically-typed languages I'm aware of that support these kinds of loops (namely OCaml and Haskell), they are modeled as “existential types”. I see a few resources about existential types on the Internet,¹ but the best introduction I'm aware of is chapter 24 of Pierce's Types and Programming Languages.

Existential types are very closely related to Go's “interface types”: they define operations on abstract types, and at run-time they pack a descriptor for a concrete type together with a value that supports the defined operations on those types.

I think it would be possible in principle to extend Go's interfaces with generic types as proposed to produce something equivalent (or at least very close) to existential types. However, I don't have the bandwidth to look at that extension at the moment. (If there is a compelling use-case for this sort of extension, I might give it some more thought after ordinary type parameters are released. 😅)

---

¹

• https://www.cs.cornell.edu/courses/cs4110/2018fa/lectures/lecture26.pdf has a very brief overview of the theory.
• https://en.wikibooks.org/wiki/Haskell/Existentially_quantified_types has a good overview of existential types in Haskell.
• https://ocaml.org/manual/gadts.html describes existential types in OCaml
• https://stephenebly.medium.com/an-introduction-to-existential-types-25c130ba61a4 gives an overview of existential types in Standard ML, but notes that they can only be used at “module” boundaries. (Note that SML “modules” are analogous to Go “packages”, not Go modules.)
• https://homepages.inf.ed.ac.uk/gdp/publications/Abstract_existential.pdf is the theoretical foundation for existential types in Standard ML, if you want more detail.

[ianlancetaylor]

Based on the discussion above this is a likely decline. Leaving open for four weeks for final comments.

[benjaminjkraft]

Note I believe you can also do this with interfaces, although you still have to put the test case details in a separate function. To your example, add a method

func (MapTestCase[F, T]) runMapTest(t *testing.T) {
  // same as runMapTest you have
}

func TestMap(t *testing.T) {
  for _, tc := range []interface{ runMapTest(t *testing.T) }{
    MapTestCase[int, string]{...},
    MapTestCase[string, string]{...},
  } {
    tc.runMapTest(t)
  }
}

The trick is that MapTestCase[F, T] implements the given non-generic interface regardless of the values of F and T.

[rvolosatovs]

@benjaminjkraft awesome idea, that's what I ended up doing (different function, same idea):

type KeysTestCase[K comparable, V any] struct {
    Value    map[K]V
    Expected []K
}

func (tc KeysTestCase[K, V]) Run(t *testing.T) {
    test.AssertSameElementsDeepEqual(t, slices.Collect[K](maps.Keys(tc.Value), []K{}), tc.Expected)
}

func TestKeys(t *testing.T) {
    for name, tc := range map[string]test.Runner{
        "string->int": KeysTestCase[string, int]{
            Value:    map[string]int{"1": 1, "2": 2, "3": 3},
            Expected: []string{"1", "2", "3"},
        },
        "int->struct{}": KeysTestCase[int, struct{}]{
            Value:    map[int]struct{}{1: struct{}{}, 42: struct{}{}, 512: struct{}{}},
            Expected: []int{1, 42, 512},
        },
    } {
        t.Run(name, tc.Run)
    }
}

https://github.com/rvolosatovs/fungo/blob/87e1d650160196a7037ce1f91dc9f0c43cfe2d23/maps/maps_test.go2#L11-L57 with the help of little shared interface https://github.com/rvolosatovs/fungo/blob/87e1d650160196a7037ce1f91dc9f0c43cfe2d23/internal/test/test.go2#L9-L11

[ianlancetaylor]

No change in consensus.