RFC: Consider supporting function return type deduction #10448

erickt · 2013-11-12T20:42:46Z

I had a brief chat on IRC today about adding support for deducing the function return type. I realize we decided against doing this a couple years ago, but I think it's worth revisiting in light of iterators. One of the challenges with our iterators is that the types of complex iterators are unwieldy. For example, here's the type of chaining two vecs together:

type T<'self> = std::iter::Chain<
    std::vec::VecIterator<'self, int>,
    std::vec::VecIterator<'self, int>
>;

fn main() {
    let x = [1,2,3];
    let y = [4,5,6];
    let iter: T = x.iter().chain(y.iter());
}

While we can generally rely on type inference inside a function, things get really messy once we try to return an iterator from a function. One way to avoid this complicated type is to box of the iterators inside a ~Iterator<int>, but according to @thestinger, this is ~1000x slower than with a monomorphized iterator. Having return type deduction would make it much easier to pass around iterators.

This would also be really handy for macros and syntax extensions. For example, we could convert the serialize.rs over to iterators without needing generators (#9145).

This has been proposed for (C++14)[http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3638.html].

@cmr had an argument against this. He felt that adding return type deduction would make it that much easier to break ABIs.

The text was updated successfully, but these errors were encountered:

thestinger · 2013-11-12T20:59:23Z

FWIW, it's only 1000x slower with a vector iterator and is more reasonable with something like an unbuffered line iterator

erickt · 2013-11-12T23:06:02Z

@huonw mentioned that typeof (#3228) could be used to address the complication of code generating a complex return type. Assuming that typeof used as the return type would have a method's self in scope, you could write:

struct Foo { x: ~[int] }

impl Foo {
    fn foo(&self) -> typeof(self.x.iter()) { self.x.iter() }
}

It would be uncomfortable enough for a human to write so it wouldn't get much use, but it'd be simple for a macro/syntax extension to duplicate the fn body into both the type and the actual fn body.

thestinger · 2013-11-12T23:19:51Z

C++11 added decltype, but C++14 is adding decltype(auto), in part to solve the issue of still not being able to return unboxed closures with decltype and to avoid needless repetition of the function body.

huonw · 2013-11-12T23:27:58Z

FWIW, Rust has nicer macros than C++, so it is possible to write something like

ret_type_infer!(fn foo(x: int, y: int) -> _ { <body> })

// expands to

fn foo(x: int, y: int) -> typeof({ <body> }) { <body> }

(For this, typeof would have to understand return.)

thestinger · 2013-11-12T23:30:11Z

It still wouldn't work for unboxed closures.

huonw · 2013-11-12T23:47:39Z

It could, in theory. If the type of an unboxed closure depended only on the AST/types (ignoring NodeIds) used to construct it (i.e. its body and its captures), so two equal pieces of code would give the same closure type.

(This is likely to be unreasonably complicated to achieve, of course.)

nikomatsakis · 2013-11-13T14:06:29Z

Adding typeof is in no way simpler than just inferring the return type in the first place. I agree that as types get more complicated, writing out the return type is sometimes unreasonable. There is no fundamental reason we cannot infer return types so long as the call graph in the file forms a DAG; it complicates type checking, in that the current two-phase structure no longer works. Rather, what we call collect and check must be intertwined. (We can even infer return types in the face of cycles in the call graph, but it gets more complicated, because we would need to use a single inference context for multiple fn items.) Still, it's not that hard. Future efforts to parallelize would get more complicated but also not impossible; something like futures models the problem fairly well.

emberian · 2013-11-13T15:31:45Z

OTOH, I wouldn't be opposed to ABI-breaking features if it wasn't allowed to mark them #[stable], and if there was a lint for using things which either make breaking ABI unnoticable .

pnkfelix · 2014-03-13T14:30:38Z

I suspect associated items could alleviate some of these cases, though probably not all of them.

E.g. instead of writing:

fn foo<'a>(v: &'a [int]) -> std::iter::Rev<std::vec::Items<'a, int>> {
    v.iter().rev()
}

(which require you have knowledge of the names of implementing structs within std::vec and also std::iter), with associated types you would instead write something like

fn foo<'a>(v: &'a [int]) -> std::vec::Slice<'a, int>::Iter::Rev {
    v.iter().rev()
}

and in practice since you'll be use'ing the types you're working with, that's likely to be just:

fn foo<'a>(v: &'a [int]) -> Slice<'a, int>::Iter::Rev {
    v.iter().rev()
}

Like I said at the outset, it doesn't handle all cases cleanly (e.g. the Chain example still looks bad I think), but it would enable a step forward in terms of making it easy to write these signatures without much thought. (And also write methods like foo in generic code since it does not need to encode the concrete iterator types.)

I actually suspect the ideal thing could be a hypothetical statically-resolved existential syntax like

fn foo<'a>(v: &'a [int]) -> <I:Iter> I {
    v.iter().rev()
}

that is the dual to the universal parameterization syntax that one sees with <I:Iter> on the left-hand side of the ->; in this case the compiler would enforce that clients of foo never used any methods on I except for those provided by the Iter interface, but the method dispatch would still be tied via monomorphization directly to the implementing methods provided by I itself, not dynamically dispatched the way you would see with a trait object like ~Iter. (It would still break ABI's, but at least you'd have some notion of source compatibility with the above interface.)

But no need to work on any of this until after 1.0 I think.

glaebhoerl · 2014-03-13T15:58:30Z

@pnkfelix That's #11455. :)

pnkfelix · 2014-03-13T21:19:27Z

@glaebhoerl ah, thanks for the link. I suppose my suggestion is indeed a kind of type-inference, though my mental model remains that of a statically-resolved existential (probably because I see the <I:Iter> as denoting either forall or exists depending on which side of the -> arrow it is on. In any case, I do find it interesting that none of the syntaxes on #11455 took the form of an existential with an explicitly bound name, which could be useful for doing constructions like:

fn bar<'a>(v: &'a [int]) -> <I:Iter> Option<I> { ... }

glaebhoerl · 2014-03-14T09:58:06Z

@pnkfelix The acid test here is:

fn f(n: int) -> Trait { ... }
let a = f(0);
let b = f(1);
swap(&mut a, &mut b);

Should we allow this? We know the result of f(n) can only ever be the same type, so we could allow it: in this case, it's better to think of it as inference. However, if we think of it as an existential, then we should assume that f(n) might branch on n and return different types for different inputs (even though, physically speaking, it cannot), and therefore we should reject the above.

I've actually come around to prefer the latter: this means that from outside f(), it will behave exactly like an unboxed trait object, which is good for intuition and consistency. It's also the forwards-compatible choice: we can make it more permissive later if we choose to without breaking anything, but not vice versa.

In any case, I do find it interesting that none of the syntaxes on #11455 took the form of an existential with an explicitly bound name, which could be useful for doing constructions like:
fn bar<'a>(v: &'a [int]) -> <I:Iter> Option<I> { ... }

This reads to me as a universal: forall I: Iter. Option<I>, not an existential. In Rust existentials are formed by omitting the name of a type and substituting the name of a trait. If we want to follow the analogy (and I think we should), then we should write simply Option<Iter>. (If, following the above, from outside of bar() the analogy Iter : &Iter :: T : &T is exact, then I think this "abuse of notation" is safe to introduce.)

Incidentally:

fn bar<'a>(v: &'a [int]) -> Option<Iter> { ... }

This happens to be incorrect as written, because information about the lifetime is lost in the result. Just as with boxed trait objects, you would have to write -> Option<Iter: 'a>.

pnkfelix · 2014-03-14T12:59:40Z

From the viewpoint of the caller of bar, I was intending something that denoted fn bar<'a>(v: &'a [int]) -> Exists (I : 'a + Iter) . Option<I>. I thought putting the <I:'a + Iter> on the right-side of the arrow as a way to denote this was cute, but if it is confusing, then obviously we would need to find another syntax.

Anyway, you are correct, my example did not illustrate an instance where one would need explicit binding of an actual name. One needs binding if one wants to use the same existentially-bound type variable multiple times in the type expression, like in the following, which returns a tuple where both Iters must actually be the same type:

fn bar<'a>(v: &'a [int]) -> Exists (I : 'a + Iter) . (I, I)

(Is it useful? I don't know yet. I suppose the implicit point of your message is that our existing syntax for existential types a la trait objects does not let one express something like the above, and therefore it is unlikely to be of use.)

glaebhoerl · 2014-03-14T14:39:15Z

I think my implicit point was that explicit existential syntax, while potentially useful, is orthogonal to this feature.

dobkeratops · 2014-04-10T13:08:22Z

tangential comment,having perhaps -> _ could help IDE autocomplete: where you're trying to compile incomplete code, the 'dot-completion' workflow is generally forward inference where you dig into a datastructure exploring it with each call. I realise the arguments against whole program inference, perhaps you could have this restricted to 'inline' or 'private' functions if you're concerned about that, and of course the IDE issue of trying to compile incomplete code where the return type doesn't yet match up could be solved with compiler flags specific to that case.

aturon · 2014-06-03T23:15:37Z

I've written a formal RFC: rust-lang/rfcs#105

thestinger · 2014-09-19T03:39:17Z

Keeping around an issue here isn't necessary because this isn't backwards incompatible or actionable. A proposal needs to be accepted through the RFC process.

Add new `redundant_async_block` lint Fixes rust-lang#10444 changelog: [`redundant_async_block`]: new lint to detect `async { future.await }`

erickt mentioned this issue Mar 12, 2014

Added support for partial type hints (Foo<_>). #12764

Merged

thestinger closed this as completed Sep 19, 2014

eternaleye mentioned this issue May 8, 2016

Minimal impl Trait rust-lang/rfcs#1522

Merged

traviscross mentioned this issue Apr 2, 2023

TAIT defining scope options #107645

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

RFC: Consider supporting function return type deduction #10448

RFC: Consider supporting function return type deduction #10448

erickt commented Nov 12, 2013

thestinger commented Nov 12, 2013

erickt commented Nov 12, 2013

thestinger commented Nov 12, 2013

huonw commented Nov 12, 2013

thestinger commented Nov 12, 2013

huonw commented Nov 12, 2013

nikomatsakis commented Nov 13, 2013

emberian commented Nov 13, 2013

pnkfelix commented Mar 13, 2014

glaebhoerl commented Mar 13, 2014

pnkfelix commented Mar 13, 2014

glaebhoerl commented Mar 14, 2014

pnkfelix commented Mar 14, 2014

glaebhoerl commented Mar 14, 2014

dobkeratops commented Apr 10, 2014

aturon commented Jun 3, 2014

thestinger commented Sep 19, 2014

RFC: Consider supporting function return type deduction #10448

RFC: Consider supporting function return type deduction #10448

Comments

erickt commented Nov 12, 2013

thestinger commented Nov 12, 2013

erickt commented Nov 12, 2013

thestinger commented Nov 12, 2013

huonw commented Nov 12, 2013

thestinger commented Nov 12, 2013

huonw commented Nov 12, 2013

nikomatsakis commented Nov 13, 2013

emberian commented Nov 13, 2013

pnkfelix commented Mar 13, 2014

glaebhoerl commented Mar 13, 2014

pnkfelix commented Mar 13, 2014

glaebhoerl commented Mar 14, 2014

pnkfelix commented Mar 14, 2014

glaebhoerl commented Mar 14, 2014

dobkeratops commented Apr 10, 2014

aturon commented Jun 3, 2014

thestinger commented Sep 19, 2014