rust - What makes `impl Trait` as an argument "universal" and as a return value "existential"?

Question

I was reading the RFC on "expanding" impl Trait when I came upon the following:

By contrast, a programmer who first learned: fn take_iter(t: impl Iterator) and then tried: fn give_iter() -> impl Iterator would be successful, without any rigorous understanding that they just transitioned from a universal to an existential.

While I understand universal vs existential from a logic perspective, what makes the first one above universal and the second one existential?

Answer 1

The RFC defines the terms multiple times in multiple manners:

between existential types (where the callee chooses the type) and universal types (where the caller chooses)

There's been a lot of discussion around universals vs. existentials (in today's Rust, generics vs impl Trait).

• Universal quantification, i.e. "for any type T", i.e. "caller chooses". This is how generics work today. When you write fn foo<T>(t: T), you're saying that the function will work for any choice of T, and leaving it to your caller to choose the T.

• Existential quantification, i.e. "for some type T", i.e. "callee chooses". This is how impl Trait works today (which is in return position only). When you write fn foo() -> impl Iterator, you're saying that the function will produce some type T that implements Iterator, but the caller is not allowed to assume anything else about that type.

TL;DR:

• fn take_iter(t: impl Iterator) — the person calling take_iter picks the concrete type. The function has to work for the entire "universe" of types that implement the trait.

• fn give_iter() -> impl Iterator — the implementation of give_iter picks the concrete type. There is some type which "exists" and implements the trait that will be returned by the function.