Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow loops to return values other than () #961

Closed
pnkfelix opened this issue Mar 10, 2015 · 157 comments
Labels

Comments

@pnkfelix
Copy link
Member

@pnkfelix pnkfelix commented Mar 10, 2015

Extend for, loop, and while loops to allow them to return values other than ():

  • add an optional else clause that is evaluated if the loop ended without using break;
  • add an optional expression parameter to break expressions to break out of a loop with a value.

Proposed in #352

Some discussion of future-proofing is available in #955

@JelteF

This comment has been minimized.

Copy link

@JelteF JelteF commented Jan 23, 2016

I'm just starting with rust, but why would loops not just return their last statement like everything else seems to do, functions, if, match?

break statements could be treated like early returns and accept an expression parameter. The same could be done for continue statements, its argument would only be used when the loop exits afterwards.

The else clause is not even needed when implemented like this.

@ticki

This comment has been minimized.

Copy link
Contributor

@ticki ticki commented Jan 24, 2016

@JelteF the problem is that a loop without a return or break statement will never return, for that reason you cannot end your loop on an expression.

@withoutboats

This comment has been minimized.

Copy link
Contributor

@withoutboats withoutboats commented Jan 25, 2016

@ticki for and while loops do return without a break, and could evaluate to the value on last iteration of the final expression in their block.

@ticki

This comment has been minimized.

Copy link
Contributor

@ticki ticki commented Jan 25, 2016

@withoutboats Yeah, that's right. for and while could definitely return a value! But loop cannot, without being able to specify a return value to the break statement.

@KalitaAlexey

This comment has been minimized.

Copy link

@KalitaAlexey KalitaAlexey commented Jan 25, 2016

You want to make loops return value of last expression? You want to make it implicit without any break?
What if I want to break the while and return value? Do you suggest me to use code like

let mut done = false;
while (!done)
{
    let value = get_value();
    done = value.is_valid();
    value
}

I think this is ugly.
We need else block because loop may end before it started when a condition true from start.

@pnkfelix

This comment has been minimized.

Copy link
Member Author

@pnkfelix pnkfelix commented Jan 25, 2016

Update: never mind the note below (which is preserved just so the responses that follow continue to make sense).

  • The reason that the note is irrelevant is that we currently have rules in the type checker ensuring that if a loop-body ends with a expression, that expression must have type ().
  • (This, I think, will ensure that no existing code will introduce temporaries that need to outlive the loop body itself, unless I am wrong about how the temporary r-value extents are assigned in such a case...)

@JelteF another reason to not just use the last expression in the loop-form's body as its return value is that it would be a breaking change: loop-form bodies today are allowed to end with an expression that is evaluated and then discarded.

Returning the last expression implicitly would change the dynamic extent of the returned value, which in turn would change the lifetime associated with it and its r-value temporaries. And that change would probably inject borrowck errors into existing stable code.

(The alternative of solely using break and else for the return value would be, I think, entirely backwards compatible...)

@JelteF

This comment has been minimized.

Copy link

@JelteF JelteF commented Jan 25, 2016

@ticki You might have misunderstood. I only said we did not need the else block but the break and continue statements are obviously needed for early loop exits.

@KalitaAlexey I did suggest code like that, but the break could still be used. It is a very good point that you are making though. I had not thought about the case that the loop would never be evaluated. It seems you are right that the else block is needed in cases where the loop body is never executed, so there is no way to return from it.

@pnkfelix I'm not sure what the breaking change is, since the check for the type of the return value could simply be skipped in cases where it is not saved in a value.

@nagisa

This comment has been minimized.

Copy link
Contributor

@nagisa nagisa commented Jan 25, 2016

add an optional else clause that is evaluated if the loop ended without using break;

Please, no. Python has this, and every time I encountered it I had to jump into REPL and see when this else thing would get evaluated: on or in absence of break.

I’m not that opposed to being able to “return” something from the loop with a break, but necessity of adding a else-ish thing makes this a no-brainer minus one million to me.

@golddranks

This comment has been minimized.

Copy link

@golddranks golddranks commented Jan 25, 2016

I think that an else block is strictly more expressive than returning the final expression and only thing that makes sense in the presence of value-returning breaks. If the value of final expression is going to be returned, why should the evaluation of the last run of the loop be any different from any other run? And are the final expressions (given that there is no side effects) evaluated for nothing on all the other runs? Optimizing them off becomes then burden on the compiler.

If the value-returning break isn't hit, then there needs to be an alternative path that returns a value of the same type. It doesn't have to be named "else", but I think that's a sensible name.

@erikjohnston

This comment has been minimized.

Copy link

@erikjohnston erikjohnston commented Jan 25, 2016

@nagisa

Please, no. Python has this, and every time I encountered it I had to jump into REPL and see when this else thing would get evaluated: on or in absence of break.

This bites me every time too, mainly because while useful its a rarely used feature. Maybe a better/more accurate name would help? (Nothing immediately springs to mind though.)

Or perhaps something slightly different, like having a default expression instead? e.g.:

for x in iterator {
  if foo(x) {
    break "yes!";
  }
} default {
  "awww :("
}

Where the default expression is evaluated either if iterator is empty or foo(x) is false for all x in iterator.

@JelteF

This comment has been minimized.

Copy link

@JelteF JelteF commented Jan 25, 2016

@erikjohnston @nagisa

I agree that the else is always confusing when seeing it. I do think it will be less of a problem when break returns a value, which it doesn't do in Python. But the case still exists when else would be used like in python when the value is not saved in anything and the break might be empty.

I think another name would indeed be good. Something that comes to my mind would simply be nobreak. It's short and describes quite clearly what it is for.

PS. I retract my initial proposal about using the last statement instead of the else block, because of the good arguments against it.

@glaebhoerl

This comment has been minimized.

Copy link
Contributor

@glaebhoerl glaebhoerl commented Jan 25, 2016

FWIW I think the best way to move forward on this, incrementally, would be to start by only allowing break EXPR inside of loops, and to not touch any of the other looping constructs for now. That sidesteps all the other tricky design questions we've been spinning in circles around.

@JelteF

This comment has been minimized.

Copy link

@JelteF JelteF commented Jan 25, 2016

@glaebhoerl
I doubt that's a good way to go about it. It will only encourage people to "hack" a for or a while loop inside a loop loop. I've not heard any argument against using the else statement except for its name.

@arielb1

This comment has been minimized.

Copy link
Contributor

@arielb1 arielb1 commented Jan 25, 2016

This can kind-of be already done as

{
    let _RET;
    for x in iter {
        if pred(x) {
            _RET = x;
            break;
        }
    }
    _RET
}
@Ericson2314

This comment has been minimized.

Copy link
Contributor

@Ericson2314 Ericson2314 commented Jan 25, 2016

Yet again, @glaebhoerl says exactly what I was going to say :). Somebody want to make an RFC for this, I'd be willing to help?

@JelteF heh, that's kinda the point! Once people see how nice this is, there will be more motivation to actually reach a consensus on break-with-value for other types of loops (and maybe even normal blocks!).

@JelteF

This comment has been minimized.

Copy link

@JelteF JelteF commented Jan 25, 2016

@arielb1 Of course it can be done, but the point is that this:

let a = for x in 1..4 {
    if x == 2 {
        break x
    }
} nobreak {
    0
}

looks much cleaner than this:

let a = {
    let mut _ret = 0;
    for x in 1..4 {
        if x == 2 {
            _ret = x;
            break;
        }
    }
    _ret
}

@Ericson2314 It seems that if the only consensus that needs to be reached is the naming, it could be solved rather quickly. It would be weird to hurry an incomplete proposal, if all that needs to be done is pick a name for a statement.

@Ericson2314

This comment has been minimized.

Copy link
Contributor

@Ericson2314 Ericson2314 commented Jan 25, 2016

@JelteF Well I'll grant you that originally there were more ideas, but because #955 did not happen else { } is the last one that makes sense. On the other hand, there are a few more small details than just the keyword. E.g. should this work?

<some loop> {
    ...
    break; // as opposed to break (); 
    ...
} else {
    my_fun() // returns ()
};

@nagisa Anyone playing around will notice that the type checker will require break .. and else { .. }` to have the same type. IMO that will help make clear the behavior, no manuals needed.

@JelteF

This comment has been minimized.

Copy link

@JelteF JelteF commented Jan 25, 2016

@Ericson2314 I don't see a reason why that should not work. In Python it is not an expression and it still has a use. Namely handeling the edge case when the loop does not break. A simple example can be found here: https://shahriar.svbtle.com/pythons-else-clause-in-loops#but-why
Copy pasted:

for x in data:
    if meets_condition(x):
        break
else:
    # raise error or do additional processing 

vs

condition_is_met = False
for x in data:
    if meets_condition(x):
        condition_is_met = True

if not condition_is_met:
    # raise error or do additional processing

As for your comment @nagisa. In this case it might not be directly clear what the else does, which is why I think another name would still be clearer.

@nagisa

This comment has been minimized.

Copy link
Contributor

@nagisa nagisa commented Jan 25, 2016

I passionately hate the idea itself of having an else keyword associated to a loop in any way, @Ericson2314. It simply makes no sense and I intensely highly doubt one can prove it otherwise. Thinking about it, it might make some sense if the else block was executed when 0 iterations of the loop are executed, actually, but that’s overall an useless construct.

I don’t want to see any of that weirdness in Rust just because Python has it. One might argue for a new keyword, but that’s ain’t happening either, because of backwards compatibility.

EDIT: All looping constructs have trivial desugarings into a plain old loop, @glaebhoerl, so there’s no necessity to do any of the “only allow x in y” dance, I think.

@glaebhoerl

This comment has been minimized.

Copy link
Contributor

@glaebhoerl glaebhoerl commented Jan 25, 2016

@nagisa Sure, but the desugarings of while and for into loops contain breaks, ones which don't return a value (said differently: return ()) -- so if you want to break with a value elsewhere in the loop you have a type mismatch. This is precisely what the else clause would be for: in effect it's doing nothing else but providing the value argument to the implicit break embedded in the while/for constructs.

@JelteF

This comment has been minimized.

Copy link

@JelteF JelteF commented Jan 25, 2016

@nagisa
if new keywords are a problem, maybe something like !break could be used. Which I guess is currently invalid syntax.

@Ericson2314

This comment has been minimized.

Copy link
Contributor

@Ericson2314 Ericson2314 commented Jan 25, 2016

@nagisa Personally, it reminds me of the base case of a fold, and thus actually feels quite elegant.

@golddranks

This comment has been minimized.

Copy link

@golddranks golddranks commented Jan 26, 2016

@nagisa If all looping constructs desugar into loop, we can use value-returning break without problems with loop, but with for, the types don't unify because there is more than one way to return from to loop: either break or then just looping 'till the end, which produces currently (). That's why we need some kind of "default" return value in the case a break isn't hit. Is it just the keyword else you are detesting, or the concept of having default return value by itself?

I just came to think of another possibility for for loop: the for loop could return an Option<T>. This way, we could write

let result = for i in haystack_iter {
    if i == needle {
        break "Found!";
    }
}.unwrap_or("Not found :(");

This is nice in the sense that it doesn't need any new keywords or reusing old keywords in surprising way.

@KalitaAlexey

This comment has been minimized.

Copy link

@KalitaAlexey KalitaAlexey commented Jan 26, 2016

@golddranks But that's confusing. It is like functional programming but ugly.

@golddranks

This comment has been minimized.

Copy link

@golddranks golddranks commented Jan 26, 2016

Another note: sometimes I've written a loop that is expected to set some outer state inside the loop. But because setting the state (in that particulal case was) may be expensive, you might want to avoid setting a "default" state before running the loop.

But this results in the fact that the control flow analysis can't be sure if the state is set in the end, since it's possible that the loop runs 0 times. I have to make a boolean flag to check, and even then, if the analysis isn't super smart, it won't be sure. Having a default/nobreak (whatever the name is going to be) code block would help the flow analysis in these kinds of situations. EDIT: of course for that to be of any help, there should be a piece of information available whether the loop terminated without running even once, or if it terminated because it iterated until the end.

@taralx

This comment has been minimized.

Copy link

@taralx taralx commented Mar 31, 2017

@fstirlitz Making the type of for-without-break anything other than () is a breaking change.

Making everything coerce into () restricts the type system in subtle and difficult-to-fix ways. If you want the nitty-gritty I recommend Stephen Dolan's paper on Algebraic Subtyping.

@le-jzr

This comment has been minimized.

Copy link

@le-jzr le-jzr commented Mar 31, 2017

@fstirlitz

This comment has been minimized.

Copy link

@fstirlitz fstirlitz commented Mar 31, 2017

I don't understand what is so supposedly 'horrid' about making a unit type into a terminal object in the diagram of possible type casts. It's mathematically sound. The RFC defining the ! type makes it coercible into anything (making it an initial object), and the sky is hardly falling. I don't see many people complaining that C is broken for making casts into (void) possible.

@glaebhoerl

This comment has been minimized.

Copy link
Contributor

@glaebhoerl glaebhoerl commented Mar 31, 2017

I agree, it would be perfectly sound theoretically to allow any type to coerce into (): after all, it's just the same thing as manually writing let foo: () = { bar; }. I can't think of anything type-system-restricting or mathematically horrid about it. Not everything that's theoretically sound is prudent, however, and it seems like this would be error-prone in practice. Consider fn do_thing() { ... code ... return false; ... code ... }. We could turn that false into a () implicitly to match the return type of the function, but it's quite possible that this would end up masking a bug.

(It's an interesting question why this kind of error-proneness seems to be the case for coercing into (), but not for coercing out of !, given that the two are, as far as I can tell, duals.)

@le-jzr

This comment has been minimized.

Copy link

@le-jzr le-jzr commented Mar 31, 2017

! is naturally coercible into anything because it has no values. Every value of ! is also a value of any other type. In order for () to be a supertype of everything (and a dual of !), it would need to contain ALL the values representible in Rust. In other words, traditional intuition is that when something coerces, there is no loss of information about the value. This clearly doesn't hold here.

@le-jzr

This comment has been minimized.

Copy link

@le-jzr le-jzr commented Mar 31, 2017

I don't see many people complaining that C is broken for making casts into (void) possible.

C is broken in so many more important ways that casts into (void) are hardly worth mentioning.

@withoutboats

This comment has been minimized.

Copy link
Contributor

@withoutboats withoutboats commented Mar 31, 2017

(It's an interesting question why this kind of error-proneness seems to be the case for coercing into (), but not for coercing out of !, given that the two are, as far as I can tell, duals.)

They're not duals; coercing into () loses enormous amounts of information; coercing from ! only loses information about what code is unreachable.

@le-jzr

This comment has been minimized.

Copy link

@le-jzr le-jzr commented Mar 31, 2017

They're not duals; coercing into () loses enormous amounts of information; coercing from ! only loses information about what code is unreachable.

That's not it either. To coerce a value at runtime, you need to have the value, and ! type encodes the fact that the value cannot exist. ! can coerce to anything simply because no path of execution can ever reach the coercion at run time -- it's dead code. You can't lose information in a process that doesn't happen.

@ubsan

This comment has been minimized.

Copy link
Contributor

@ubsan ubsan commented Apr 1, 2017

(tired so may not be the best explanation)

The reason that they're duals is that () is the top type. From all types, it's possible to get a () (the ; operator). ! is the bottom type; from !, it's possible to get any type (coercions).

In other words, () is the result of affine-style weakening; you take an arbitrary T, and lose all information. ! is weakening run in reverse; you take no information, and create an arbitrary T out of thin air.

fn weaken<T>(t: T) -> () {
  t;
}

fn reverse_weaken<T>(bot: !) -> T {
  bot
}

(thanks to @eternaleye for help with phrasing)

@le-jzr

This comment has been minimized.

Copy link

@le-jzr le-jzr commented Apr 1, 2017

() is not the top type. It's the type that has a single empty value (), i.e. a zero-sized type. Perhaps you are confused by the Rust semicolon, which (explicitly) throws away the value in front of it and returns ().

On the flipside, coercing from ! (which as you correctly said IS the bottom type) does not create anything out of thin air. It takes the value that was there, and returns it as another type, just like any other coercion. The specific of ! is simply that it's the empty set (this is very different from zero-sized types like ()!), so the value will never exist. In your example, reverse_weaken is impossible to invoke at runtime.

A top type, however, is a type that can hold any value. Note that a true top type cannot exist in Rust, because of value semantics and lack of automatic boxing -- values in Rust can have arbitrary static length, and a top type would need to represent them all, so no amount of memory would suffice for a single value of the top type.

@le-jzr

This comment has been minimized.

Copy link

@le-jzr le-jzr commented Apr 1, 2017

While many people here make arguments out of misunderstandings about the type system, this does not mean the original proposal is without merit. Let's stop talking about breaking the type system and focus on the original problem instead?

@dhardy

This comment has been minimized.

Copy link
Contributor

@dhardy dhardy commented Apr 1, 2017

No, () never was the top type. Perhaps what you're thinking of is Any (Scala, Boost, also in Rust's std library)?

() is the unit type, a bit like C's void. Thus fn f(...) -> () {...} is the same as fn f(...) {...}. But not at all like void* which is (possibly) a value with undefined type. void* is more like Any, except Any actually has some guarantees whereas void* doesn't.

As for @fstirlitz's suggestion of allowing any type to be implicitly convertible to (), there have already been several arguments against that and I agree with them (it would be a major change to the type system, significantly reduce type safety and might have other consequences).

As for solving break-with-value from for and while, I still haven't seen a great solution (maybe a couple of "okay" ones involving extra syntax).

@burdges

This comment has been minimized.

Copy link

@burdges burdges commented Apr 1, 2017

If folks still really want these, then we might consider adding a variant of any with a result :

fn any_map<B, F>(self, f: F) -> Option<B> where F: FnMut(Self::Item) -> Option<B> { .. }

And/or a short circuiting fold method :

fn fold_while<B, F>(self, init: B, f: F) -> B where F: FnMut(B, Self::Item) -> Result<B,B> { .. }

At least these treat the borrowing problem that makes for/while .. else .. unworkable by consolidating the borrows into F.

@ubsan

This comment has been minimized.

Copy link
Contributor

@ubsan ubsan commented Apr 1, 2017

@le-jzr I feel like you misunderstand basic type theory. I am not talking about the Python or Java interpretation of types.

The wikipedia article mentions it wrt propositional calculus:

The notion of top is also found in propositional calculus, corresponding to a formula which is true in every possible interpretation.

Just because my comment uses a phrasing you are not used to, does not make my point invalid. In classical type theory, there is no "top type" as used by the GC languages, because there's no way to construct such a type.

Please don't assume I don't understand. It makes me very cranky.

@comex

This comment has been minimized.

Copy link

@comex comex commented Apr 1, 2017

@ubsan But by that interpretation, any type that corresponds to a formula that is true - that is, any inhabited type - should be a top type.

In other words, you can also implement:

fn weaken<T>(t: T) -> i32 {
  4
}

You could argue that this doesn't merely throw away information but also adds it - because this weaken is not surjective - although that gets away from the types-as-propositions interpretation. But then, what about, say, enums with a single variant, or Option<!>, or other types that are homomorphic to ()? Should they allow coercion from anything? (I guess you haven't specifically advocated for coercion, but my point is that they're just as eligible to be 'top types'.)

@Ixrec

This comment has been minimized.

Copy link
Contributor

@Ixrec Ixrec commented Apr 1, 2017

Regardless of how () and ! should behave, and whatever "top type" does or doesn't mean, allowing for loops to return a value seems like a really weak argument for making a change as fundamental and far-reaching as enabling casting any type into ().

@ubsan

This comment has been minimized.

Copy link
Contributor

@ubsan ubsan commented Apr 1, 2017

@comex On the Option<!> front:

Option<!> is equivalent to 1+0, which is isomorphic to 1: it has exactly one value (left ()), equivalent to 1, which has exactly one value (()).

i32 is not isomorphic to 1. Given bit := 1 + 1, byte := bit x bit x bit x bit x bit x bit x bit x bit, and i32 := byte x byte x byte x byte; there are ~4 billion valid values, unlike 1, which has one valid value.

For more information theory, I recommend Roshan James' "The computational content of isomorphisms".

Otoh, I don't want coercions to (); just pointing out that ! and () are duals.

@comex

This comment has been minimized.

Copy link

@comex comex commented Apr 2, 2017

@ubsan I said "homomorphic" when I meant "isomorphic", but otherwise, yes, I know.

Actually, I'm not sure I disagree with you at all.

But my point was:

  • i32, while not isomorphic to (), has an equal claim to being "top" when considered as a proposition. Propositions can only be true or false, corresponding to inhabited or uninhabited; both i32 and () are inhabited base types. The only difference in this sense is that T -> () is built into Rust as the ; operator, while if you want T -> i32 you have to write it yourself.
  • If you add the requirement that a type must have exactly one possible value to count as top-like, then () is a candidate, but so are types isomorphic to it such as Option<!>. This is where I may have misunderstood your argument. I agree that () could be viewed as dual to !; I just don't think it's necessarily desirable for the language to view it that way, such as by enabling anything-to-() coercion, or in any other respect. In other words, () is just another type that happens to be top-like; it's not the canonical top-like type.

(I say "top-like" rather than "top" because of course it's not actually a supertype of anything; Rust doesn't have much true subtyping.)

@dhardy

This comment has been minimized.

Copy link
Contributor

@dhardy dhardy commented Apr 2, 2017

I'm not sure that "top-like" matters very much, but the homomorphisms do (and I mean homomorphism: a bijective map which in some sense preserves operations/meaning).

@ubsan I assume you mean Option<!> and () are duals. ! and () certainly aren't (() has one value, ! has none).

Duals in the sense that they have the same number of values? Yes, but only if Option::<!>::None is actually constructible (currently it isn't).

Duals in the sense that there exists an isomorphism between the type () and Option<!>, or even just a homomorphism (one-way)? That requires an understanding that the value () and Option::<T>::None are somehow equivalent, e.g. that both are "none".

I am not averse to such concepts being explored and potentially even being accepted, but I don't think here is the place.

I also don't think it would solve this problem: if Option<!> is homomorphic to () with an implicit conversion allowed (so that fn f() { for x in vec![] {} } is valid when for x in vec![] {} has type Option<!>), then the natural implication is surely that Option::<T>::None is implicitly convertible to () for all T via the same homomorphism? Actually, no, because a homomorphism from Option<T> to a tuple would presumably map Some(x) to (x), but this is not type-sound ((x) and () being different types).

I am not so happy defining a homomorphism from Option<!> to () as a special case, though I suppose it could work (it is however rather awkward and a surprising thing for new users to learn).

@ubsan

This comment has been minimized.

Copy link
Contributor

@ubsan ubsan commented Apr 2, 2017

@dhardy no, duals does not mean isomorphic, it means "(of a theorem, expression, etc.) related to another by the interchange of particular pairs of terms". i.e., forall T, T -> U or forall T, U -> T, where the first U is 1, and the second is 0.

@comex the important thing is that, given referential transparency, there is exactly one implementation of forall T, T -> 1, which is why it's the top type. No matter what type T is, it's impossible to output anything but exactly one value, ().

@le-jzr

This comment has been minimized.

Copy link

@le-jzr le-jzr commented Apr 2, 2017

@ubsan Your arguments are entirely invalid, and I don't know how to explain why any more than I already did. My best guess is that you consider "top" to mean something entirely different than the intended meaning in context of type theory. As for "dual", I can't even guess what formalism you are coming from, as the concept of duality means essentially a completely different thing in each corner of mathematics it's used. That does not implicitly make the definition invalid (after all, same or similar names are used in many contexts for different things), but it does make it irrelevant in this context.

Furthermore, fact remains that Rust does not include any way to convert a value from any type to (). All rust has is the ; operator which discards value on the left and produces (). In fact, by your logic, any zero-sized type would have to be considered a "top type", since for any zero-sized type (also called singleton types in some contexts), "there is exactly one implementation of forall T, T -> 1". Does that mean everything should implicitly coerce into any zero-sized type? Certainly not! That would completely break numerous type safety idioms.

So while we can go back and forth arguing what a top type is, that conversation is meaningless. It was suggested that "() is a top type" implies that "it doesn't hurt the language to implicitly coerce to ()". However, that implication derives from the definition of top type as "type that can hold any possible value without loss". It certainly doesn't hold for a singleton type, even if you lawyer it into "top" by using a different definition.

@canndrew

This comment has been minimized.

Copy link
Contributor

@canndrew canndrew commented Apr 7, 2017

Your arguments are entirely invalid, and I don't know how to explain why any more than I already did. My best guess is that you consider "top" to mean something entirely different than the intended meaning in context of type theory.

Huh? @ubsan is using "top" the way it's always used in type theory. The top type is the type which can hold values of any other type. () can do this, but you can't access the information once you convert into it. Categorically, the top type is the type for which there's exactly one function T -> () for any given T. ``i32is inhabited but that doesn't make it the top type,Option<!>` is also the top type because it's isomorphic to `()` but it's not Rust's canonical incarnation of the top type. Note that though, in some sense, Rust doesn't really have a top type because expressions can diverge and cause side-effect

As for "dual", I can't even guess what formalism you are coming from, as the concept of duality means essentially a completely different thing in each corner of mathematics it's used. That does not implicitly make the definition invalid (after all, same or similar names are used in many contexts for different things), but it does make it irrelevant in this context.

Given that we're talking about type theory I'd assume that @ubsan means dual in the category-theoretic sense, in which case ! and () are duals as the initial and terminal objects of the category of Rust types.

Furthermore, fact remains that Rust does not include any way to convert a value from any type to (). All rust has is the ; operator which discards value on the left and produces ().

What's the difference between "convert" and "discard"?

In fact, by your logic, any zero-sized type would have to be considered a "top type", since for any zero-sized type (also called singleton types in some contexts), "there is exactly one implementation of forall T, T -> 1".

Correct. They would all be considered the top type if we had subtyping and put them at the top of the type hierarchy.

Does that mean everything should implicitly coerce into any zero-sized type? Certainly not! That would completely break numerous type safety idioms.

Like what? I'm not saying it's a good idea from a language-design point of view, but it's type-theoretically sound.

So while we can go back and forth arguing what a top type is, that conversation is meaningless. It was suggested that "() is a top type" implies that "it doesn't hurt the language to implicitly coerce to ()". However, that implication derives from the definition of top type as "type that can hold any possible value without loss".

No it doesn't. It doesn't hurt the language to implicitly coerce to () because it loses all information when you coerce any value - since there's only one way to be in a state of no information there's no ambiguity about what the coercion means. This coercion satisfies congruence in the sense that if you want to calculate 2 + 3 as a () you can either perform the calculation with ints then convert to (), or convert the ints to ()s then perform the computation on them, and you'll get the same () either way. If you're worried about reversing the coercion and getting the information back out, you can't do this with variants either (not in a type-safe way at least).

It certainly doesn't hold for a singleton type, even if you lawyer it into "top" by using a different definition.

From the Wikipedia article on the top type:

In languages with a structural type system, the top type is the empty structure.

ie. (). If you strictly enforce type-safety and don't have downcasting (which is unsound), then this is equivalent to Variant because a Variant can never be used type-safely and so effectively contains no information.

@dhardy

This comment has been minimized.

Copy link
Contributor

@dhardy dhardy commented Apr 7, 2017

@canndrew are you advocating @fstirlitz's proposal or just defending @ubsan's logic?

I doesn't appear to me that everyone agrees a value-less type (like /dev/null) or Singleton is a top type, but allowing that, the arguments (roughly) make sense.

But I end with the same point as my last post: I am not so happy allowing an implicit conversion from Option<!> to () as a special case, though I suppose it could work (it is however rather awkward and a surprising thing for new users to learn).

@le-jzr

This comment has been minimized.

Copy link

@le-jzr le-jzr commented Apr 7, 2017

I replied in https://internals.rust-lang.org/t/on-type-systems-and-nature-of-the-top-type/5053.
Let's move the conversation there, it doesn't belong here any more.

@withoutboats

This comment has been minimized.

Copy link
Contributor

@withoutboats withoutboats commented Apr 8, 2017

Per #1767 I'm closing this issue. We now support loops to evaluate to non-() values, but we've decided that none of the solutions to making for and while evaluate to other values have small enough downsides to implement. else confuses users, !break is a very surprising syntax, and making them evaluate to Option<T> is a breaking change.

We're open to revisiting this some day if conditions change a lot. For example, possible now that break value is on stable, we'll find out we are frequently transforming for loops into loops to acess this feature. Maybe if we are close to finalizing a generator/coroutine proposal, the calculus on this will change.

@orent

This comment has been minimized.

Copy link

@orent orent commented Apr 20, 2017

In case this ever gets revisited, how about combining @glaebhoerl's idea of moving the break into the block and using the 'final' keyword as proposed by @canndrew:

... } final { break value }

I would find the meaning obvious enough reading this code even if I was not familiar with the feature (something I can't say about python's for/else).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.