Tracking issue for `impl Trait` (RFC 1522, RFC 1951, RFC 2071) #34511

Open
aturon opened this Issue Jun 27, 2016 · 358 comments

Comments

Projects
None yet
@aturon
Member

aturon commented Jun 27, 2016

Implementation status

The basic feature as specified in RFC 1522 is implemented, however there have been revisions that are still in need of work:

RFCs

There have been a number of RFCs regarding impl trait, all of which are tracked by this central tracking issue.

  • rust-lang/rfcs#1522
    • the original, which covered only impl Trait in return position for inherent functions
  • rust-lang/rfcs#1951
    • settling on a particular syntax design, resolving questions around the some/any proposal and others.
    • resolving questions around which type and lifetime parameters are considered in scope for an impl Trait.
    • adding impl Trait to argument position.
  • rust-lang/rfcs#2071
    • named abstract type in modules and impls
    • use of impl trait in let, const, and static positions
  • rust-lang/rfcs#2250
    • Finalizing the syntax of impl Trait and dyn Trait with multiple bounds

Unresolved questions

The implementation has raised a number of interesting questions as well:

  • What is the precedence of the impl keyword when parsing types? Discussion: 1
    • e.g., how to associate Send for where F: Fn() -> impl Foo + Send?
    • Resolved by rust-lang/rfcs#2250.
    • Implemented (?) in #45294
  • Should we allow impl Trait after -> in fn types or parentheses sugar? #45994
  • Do we have to impose a DAG across all functions to allow for auto-safe leakage, or can we use some kind of deferral. Discussion: 1
    • Present semantics: DAG.
  • How should we integrate impl trait into regionck? Discussion: 1, 2
  • Should we permit specifying types if some parameters are implicit and some are explicit? e.g., fn foo<T>(x: impl Iterator<Item = T>>)?
  • Some concerns about nested impl Trait usage

@bstrie bstrie referenced this issue in rust-lang/rfcs Jun 28, 2016

Merged

Minimal `impl Trait` #1522

@pthariensflame

This comment has been minimized.

Show comment
Hide comment
@pthariensflame

pthariensflame Jul 15, 2016

Contributor

@aturon Can we actually put the RFC in the repository? (@mbrubeck commented there that this was a problem.)

Contributor

pthariensflame commented Jul 15, 2016

@aturon Can we actually put the RFC in the repository? (@mbrubeck commented there that this was a problem.)

@aturon

This comment has been minimized.

Show comment
Hide comment
@aturon

aturon Jul 15, 2016

Member

Done.

Member

aturon commented Jul 15, 2016

Done.

@eddyb

This comment has been minimized.

Show comment
Hide comment
@eddyb

eddyb Jul 31, 2016

Member

First attempt at implementation is #35091 (second, if you count my branch from last year).

One problem I ran into is with lifetimes. Type inference likes to put region variables everywhere and without any region-checking changes, those variables don't infer to anything other than local scopes.
However, the concrete type must be exportable, so I restricted it to 'static and explicitly named early-bound lifetime parameters, but it's never any of those if any function is involved - even a string literal doesn't infer to 'static, it's pretty much completely useless.

One thing I thought of, that would have 0 impact on region-checking itself, is to erase lifetimes:

  • nothing exposing the concrete type of an impl Trait should care about lifetimes - a quick search for Reveal::All suggests that's already the case in the compiler
  • a bound needs to be placed on all concrete types of impl Trait in the return type of a function, that it outlives the call of that function - this means that any lifetime is, by necessity, either 'static or one of the lifetime parameters of the function - even if we can't know which (e.g. "shortest of 'a and 'b")
  • we must choose a variance for the implicit lifetime parametrism of impl Trait (i.e. on all lifetime parameters in scope, same as with type parameters): invariance is easiest and gives more control to the callee, while contravariance lets the caller do more and would require checking that every lifetime in the return type is in a contravariant position (same with covariant type parametrism instead of invariant)
  • the auto trait leaking mechanism requires that a trait bound may be put on the concrete type, in another function - since we've erased the lifetimes and have no idea what lifetime goes where, every erased lifetime in the concrete type will have to be substituted with a fresh inference variable that is guaranteed to not be shorter than the shortest lifetime out of all actual lifetime parameters; the problem lies in the fact that trait impls can end up requiring stronger lifetime relationships (e.g. X<'a, 'a> or X<'static>), which must be detected and errored on, as they can't be proven for those lifetimes

That last point about auto trait leakage is my only worry, everything else seems straight-forward.
It's not entirely clear at this point how much of region-checking we can reuse as-is. Hopefully all.

cc @rust-lang/lang

Member

eddyb commented Jul 31, 2016

First attempt at implementation is #35091 (second, if you count my branch from last year).

One problem I ran into is with lifetimes. Type inference likes to put region variables everywhere and without any region-checking changes, those variables don't infer to anything other than local scopes.
However, the concrete type must be exportable, so I restricted it to 'static and explicitly named early-bound lifetime parameters, but it's never any of those if any function is involved - even a string literal doesn't infer to 'static, it's pretty much completely useless.

One thing I thought of, that would have 0 impact on region-checking itself, is to erase lifetimes:

  • nothing exposing the concrete type of an impl Trait should care about lifetimes - a quick search for Reveal::All suggests that's already the case in the compiler
  • a bound needs to be placed on all concrete types of impl Trait in the return type of a function, that it outlives the call of that function - this means that any lifetime is, by necessity, either 'static or one of the lifetime parameters of the function - even if we can't know which (e.g. "shortest of 'a and 'b")
  • we must choose a variance for the implicit lifetime parametrism of impl Trait (i.e. on all lifetime parameters in scope, same as with type parameters): invariance is easiest and gives more control to the callee, while contravariance lets the caller do more and would require checking that every lifetime in the return type is in a contravariant position (same with covariant type parametrism instead of invariant)
  • the auto trait leaking mechanism requires that a trait bound may be put on the concrete type, in another function - since we've erased the lifetimes and have no idea what lifetime goes where, every erased lifetime in the concrete type will have to be substituted with a fresh inference variable that is guaranteed to not be shorter than the shortest lifetime out of all actual lifetime parameters; the problem lies in the fact that trait impls can end up requiring stronger lifetime relationships (e.g. X<'a, 'a> or X<'static>), which must be detected and errored on, as they can't be proven for those lifetimes

That last point about auto trait leakage is my only worry, everything else seems straight-forward.
It's not entirely clear at this point how much of region-checking we can reuse as-is. Hopefully all.

cc @rust-lang/lang

@arielb1

This comment has been minimized.

Show comment
Hide comment
@arielb1

arielb1 Jul 31, 2016

Contributor

@eddyb

But lifetimes are important with impl Trait - e.g.

fn get_debug_str(s: &str) -> impl fmt::Debug {
    s
}

fn get_debug_string(s: &str) -> impl fmt::Debug {
    s.to_string()
}

fn good(s: &str) -> Box<fmt::Debug+'static> {
    // if this does not compile, that would be quite annoying
    Box::new(get_debug_string())
}

fn bad(s: &str) -> Box<fmt::Debug+'static> {
    // if this *does* compile, we have a problem
    Box::new(get_debug_str())
}

I mentioned that several times in the RFC threads

Contributor

arielb1 commented Jul 31, 2016

@eddyb

But lifetimes are important with impl Trait - e.g.

fn get_debug_str(s: &str) -> impl fmt::Debug {
    s
}

fn get_debug_string(s: &str) -> impl fmt::Debug {
    s.to_string()
}

fn good(s: &str) -> Box<fmt::Debug+'static> {
    // if this does not compile, that would be quite annoying
    Box::new(get_debug_string())
}

fn bad(s: &str) -> Box<fmt::Debug+'static> {
    // if this *does* compile, we have a problem
    Box::new(get_debug_str())
}

I mentioned that several times in the RFC threads

@arielb1

This comment has been minimized.

Show comment
Hide comment
@arielb1

arielb1 Jul 31, 2016

Contributor

trait-object-less version:

fn as_debug(s: &str) -> impl fmt::Debug;

fn example() {
    let mut s = String::new("hello");
    let debug = as_debug(&s);
    s.truncate(0);
    println!("{:?}", debug);
}

This is either UB or not depending on the definition of as_debug.

Contributor

arielb1 commented Jul 31, 2016

trait-object-less version:

fn as_debug(s: &str) -> impl fmt::Debug;

fn example() {
    let mut s = String::new("hello");
    let debug = as_debug(&s);
    s.truncate(0);
    println!("{:?}", debug);
}

This is either UB or not depending on the definition of as_debug.

@eddyb

This comment has been minimized.

Show comment
Hide comment
@eddyb

eddyb Jul 31, 2016

Member

@arielb1 Ah, right, I forgot that one of the reasons I did what I did was to only capture lifetime parameters, not anonymous late-bound ones, except it doesn't really work.

Member

eddyb commented Jul 31, 2016

@arielb1 Ah, right, I forgot that one of the reasons I did what I did was to only capture lifetime parameters, not anonymous late-bound ones, except it doesn't really work.

@eddyb

This comment has been minimized.

Show comment
Hide comment
@eddyb

eddyb Jul 31, 2016

Member

@arielb1 Do we have a strict outlives relation we can put between lifetimes found in the concrete type pre-erasure and late-bound lifetimes in the signature? Otherwise, it might not be a bad idea to just look at lifetime relationships and insta-fail any direct or indirect 'a outlives 'b where 'a is anything other than 'static or a lifetime parameter and 'b appears in the concrete type of an impl Trait.

Member

eddyb commented Jul 31, 2016

@arielb1 Do we have a strict outlives relation we can put between lifetimes found in the concrete type pre-erasure and late-bound lifetimes in the signature? Otherwise, it might not be a bad idea to just look at lifetime relationships and insta-fail any direct or indirect 'a outlives 'b where 'a is anything other than 'static or a lifetime parameter and 'b appears in the concrete type of an impl Trait.

@nikomatsakis

This comment has been minimized.

Show comment
Hide comment
@nikomatsakis

nikomatsakis Aug 3, 2016

Contributor

Sorry for taking a while to write back here. So I've been thinking
about this problem. My feeling is that we do, ultimately, have to (and
want to) extend regionck with a new kind of constraint -- I'll call it
an \in constraint, because it allows you to say something like '0 \in {'a, 'b, 'c}, meaning that the region used for '0 must be
either 'a, 'b, or 'c. I'm not sure of the best way to integrate
this into solving itself -- certainly if the \in set is a singleton
set, it's just an equate relation (which we don't currently have as a
first-class thing, but which can be composed out of two bounds), but
otherwise it makes things complicated.

This all relates to my desire to make the set of region constraints
more expressive than what we have today. Certainly one could compose a
\in constraint out of OR and == constraints. But of course more
expressive constraints are harder to solve and \in is no different.

Anyway, let me just lay out a bit of my thinking here. Let's work with this
example:

pub fn foo<'a,'b>(x: &'a [u32], y: &'b [u32]) -> impl Iterator<Item=u32> {...}

I think the most accurate desugaring for a impl Trait is probably a
new type:

pub struct FooReturn<'a, 'b> {
    field: XXX // for some suitable type XXX
}

impl<'a,'b> Iterator for FooReturn<'a,'b> {
    type Item = <XXX as Iterator>::Item;
}

Now the impl Iterator<Item=u32> in foo should behave the same as
FooReturn<'a,'b> would behave. It's not a perfect match though. One
difference, for example, is variance, as eddyb brought up -- I am
assuming we will make impl Foo-like types invariant over the type
parameters of foo. The auto trait behavior works out, however.
(Another area where the match might not be ideal is if we ever add the
ability to "pierce" the impl Iterator abstraction, so that code
"inside" the abstraction knows the precise type -- then it would sort
of have an implicit "unwrap" operation taking place.)

In some ways a better match is to consider a kind of synthetic trait:

trait FooReturn<'a,'b> {
    type Type: Iterator<Item=u32>;
}

impl<'a,'b> FooReturn<'a,'b> for () {
    type Type = XXX;
}

Now we could consider the impl Iterator type to be like <() as FooReturn<'a,'b>>::Type. This is also not a perfect match, because we
would ordinarily normalize it away. You might imagine using specialization
to prevent that though:

trait FooReturn<'a,'b> {
    type Type: Iterator<Item=u32>;
}

impl<'a,'b> FooReturn<'a,'b> for () {
    default type Type = XXX; // can't really be specialized, but wev
}

In this case, <() as FooReturn<'a,'b>>::Type would not normalize,
and we have a much closer match. The variance, in particular, behaves
right; if we ever wanted to have some type that are "inside" the
abstraction, they would be the same but they are allowed to
normalize. However, there is a catch: the auto trait stuff doesn't
quite work. (We may want to consider harmonizing things here,
actually.)

Anyway, my point in exploring these potential desugarings is not to
suggest that we implement "impl Trait" as an actual desugaring
(though it might be nice...) but to give an intuition for our job. I
think that the second desugaring -- in terms of projections -- is a
pretty helpful one for guiding us forward.

One place that this projection desugaring is a really useful guide is
the "outlives" relation. If we wanted to check whether <() as FooReturn<'a,'b>>::Type: 'x, RFC 1214 tells us that we can prove this
so long as 'a: 'x and 'b: 'x holds. This is I think how we want
to handle things for impl trait as well.

At trans time, and for auto-traits, we will have to know what XXX
is, of course. The basic idea here, I assume, is to create a type
variable for XXX and check that the actual values which are returned
can all be unified with XXX. That type variable should, in theory,
tell us our answer. But of course the problem is that this type
variable may refer to a lot of regions which are not in scope in the
fn signature -- e.g., the regions of the fn body. (This same problem
does not occur with types; even though, technically, you could put
e.g. a struct declaration in the fn body and it would be unnameable,
that's a kind of artificial restriction -- one could just as well move
the struct outside the fn.)

If you look both at the struct desugaring or the impl, there is an
(implicit in the lexical structure of Rust) restriction that XXX can
only name either 'static or lifetimes like 'a and 'b, which
appear in the function signature. That is the thing we are not
modeling here. I'm not sure the best way to do it -- some type
inference schemes have a more direct representation of scoping, and
I've always wanted to add that to Rust, to help us with closures. But
let's think about smaller deltas first I guess.

This is where the \in constraint comes from. One can imagine adding
a type-check rule that (basically) FR(XXX) \subset {'a, 'b} --
meaning that the "free regions" appearing in XXX can only be 'a and
'b. This would wind up translating to \in requirements for the
various regions that appear in XXX.

Let's look at an actual example:

fn foo<'a,'b>(x: &'a [u32], y: &'b [u32]) -> impl Iterator<Item=u32> {
    if condition { x.iter().cloned() } else { y.iter().cloned() }
}

Here, the type if condition is true would be something like
Cloned<SliceIter<'a, i32>>. But if condition is false, we would
want Cloned<SliceIter<'b, i32>>. Of course in both cases we would
wind up with something like (using numbers for type/region variables):

Cloned<SliceIter<'0, i32>> <: 0
'a: '0 // because the source is x.iter()
Cloned<SliceIter<'1, i32>> <: 0
'b: '1 // because the source is y.iter()

If we then instantiate the variable 0 to Cloned<SliceIter<'2, i32>>,
we have '0: '2 and '1: '2, or a total set of region relations
like:

'a: '0
'0: '2
'b: '1
'1: '2
'2: 'body // the lifetime of the fn body

So what value should we use for '2? We have also the additional
constraint that '2 in {'a, 'b}. With the fn as written, I think we
would have to report an error, since neither 'a nor 'b is a
correct choice. Interestingly, though, if we added the constraint 'a: 'b, then there would be a correct value ('b).

Note that if we just run the normal algorithm, we would wind up with
'2 being 'body. I'm not sure how to handle the \in relations
except for exhaustive search (though I can imagine some special
cases).

OK, that's as far as I've gotten. =)

Contributor

nikomatsakis commented Aug 3, 2016

Sorry for taking a while to write back here. So I've been thinking
about this problem. My feeling is that we do, ultimately, have to (and
want to) extend regionck with a new kind of constraint -- I'll call it
an \in constraint, because it allows you to say something like '0 \in {'a, 'b, 'c}, meaning that the region used for '0 must be
either 'a, 'b, or 'c. I'm not sure of the best way to integrate
this into solving itself -- certainly if the \in set is a singleton
set, it's just an equate relation (which we don't currently have as a
first-class thing, but which can be composed out of two bounds), but
otherwise it makes things complicated.

This all relates to my desire to make the set of region constraints
more expressive than what we have today. Certainly one could compose a
\in constraint out of OR and == constraints. But of course more
expressive constraints are harder to solve and \in is no different.

Anyway, let me just lay out a bit of my thinking here. Let's work with this
example:

pub fn foo<'a,'b>(x: &'a [u32], y: &'b [u32]) -> impl Iterator<Item=u32> {...}

I think the most accurate desugaring for a impl Trait is probably a
new type:

pub struct FooReturn<'a, 'b> {
    field: XXX // for some suitable type XXX
}

impl<'a,'b> Iterator for FooReturn<'a,'b> {
    type Item = <XXX as Iterator>::Item;
}

Now the impl Iterator<Item=u32> in foo should behave the same as
FooReturn<'a,'b> would behave. It's not a perfect match though. One
difference, for example, is variance, as eddyb brought up -- I am
assuming we will make impl Foo-like types invariant over the type
parameters of foo. The auto trait behavior works out, however.
(Another area where the match might not be ideal is if we ever add the
ability to "pierce" the impl Iterator abstraction, so that code
"inside" the abstraction knows the precise type -- then it would sort
of have an implicit "unwrap" operation taking place.)

In some ways a better match is to consider a kind of synthetic trait:

trait FooReturn<'a,'b> {
    type Type: Iterator<Item=u32>;
}

impl<'a,'b> FooReturn<'a,'b> for () {
    type Type = XXX;
}

Now we could consider the impl Iterator type to be like <() as FooReturn<'a,'b>>::Type. This is also not a perfect match, because we
would ordinarily normalize it away. You might imagine using specialization
to prevent that though:

trait FooReturn<'a,'b> {
    type Type: Iterator<Item=u32>;
}

impl<'a,'b> FooReturn<'a,'b> for () {
    default type Type = XXX; // can't really be specialized, but wev
}

In this case, <() as FooReturn<'a,'b>>::Type would not normalize,
and we have a much closer match. The variance, in particular, behaves
right; if we ever wanted to have some type that are "inside" the
abstraction, they would be the same but they are allowed to
normalize. However, there is a catch: the auto trait stuff doesn't
quite work. (We may want to consider harmonizing things here,
actually.)

Anyway, my point in exploring these potential desugarings is not to
suggest that we implement "impl Trait" as an actual desugaring
(though it might be nice...) but to give an intuition for our job. I
think that the second desugaring -- in terms of projections -- is a
pretty helpful one for guiding us forward.

One place that this projection desugaring is a really useful guide is
the "outlives" relation. If we wanted to check whether <() as FooReturn<'a,'b>>::Type: 'x, RFC 1214 tells us that we can prove this
so long as 'a: 'x and 'b: 'x holds. This is I think how we want
to handle things for impl trait as well.

At trans time, and for auto-traits, we will have to know what XXX
is, of course. The basic idea here, I assume, is to create a type
variable for XXX and check that the actual values which are returned
can all be unified with XXX. That type variable should, in theory,
tell us our answer. But of course the problem is that this type
variable may refer to a lot of regions which are not in scope in the
fn signature -- e.g., the regions of the fn body. (This same problem
does not occur with types; even though, technically, you could put
e.g. a struct declaration in the fn body and it would be unnameable,
that's a kind of artificial restriction -- one could just as well move
the struct outside the fn.)

If you look both at the struct desugaring or the impl, there is an
(implicit in the lexical structure of Rust) restriction that XXX can
only name either 'static or lifetimes like 'a and 'b, which
appear in the function signature. That is the thing we are not
modeling here. I'm not sure the best way to do it -- some type
inference schemes have a more direct representation of scoping, and
I've always wanted to add that to Rust, to help us with closures. But
let's think about smaller deltas first I guess.

This is where the \in constraint comes from. One can imagine adding
a type-check rule that (basically) FR(XXX) \subset {'a, 'b} --
meaning that the "free regions" appearing in XXX can only be 'a and
'b. This would wind up translating to \in requirements for the
various regions that appear in XXX.

Let's look at an actual example:

fn foo<'a,'b>(x: &'a [u32], y: &'b [u32]) -> impl Iterator<Item=u32> {
    if condition { x.iter().cloned() } else { y.iter().cloned() }
}

Here, the type if condition is true would be something like
Cloned<SliceIter<'a, i32>>. But if condition is false, we would
want Cloned<SliceIter<'b, i32>>. Of course in both cases we would
wind up with something like (using numbers for type/region variables):

Cloned<SliceIter<'0, i32>> <: 0
'a: '0 // because the source is x.iter()
Cloned<SliceIter<'1, i32>> <: 0
'b: '1 // because the source is y.iter()

If we then instantiate the variable 0 to Cloned<SliceIter<'2, i32>>,
we have '0: '2 and '1: '2, or a total set of region relations
like:

'a: '0
'0: '2
'b: '1
'1: '2
'2: 'body // the lifetime of the fn body

So what value should we use for '2? We have also the additional
constraint that '2 in {'a, 'b}. With the fn as written, I think we
would have to report an error, since neither 'a nor 'b is a
correct choice. Interestingly, though, if we added the constraint 'a: 'b, then there would be a correct value ('b).

Note that if we just run the normal algorithm, we would wind up with
'2 being 'body. I'm not sure how to handle the \in relations
except for exhaustive search (though I can imagine some special
cases).

OK, that's as far as I've gotten. =)

@nikomatsakis

This comment has been minimized.

Show comment
Hide comment
@nikomatsakis

nikomatsakis Aug 10, 2016

Contributor

On the PR #35091, @arielb1 wrote:

I don't like the "capture all lifetimes in the impl trait" approach and would prefer something more like lifetime elision.

I thought it would make more sense to discuss here. @arielb1, can you elaborate more on what you have in mind? In terms of the analogies I made above, I guess you are fundamentally talking about "pruning" the set of lifetimes that would appear either as parameters on the newtype or in the projection (i.e., <() as FooReturn<'a>>::Type instead of <() as FooReturn<'a,'b>>::Type or something?

I don't think that the lifetime elision rules as they exist would be a good guide in this respect: if we just picked the lifetime of &self to include only, then we wouldn't necessarily be able to include the type parameters from the Self struct, nor type parameters from the method, since they may have WF conditions that require us to name some of the other lifetimes.

Anyway, it'd be great to see some examples that illustrate the rules you have in mind, and perhaps any advantages thereof. :) (Also, I guess we would need some syntax to override the choice.) All other things being equal, if we can avoid having to pick from N lifetimes, I'd prefer that.

Contributor

nikomatsakis commented Aug 10, 2016

On the PR #35091, @arielb1 wrote:

I don't like the "capture all lifetimes in the impl trait" approach and would prefer something more like lifetime elision.

I thought it would make more sense to discuss here. @arielb1, can you elaborate more on what you have in mind? In terms of the analogies I made above, I guess you are fundamentally talking about "pruning" the set of lifetimes that would appear either as parameters on the newtype or in the projection (i.e., <() as FooReturn<'a>>::Type instead of <() as FooReturn<'a,'b>>::Type or something?

I don't think that the lifetime elision rules as they exist would be a good guide in this respect: if we just picked the lifetime of &self to include only, then we wouldn't necessarily be able to include the type parameters from the Self struct, nor type parameters from the method, since they may have WF conditions that require us to name some of the other lifetimes.

Anyway, it'd be great to see some examples that illustrate the rules you have in mind, and perhaps any advantages thereof. :) (Also, I guess we would need some syntax to override the choice.) All other things being equal, if we can avoid having to pick from N lifetimes, I'd prefer that.

bors added a commit that referenced this issue Aug 12, 2016

Auto merge of #35091 - eddyb:impl-trait, r=nikomatsakis
Implement `impl Trait` in return type position by anonymization.

This is the first step towards implementing `impl Trait` (cc #34511).
`impl Trait` types are only allowed in function and inherent method return types, and capture all named lifetime and type parameters, being invariant over them.
No lifetimes that are not explicitly named lifetime parameters are allowed to escape from the function body.
The exposed traits are only those listed explicitly, i.e. `Foo` and `Clone` in `impl Foo + Clone`, with the exception of "auto traits" (like `Send` or `Sync`) which "leak" the actual contents.

The implementation strategy is anonymization, i.e.:
```rust
fn foo<T>(xs: Vec<T>) -> impl Iterator<Item=impl FnOnce() -> T> {
    xs.into_iter().map(|x| || x)
}

// is represented as:
type A</*invariant over*/ T> where A<T>: Iterator<Item=B<T>>;
type B</*invariant over*/ T> where B<T>: FnOnce() -> T;
fn foo<T>(xs: Vec<T>) -> A<T> {
    xs.into_iter().map(|x| || x): $0 where $0: Iterator<Item=$1>, $1: FnOnce() -> T
}
```
`$0` and `$1` are resolved (to `iter::Map<vec::Iter<T>, closure>` and the closure, respectively) and assigned to `A` and `B`, after checking the body of `foo`. `A` and `B` are *never* resolved for user-facing type equality (typeck), but always for the low-level representation and specialization (trans).

The "auto traits" exception is implemented by collecting bounds like `impl Trait: Send` that have failed for the obscure `impl Trait` type (i.e. `A` or `B` above), pretending they succeeded within the function and trying them again after type-checking the whole crate, by replacing `impl Trait` with the real type.

While passing around values which have explicit lifetime parameters (of the function with `-> impl Trait`) in their type *should* work, regionck appears to assign inference variables in *way* too many cases, and never properly resolving them to either explicit lifetime parameters, or `'static`.
We might not be able to handle lifetime parameters in `impl Trait` without changes to lifetime inference, but type parameters can have arbitrary lifetimes in them from the caller, so most type-generic usecases (or not generic at all) should not run into this problem.

cc @rust-lang/lang
@petrochenkov

This comment has been minimized.

Show comment
Hide comment
@petrochenkov

petrochenkov Aug 12, 2016

Contributor

I haven't seen interactions of impl Trait with privacy discussed anywhere.
Now fn f() -> impl Trait can return a private type S: Trait similarly to trait objects fn f() -> Box<Trait>. I.e. objects of private types can walk freely outside of their module in anonymized form.
This seems reasonable and desirable - the type itself is an implementation detail, only its interface, available through a public trait Trait is public.
However there's one difference between trait objects and impl Trait. With trait objects alone all trait methods of private types can get internal linkage, they will still be callable through function pointers. With impl Traits trait methods of private types are directly callable from other translation units. The algorithm doing "internalization" of symbols will have to try harder to internalize methods only for types not anonymized with impl Trait, or to be very pessimistic.

Contributor

petrochenkov commented Aug 12, 2016

I haven't seen interactions of impl Trait with privacy discussed anywhere.
Now fn f() -> impl Trait can return a private type S: Trait similarly to trait objects fn f() -> Box<Trait>. I.e. objects of private types can walk freely outside of their module in anonymized form.
This seems reasonable and desirable - the type itself is an implementation detail, only its interface, available through a public trait Trait is public.
However there's one difference between trait objects and impl Trait. With trait objects alone all trait methods of private types can get internal linkage, they will still be callable through function pointers. With impl Traits trait methods of private types are directly callable from other translation units. The algorithm doing "internalization" of symbols will have to try harder to internalize methods only for types not anonymized with impl Trait, or to be very pessimistic.

@arielb1

This comment has been minimized.

Show comment
Hide comment
@arielb1

arielb1 Aug 14, 2016

Contributor

@nikomatsakis

The "explicit" way to write foo would be

fn foo<'a: 'c,'b: 'c,'c>(x: &'a [u32], y: &'b [u32]) -> impl Iterator<Item=u32> + 'c {
    if condition { x.iter().cloned() } else { y.iter().cloned() }
}

Here there is no question about the lifetime bound. Obviously, having to write the lifetime bound each time would be quite repetitive. However, the way we deal with that kind of repetition is generally through lifetime elision. In the case of foo, elision would fail and force the programmer to explicitly specify lifetimes.

I am opposed to adding explicitness-sensitive lifetime elision as @eddyb did only in the specific case of impl Trait and not otherwise.

Contributor

arielb1 commented Aug 14, 2016

@nikomatsakis

The "explicit" way to write foo would be

fn foo<'a: 'c,'b: 'c,'c>(x: &'a [u32], y: &'b [u32]) -> impl Iterator<Item=u32> + 'c {
    if condition { x.iter().cloned() } else { y.iter().cloned() }
}

Here there is no question about the lifetime bound. Obviously, having to write the lifetime bound each time would be quite repetitive. However, the way we deal with that kind of repetition is generally through lifetime elision. In the case of foo, elision would fail and force the programmer to explicitly specify lifetimes.

I am opposed to adding explicitness-sensitive lifetime elision as @eddyb did only in the specific case of impl Trait and not otherwise.

@jamesmunns jamesmunns referenced this issue in Covertness/coap-rs Aug 14, 2016

Open

static handler brings problems #10

@nikomatsakis

This comment has been minimized.

Show comment
Hide comment
@nikomatsakis

nikomatsakis Aug 15, 2016

Contributor

@arielb1 hmm, I'm not 100% sure how to think about this proposed syntax in terms of the "desugarings" that I discussed. It allows you to specify what appears to be a lifetime bound, but the thing we are trying to infer is mostly what lifetimes appear in the hidden type. Does this suggest that at most one lifetime could be "hidden" (and that it would have to be specified exactly?)

It seems like it's not always the case that a "single lifetime parameter" suffices:

fn foo<'a, 'b>(x: &'a [u32], y: &'b [u32]) -> impl Iterator<Item=u32> {
    x.iter().chain(y).cloned()
}

In this case, the hidden iterator type refers to both 'a and 'b (although it is variant in both of them; but I guess we could come up with an example that is invariant).

Contributor

nikomatsakis commented Aug 15, 2016

@arielb1 hmm, I'm not 100% sure how to think about this proposed syntax in terms of the "desugarings" that I discussed. It allows you to specify what appears to be a lifetime bound, but the thing we are trying to infer is mostly what lifetimes appear in the hidden type. Does this suggest that at most one lifetime could be "hidden" (and that it would have to be specified exactly?)

It seems like it's not always the case that a "single lifetime parameter" suffices:

fn foo<'a, 'b>(x: &'a [u32], y: &'b [u32]) -> impl Iterator<Item=u32> {
    x.iter().chain(y).cloned()
}

In this case, the hidden iterator type refers to both 'a and 'b (although it is variant in both of them; but I guess we could come up with an example that is invariant).

@nikomatsakis

This comment has been minimized.

Show comment
Hide comment
@nikomatsakis

nikomatsakis Aug 18, 2016

Contributor

So @aturon and I discussed this issue somewhat and I wanted to share. There are really a couple of orthogonal questions here and I want to separate them out. The first question is "what type/lifetime parameters can potentially be used in the hidden type?" In terms of the (quasi-)desugaring into a default type, this comes down to "what type parameters appear on the trait we introduce". So, for example, if this function:

fn foo<'a, 'b, T>() -> impl Trait { ... }

would get desugared to something like:

fn foo<'a, 'b, T>() -> <() as Foo<...>>::Type { ... }
trait Foo<...> {
  type Type: Trait;
}
impl<...> Foo<...> for () {
  default type Type = /* inferred */;
}

then this question comes down to "what type parameters appear on the trait Foo and its impl"? Basically, the ... here. Clearly this include include the set of type parameters that appear are used by Trait itself, but what additional type parameters? (As I noted before, this desugaring is 100% faithful except for the leakage of auto traits, and I would argue that we should leak auto traits also for specializable impls.)

The default answer we've been using is "all of them", so here ... would be 'a, 'b, T (along with any anonymous parameters that may appear). This may be a reasonable default, but it's not necessarily the best default. (As @arielb1 pointed out.)

This has an effect on the outlives relation, since, in order to determine that <() as Foo<...>>::Type (referring to some particular, opaque instantiation of impl Trait) outlives 'x, we effectively must show that ...: 'x (that is, every lifetime and type parameter).

This is why I say it is not enough to consider lifetime parameters: imagine that we have some call to foo like foo::<'a0, 'b0, &'c0 i32>. This implies that all three lifetimes, '[abc]0, must outlive 'x -- in other words, so long as the return value is in use, this will prolog the loans of all data given into the function. But, as @arielb1 poitned out, elision suggests that this will usually be longer than necessary.

So I imagine that what we need is:

  • to settle on a reasonable default, perhaps using intution from elision;
  • to have an explicit syntax for when the default is not appropriate.

@aturon spitballed something like impl<...> Trait as the explicit syntax, which seems reasonable. Therefore, one could write:

fn foo<'a, 'b, T>(...) -> impl<T> Trait { }

to indicate that the hidden type does not in fact refer to 'a or 'b but only T. Or one might write impl<'a> Trait to indicate that neither 'b nor T are captured.

As for the defaults, it seems like having more data would be pretty useful -- but the general logic of elision suggests that we would do well to capture all the parameters named in the type of self, when applicable. E.g., if you have fn foo<'a,'b>(&'a self, v: &'b [u8]) and the type is Bar<'c, X>, then the type of self would be &'a Bar<'c, X> and hence we would capture 'a, 'c, and X by default, but not 'b.


Another related note is what the meaning of a lifetime bound is. I think that sound lifetime bounds have an existing meaning that should not be changed: if we write impl (Trait+'a) that means that the hidden type T outlives 'a. Similarly one can write impl (Trait+'static) to indicate that there are no borrowed pointers present (even if some lifetimes are captured). When inferring the hidden type T, this would imply a lifetime bound like $T: 'static, where $T is the inference variable we create for the hidden type. This would be handled in the usual way. From a caller's perspective, where the hidden type is, well, hidden, the 'static bound would allow us to conclude that impl (Trait+'static) outlives 'static even if there are lifetime parameters captured.

Here it just behaves exactly as the desugaring would behave:

fn foo<'a, 'b, T>() -> <() as Foo<'a, 'b, 'T>>::Type { ... }
trait Foo<'a, 'b, T> {
  type Type: Trait + 'static; // <-- note the `'static` bound appears here
}
impl<'a, 'b, T> Foo<...> for () {
  default type Type = /* something that doesn't reference `'a`, `'b`, or `T` */;
}

All of this is orthogonal from inference. We still want (I think) to add the notion of a "choose from" constraint and modify inference with some heuristics and, possibly, exhaustive search (the experience from RFC 1214 suggests that heuristics with a conservative fallback can actually get us very far; I'm not aware of people running into limitations in this respect, though there is probably an issue somewhere). Certainly, adding lifetime bounds like 'static or 'a` may influence inference, and thus be helpful, but that is not a perfect solution: for one thing, they are visible to the caller and become part of the API, which may not be desired.

Contributor

nikomatsakis commented Aug 18, 2016

So @aturon and I discussed this issue somewhat and I wanted to share. There are really a couple of orthogonal questions here and I want to separate them out. The first question is "what type/lifetime parameters can potentially be used in the hidden type?" In terms of the (quasi-)desugaring into a default type, this comes down to "what type parameters appear on the trait we introduce". So, for example, if this function:

fn foo<'a, 'b, T>() -> impl Trait { ... }

would get desugared to something like:

fn foo<'a, 'b, T>() -> <() as Foo<...>>::Type { ... }
trait Foo<...> {
  type Type: Trait;
}
impl<...> Foo<...> for () {
  default type Type = /* inferred */;
}

then this question comes down to "what type parameters appear on the trait Foo and its impl"? Basically, the ... here. Clearly this include include the set of type parameters that appear are used by Trait itself, but what additional type parameters? (As I noted before, this desugaring is 100% faithful except for the leakage of auto traits, and I would argue that we should leak auto traits also for specializable impls.)

The default answer we've been using is "all of them", so here ... would be 'a, 'b, T (along with any anonymous parameters that may appear). This may be a reasonable default, but it's not necessarily the best default. (As @arielb1 pointed out.)

This has an effect on the outlives relation, since, in order to determine that <() as Foo<...>>::Type (referring to some particular, opaque instantiation of impl Trait) outlives 'x, we effectively must show that ...: 'x (that is, every lifetime and type parameter).

This is why I say it is not enough to consider lifetime parameters: imagine that we have some call to foo like foo::<'a0, 'b0, &'c0 i32>. This implies that all three lifetimes, '[abc]0, must outlive 'x -- in other words, so long as the return value is in use, this will prolog the loans of all data given into the function. But, as @arielb1 poitned out, elision suggests that this will usually be longer than necessary.

So I imagine that what we need is:

  • to settle on a reasonable default, perhaps using intution from elision;
  • to have an explicit syntax for when the default is not appropriate.

@aturon spitballed something like impl<...> Trait as the explicit syntax, which seems reasonable. Therefore, one could write:

fn foo<'a, 'b, T>(...) -> impl<T> Trait { }

to indicate that the hidden type does not in fact refer to 'a or 'b but only T. Or one might write impl<'a> Trait to indicate that neither 'b nor T are captured.

As for the defaults, it seems like having more data would be pretty useful -- but the general logic of elision suggests that we would do well to capture all the parameters named in the type of self, when applicable. E.g., if you have fn foo<'a,'b>(&'a self, v: &'b [u8]) and the type is Bar<'c, X>, then the type of self would be &'a Bar<'c, X> and hence we would capture 'a, 'c, and X by default, but not 'b.


Another related note is what the meaning of a lifetime bound is. I think that sound lifetime bounds have an existing meaning that should not be changed: if we write impl (Trait+'a) that means that the hidden type T outlives 'a. Similarly one can write impl (Trait+'static) to indicate that there are no borrowed pointers present (even if some lifetimes are captured). When inferring the hidden type T, this would imply a lifetime bound like $T: 'static, where $T is the inference variable we create for the hidden type. This would be handled in the usual way. From a caller's perspective, where the hidden type is, well, hidden, the 'static bound would allow us to conclude that impl (Trait+'static) outlives 'static even if there are lifetime parameters captured.

Here it just behaves exactly as the desugaring would behave:

fn foo<'a, 'b, T>() -> <() as Foo<'a, 'b, 'T>>::Type { ... }
trait Foo<'a, 'b, T> {
  type Type: Trait + 'static; // <-- note the `'static` bound appears here
}
impl<'a, 'b, T> Foo<...> for () {
  default type Type = /* something that doesn't reference `'a`, `'b`, or `T` */;
}

All of this is orthogonal from inference. We still want (I think) to add the notion of a "choose from" constraint and modify inference with some heuristics and, possibly, exhaustive search (the experience from RFC 1214 suggests that heuristics with a conservative fallback can actually get us very far; I'm not aware of people running into limitations in this respect, though there is probably an issue somewhere). Certainly, adding lifetime bounds like 'static or 'a` may influence inference, and thus be helpful, but that is not a perfect solution: for one thing, they are visible to the caller and become part of the API, which may not be desired.

@arielb1

This comment has been minimized.

Show comment
Hide comment
@arielb1

arielb1 Aug 18, 2016

Contributor

Possible options:

Explicit lifetime bound with output parameter elision

Like trait objects today, impl Trait objects have a single lifetime bound parameter, which is inferred using the elision rules.

Disadvantage: unergonomic
Advantage: clear

Explicit lifetime bounds with "all generic" elision

Like trait objects today, impl Trait objects have a single lifetime bound parameter.

However, elision creates a new early-bound parameters that outlives all explicit parameters:

fn foo<T>(&T) -> impl Foo
-->
fn foo<'total, T: 'total>(&T) -> impl Foo + 'total

Disadvantage: adds an early-bound parameter

more.

Contributor

arielb1 commented Aug 18, 2016

Possible options:

Explicit lifetime bound with output parameter elision

Like trait objects today, impl Trait objects have a single lifetime bound parameter, which is inferred using the elision rules.

Disadvantage: unergonomic
Advantage: clear

Explicit lifetime bounds with "all generic" elision

Like trait objects today, impl Trait objects have a single lifetime bound parameter.

However, elision creates a new early-bound parameters that outlives all explicit parameters:

fn foo<T>(&T) -> impl Foo
-->
fn foo<'total, T: 'total>(&T) -> impl Foo + 'total

Disadvantage: adds an early-bound parameter

more.

@nrc nrc added the T-lang label Aug 19, 2016

@dimbleby dimbleby referenced this issue in dimbleby/rust-c-ares Oct 15, 2016

Closed

Remove boxing from futures example #26

@frewsxcv frewsxcv referenced this issue in zargony/atom-language-rust Oct 26, 2016

Open

Recognize minimal impl traits (Rust RFC 1522) #86

@WaDelma WaDelma referenced this issue in WaDelma/poisson Nov 5, 2016

Open

Allow non-uniform point densities #5

@Boscop

This comment has been minimized.

Show comment
Hide comment
@Boscop

Boscop Nov 15, 2016

I ran into this issue with impl Trait +'a and borrowing: #37790

Boscop commented Nov 15, 2016

I ran into this issue with impl Trait +'a and borrowing: #37790

@IanWhitney

This comment has been minimized.

Show comment
Hide comment
@IanWhitney

IanWhitney Jan 9, 2017

If I'm understanding this change correctly (and the chance of that is probably low!), then I think this playground code should work:

https://play.rust-lang.org/?gist=496ec05e6fa9d3a761df09c95297aa2a&version=nightly&backtrace=0

Both ThingOne and ThingTwo implement the Thing trait. build says it will return something that implements Thing, which it does. Yet it does not compile. So I'm clearly misunderstanding something.

If I'm understanding this change correctly (and the chance of that is probably low!), then I think this playground code should work:

https://play.rust-lang.org/?gist=496ec05e6fa9d3a761df09c95297aa2a&version=nightly&backtrace=0

Both ThingOne and ThingTwo implement the Thing trait. build says it will return something that implements Thing, which it does. Yet it does not compile. So I'm clearly misunderstanding something.

@eddyb

This comment has been minimized.

Show comment
Hide comment
@eddyb

eddyb Jan 9, 2017

Member

That "something" must have a type, but in your case you have two conflicting types. @nikomatsakis has previously suggested making this work in general by creating e.g. ThingOne | ThingTwo as type mismatches appear.

Member

eddyb commented Jan 9, 2017

That "something" must have a type, but in your case you have two conflicting types. @nikomatsakis has previously suggested making this work in general by creating e.g. ThingOne | ThingTwo as type mismatches appear.

@WiSaGaN

This comment has been minimized.

Show comment
Hide comment
@WiSaGaN

WiSaGaN Jan 9, 2017

Contributor

@eddyb could you elaborate on ThingOne | ThingTwo? Don't you need to have Box if we only know the type at run-time? Or is it a kind of enum?

Contributor

WiSaGaN commented Jan 9, 2017

@eddyb could you elaborate on ThingOne | ThingTwo? Don't you need to have Box if we only know the type at run-time? Or is it a kind of enum?

@eddyb

This comment has been minimized.

Show comment
Hide comment
@eddyb

eddyb Jan 9, 2017

Member

Yeah it could be an ad-hoc enum-like type that delegated trait method calls, where possible, to its variants.

Member

eddyb commented Jan 9, 2017

Yeah it could be an ad-hoc enum-like type that delegated trait method calls, where possible, to its variants.

@glaebhoerl

This comment has been minimized.

Show comment
Hide comment
@glaebhoerl

glaebhoerl Jan 9, 2017

Contributor

I've wanted that kind of thing before too. The anonymous enums RFC: rust-lang/rfcs#1154

Contributor

glaebhoerl commented Jan 9, 2017

I've wanted that kind of thing before too. The anonymous enums RFC: rust-lang/rfcs#1154

@eddyb

This comment has been minimized.

Show comment
Hide comment
@eddyb

eddyb Jan 9, 2017

Member

It's a rare case of something that works better if it's inference-driven, because if you only create these types on a mismatch, the variants are different (which is a problem with the generalized form).
Also you can get something out of not having pattern-matching (except in obviously disjoint cases?).
But IMO delegation sugar would "just work" in all relevant cases, even if you manage to get a T | T.

Member

eddyb commented Jan 9, 2017

It's a rare case of something that works better if it's inference-driven, because if you only create these types on a mismatch, the variants are different (which is a problem with the generalized form).
Also you can get something out of not having pattern-matching (except in obviously disjoint cases?).
But IMO delegation sugar would "just work" in all relevant cases, even if you manage to get a T | T.

@glaebhoerl

This comment has been minimized.

Show comment
Hide comment
@glaebhoerl

glaebhoerl Jan 9, 2017

Contributor

Could you spell out the other, implicit halves of those sentences? I don't understand most of it, and suspect I'm missing some context. Were you implicitly responding to the problems with union types? That RFC is simply anonymous enums, not union types - (T|T) would be exactly as problematic as Result<T, T>.

Contributor

glaebhoerl commented Jan 9, 2017

Could you spell out the other, implicit halves of those sentences? I don't understand most of it, and suspect I'm missing some context. Were you implicitly responding to the problems with union types? That RFC is simply anonymous enums, not union types - (T|T) would be exactly as problematic as Result<T, T>.

@varkor

This comment has been minimized.

Show comment
Hide comment
@varkor

varkor Jul 3, 2018

Contributor

@cramertj: the semantics of impl Trait in the language is entirely restricted to its use in function signatures and it's not true that extending it to other positions has an obvious meaning. I'll say something more detailed about this soon, where most of the conversation seems to be going on.

Contributor

varkor commented Jul 3, 2018

@cramertj: the semantics of impl Trait in the language is entirely restricted to its use in function signatures and it's not true that extending it to other positions has an obvious meaning. I'll say something more detailed about this soon, where most of the conversation seems to be going on.

@cramertj

This comment has been minimized.

Show comment
Hide comment
@cramertj

cramertj Jul 3, 2018

Member

@varkor

the semantics of impl Trait in the language is entirely restricted to its use in function signatures and it's not true that extending it to other positions has an obvious meaning.

The meaning was specified in RFC 2071.

Member

cramertj commented Jul 3, 2018

@varkor

the semantics of impl Trait in the language is entirely restricted to its use in function signatures and it's not true that extending it to other positions has an obvious meaning.

The meaning was specified in RFC 2071.

@varkor

This comment has been minimized.

Show comment
Hide comment
@varkor

varkor Jul 3, 2018

Contributor

@cramertj: the meaning in RFC 2071 is ambiguous and permits multiple interpretations of what the phrase "existential type" means there.

Contributor

varkor commented Jul 3, 2018

@cramertj: the meaning in RFC 2071 is ambiguous and permits multiple interpretations of what the phrase "existential type" means there.

@varkor

This comment has been minimized.

Show comment
Hide comment
@varkor

varkor Jul 3, 2018

Contributor

TL;DR — I've tried to set out a precise meaning for impl Trait, which I think clarifies details that were, at least intuitively, unclear; along with a proposal for a new type alias syntax.

Existential types in Rust (post)


There's been a lot of discussion going on in the Discord rust-lang chat about the precise (i.e. formal, theoretic) semantics of impl Trait in the last couple of days. I think it's been helpful to clarify a lot of details about the feature and exactly what it is and is not. It also sheds some light on which syntaxes are plausible for type aliases.

I wrote a little summary of some of our conclusions. This provides an interpretation of impl Trait which I think is fairly clean, and precisely describes the differences between argument-position impl Trait and return-position impl Trait (which is not "universally-quantified" vs "existentially-quantified"). There are also some practical conclusions.

In it, I propose a new syntax fulfilling the commonly-stated requirements of an "existential type alias":
type Foo: Bar = _;

Because it's such a complex topic, there's quite a lot that needs to be clarified first though, so I've written it as a separate post. Feedback is very much appreciated!

Existential types in Rust (post)

Contributor

varkor commented Jul 3, 2018

TL;DR — I've tried to set out a precise meaning for impl Trait, which I think clarifies details that were, at least intuitively, unclear; along with a proposal for a new type alias syntax.

Existential types in Rust (post)


There's been a lot of discussion going on in the Discord rust-lang chat about the precise (i.e. formal, theoretic) semantics of impl Trait in the last couple of days. I think it's been helpful to clarify a lot of details about the feature and exactly what it is and is not. It also sheds some light on which syntaxes are plausible for type aliases.

I wrote a little summary of some of our conclusions. This provides an interpretation of impl Trait which I think is fairly clean, and precisely describes the differences between argument-position impl Trait and return-position impl Trait (which is not "universally-quantified" vs "existentially-quantified"). There are also some practical conclusions.

In it, I propose a new syntax fulfilling the commonly-stated requirements of an "existential type alias":
type Foo: Bar = _;

Because it's such a complex topic, there's quite a lot that needs to be clarified first though, so I've written it as a separate post. Feedback is very much appreciated!

Existential types in Rust (post)

@cramertj

This comment has been minimized.

Show comment
Hide comment
@cramertj

cramertj Jul 4, 2018

Member

@varkor

RFC 2071 is ambiguous and permits multiple interpretations of what the phrase "existential type" means there.

How is it ambiguous? I've read your post-- I'm still only aware of one meaning of non-dynamic existential in statics and constants. It behaves the same way that return position impl Trait does, by introducing a new existential type definition per-item.

type Foo: Bar = _;

We discussed this syntax during RFC 2071. As I said there, I like that it demonstrates clearly that Foo is a single inferred type and that it leaves room for non-inferred types that are left existential outside the current module (e.g. type Foo: Bar = u32;). I disliked two aspects of it: (1) it has no keyword, and is therefore harder to search for and (b) it has the same verbosity issue in comparison to type Foo = impl Trait that the abstract type Foo: Bar; syntax has: type Foo = impl Iterator<Item = impl Display>; becomes type Foo: Iterator<Item = MyDisplay> = _; type MyDisplay: Display = _;. I don't think either of these are deal-breakers, but it's not a clear win one way or another IMO.

Member

cramertj commented Jul 4, 2018

@varkor

RFC 2071 is ambiguous and permits multiple interpretations of what the phrase "existential type" means there.

How is it ambiguous? I've read your post-- I'm still only aware of one meaning of non-dynamic existential in statics and constants. It behaves the same way that return position impl Trait does, by introducing a new existential type definition per-item.

type Foo: Bar = _;

We discussed this syntax during RFC 2071. As I said there, I like that it demonstrates clearly that Foo is a single inferred type and that it leaves room for non-inferred types that are left existential outside the current module (e.g. type Foo: Bar = u32;). I disliked two aspects of it: (1) it has no keyword, and is therefore harder to search for and (b) it has the same verbosity issue in comparison to type Foo = impl Trait that the abstract type Foo: Bar; syntax has: type Foo = impl Iterator<Item = impl Display>; becomes type Foo: Iterator<Item = MyDisplay> = _; type MyDisplay: Display = _;. I don't think either of these are deal-breakers, but it's not a clear win one way or another IMO.

@rpjohnst

This comment has been minimized.

Show comment
Hide comment
@rpjohnst

rpjohnst Jul 4, 2018

Contributor

@cramertj The ambiguity comes up here:

type Foo = impl Bar;
fn f() -> Foo { .. }
fn g() -> Foo { .. }

If Foo were really a type alias for an existential type, then f and g would support different concrete return types. Several people have instinctively read that syntax this way, and in fact some participants in the RFC 2071 syntax discussion only just realized that that's not how the proposal works as part of the recent Discord discussion.

The problem is that, especially in the face of argument-position impl Trait, it's not at all clear where the existential quantifier is meant to go. For arguments it's tightly-scoped; for return position it seems tightly-scoped but turns out to be wider than that; for type Foo = impl Bar both positions are plausible. The _-based syntax nudges toward an interpretation that doesn't even involve "existential," neatly sidestepping this problem.

Contributor

rpjohnst commented Jul 4, 2018

@cramertj The ambiguity comes up here:

type Foo = impl Bar;
fn f() -> Foo { .. }
fn g() -> Foo { .. }

If Foo were really a type alias for an existential type, then f and g would support different concrete return types. Several people have instinctively read that syntax this way, and in fact some participants in the RFC 2071 syntax discussion only just realized that that's not how the proposal works as part of the recent Discord discussion.

The problem is that, especially in the face of argument-position impl Trait, it's not at all clear where the existential quantifier is meant to go. For arguments it's tightly-scoped; for return position it seems tightly-scoped but turns out to be wider than that; for type Foo = impl Bar both positions are plausible. The _-based syntax nudges toward an interpretation that doesn't even involve "existential," neatly sidestepping this problem.

@Nemo157

This comment has been minimized.

Show comment
Hide comment
@Nemo157

Nemo157 Jul 4, 2018

Contributor

If Foo were really a type alias for an existential type

(emphasis mine). I read that 'an' as 'a specific' which means f and g would not support different concrete return types, since they refer to the same existential type. I have always seen type Foo = impl Bar; as using the same meaning as let foo: impl Bar;, i.e. introducing a new anonymous existential type; making your example equivalent to

existential type _0: Bar;
type Foo = _0;
fn f() -> Foo { .. }
fn g() -> Foo { .. }

which I would hope is relatively unambiguous.


One issue is that the meaning of "impl Trait in type aliases" has never been specified in an RFC. It is briefly mentioned in RFC 2071's "Alternatives" section, but explicitly discounted because of these inherent teaching ambiguities.

I also feel like I saw some mention that type aliases are already not referentially transparent. I think it was on u.rl.o, but I haven't been able to find the discussion after some searching.

Contributor

Nemo157 commented Jul 4, 2018

If Foo were really a type alias for an existential type

(emphasis mine). I read that 'an' as 'a specific' which means f and g would not support different concrete return types, since they refer to the same existential type. I have always seen type Foo = impl Bar; as using the same meaning as let foo: impl Bar;, i.e. introducing a new anonymous existential type; making your example equivalent to

existential type _0: Bar;
type Foo = _0;
fn f() -> Foo { .. }
fn g() -> Foo { .. }

which I would hope is relatively unambiguous.


One issue is that the meaning of "impl Trait in type aliases" has never been specified in an RFC. It is briefly mentioned in RFC 2071's "Alternatives" section, but explicitly discounted because of these inherent teaching ambiguities.

I also feel like I saw some mention that type aliases are already not referentially transparent. I think it was on u.rl.o, but I haven't been able to find the discussion after some searching.

@varkor

This comment has been minimized.

Show comment
Hide comment
@varkor

varkor Jul 4, 2018

Contributor

@cramertj
To follow on from @rpjohnst's point, there are multiple interpretations of the semantics of impl Trait, which are all consistent with the current usage in signatures, but have different consequences when extending impl Trait to other locations (I know of 2 other than the one described in the post, but which aren't quite ready for discussion). And I don't think it's true that the interpretation in the post is necessarily the most obvious (I personally didn't see any similar explanation about APIT and RTIP from that perspective).

Regarding the type Foo: Bar = _;, I think perhaps it ought to be discussed again — there's no harm in revisiting old ideas with fresh eyes. Regarding your issues with it:
(1) It has no keyword, but it's the same syntax as type inference anywhere. Searching documentation for "underscore" / "underscore type" / etc. could easily provide a page on type inference.
(2) Yes, that is true. We've been thinking of a solution to this, which I think fits nicely with the underscore notation, which will hopefully be ready to suggest soon.

Contributor

varkor commented Jul 4, 2018

@cramertj
To follow on from @rpjohnst's point, there are multiple interpretations of the semantics of impl Trait, which are all consistent with the current usage in signatures, but have different consequences when extending impl Trait to other locations (I know of 2 other than the one described in the post, but which aren't quite ready for discussion). And I don't think it's true that the interpretation in the post is necessarily the most obvious (I personally didn't see any similar explanation about APIT and RTIP from that perspective).

Regarding the type Foo: Bar = _;, I think perhaps it ought to be discussed again — there's no harm in revisiting old ideas with fresh eyes. Regarding your issues with it:
(1) It has no keyword, but it's the same syntax as type inference anywhere. Searching documentation for "underscore" / "underscore type" / etc. could easily provide a page on type inference.
(2) Yes, that is true. We've been thinking of a solution to this, which I think fits nicely with the underscore notation, which will hopefully be ready to suggest soon.

@Ixrec

This comment has been minimized.

Show comment
Hide comment
@Ixrec

Ixrec Jul 4, 2018

Contributor

Like @cramertj I'm not really seeing the argument here.

I just don't see the fundamental ambiguity that @varkor's post describes. I think we've always interpreted "existential type" in Rust as "there exists a unique type that..." and not "there exists at least one type that..." because (as @varkor's post says) the latter is equivalent to "universal types" and therefore the phrase "existential type" would be totally useless if we were intending to allow that interpretation. afaik every RFC on the subject has always assumed universal and existential types were two distinct things. I get that in actual type theory that is what it means and that isomorphism is very mathematically real, but to me that's just an argument that we've been misusing type theory terminology and need to choose some other jargon for this, not an argument that the intended semantics of impl Trait were always unclear and need to be rethought.

The scoping ambiguity that @rpjohnst describes is a serious problem, but every proposed syntax is potentially confusable with either type alises or associated types. Which of those confusions is "worse" or "more likely" is precisely the neverending bikeshed that we've already failed to resolve after several hundred comments. I do like that type Foo: Bar = _; seems to fix type Foo: Bar;'s problem of needing an explosion of several statements to declare any slightly non-trivial existential, but I don't think that's enough to really change the "neverending bikeshed" situation.

What I am convinced of is that whatever syntax we end up with needs to have a keyword other than type, because all of the "just type" syntaxes are too misleading. In fact, maybe don't use type in the syntax at all so there's no way someone could assume they're looking at "a type alias, but more existential somehow".

existential Foo = impl Trait;
fn f() -> Foo { .. }
fn g() -> Foo { .. }
existential Foo: Trait;
fn f() -> Foo { .. }
fn g() -> Foo { .. }
existential Foo: Trait = _;
fn f() -> Foo { .. }
fn g() -> Foo { .. }

It's not obvious to me that any of these completely prevent the misinterpretation that f and g could return two different types implementing Trait, but I suspect this is as close to prevention as we could possibly get.

Contributor

Ixrec commented Jul 4, 2018

Like @cramertj I'm not really seeing the argument here.

I just don't see the fundamental ambiguity that @varkor's post describes. I think we've always interpreted "existential type" in Rust as "there exists a unique type that..." and not "there exists at least one type that..." because (as @varkor's post says) the latter is equivalent to "universal types" and therefore the phrase "existential type" would be totally useless if we were intending to allow that interpretation. afaik every RFC on the subject has always assumed universal and existential types were two distinct things. I get that in actual type theory that is what it means and that isomorphism is very mathematically real, but to me that's just an argument that we've been misusing type theory terminology and need to choose some other jargon for this, not an argument that the intended semantics of impl Trait were always unclear and need to be rethought.

The scoping ambiguity that @rpjohnst describes is a serious problem, but every proposed syntax is potentially confusable with either type alises or associated types. Which of those confusions is "worse" or "more likely" is precisely the neverending bikeshed that we've already failed to resolve after several hundred comments. I do like that type Foo: Bar = _; seems to fix type Foo: Bar;'s problem of needing an explosion of several statements to declare any slightly non-trivial existential, but I don't think that's enough to really change the "neverending bikeshed" situation.

What I am convinced of is that whatever syntax we end up with needs to have a keyword other than type, because all of the "just type" syntaxes are too misleading. In fact, maybe don't use type in the syntax at all so there's no way someone could assume they're looking at "a type alias, but more existential somehow".

existential Foo = impl Trait;
fn f() -> Foo { .. }
fn g() -> Foo { .. }
existential Foo: Trait;
fn f() -> Foo { .. }
fn g() -> Foo { .. }
existential Foo: Trait = _;
fn f() -> Foo { .. }
fn g() -> Foo { .. }

It's not obvious to me that any of these completely prevent the misinterpretation that f and g could return two different types implementing Trait, but I suspect this is as close to prevention as we could possibly get.

@varkor

This comment has been minimized.

Show comment
Hide comment
@varkor

varkor Jul 4, 2018

Contributor

@Ixrec
The phrase "existential type" is problematic specifically because of the scoping ambiguity. I haven't seen anyone else point out that the scoping is entirely different for the APIT and RPIT. This means that a syntax like type Foo = impl Bar, where impl Bar is an "existential type" is inherently ambiguous.

Yes, the type theory terminology has been misused, a lot. But it's been misused (or at least not explained) in the RFC — so there's ambiguity stemming from the RFC itself.

The scoping ambiguity that @rpjohnst describes is a serious problem, but every proposed syntax is potentially confusable with either type alises or associated types. Which of those confusions is "worse" or "more likely" is precisely the neverending bikeshed that we've already failed to resolve after several hundred comments.

No, I don't think this is true. It's possible to come up with a consistent syntax that doesn't have this confusion. I would venture the bike-shedding is because the two current proposals are bad, so they don't really satisfy anyone.

What I am convinced of is that whatever syntax we end up with needs to have a keyword other than type

I don't think this is necessary either. In your examples, you've invented entirely new notation, which is something you want to avoid in language design wherever possible — otherwise you create a huge language full of inconsistent syntax. You should explore completely new syntax only when there aren't any better options. And I argue that there is a better option.

Aside: on a side note, I think it's possible to move away from "existential types" entirely, making the entire situation clearer, which I or someone else will follow up with soon.

Contributor

varkor commented Jul 4, 2018

@Ixrec
The phrase "existential type" is problematic specifically because of the scoping ambiguity. I haven't seen anyone else point out that the scoping is entirely different for the APIT and RPIT. This means that a syntax like type Foo = impl Bar, where impl Bar is an "existential type" is inherently ambiguous.

Yes, the type theory terminology has been misused, a lot. But it's been misused (or at least not explained) in the RFC — so there's ambiguity stemming from the RFC itself.

The scoping ambiguity that @rpjohnst describes is a serious problem, but every proposed syntax is potentially confusable with either type alises or associated types. Which of those confusions is "worse" or "more likely" is precisely the neverending bikeshed that we've already failed to resolve after several hundred comments.

No, I don't think this is true. It's possible to come up with a consistent syntax that doesn't have this confusion. I would venture the bike-shedding is because the two current proposals are bad, so they don't really satisfy anyone.

What I am convinced of is that whatever syntax we end up with needs to have a keyword other than type

I don't think this is necessary either. In your examples, you've invented entirely new notation, which is something you want to avoid in language design wherever possible — otherwise you create a huge language full of inconsistent syntax. You should explore completely new syntax only when there aren't any better options. And I argue that there is a better option.

Aside: on a side note, I think it's possible to move away from "existential types" entirely, making the entire situation clearer, which I or someone else will follow up with soon.

@joshtriplett

This comment has been minimized.

Show comment
Hide comment
@joshtriplett

joshtriplett Jul 4, 2018

Member

I find myself thinking that a syntax other than type would help as well, precisely because many people interpret type as a simple substitutable alias, which would imply the "potentially different type every time" interpretation.

Member

joshtriplett commented Jul 4, 2018

I find myself thinking that a syntax other than type would help as well, precisely because many people interpret type as a simple substitutable alias, which would imply the "potentially different type every time" interpretation.

@Ixrec

This comment has been minimized.

Show comment
Hide comment
@Ixrec

Ixrec Jul 4, 2018

Contributor

I haven't seen anyone else point out that the scoping is entirely different for the APIT and RPIT.

I thought the scoping was always an explicit part of the impl Trait proposals, so it didn't need "pointing out". Everything you've said about scoping seems like it's just reiterating what we've already accepted in past RFCs. I get that it's not obvious to everyone from the syntax and that's a problem, but it's not like nobody understood this before. In fact, I thought a huge chunk of the discussion on RFC 2701 was all about what the scoping of type Foo = impl Trait; should be, in the sense of what type inference is and is not allowed to look at.

It's possible to come up with a consistent syntax that doesn't have this confusion.

Are you trying to say type Foo: Bar = _; is that syntax, or do you think we haven't found it yet?

I don't think it's possible to come up with a syntax lacking any similar confusion, not because we're insufficiently creative, but because most programmers are not type theorists. We can probably find a syntax that reduces confusion to a tolerable level, and certainly there are plenty of syntaxes which would be unambiguous to type theory veterans, but we'll never eliminate confusion completely.

you've invented entirely new notation

I thought I just replaced one keyword with another keyword. Are you seeing some additional change I didn't intend?

Contributor

Ixrec commented Jul 4, 2018

I haven't seen anyone else point out that the scoping is entirely different for the APIT and RPIT.

I thought the scoping was always an explicit part of the impl Trait proposals, so it didn't need "pointing out". Everything you've said about scoping seems like it's just reiterating what we've already accepted in past RFCs. I get that it's not obvious to everyone from the syntax and that's a problem, but it's not like nobody understood this before. In fact, I thought a huge chunk of the discussion on RFC 2701 was all about what the scoping of type Foo = impl Trait; should be, in the sense of what type inference is and is not allowed to look at.

It's possible to come up with a consistent syntax that doesn't have this confusion.

Are you trying to say type Foo: Bar = _; is that syntax, or do you think we haven't found it yet?

I don't think it's possible to come up with a syntax lacking any similar confusion, not because we're insufficiently creative, but because most programmers are not type theorists. We can probably find a syntax that reduces confusion to a tolerable level, and certainly there are plenty of syntaxes which would be unambiguous to type theory veterans, but we'll never eliminate confusion completely.

you've invented entirely new notation

I thought I just replaced one keyword with another keyword. Are you seeing some additional change I didn't intend?

@Ixrec

This comment has been minimized.

Show comment
Hide comment
@Ixrec

Ixrec Jul 4, 2018

Contributor

Come to think of it, since we've been misusing "existential" all this time, that means existential Foo: Trait/= impl Trait probably aren't legitimate syntaxes anymore.

So we need a new keyword to put in front of names that refer to some unknown-to-external-code type... and I'm drawing a blank on this. alias, secret, internal, etc all seem pretty terrible, and unlikely to have any less "uniqueness confusion" than type.

Contributor

Ixrec commented Jul 4, 2018

Come to think of it, since we've been misusing "existential" all this time, that means existential Foo: Trait/= impl Trait probably aren't legitimate syntaxes anymore.

So we need a new keyword to put in front of names that refer to some unknown-to-external-code type... and I'm drawing a blank on this. alias, secret, internal, etc all seem pretty terrible, and unlikely to have any less "uniqueness confusion" than type.

@varkor

This comment has been minimized.

Show comment
Hide comment
@varkor

varkor Jul 4, 2018

Contributor

Come to think of it, since we've been misusing "existential" all this time, that means existential Foo: Trait/= impl Trait probably aren't legitimate syntaxes anymore.

Yes, I completely agree — I think we need to move away from the term "existential" entirely* (there have been some tentative ideas for how to do this while still explaining impl Trait well).

*(possibly reserving the term for dyn Trait only)

@joshtriplett, @Ixrec: I agree that the _ notation means you can no longer substitute to the same extent you could before, and if that's a priority to keep, we would need a different syntax.

Bear in mind that _ is already a special case with respect to substitution anyway — it's not just type aliases that this affects: anywhere you can currently use _, you're preventing full referential transparency.

Contributor

varkor commented Jul 4, 2018

Come to think of it, since we've been misusing "existential" all this time, that means existential Foo: Trait/= impl Trait probably aren't legitimate syntaxes anymore.

Yes, I completely agree — I think we need to move away from the term "existential" entirely* (there have been some tentative ideas for how to do this while still explaining impl Trait well).

*(possibly reserving the term for dyn Trait only)

@joshtriplett, @Ixrec: I agree that the _ notation means you can no longer substitute to the same extent you could before, and if that's a priority to keep, we would need a different syntax.

Bear in mind that _ is already a special case with respect to substitution anyway — it's not just type aliases that this affects: anywhere you can currently use _, you're preventing full referential transparency.

@Ixrec

This comment has been minimized.

Show comment
Hide comment
@Ixrec

Ixrec Jul 4, 2018

Contributor

Bear in mind that _ is already a special case with respect to substitution anyway — it's not just type aliases that this affects: anywhere you can currently use _, you're preventing full referential transparency.

Could you walk us through what this means exactly? I wasn't aware of a notion of "referential transparency" that's affected by _.

I agree that the _ notation means you can no longer substitute to the same extent you could before, and if that's a priority to keep, we would need a different syntax.

I'm not sure it's a priority. To me it was just the only objective-ish argument that we ever found that seemed to prefer one syntax over the other. But that's all likely to change based on what keywords we can come up with to replace type.

Contributor

Ixrec commented Jul 4, 2018

Bear in mind that _ is already a special case with respect to substitution anyway — it's not just type aliases that this affects: anywhere you can currently use _, you're preventing full referential transparency.

Could you walk us through what this means exactly? I wasn't aware of a notion of "referential transparency" that's affected by _.

I agree that the _ notation means you can no longer substitute to the same extent you could before, and if that's a priority to keep, we would need a different syntax.

I'm not sure it's a priority. To me it was just the only objective-ish argument that we ever found that seemed to prefer one syntax over the other. But that's all likely to change based on what keywords we can come up with to replace type.

@varkor

This comment has been minimized.

Show comment
Hide comment
@varkor

varkor Jul 4, 2018

Contributor

Could you walk us through what this means exactly? I wasn't aware of a notion of "referential transparency" that's affected by _.

Yeah, sorry, I'm throwing words about without explaining them. Let me gather my thoughts, and I'll formulate a more cohesive explanation. It fits in well with an alternative (and potentially more helpful) way to look at impl Trait.

Contributor

varkor commented Jul 4, 2018

Could you walk us through what this means exactly? I wasn't aware of a notion of "referential transparency" that's affected by _.

Yeah, sorry, I'm throwing words about without explaining them. Let me gather my thoughts, and I'll formulate a more cohesive explanation. It fits in well with an alternative (and potentially more helpful) way to look at impl Trait.

@Centril

This comment has been minimized.

Show comment
Hide comment
@Centril

Centril Jul 4, 2018

Contributor

By referential transparency, it is meant that it is possible to substitute a reference for its definition and vice versa without a change in semantics. In Rust, this clearly does not hold at the term level for fn. For example:

fn foo() -> usize {
    println!("ey!");
    42
}

fn main() {
    let bar = foo();
    let baz = bar + bar;
}

if we substitute each occurence of bar for foo() (the definition of bar), then we clearly get a different output.

However, for type aliases, referential transparency hold (AFAIK) at the moment. If you have an alias:

type Foo = Definition;

Then you can do (capture avoiding) substitution of occurrences of Foo for Definition and substitution of occurrences of Definition for Foo without changing the semantics of your program, or its type correctness.

Introducing:

type Foo = impl Bar;

to mean that each occurrence of Foo is the same type means that if you write:

fn stuff() -> Foo { .. }
fn other_stuff() -> Foo { .. }

you can't substitute occurrences of Foo for impl Bar and vice versa. That is, if you write:

fn stuff() -> impl Bar { .. }
fn other_stuff() -> impl Bar { .. }

the return types won't unify with Foo. Thus referential transparency is broken for type aliases by introducing impl Trait with the semantics of RFC 2071 inside of them.

On referential transparency and type Foo = _;, to be continued... (by @varkor)

Contributor

Centril commented Jul 4, 2018

By referential transparency, it is meant that it is possible to substitute a reference for its definition and vice versa without a change in semantics. In Rust, this clearly does not hold at the term level for fn. For example:

fn foo() -> usize {
    println!("ey!");
    42
}

fn main() {
    let bar = foo();
    let baz = bar + bar;
}

if we substitute each occurence of bar for foo() (the definition of bar), then we clearly get a different output.

However, for type aliases, referential transparency hold (AFAIK) at the moment. If you have an alias:

type Foo = Definition;

Then you can do (capture avoiding) substitution of occurrences of Foo for Definition and substitution of occurrences of Definition for Foo without changing the semantics of your program, or its type correctness.

Introducing:

type Foo = impl Bar;

to mean that each occurrence of Foo is the same type means that if you write:

fn stuff() -> Foo { .. }
fn other_stuff() -> Foo { .. }

you can't substitute occurrences of Foo for impl Bar and vice versa. That is, if you write:

fn stuff() -> impl Bar { .. }
fn other_stuff() -> impl Bar { .. }

the return types won't unify with Foo. Thus referential transparency is broken for type aliases by introducing impl Trait with the semantics of RFC 2071 inside of them.

On referential transparency and type Foo = _;, to be continued... (by @varkor)

@alexreg

This comment has been minimized.

Show comment
Hide comment
@alexreg

alexreg Jul 4, 2018

Contributor

I find myself thinking that a syntax other than type would help as well, precisely because many people interpret type as a simple substitutable alias, which would imply the "potentially different type every time" interpretation.

Good point. But doesn't the = _ assignment bit imply that it's only a single type?

Contributor

alexreg commented Jul 4, 2018

I find myself thinking that a syntax other than type would help as well, precisely because many people interpret type as a simple substitutable alias, which would imply the "potentially different type every time" interpretation.

Good point. But doesn't the = _ assignment bit imply that it's only a single type?

@lnicola

This comment has been minimized.

Show comment
Hide comment
@lnicola

lnicola Jul 4, 2018

Contributor

I've written this before, but...

Re referential transparency: I think it's more useful to look at type as a binding (like let) instead of C preprocessor-like substitution. Once you look at it that way, type Foo = impl Trait means exactly what it seems.

I imagine beginners will be less likely to think of impl Trait as existential vs. universtal types, but as "a thing that impls a Trait. If they want to know more, they can read theimpl Trait` documentation. Once you change the syntax, you lose the connection between it and the existing feature with not much benefit. You're only replacing one potentially misleading syntax with another.

Re type Foo = _, it overloads _ with a completely unrelated meaning. It can also seem tricky to find in the documentation and/or Google.

Contributor

lnicola commented Jul 4, 2018

I've written this before, but...

Re referential transparency: I think it's more useful to look at type as a binding (like let) instead of C preprocessor-like substitution. Once you look at it that way, type Foo = impl Trait means exactly what it seems.

I imagine beginners will be less likely to think of impl Trait as existential vs. universtal types, but as "a thing that impls a Trait. If they want to know more, they can read theimpl Trait` documentation. Once you change the syntax, you lose the connection between it and the existing feature with not much benefit. You're only replacing one potentially misleading syntax with another.

Re type Foo = _, it overloads _ with a completely unrelated meaning. It can also seem tricky to find in the documentation and/or Google.

@Centril

This comment has been minimized.

Show comment
Hide comment
@Centril

Centril Jul 4, 2018

Contributor

@lnicola You could just as well go with const bindings instead of let bindings, where the former is referentially transparent. Picking let (which happens to not be referentially transparent inside fn) is an arbitrary choice that I don't think is particularly intuitive. I think the intuitive view of type aliases is that they are referentially transparent (even if that word is not used) because they are aliases.

I'm also not looking at type as C preprocessor substitution because it has to be capture avoiding and respect generics (no SFINAE). Instead, I'm thinking of type precisely as I would a binding in a language like Idris or Agda where all bindings are pure.

I imagine beginners will be less likely to think of impl Trait as existential vs. universtal types, but as "a thing that impls a Trait

That seems like a distinction without a difference to me. The jargon "existential" is not used, but I believe the user is intuitively linking it to the same concept as that of an existential type (which is nothing more than "some type Foo that impls Bar" in the context of Rust).

Re type Foo = _, it overloads _ with a completely unrelated meaning.

How so? type Foo = _; here aligns with the use of _ in other contexts where a type is expected.
It means "infer the real type", just as when you write .collect::<Vec<_>>().

It can also seem tricky to find in the documentation and/or Google.

Shouldn't be that difficult? "type alias underscore" should hopefully bring up the wanted result...?
Doesn't seem any different than searching for "type alias impl trait".

Contributor

Centril commented Jul 4, 2018

@lnicola You could just as well go with const bindings instead of let bindings, where the former is referentially transparent. Picking let (which happens to not be referentially transparent inside fn) is an arbitrary choice that I don't think is particularly intuitive. I think the intuitive view of type aliases is that they are referentially transparent (even if that word is not used) because they are aliases.

I'm also not looking at type as C preprocessor substitution because it has to be capture avoiding and respect generics (no SFINAE). Instead, I'm thinking of type precisely as I would a binding in a language like Idris or Agda where all bindings are pure.

I imagine beginners will be less likely to think of impl Trait as existential vs. universtal types, but as "a thing that impls a Trait

That seems like a distinction without a difference to me. The jargon "existential" is not used, but I believe the user is intuitively linking it to the same concept as that of an existential type (which is nothing more than "some type Foo that impls Bar" in the context of Rust).

Re type Foo = _, it overloads _ with a completely unrelated meaning.

How so? type Foo = _; here aligns with the use of _ in other contexts where a type is expected.
It means "infer the real type", just as when you write .collect::<Vec<_>>().

It can also seem tricky to find in the documentation and/or Google.

Shouldn't be that difficult? "type alias underscore" should hopefully bring up the wanted result...?
Doesn't seem any different than searching for "type alias impl trait".

@iopq

This comment has been minimized.

Show comment
Hide comment
@iopq

iopq Jul 4, 2018

Google doesn't index special characters. If my StackOverflow question has an underscore in it, Google won't automatically index that for queries that contain the word underscore

iopq commented Jul 4, 2018

Google doesn't index special characters. If my StackOverflow question has an underscore in it, Google won't automatically index that for queries that contain the word underscore

@rkruppe

This comment has been minimized.

Show comment
Hide comment
@rkruppe

rkruppe Jul 4, 2018

Contributor

@Centril

How so? type Foo = _; here aligns with the use of _ in other contexts where a type is expected.
It means "infer the real type", just as when you write .collect::<Vec<_>>().

But this feature doesn't infer the type and give you a type alias for it, it creates an existential type which (outside of some limited scope like module or crate) doesn't unify with "the real type".

Contributor

rkruppe commented Jul 4, 2018

@Centril

How so? type Foo = _; here aligns with the use of _ in other contexts where a type is expected.
It means "infer the real type", just as when you write .collect::<Vec<_>>().

But this feature doesn't infer the type and give you a type alias for it, it creates an existential type which (outside of some limited scope like module or crate) doesn't unify with "the real type".

@varkor

This comment has been minimized.

Show comment
Hide comment
@varkor

varkor Jul 4, 2018

Contributor

Google doesn't index special characters.

This is no longer true (though possibly whitespace-dependent..?).

But this feature doesn't infer the type and give you a type alias for it, it creates an existential type which (outside of some limited scope like module or crate) doesn't unify with "the real type".

The suggested semantics of type Foo = _; is as an alternative to having an existential type alias, based entirely on inference. If that wasn't entirely clear, I'm going to follow up soon with something that should explain the intentions a bit better.

Contributor

varkor commented Jul 4, 2018

Google doesn't index special characters.

This is no longer true (though possibly whitespace-dependent..?).

But this feature doesn't infer the type and give you a type alias for it, it creates an existential type which (outside of some limited scope like module or crate) doesn't unify with "the real type".

The suggested semantics of type Foo = _; is as an alternative to having an existential type alias, based entirely on inference. If that wasn't entirely clear, I'm going to follow up soon with something that should explain the intentions a bit better.

@Centril

This comment has been minimized.

Show comment
Hide comment
@Centril

Centril Jul 4, 2018

Contributor

@iopq In addition to @varkor's note about recent changes, I'd also like to add that for other search engines, it is always possible that official documentation and such explicitly use the literal word "underscore" in conjunction with type such that it becomes searchable.

Contributor

Centril commented Jul 4, 2018

@iopq In addition to @varkor's note about recent changes, I'd also like to add that for other search engines, it is always possible that official documentation and such explicitly use the literal word "underscore" in conjunction with type such that it becomes searchable.

@iopq

This comment has been minimized.

Show comment
Hide comment
@iopq

iopq Jul 4, 2018

You still won't get good results with _ in your query, for whatever reason. If you search underscore, you get things with the word underscore in them. If you search _ you get everything that has an underscore, so I don't even know if it's relevant

iopq commented Jul 4, 2018

You still won't get good results with _ in your query, for whatever reason. If you search underscore, you get things with the word underscore in them. If you search _ you get everything that has an underscore, so I don't even know if it's relevant

@stjepang

This comment has been minimized.

Show comment
Hide comment
@stjepang

stjepang Jul 4, 2018

Contributor

@Centril

Picking let (which happens to not be referentially transparent inside fn) is an arbitrary choice that I don't think is particularly intuitive. I think the intuitive view of type aliases is that they are referentially transparent (even if that word is not used) because they are aliases.

Sorry, I still can't wrap my head around this because my intuition is completely backwards.

For example, if we have type Foo = Bar, my intuition says:
"We're declaring Foo, which becomes the same type as Bar."

Then, if we write type Foo = impl Bar, my intuition says:
"We're declaring Foo, which becomes a type that implements Bar."

If Foo is just a textual alias for impl Bar, then that'd be super unintuitive to me. I like thinking of this as textual vs semantic aliases.

So if Foo can be replaced with impl Bar anywhere it appears, that's a textual alias, to me most reminiscent of macros and metaprogramming. But if Foo was assigned a meaning at the point of declaration and can be used in multiple places with that original meaning (not contextual meaning!), that's a semantic alias.

Also, I fail to understand the motivation behind contextual existential types anyhow. Would they ever be useful, considering that trait aliases can achieve the exact same thing?

Perhaps I find referential transparency unintuitive because of my non-Haskell background, who knows... :) But in any case, it's definitely not the kind of behavior I'd expect in Rust.

Contributor

stjepang commented Jul 4, 2018

@Centril

Picking let (which happens to not be referentially transparent inside fn) is an arbitrary choice that I don't think is particularly intuitive. I think the intuitive view of type aliases is that they are referentially transparent (even if that word is not used) because they are aliases.

Sorry, I still can't wrap my head around this because my intuition is completely backwards.

For example, if we have type Foo = Bar, my intuition says:
"We're declaring Foo, which becomes the same type as Bar."

Then, if we write type Foo = impl Bar, my intuition says:
"We're declaring Foo, which becomes a type that implements Bar."

If Foo is just a textual alias for impl Bar, then that'd be super unintuitive to me. I like thinking of this as textual vs semantic aliases.

So if Foo can be replaced with impl Bar anywhere it appears, that's a textual alias, to me most reminiscent of macros and metaprogramming. But if Foo was assigned a meaning at the point of declaration and can be used in multiple places with that original meaning (not contextual meaning!), that's a semantic alias.

Also, I fail to understand the motivation behind contextual existential types anyhow. Would they ever be useful, considering that trait aliases can achieve the exact same thing?

Perhaps I find referential transparency unintuitive because of my non-Haskell background, who knows... :) But in any case, it's definitely not the kind of behavior I'd expect in Rust.

@rpjohnst

This comment has been minimized.

Show comment
Hide comment
@rpjohnst

rpjohnst Jul 4, 2018

Contributor

@Nemo157 @stjepang

If Foo were really a type alias for an existential type

(emphasis mine). I read that 'an' as 'a specific' which means f and g would not support different concrete return types, since they refer to the same existential type.

This is a misuse of the term "existential type," or at least a way that is at odds with @varkor's post. type Foo = impl Bar can appear to make Foo an alias for the type ∃ T. T: Trait- and if you substitute ∃ T. T: Trait everywhere you use Foo, even non-textually, you can get a different concrete type in each position.

The scoping of this ∃ T quantifier (expressed in your example as existential type _0) is the thing in question. It's tight like this in APIT- the caller can pass any value that satisfies ∃ T. T: Trait. But it's not in RPIT, and not in RFC 2071's existential type declarations, and not in your desugaring example- there, the quantifier is farther out, at the whole-function or whole-module level, and you deal with the same T everywhere.

Thus the ambiguity- we already have impl Trait placing its quantifier in different places depending on its position, so which one should we expect for type T = impl Trait? Some informal polls, as well as some after-the-fact-realizations by participants in the RFC 2071 thread, prove that it's not clear one way or the other.

This is why we want to move away from the interpretation of impl Trait as anything at all to do with existentials, and instead describe its semantics in terms of type inference. type T = _ does not have the same sort of ambiguity- there's still the surface-level "can't copy-paste the _ in place of T," but there's no longer "the single type that T is an alias of can mean multiple concrete types." (The opaque/doesn't-unify behavior is the thing @varkor is talking about following up on.)

Contributor

rpjohnst commented Jul 4, 2018

@Nemo157 @stjepang

If Foo were really a type alias for an existential type

(emphasis mine). I read that 'an' as 'a specific' which means f and g would not support different concrete return types, since they refer to the same existential type.

This is a misuse of the term "existential type," or at least a way that is at odds with @varkor's post. type Foo = impl Bar can appear to make Foo an alias for the type ∃ T. T: Trait- and if you substitute ∃ T. T: Trait everywhere you use Foo, even non-textually, you can get a different concrete type in each position.

The scoping of this ∃ T quantifier (expressed in your example as existential type _0) is the thing in question. It's tight like this in APIT- the caller can pass any value that satisfies ∃ T. T: Trait. But it's not in RPIT, and not in RFC 2071's existential type declarations, and not in your desugaring example- there, the quantifier is farther out, at the whole-function or whole-module level, and you deal with the same T everywhere.

Thus the ambiguity- we already have impl Trait placing its quantifier in different places depending on its position, so which one should we expect for type T = impl Trait? Some informal polls, as well as some after-the-fact-realizations by participants in the RFC 2071 thread, prove that it's not clear one way or the other.

This is why we want to move away from the interpretation of impl Trait as anything at all to do with existentials, and instead describe its semantics in terms of type inference. type T = _ does not have the same sort of ambiguity- there's still the surface-level "can't copy-paste the _ in place of T," but there's no longer "the single type that T is an alias of can mean multiple concrete types." (The opaque/doesn't-unify behavior is the thing @varkor is talking about following up on.)

@kennytm

This comment has been minimized.

Show comment
Hide comment
@kennytm

kennytm Jul 4, 2018

Member

referential transparency

Just because a type alias currently being compatible with referential transparency, doesn't mean people expect the feature to follow it.

As an example, the const item is referential transparent (mentioned in #34511 (comment)), and that actually caused confusion to new and old users (rust-lang-nursery/rust-clippy#1560).

So I think for a Rust programmer referential transparency isn't the first thing they would think of.

Member

kennytm commented Jul 4, 2018

referential transparency

Just because a type alias currently being compatible with referential transparency, doesn't mean people expect the feature to follow it.

As an example, the const item is referential transparent (mentioned in #34511 (comment)), and that actually caused confusion to new and old users (rust-lang-nursery/rust-clippy#1560).

So I think for a Rust programmer referential transparency isn't the first thing they would think of.

@Centril

This comment has been minimized.

Show comment
Hide comment
@Centril

Centril Jul 4, 2018

Contributor

@stjepang @kennytm I'm not saying that everyone will expect that type aliases with type Foo = impl Trait; will act in a referentially transparent manner. But I think a non-trivial amount of users will, as evidenced by confusions in this thread and elsewhere (what @rpjohnst is referring to...). This is a problem, but perhaps not an insurmountable one. It is something to keep in mind tho as we move forward.

My current thinking on what should be done in this matter has moved in line with @varkor and @rpjohnst.

Contributor

Centril commented Jul 4, 2018

@stjepang @kennytm I'm not saying that everyone will expect that type aliases with type Foo = impl Trait; will act in a referentially transparent manner. But I think a non-trivial amount of users will, as evidenced by confusions in this thread and elsewhere (what @rpjohnst is referring to...). This is a problem, but perhaps not an insurmountable one. It is something to keep in mind tho as we move forward.

My current thinking on what should be done in this matter has moved in line with @varkor and @rpjohnst.

@ExpHP

This comment has been minimized.

Show comment
Hide comment
@ExpHP

ExpHP Jul 4, 2018

Contributor

re: referential transparency

type Foo<T> = (T, T);

type Bar = Foo<impl Copy>;   // not equivalent to (impl Copy, impl Copy)

that is to say, even generating new types at every instance is not referentially transparent in the context of generic type aliases.

Contributor

ExpHP commented Jul 4, 2018

re: referential transparency

type Foo<T> = (T, T);

type Bar = Foo<impl Copy>;   // not equivalent to (impl Copy, impl Copy)

that is to say, even generating new types at every instance is not referentially transparent in the context of generic type aliases.

@alexreg

This comment has been minimized.

Show comment
Hide comment
@alexreg

alexreg Jul 4, 2018

Contributor

@Centril I raise my hand when it comes to expecting referential transparency for Foo in type Foo = impl Bar;. With type Foo: Bar = _; however, I would not expect referential transparency.

Contributor

alexreg commented Jul 4, 2018

@Centril I raise my hand when it comes to expecting referential transparency for Foo in type Foo = impl Bar;. With type Foo: Bar = _; however, I would not expect referential transparency.

@rpjohnst

This comment has been minimized.

Show comment
Hide comment
@rpjohnst

rpjohnst Jul 11, 2018

Contributor

It's also possible that we could extend return-position impl Trait to support multiple types, without any sort of enum impl Trait-like mechanism, by monomorphizing (pieces of) the caller. This strengthens the "impl Trait is always existential" interpretation, brings it closer in line with dyn Trait, and suggests an abstract type syntax that doesn't use impl Trait at all.

I wrote this up on internals here: https://internals.rust-lang.org/t/extending-impl-trait-to-allow-multiple-return-types/7921

Contributor

rpjohnst commented Jul 11, 2018

It's also possible that we could extend return-position impl Trait to support multiple types, without any sort of enum impl Trait-like mechanism, by monomorphizing (pieces of) the caller. This strengthens the "impl Trait is always existential" interpretation, brings it closer in line with dyn Trait, and suggests an abstract type syntax that doesn't use impl Trait at all.

I wrote this up on internals here: https://internals.rust-lang.org/t/extending-impl-trait-to-allow-multiple-return-types/7921

@nrc

This comment has been minimized.

Show comment
Hide comment
@nrc

nrc Jul 19, 2018

Member

Just a note for when we stabilise the new existential types - "existential" was always intended to be a temporary keyword (according to the RFC) and (IMO) is terrible. We must come up with something better before stabilising.

Member

nrc commented Jul 19, 2018

Just a note for when we stabilise the new existential types - "existential" was always intended to be a temporary keyword (according to the RFC) and (IMO) is terrible. We must come up with something better before stabilising.

@jan-hudec

This comment has been minimized.

Show comment
Hide comment
@jan-hudec

jan-hudec Jul 22, 2018

The talk about “existential” types does not seem to be clearing things. I would say that impl Trait stands for a specific, inferred type implementing Trait. Described that way, type Foo = impl Bar is clearly a specific, always the same, type—and that is also the only interpretation that is actually useful: so it can be used in other contexts besides the one from which it was inferred, like in structs.

In this sense, it would make sense to also write impl Trait as _ : Trait.

@rpjohnst,

It's also possible that we could extend return-position impl Trait to support multiple types

That would make it strictly less useful IMO. The point of aliases to impl types is that a function can be defined as returning impl Foo, but the specific type still propagated through the program in other structs and stuff. That would work if the compiler implicitly generated suitable enum, but not with monomorphisation.

The talk about “existential” types does not seem to be clearing things. I would say that impl Trait stands for a specific, inferred type implementing Trait. Described that way, type Foo = impl Bar is clearly a specific, always the same, type—and that is also the only interpretation that is actually useful: so it can be used in other contexts besides the one from which it was inferred, like in structs.

In this sense, it would make sense to also write impl Trait as _ : Trait.

@rpjohnst,

It's also possible that we could extend return-position impl Trait to support multiple types

That would make it strictly less useful IMO. The point of aliases to impl types is that a function can be defined as returning impl Foo, but the specific type still propagated through the program in other structs and stuff. That would work if the compiler implicitly generated suitable enum, but not with monomorphisation.

@rpjohnst

This comment has been minimized.

Show comment
Hide comment
@rpjohnst

rpjohnst Jul 22, 2018

Contributor

@jan-hudec Those ideas have come up in discussion on Discord, and there are some issues, primarily based around the fact that the current interpretation of return-position and argument-position impl Trait are inconsistent.

Making impl Trait stand for a specific inferred type is a good option, but for it to fix that inconsistency, it must be a different kind of type inference than Rust has today- it must infer polymorphic types so that it can preserve the current behavior of argument-position impl Trait. This is probably the most straightforward way to go, but it's not as simple as you say.

For example, once impl Trait means "use this new type of inference to find a polymorphic-as-possible type that implements Trait," type Foo = impl Bar starts to imply things about modules. The RFC 2071 rules around how to infer an abstract type say that all uses must independently infer the same type, but this polymorphic inference would at least imply that more is possible. And if we ever got parametrized modules (even just over lifetimes, a far more plausible idea), there would be questions around that interaction.

There's also the fact that some people will always interpret the type Foo = impl Bar syntax as an alias for an existential, regardless of whether they understand the word "existential" and regardless of how we teach it. So picking an alternative syntax, even if it happens to work out with the inference-based interpretation, is probably still a good idea.

Further, while the _: Trait syntax is actually what inspired the discussion around the inference-based interpretation in the first place, it does not do what we want. First, the inference implied by _ is not polymorphic, so that's a bad analogy to the rest of the language. Second, _ implies that the actual type is visible elsewhere, while impl Trait is specifically designed to hide the actual type.

Finally, the reason I wrote that monomorphization proposal was from the angle of finding another way to unify the meaning of argument and return-position impl Trait. And while yes, it does mean that -> impl Trait no longer guarantees a single concrete type, we don't currently have a way to take advantage of that anyway. And the proposed solutions are all annoying workarounds- extra boilerplate abstract type tricks, typeof, etc. Forcing everyone who wants to rely on single-type behavior to also name that single type via the abstract type syntax (whatever it may be) is arguably a benefit overall.

Contributor

rpjohnst commented Jul 22, 2018

@jan-hudec Those ideas have come up in discussion on Discord, and there are some issues, primarily based around the fact that the current interpretation of return-position and argument-position impl Trait are inconsistent.

Making impl Trait stand for a specific inferred type is a good option, but for it to fix that inconsistency, it must be a different kind of type inference than Rust has today- it must infer polymorphic types so that it can preserve the current behavior of argument-position impl Trait. This is probably the most straightforward way to go, but it's not as simple as you say.

For example, once impl Trait means "use this new type of inference to find a polymorphic-as-possible type that implements Trait," type Foo = impl Bar starts to imply things about modules. The RFC 2071 rules around how to infer an abstract type say that all uses must independently infer the same type, but this polymorphic inference would at least imply that more is possible. And if we ever got parametrized modules (even just over lifetimes, a far more plausible idea), there would be questions around that interaction.

There's also the fact that some people will always interpret the type Foo = impl Bar syntax as an alias for an existential, regardless of whether they understand the word "existential" and regardless of how we teach it. So picking an alternative syntax, even if it happens to work out with the inference-based interpretation, is probably still a good idea.

Further, while the _: Trait syntax is actually what inspired the discussion around the inference-based interpretation in the first place, it does not do what we want. First, the inference implied by _ is not polymorphic, so that's a bad analogy to the rest of the language. Second, _ implies that the actual type is visible elsewhere, while impl Trait is specifically designed to hide the actual type.

Finally, the reason I wrote that monomorphization proposal was from the angle of finding another way to unify the meaning of argument and return-position impl Trait. And while yes, it does mean that -> impl Trait no longer guarantees a single concrete type, we don't currently have a way to take advantage of that anyway. And the proposed solutions are all annoying workarounds- extra boilerplate abstract type tricks, typeof, etc. Forcing everyone who wants to rely on single-type behavior to also name that single type via the abstract type syntax (whatever it may be) is arguably a benefit overall.

@KodrAus

This comment has been minimized.

Show comment
Hide comment
@KodrAus

KodrAus Jul 23, 2018

Those ideas have come up in discussion on Discord, and there are some issues, primarily based around the fact that the current interpretation of return-position and argument-position impl Trait are inconsistent.

Personally, I don't find this inconsistency to be a problem in practice. The scope in which concrete types are determined for argument position vs return position vs type position seem to work out fairly intuitively.

KodrAus commented Jul 23, 2018

Those ideas have come up in discussion on Discord, and there are some issues, primarily based around the fact that the current interpretation of return-position and argument-position impl Trait are inconsistent.

Personally, I don't find this inconsistency to be a problem in practice. The scope in which concrete types are determined for argument position vs return position vs type position seem to work out fairly intuitively.

@iopq

This comment has been minimized.

Show comment
Hide comment
@iopq

iopq Jul 23, 2018

I have a function where the caller decides its return type. Of course, I can't use impl Trait there. It's not as intuitive as you imply until you understand the difference.

iopq commented Jul 23, 2018

I have a function where the caller decides its return type. Of course, I can't use impl Trait there. It's not as intuitive as you imply until you understand the difference.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment