Syntax for existential type as a box for generic type

Nickolas_Pohilets · September 29, 2020, 1:44pm

I briefly mentioned this in the Introduce Any<P> as a better way of writing existentials - #51 by Nickolas_Pohilets, but initial edit was somewhat hard to read, and idea seems to be lost in the discussion. But I think this is still relatively unexplored area, and deserves more discussion.

In was thinking on several messages from @Karl, highlighting that existentials first of all are boxes for generic types. And from that perspective, current syntax for existentials is quite limited. We can express box for T where T: P, and that's pretty much it for today. There are some discussions that would enable us to express boxes for T where T: Collection, T.Element == Int (suggested syntax was Collection<.Element == Int>) and Array<T> (with syntax any Array).

But what if we can generalise this even further, and have a syntax that allows to box any generic type?

What about a box for Dictionary<KeyWrapper<T>, ValueWrapper<T>> where T: P? Here types of key and value are related. And responsibility of the existential type should be to preserve this relationship until existential is unboxed.

If we try to think of existential syntax that is expressive enough to preserve all the information from the underlying generic type, then we will end up with something like this:

any<T> Dictionary<KeyWrapper<T>, ValueWrapper<T>> where T: P

If consists of the tree parts:

any<T> - lists generic types captured inside the existential, required
Dictionary<KeyWrapper<T>, ValueWrapper<T>> - defines the type of the value captured inside the existential, required.
where T: P - lists additional conformance and equality constraints, optional.

Writing it as any<T: P> Dictionary<KeyWrapper<T>, ValueWrapper<T>> also should be possible.

Then we can think of the existing existential types as syntax sugar/type aliases for the full syntax:

typealias Any = any<T> T
typealias AnyHashable = any<T: Hashable> // = any<T> T where T: Hashable
typealias AnySequence<T> = any<U> U: Sequence where U.Element == T
protocol P {}
var x: P {} // syntax sugar for var x: any<T: P> T

When unboxing such type, I think we should be binding the types from the any<...> part.

let boxed: any<T: P> Dictionary<KeyWrapper<T>, ValueWrapper<T>> = ...

// T is bound to the generic parameter of KeyWrapper/ValueWrapper, not entire dictionary.
// Conformance T: P is implied.
let <T> unboxed = boxed 

for key: KeyWrapper<T> in unboxed.keys {
    // ...
}

technogen · September 30, 2020, 5:44am

I love the proposed syntax! I tried to find what might be wrong with it, but so far I found nothing!

+1

Nickolas_Pohilets · October 2, 2020, 10:06am

@Karl, @Joe_Groff, I’m really interested to hear your opinion on this.

xAlien95 · October 2, 2020, 12:48pm

We saw the any keyword surfacing in Improving the UI of generics: Clarifying existential types as a way to explicitly refer to existentials types (should we officially call them Protocol Types from now on like the Swift Programming Language Guide does?) and having semantic connections with the some keyword used to refer to opaque types. Ideally, you would have

var a: some Collection = [1, 2]  // a concrete type
var b: any Collection = [9, 12]  // an existential type

a = [3, 4]  // error, type of a is known only at runtime
            // and differs from any Collection conforming type

b = [3, 4]  // no error, b can store any Collection

Opaque types can only be built with protocols or base classes as of Swift 5.3:

var a: some Int = 2  // error: an 'opaque' type must specify only
                     // 'Any', 'AnyObject', protocols, and/or a base class

(weirdly Any and AnyObject are explicitly mentioned in the error, although both of them are protocols, so there's a bit of redundancy here)

I suspect that the any keyword should behave the same, i.e. it should be allowed to be put before a protocol or a base class.

The syntax you are proposing differs in this regard since you would like to put any before a type instead of a protocol, thus removing any similarities between any and some.

Let us compare your proposed syntax with the current one and the imagined any syntax discussed in Improving the UI of generics:

// proposed syntax
var c: any<T> [T]
var d: any<T> [T] where T: Protocol
var d: any<T: Protocol> [T]

// current syntax
var c: [Any]
var d: [Protocol]  // if Protocol can be a protocol type (existential)

// proposed syntax in "Clarifying existential types"
var c: [any Any]
var d: [any Protocol]

If I'm correct you want to use any<...> as a collector of type parameters involved in a generic type, thus gaining the ability to refer to existential types having constrained concrete types (which are only available at runtime) in multiple places:

var e: any<T> [KeyWrapper<T>: ValueWrapper<T>]
var f: any<T> [KeyWrapper<T>: ValueWrapper<T>] where T: Protocol
var f: any<T: Protocol> [KeyWrapper<T>: ValueWrapper<T>]

This feature however can already be expressed today using a generic typealias as a mid step:

typealias MyDictionary<T> = [KeyWrapper<T>: ValueWrapper<T>]

// current syntax
var e: MyDictionary<Any>
var f: MyDictionary<Protocol>  // if Protocol can be a protocol type

// proposed syntax in "Clarifying existential types"
var e: MyDictionary<any Any>
var f: MyDictionary<any Protocol>

Here, the protocol type, although existential, is constrained to have the same concrete type at runtime in both the wrapped keys and values of the dictionary.

My question is: should we break any and some analogies in favor of this different use of the any keyword?

Nickolas_Pohilets · October 2, 2020, 4:48pm

@xAlien95, I think you misunderstood me. I’m talking about a type that can type-erase [KeyWrapper<Int>: ValueWrapper<Int>] and [KeyWrapper<String>: ValueWrapper<String>] to a common type, while preserving relationship between key and value type.

But idea to use typealias as a workaround is an interesting one. It will cover use case in question when used in combination with any for generic types (as in any Array):

let a: [KeyWrapper<Int>: ValueWrapper<Int>] = ...
let b: [KeyWrapper<String>: ValueWrapper<String>] = ...
let x: [any<T> [KeyWrapper<T>, ValueWrapper<T>] = [a, b]

typealias MyDictionary<T> = [KeyWrapper<T>: ValueWrapper<T>]
let y: [any MyDictionary] = [a, b]

xAlien95 · October 2, 2020, 7:53pm

I did misunderstand, thank you for the clarification.

Karl · October 2, 2020, 9:32pm

It's an interesting idea to have types which themselves contain generic types. I'm not sure it's strictly necessary: if this is about preserving type relationships, you can already do that with constraints.

One of the issues with our current constraints is that they don't work well with generic types, at all. If these were all protocols, there would be no trouble:

DictionaryProtocol where 
  Key: KeyWrapperProtocol,
  Value: ValueWrapperProtocol,
  Key.Wrapped == Value.Wrapped,
  Key.Wrapped: P

We don't have the ability to express something like Dictionary<String, ?> (or Dictionary<String, some Any>, if that's how you want to look at it), but in theory you could box a value like that in some kind of existential. You'd need to ask a compiler/runtime engineer like @Joe_Groff, but I think we could still do things like call functions on a partially-unspecialised generic value, using the same mechanisms unspecialised generic code uses today.

Nickolas_Pohilets · October 5, 2020, 12:16pm

And with generic types, it would be something like this, right?

any Dictionary where Key == some KeyWrapper, Value == some ValueWrapper, Key.Wrapped == Value.Wrapped, Key.Wrapped: P

I guess this would work too. The two syntaxes seem to be equivalent in their expressiveness, with first one being bottom-up and second one being top-down, but otherwise describing the same DAG.

Actually, my point is not even about the specific syntax, but rather about the feature parity between generics and existentials.

The statement above does not need to be true. If we want, it is possible to make existentials as expressive as generics, and keep them in sync in the future as new features are added. But I don't know if we do want it. I don't have yet any motivational real-world examples where this would be needed. If anyone has - please share.

xAlien95 · October 5, 2020, 1:02pm

Searching for a similar feature in other languages I stumbled upon Scala, its wildcard types and its forSome keyword:

"It is now possible to define existential types using the new keyword forSome . An existential type has the form T forSome {Q} where Q is a sequence of value and/or type declarations."

In Scala, generic parameters are written in [ ] instead of < >, but the core concepts are the same.
Given a type (not a protocol) List[Element], you can refer to the existential type of all the Lists with

List[T] forSome { type T }

or by using a wildcard (wildcards are available in Java too)

List[?]  // as of Scala 3, List[_] in Scala 2.XX

Your example in Scala would be:

Dictionary[KeyWrapper[T], ValueWrapper[T]] forSome { type T <: P }

Edit: in an effort to make the Scala language simpler and based on a proven sound type system, a different language named Dotty has been developed alongside Scala 2 in order to become Scala 3. While wildcard type arguments have remained, the forSome keyword has been dropped:

Anachron · October 8, 2020, 10:20am

Generics in Swift seem to cause a lot of trouble. I just found another problem that could easily be solved with those.

Suppose you wanted to write ViewBuilder's buildBlock for an arbitrarily long list of Views. It turns out that you could actually express this even with today's syntax:

static func buildBlock<C : Collection>(_ c: C) -> some View where c.Element : View {...}

No problems here! But ... what if you actually tried to call it with a heterogenous collection of views? Well, nothing. The code will just not compile, because if you actually create a collection of heterogenous views, the type will be inferred to a collection of Any

If we could automatically erase all those views in the collection to anyview, there wouldn't be a problem.

However, we also know that dynamic features like this prevent stuff like inlining and other magic that depends on static type information.

Now, in this use case, there could actually be a static solution without type erasure. If we could somehow declare the generic type Cin buildBlock to be not a collection, but some collection literal, then the types can be inferred at the callsite and the compiler could generate the appropriate variadic function for us. Having the collection literal at any other place in the code would still lead to some [Any], but having the literal as a function argument could just be ok'd be the compiler.

Should we have automatic dynamic type erasure? Sure! But I would love to additionally have such a static pseudo-type-erasure feature.

xAlien95 · October 8, 2020, 10:42am

This is more related to either Variadic Generics or Unlock Existential Types for All Protocols.

In the first case you would have a list of heterogeneous types T0: View, T1: View, T2: View, etc. statically defined on the call site (strawman syntax ahead)

static func buildBlock<T...: View>(_ c: T...) -> some View { ... }

In the second case you would have to use an array having as Element type the existential protocol type any View

static func buildBlock(_ c: [any View]) -> some View { ... }

in which each element has access to most of the features provided by the View protocol.

Anachron · October 8, 2020, 1:09pm

I have a question regarding the construction of existentials.

Obviously, it should be possible to write

let foo : any Collection = [1,2,3]

But what about actual dynamic creation of a collection? Should the compiler synthesize a constructor for Any[WhateverProtocol] that asks you to hand over an implementation using closures and variables? Like

let iterator : any Iterator = AnyIterator{() -> Something? in ...}

xAlien95 · October 8, 2020, 1:24pm

Anachron:

But what about actual dynamic creation of a collection? Should the compiler synthesize a constructor for Any[WhateverProtocol] that asks you to hand over an implementation using closures and variables? Like
let iterator : any Iterator = AnyIterator{() -> Something? in ...}

Existential protocol types cannot/shouldn't have initializers. You always need a proper concrete type, i.e. the one used to store your entity in memory.

What do you mean with "dynamic creation"? What is your goal?

Anachron · October 8, 2020, 1:53pm

It has been brought up that in the future AnySequence could simply be a type alias for any Sequence. But in today's Swift, I am allowed to create an AnySequence without already having a sequence by just telling the AnySequence constructor how to iterate.

If this should still be possible, one would either have to create a concrete _AnySequence type with a constructor that can then be erased to any Sequence; and then you would write some boilerplate initializer for AnySequence assigning selfto _AnySequence(...). Or the existential type would be a synthesized AnySequence type with a witness table satisfied by closures; in the latter case, one could also synthesize two initializers: one that consumes a concrete Sequence and which is used under the hood to make let foo : any Sequence = [1,2,3] work and another one taking an anonymous implementation. In my opinion, there should of course be a way to hide or override this second synthesized initializer, but in general, why wouldn't there be one?

xAlien95 · October 8, 2020, 3:30pm

To avoid going off-topic, it's best to open a separate thread on the issue. Although this thread is about existentials, its main scope is about adding the possibility to generate existentials types from generic types (enums, structs, classes) rather that from protocols.

Regarding the ability to add initializers to existential types...

Yes, you always need a concrete type. Within AnyIterator, as an example, you have an hidden _ClosureBasedIterator: Iterator Protocol concrete type that stores the closure passed during the initialization: AnyIterator stores a _box variable containing an _IteratorBox that contains a _ClosureBasedIterator which in turn contains the closure.

https://github.com/apple/swift/blob/9af806e8fd93df3499b1811deae7729176879cb0/stdlib/public/core/ExistentialCollection.swift#L82-L85

You are proposing (strawman syntax ahead, as always)

typealias AnyIterator<T> = any IteratorProtocol where Element == T

extension AnyIterator: IteratorProtocol {
    typealias Element = T

    init(_ body: @escaping () -> Element?) {
        self = _ClosureBasedIterator(body)
    }
}

but that would be visually acceptable only if you explicitly typealias your existential type.

let myIterator = (any IteratorProtocol)( ... )

is less good looking for sure. Further more, protocols without 'Self' or associated type requirements (PATs), which can be used as existential protocol types today, do not provide initializers

let a = Any(3)    ❌

let a: Any = 3    ✅
let a = 3 as Any  ✅

so I expect that PATs or partially constrained PATs would work the same when used as existentials.

Anachron · October 8, 2020, 3:54pm

Wow, kind of unexpected implementation detail there. They hide an abstract class inside a struct just to avoid making it directly closure based? Curious design choice.

I agree that not all existential types should provide inits, but writing inits where you do want to have them is often annoying if they could as well be synthesized. Maybe a hiding mechanism would be better. But I agree, this is going increasingly off topic.