[generics] combining different instances of the same generic type

[Matt Joiner]

I had a muck around with go2 generics with my toy-ish futures package https://github.com/anacrolix/futures. The go1 implementation is in master, and a working go2 implementation in the go2 branch (using channels of different types instead of the attempt that follows). The package provides one function AsCompletedDelayed, that allows to favour futures over others with timeouts. The timeouts are implemented using the future type *F[int], where as the futures the user provides as arguments are *F[T]. In the implementation for AsCompletedDelayed I need to pass both types of futures to another function AsCompleted[T](fs ...*F[T]) <-chan *F[T], then differentiate them when they're returned: I could get back a "timeout" future, or a user/argument future. To do this I created another type timeoutOrResult[T] struct { timeout bool; timeoutIndex int; result T }, however now I ran into the situation where I need to "map" the futures of type *F[int], and *F[T] to *F[timeoutOrResult[T]]. This seems non-trivial: I believe in another language I would make F a Functor, and map the timeouts to something like `Either int T`. It is possible to write an Fmap on my *F type, but now I need to create new types, and break out an interface, and the implementation quickly increases in complexity.

This seems like a situation where the go1 style of doing this was easier albeit without enforcing the result types of the futures in the return chan for AsCompleted and AsCompletedDelayed: I could pass arbitrary *Fs to AsCompleted, and then compare the returning *F against a map[*F]struct{} that tracked which ones were timeouts.

[roger peppe]

I'm having difficulty understanding exactly what your code is trying to do (and why), and that makes it hard to understand what

generic solution might be appropriate.

However, here's one alternative implementation that doesn't seem to run into the same kind of issues that you did.

It changes the contract a little bit, but it's still within the spirit, I think and it's somewhat simpler:

    https://go2goplay.golang.org/p/cEWEUrvfZBl

FWIW when I've implemented this kind of logic in the past, the aim is usually to obtain at most one result. I don't really understand the use case being implemented here.

To address the actual question you raised:

I ran into the situation where I need to "map" the futures of type *F[int], and *F[T] to *F[timeoutOrResult[T]].

There's no reason why interface types won't still play a large role in the future where Go has generics, and that's

how I'd probably represent timeoutOrResult there, with a dynamic type switch to decide which one you've got.

 

  cheers,

    rog.

On Mon, 30 Nov 2020 at 02:09, Matt Joiner <anac...@gmail.com> wrote:

I had a muck around with go2 generics with my toy-ish futures package https://github.com/anacrolix/futures. The go1 implementation is in master, and a working go2 implementation in the go2 branch (using channels of different types instead of the attempt that follows). The package provides one function AsCompletedDelayed, that allows to favour futures over others with timeouts. The timeouts are implemented using the future type *F[int], where as the futures the user provides as arguments are *F[T]. In the implementation for AsCompletedDelayed I need to pass both types of futures to another function AsCompleted[T](fs ...*F[T]) <-chan *F[T], then differentiate them when they're returned: I could get back a "timeout" future, or a user/argument future. To do this I created another type timeoutOrResult[T] struct { timeout bool; timeoutIndex int; result T }, however now I ran into the situation where I need to "map" the futures of type *F[int], and *F[T] to *F[timeoutOrResult[T]]. This seems non-trivial: I believe in another language I would make F a Functor, and map the timeouts to something like `Either int T`. It is possible to write an Fmap on my *F type, but now I need to create new types, and break out an interface, and the implementation quickly increases in complexity.

This seems like a situation where the go1 style of doing this was easier albeit without enforcing the result types of the futures in the return chan for AsCompleted and AsCompletedDelayed: I could pass arbitrary *Fs to AsCompleted, and then compare the returning *F against a map[*F]struct{} that tracked which ones were timeouts.

--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/adb04bb6-bdda-41a9-a168-2541dd912171n%40googlegroups.com.

[roger peppe]

Slightly simpler again: https://go2goplay.golang.org/p/mKdishv4nhT

[roger peppe]

And again (no need to make a cancelable context) https://go2goplay.golang.org/p/3UFUaXijuX9

[Matt Joiner]

Thanks very much for taking a look at this Roger. I think your attempt differs from mine in that you don't make use of the future type F in implementing the waiting for the blocks of delayed futures, which means you don't have to deal with combining different instances of F (F[A], F[B] etc.). Also your delayed blocks don't wait for the preceding set of futures to be exhausted before proceeding, I think they're all triggered once the initial set is completed. I also remade use of AsCompleted, which was an extra complication, since I had the difficulty I mentioned regarding passing Fs of different types to it easily.

Now I've had more time to process it, I think my issue comes down to being unsure about how to easily/consistently perform mappings between generic types (like F[A] -> F[B]). A second thing that's not clear is how to handle the type F when I don't care about what type it's been instantiated with (say I wanted to retain the existing code, but I know that if F is in the original map[F[struct{}]struct{}] timeouts that it's a F[struct{}], otherwise it's F[T] (and I'm happy to type-assert at that point)). It's clearly not F[interface{}], for lack of better notation, I'll call it F[*].

[roger peppe]

Also your delayed blocks don't wait for the preceding set of futures to be exhausted before proceeding, I think they're all triggered once the initial set is completed

 

Each delayed block is triggered when its associated delay has elapsed. Once the initial set is completed, it returns immediately. Isn't that what you want? As I said, I'm finding it hard to imagine a scenario where these particular semantics are useful, so it's not easy to decide how to treat the edge cases.

I think my issue comes down to being unsure about how to easily/consistently perform mappings between generic types (like F[A] -> F[B]).

I assume that by "perform mappings" you're wondering how to write a function like this:

// Map returns a future that yields fn(r) where r is the result value of f.

func Map[A, B any](f *F[A], fn func(A) B) *F[B]

I don't believe that's possible with your existing package. The reason is that there's no flexibility for additional behaviour in your *F type. It can hold exactly one value of a given type. Asking for the result will yield exactly that value.

But in the above case, you don't just want to yield the value - you want to call a function on that value and return that. There's no way for the *F[B] value to somehow hold the F[A] value inside it, along with its associated type A. However, that restriction only applies when F is a purely static type. You can use a generic interface type to allow arbitrary behaviour here.

Suppose your future type was defined like this:

type F[T any] interface {
        String() string
        Err() error
        Result() (T, error)
        Done() <-chan struct{}
}

Then it becomes straightforward to define the above Map function:

func Map[A, B any](f F[A], fn func(A) B) F[B] {
        f1 := &fmap[A, B]{
                fn: fn,
        }
        // Note: go2go bug means we can't use F in the initializer above.

        f1.F = f
        return f1
}

type fmap[A, B any] struct {
        F[A]
        fn func(A) B
}

func (f *fmap[A, B]) Result() (B, error) {
        a, err := f.F.Result()
        if err != nil {
                return *new(B), err
        }
        return f.fn(a), nil
}

Note that I deliberately omitted the SetString and MustResult methods from the interface definition above, the former because it makes it into a mutable value, which isn't great in a concurrent setting, and the latter because it can always be defined in terms of Result. They're both easy enough to implement independently:

func WithName[T any](f F[T], name string) F[T] {
        f1 := &namedFuture[T]{
                name: name,
        }
        f1.F = f
        return f1
}

type namedFuture[T any] struct {
        F[T]
        name string
}

func (f *namedFuture[T]) String() string {
        return f.name
}

func Must[T any](x T, err error) T {
        if err != nil {
                panic(err)
        }
        return x
}

A second thing that's not clear is how to handle the type F when I don't care about what type it's been instantiated with (say I wanted to retain the existing code, but I know that if F is in the original map[F[struct{}]struct{}] timeouts that it's a F[struct{}], otherwise it's F[T] (and I'm happy to type-assert at that point)). It's clearly not F[interface{}], for lack of better notation, I'll call it F[*].

The question to ask here is "what do I want to do with it?"

For example, if you don't need to actually use the result values (as is the case in AsCompletedDelayed) you can define an interface that represents the behaviour that you care about.

For example (I'm not keen on the name, but...):

// Doner represents a generic future type - anything that can be waited for.
type Doner interface {
    Done() <-chan struct{}
}

In fact, it's easy to define the whole of AsCompleted and AsCompletedDelayed in terms of the above type, with a small tweak to the Delayed type to avoid the

direct dependency on F.

func AsCompletedDelayed[D Doner](ctx context.Context, initial []D, delayed []Delayed[D]) <-chan D {

I hope you find this helpful.

  rog.

[roger peppe]

On Wed, 2 Dec 2020 at 09:15, roger peppe <rogp...@gmail.com> wrote:

Also your delayed blocks don't wait for the preceding set of futures to be exhausted before proceeding, I think they're all triggered once the initial set is completed

 

Each delayed block is triggered when its associated delay has elapsed. Once the initial set is completed, it returns immediately. Isn't that what you want? As I said, I'm finding it hard to imagine a scenario where these particular semantics are useful, so it's not easy to decide how to treat the edge cases.

I think my issue comes down to being unsure about how to easily/consistently perform mappings between generic types (like F[A] -> F[B]).

I assume that by "perform mappings" you're wondering how to write a function like this:

// Map returns a future that yields fn(r) where r is the result value of f.

func Map[A, B any](f *F[A], fn func(A) B) *F[B]

I don't believe that's possible with your existing package.

I'm talking rubbish there, I'm afraid. It's entirely possible to do this, albeit at the cost of an extra goroutine:

func Map[A, B any](f *F[A], fn func(A) B) *F[B] {
        return Start(func() (B, error) {
                a, err := f.Result()

                if err != nil {
                        return *new(B), err
                }

                return fn(a), nil
        })
}

[Matt Joiner]

The conversation has drifted a little from generics, I've replied inline below:

On Wed, 2 Dec 2020 at 20:56, roger peppe <rogp...@gmail.com> wrote:

On Wed, 2 Dec 2020 at 09:15, roger peppe <rogp...@gmail.com> wrote:

Also your delayed blocks don't wait for the preceding set of futures to be exhausted before proceeding, I think they're all triggered once the initial set is completed

 

Each delayed block is triggered when its associated delay has elapsed. Once the initial set is completed, it returns immediately. Isn't that what you want? As I said, I'm finding it hard to imagine a scenario where these particular semantics are useful, so it's not easy to decide how to treat the edge cases.

Specifically if there are no pending futures at a given instant, those in the block of delayed futures next due are "unlocked". AsCompletedDelayed is designed to allow prioritizing some futures over others, with timeouts occurring if those that shouldn't be delayed anymore haven't returned in a reasonable time (the next block are unlocked and can compete with the higher priority ones). 

I'm talking rubbish there, I'm afraid. It's entirely possible to do this, albeit at the cost of an extra goroutine:

func Map[A, B any](f *F[A], fn func(A) B) *F[B] {
        return Start(func() (B, error) {
                a, err := f.Result()
                if err != nil {
                        return *new(B), err
                }
                return fn(a), nil
        })
}

This is a great observation, thanks.