Reverse generics and opaque result types

generics

(Manolo van Ee) #1

Introduction

I've been trying to wrap my head around SE-0244: Opaque Result Types and recently I had some realizations that helped me understand the proposal better. I noticed I'm not the only one confused about it, so I thought I'd write down some things that might help others to get a better grasp of the concept as well.

In doing so, I'd also like to try and rebrand opaque result types, or at least the underlying mechanism, to something I'm calling 'reverse generics'. I think viewing this all from a slightly different perspective helps a lot in understanding the concepts involved.

Disclaimer: I'm not a language expert. What I'm about to write might not be 100% accurate. If so, I hope someone with more knowledge will correct me and I will update this post accordingly.

Reverse generics

Reverse generics, as I'm calling it, is more or less the same concept as normal generics, but in a different direction as we all are familiar with. Many of the things involved work exactly in the opposite way.

Notation

In order to be able to talk about reverse generics, we need to introduce some notation. Let's start with a normal generic example and then transform it into its reverse counterpart:

// Normal generics
func callee<T: Numeric>(_ x: T) {
  // We don't know what the concrete type of x is in this context, so
  // we can only do things with x that the Numeric protocol allows us to do.
}

func caller() {
  // The caller decides what concrete type is used for T when calling
  // the callee function, as long as it conforms to the Numeric protocol.
  // In this case the concrete type of T will be Int.
  callee(42) 
}

This example is pretty straightforward and we can translate it into reverse generics as follows:

  1. Switch the inputs and outputs of the function.
  2. Change the generic type parameter T to be a reverse generic type parameter.

The first step is already possible in the language, but for the second step we need some new syntax. I will use a caret (^) as prefix for reverse generic type parameters. This means that the generic type parameter T from the example will change to a reverse generic type parameter ^T.

Before we go to the reverse example, let's explain what a reverse generic type parameter is. A reverse generic type parameter is similar to a normal generic type parameter, the difference being who decides what the concrete type of the parameter will be. With normal generics, the caller selects the concrete type for the parameter, but with reverse generics the callee selects the concrete type.

With this information we can create the following example of reverse generics, being the exact reverse counterpart of our normal generics example:

// Reverse generics
func callee<^T: Numeric>() -> T {
  // The callee decides what concrete type is used for T, as long as it
  // conforms to the Numeric protocol. In this case the concrete type
  // of T will be Int.
  return 42
}

func caller() {
  let x = callee()
  // We don't know what the concrete type of x is in this context, so
  // we can only do things with x that the Numeric protocol allows us to do.
}

The roles of the caller and callee functions with respect to generic type T are completely reversed in this example compared to the normal generics example:

  • Normal generics: The caller function works with a concrete type Int, while the callee function has to work with some unknown type T that conforms to Numeric.

  • Reverse generics: The callee function works with a concrete type Int, while the caller function has to work with some unknown type T that conforms to Numeric.

Note: It is important to understand that writing this example with a normal generic type parameter does not work:

// Incorrect reverse generics with type T instead of ^T
func callee<T: Numeric>() -> T {
  return 42 // error: The caller decides what concrete type is
            // used for T, so we cannot just return an Int here.
}

Referencing the generic type

With normal generics, the generic type can be referenced within the generic function. For example:

// Normal generics
func callee<T: Numeric>(_ x: T) {
  var y: T // Declare another variable of type T.
  y = x    // This assignment is possible, because x and y are the same
           // concrete type, even though within this context the concrete
           // type is unknown.
}

To make the reverse generic picture complete, we need to be able to refer to the generic type from the caller function. I will use the following format to do this: <function name>.<reverse generic type>

The reverse counterpart of the example above will then look like this:

// Reverse generics
func callee<^T: Numeric>() -> T {
  return 42
}

func caller() {
  let x = callee()
  var y: callee.T // Declare another variable of type callee.T
  y = x  // This assignment is possible, because x and y are the same
         // concrete type, even though within this context the concrete
         // type is unknown.
}

Which function is generic?

With a normal generic function we normally say that the function is generic over its generic parameters. However, with reverse generics it's not the function itself that is generic. With reverse generics it is actually the caller of the function that will become generic. The following can be said about our examples:

  • Normal generics: The callee function is generic over T
  • Reverse generics: The caller function is generic over callee.T

Generic types are placeholders for concrete types

What's important as well is that generic types are placeholders for concrete types and they don't suddenly change to a different type in the same context. So, just like the following is not possible with normal generics:

// Normal generics
func callee<T: Numeric>(_ x: T, _ y: T) { ... }

func caller() {
  callee(42, 42.0) // error: Type T can be an Int or a Double, not both.  
}

In the same way, the following is not possible with reverse generics:

// Reverse generics
func callee<^T: Numeric>() -> T {
  if Bool.random() {
    return 42
  } else {
    return 42.0 // error: Type T can be an Int or a Double, not both.
  }
}

This means that the caller function can rely on the fact that callee.T does not suddenly change to a different type:

// Reverse generics
func caller() {
  let x = callee() + callee() // Both calls to the reverse generic
                              // callee() function return callee.T of
                              // which the concrete type does not change.
                              // Since callee.T conforms to Numeric and
                              // both values are the same concrete type,
                              // addition is possible.
}

Note: This is the major difference in usability compared to existential types. An existential type can be a different concrete type every time. If the callee function would return an existential, then it is not known whether the two calls to callee() actually return the same concrete type. You would have to open up both existentials and make sure they are both the same concrete type before it would be possible to add them together.

Specialization

With normal generics, the compiler can specialize a generic function if it knows about the concrete type that is being used.

The same is true for reverse generics, but remember that with reverse generics it's not the callee that is generic, but it's the caller that is generic. This means that if the compiler has enough information, it is the caller function that can be specialized. If the functions are defined in different modules, then the caller function cannot be specialized, because the compiler does not know which concrete type will be returned from the callee function. (note: For simplicity I'm not taking inlining into account here)

Combining normal and reverse generics

It is possible to combine reverse generics with normal generics. The following shows an example:

// Normal and reverse generics
func makeCollection<T, ^C: Collection>(with element: T) -> C {
  return [element]
}

Here we see a makeCollection function that takes an element of type T and returns a type C to its caller. The following can be observed:

  • The makeCollection function doesn't know which concrete type T it will receive. This is chosen by the caller of the function.
  • The caller doesn't know which concrete type C will be returned. This is chosen by the makeCollection function.
  • The caller does know that C conforms to the Collection protocol, so it can for example call methods like count() or isEmpty() on the value that is returned.

Note that when makeCollection is called with an Int element, it will return an Array of Ints, but when makeCollection is called with a String element, it will return an Array of Strings. This does not correspond with what we said earlier, that reverse generic types don't change. Well, this is a little bit more nuanced. The reverse generic types are fixed with respect to the normal generic types of the function. So, for every call to the makeCollection function where T == Int, it's still the case that the concrete type of the returned C is always the same. This means that the following works properly:

// Concatenate two collections of the same type:
let c = makeCollection(with: 5) + makeCollection(with: 10)

This also means that to be able to properly refer to the reverse generic parameter C of makeCollection, we'd probably need to expand our syntax a little, like for example:

let c: makeCollection<Int>.C

Type constraints with where clauses

The syntax that we've used will naturally work with existing syntax for where clauses, which makes it possible to constrain types in more complicated ways. When looking at the previous example, which returns a collection, one thing to note is that even though the function always returns a collection with elements of the type that the caller requested, it does not promise that. The caller cannot be sure that it actually receives a collection with the requested type of elements. We can easily solve this with a where clause:

// Normal and reverse generics with where clauses
func makeCollection<T, ^C: Collection>(with element: T) -> C where C.Element == T {
  return [element]
}

Now the function promises to return a C that actually contains elements of type T. Meaning that the following will be possible at the call site:

let c = makeCollection(with: 5)
let d = c.map { $0 + 10 } // This is possible, because we are promised
                          // a collection of elements with the type of
                          // our argument to makeCollection, which was Int.

Compound and related types

The reverse generics syntax also allows for returning more complex types:

// Return an optional Collection:
func makeCollection<T: Numeric, ^C: Collection>(with element: T) -> C? {
  guard element > 0 else { return nil }
  return [element]
}

// Return two Collections of the same type:
func makeCollection<T, ^C: Collection>(with element: T) -> (C, C) {
  return ([element], [element])
}

// Return a Collection, and an Array with Collections, all of the same type
func makeCollection<T, ^C: Collection>(with element: T) -> (C, [C]) {
  return ([element] as set, [[element] as set])
}

Naturally, all these can have additional constraints in where clauses.

Lastly, returning unrelated types can of course be accomplished by introducing a second reverse generic type parameter:

// Two Collections of (possibly) different types:
func makeCollections<T, ^C: Collection, ^D: Collection>(with element: T) -> (C, D) {
  return ([element] as set, [element])
}

Opaque result types

Now we have established all that, let's have a look at how this corresponds to opaque result types.

Notation

Instead of adding the concept of reverse generic type parameters, the proposed opaque result types syntax uses the 'some' keyword to basically declare an anonymous reverse generic type parameter. After the 'some' keyword, the constraints of the result type follow. Our earlier example of the makeCollection function without where clause can easily be translated into the proposed syntax for opaque result types:

// The reverse generics syntax:
func makeCollection<T, ^C: Collection>(with element: T) -> C {
  return [element]
}

// Becomes this in the opaque result types syntax:
func makeCollection<T>(with element: T) -> some Collection {
  return [element]
}

Additionally, the proposal mentions a possible future direction that provides a similar way to define anonymous normal generic parameters:

// Possible future direction with 'some' used
// for anonymous normal and reverse generic types:
func makeCollection(with number: some Numeric) -> some Collection {
  return [number]
}

// This corresponds with the following syntax
// using named normal and reverse generic parameters:
func makeCollection<T: Numeric, ^C: Collection>(with number: T) -> C {
  return [number]
}

Additional constraints

The proposed opaque result types syntax is a little more succinct compared to the reverse generics syntax, but due to that the declared type is anonymous, it has some limitations when it comes to expressing additional constraints. It is not possible for example to refer to the type in a where clause. To solve this, some suggestions are made, like using an underscore to refer to the type, or making it possible to use angle brackets on protocols to define additional constraints. More discussion takes place here: Protocol<.AssocType == T> shorthand for combined protocol and associated type constraints without naming the constrained type

In a similar way, it is not possible to return related types with the proposed syntax, since the type parameters are anonymous and cannot be referred to.

Afterword

Personally, I think opaque result types perhaps have a place in the language, but they come with some limitations. Some of those can be lifted with additional syntax, but some limitations are probably inherent to the fact that they are anonymous types.

In my view, the opaque result types proposal basically proposes two concepts at once:

  • Reverse generic type parameters (under the hood).
  • Anonymous generic types.

I think this causes the most confusion for people (at least it did for me). Without having an understanding of the underlying mechanism and also not being able to name and place the actual types in their context makes it hard to see what we're actually talking about. Therefore, I think that first introducing a concept that has explicitly named type parameters, like the described reverse generics system, will provide a better foundation and easier to understand system for users. As a second step, the concept of anonymous generic types could be added on top of it.

Hopefully, I was able to clear up some things, at least for some people. And again, if anything I've written is incorrect, let me know. It is not my intention to add to the confusion.

Final note: This thread is meant to be informational and it is not the intention to move the discussion. Other people have come up with ideas and syntax proposals similar to what I've called 'reverse generics'. All ideas can be found and discussed in the appropriate threads.


SE-0244: Opaque Result Types
(Laszlo Korte) #2

Very clear explanation! I like how you show highlight symmetries.


(Svein Halvor Halvorsen) #3

Thanks the work put into this explanation. I think a lot of people will find it helpful to think about the duality of generics and opaque return types.

However, I don’t like your suggested terminology. Although it’s kinda useful, especially in the context of opaque return types, there is already a term of art for this concept, and using non-standard terminology—while it may be useful for some people—may also end up hurting understanding, since other languages and computer science in general uses another term.


(David Catmull) #4

I think one potential point of confusion is that a regular generic function can vary just in its return type:

func example<T: Numeric>() -> T

..which looks a lot like the "reverse generic":

func example<^T: Numeric>() -> T

So although I agree it can be useful to look at the complementary nature of generics and opaque result types, I think it's also important to emphasize their differences for the sake of readability.


SE-0244: Opaque Result Types
(Manolo van Ee) #5

That's a valid point. On the other hand, I think opaque types in Swift are very much intertwined with generics, while that's not always the case in other languages.