"Existential type" alternative: "typeof" + "impl Trait" in trait

[earthengine]

There was a proposal for the typeof operator in the past. The reason of closure is

This is the kind of thing we really need to go through the new formal RFC process.

But for years people didn't talk about it.

Now it is 2018, the year to make impl Trait available in an LTS version. But there are still limitations on this feature that it does not allow it to appear in some situations, including inside a trait implementation.

The RFC 2071 was introduced to remove those situations, but the part of this RFC that allows existential types inside traits is not even have a active PR right now.

In my opinion, RFC 2071 may not be a better solution than simply allow impl in trait function return types AND have the typeof operator available.

typeof and impl Trait can do what that existential type can

The following

// existential types
existential type Adder: Fn(usize) -> usize;
fn adder(a: usize) -> Adder {
    |b| a + b
}

can be expressed with typeof as:

type Adder = typeof(adder(a:usize));
fn adder(a: usize) -> impl Fn(usize) -> usize {
    |b| a + b
}

EDIT a previous version was naive and would not be able to compile.

and

// `impl Trait` in traits:
struct MyStruct;
impl Iterator for MyStruct {

    // Here we can declare an associated type whose concrete type is hidden
    // to other modules.
    //
    // External users only know that `Item` implements the `Debug` trait.
    existential type Item: Debug;

    fn next(&mut self) -> Option<Self::Item> {
        Some("hello")
    }
}

will become

// `impl Trait` in traits:
struct MyStruct;
impl Iterator for MyStruct {
    type Item = typeof((s:&mut Self).next().unwrap());

    fn next(&mut self) -> Option<Self::Item> {
        Some("hello")
    }
}

So at least, we should adjust RFC 2071 and add this as an alternative. Can anyone show me the workflow to add an alternative to the RFC?

In other language(s)

The above typeof is inspired by C++ decltype keyword.

[Ixrec]

I’m not sure we ever had a proper thread on this, but during the last round of impl Trait-related RFCs I realized that a typeof operator is a much thornier proposition than existential types because you have to come up with “fake expressions” for it to operate on. When you throw in specialization and type parameters and type inference, I’m not at all confident that “the obvious syntax” is actually going to be unproblematic or even unambiguous in all cases.

For example, taking your snippet:

type Adder = typeof(adder(a:usize));
fn adder(a: usize) -> Adder {
    |b| a + b
}

While it’s obvious in this simple case what you want Adder to be, how does the type inference actually work here? Is the typeof operating looking into the implementation of adder()? Or does adder() have authority over what Adder is, and typeof() has access to the results of adder()'s type inference? It seems like there’s a big risk of accidentally being circular or effectively requiring global type inference, and the in-between options I can think of amount to “global inference over small inference circles”, which isn’t necessarily any better.

But that’s just a technical issue. In my opinion, the real question is, what advantage does typeof syntax have over existential syntax? (I assume you intend them to have identical functionality) In your Adder example, just using impl Fn... seems better than either existential or typeof syntax if you don’t need to name the type, and both seem about equally clear if you do need to name the type. In your Iterator example, the existential version looks much cleaner than the typeof version to me. So just from that post, I don’t know what the motivation is for typeof syntax for existential types.

Though either way, I do agree that some argument against typeof ought to be documented somewhere. I have no idea what the correct procedure is for retroactively adding an alternative, though it might not matter since I suspect there’s going to be another RFC or two about existential syntax anyway before anything gets stabilized.

[earthengine]

All the examples are extracted from RFC 2071, I only wrote the typeof equivalent.

Right now, I believe that typeof can do everything existential type can, but I am not sure whether the other way is true or not. We need more research on this.

Learning curve

When talking about advantages, I think typeof is easier to learn for beginners. We teach new programmers to predict the type of expression from the first beginning. When they are not possible to do so (for example impl Trait and closures are in use), they will learn to expect some features (traits) for the result type.

On the other hand, they may not necessary understand the difference of existential type and universal generic type until they moved on the medium level.

Adhoc types

With typeof you can write

let closure = ||{ complicated_code_1(); complicated_code_2() }; //returns Iterator
let r: typeof(closure())::Item = v;
...

I am not sure how to do this in existential type.

I have fixed the problem you shown for the Adder example.

[rpjohnst]

Your closure example should be doable with existential type like this:

type ClosureReturn: Iterator;
let closure = || -> ClosureReturn { .. complicated_code_1 .. };
let r: ClosureReturn::Item = v;

[mark-i-m]

@earthengine

Now it is 2008

Lol, I was so confused for a moment

[scottmcm]

@Ixrec

the real question is, what advantage does typeof syntax have over existential syntax?

I think the biggest example is when someone else used -> impl Trait and not existential syntax.

Suppose you have a library with a method like pub fn foo() -> impl Trait;, and you want to store the result of that in a struct. Then it's

struct FooHolder {
    x: typeof(foo()),
}

instead of

abstract type FooReturn: Trait;
fn _dummy() -> FooReturn { foo() }
struct FooHolder {
    x: FooReturn,
}

[Nemo157]

Or we get anonymous existential types in struct declarations (although, this is almost certainly blocked from being implemented because of the confusion with anonymous universal types introduced with impl Trait in arguments)

struct FooHolder {
    x: impl Foo,
}

EDIT: also, I would hope that _dummy wouldn’t be needed. It might be under the current rules in the RFC, but hopefully once existential type declarations are implemented and there’s some experience using them they could be relaxed to avoid that.

[earthengine]

The previous version in the top post wouldn’t work because it is also cyclic definition. Should be fixed like

// `impl Trait` in traits:
struct MyStruct;
impl Iterator for MyStruct {
    type Item = typeof((s:&mut Self).next().unwrap());

    fn next(&mut self) -> Option<impl Debug> {
        Some("hello")
    }
}

In sort, calculating the type expression must not require calculating the type definition itself (no cyclic definitions).

As @Ixrec said this is a little bit ugly, so we may also want to say

// `impl Trait` in traits:
struct MyStruct;
impl Iterator for MyStruct {
    type Option<Item> = typeof((s:&mut Self).next());

    fn next(&mut self) -> Option<impl Debug> {
        Some("hello")
    }
}