Comment by lapinot | Hacker News Reader

Comment by lapinot | Hacker News Reader

And yet we somehow don't acknowledge the fact that this is just do-notation for some specific monad--yeah, that powerful abstraction that can't be expressed in Rust because we don't allow higher-order polymorphism. Don't get me wrong, i'm bitter because i feel like Rust really is almost in the right direction for the future of language design. Yet there is a long time before we get a language with a really precise type system (linear, "pure") and thus with highly efficient code generator (~rust), that at the same time has all the higher abstraction goodies, maybe even dependent types (cf quantitative type theory [1]). Of course they took that into account, it's even explicitly mentioned in the rfc, and it got turned down for being too experimental, but at some point you gotta make a bold step forward and force people to actually care about abstractions.

Now that Rust is getting some maturity i worry that it gets too complex in too much direction just because it's not powerful enough to express the few common abstraction, of which several instances are being added as distinct concepts (async&try, const datakind, higher-order poly--especially for lifetimes, named impls, before-after memory state for references...).

[1] https://bentnib.org/quantitative-type-theory.pdf

I don't have time to write a whole essay, so let me just establish my credentials:

- I wrote the generic associated types RFC (how Rust will implement higher kinded polymorphism).

- I wrote the const generics RFC (the closest Rust will get to dependent types).

- I wrote the async/await RFC, as well as the linked blog post.

That is to say that I am intimately familiar with how Rust's type system can be extended to support more "powerful" abstractions.

Monads as implemented in pure functional programming languages like Haskell cannot usefully abstract over asynchronous and synchronous IO in Rust for a variety of reasons having to do with the way the type system exposes low level details by virtue of Rust being a systems programming language. I do not believe that `do` notation could be a useful mechanism for achieving either the ergonomics or the performance that async/await syntax will have in Rust.

I'm responding to you because you're the top comment, but I could write a similar response to a lot of comments here. Monads, stackful coroutines, green threads, CSP, etc - we've heard of them! :) We have well-motivated reasons to choose async/await: its the only solution that meets our requirements.

Out of topic. Wow withoutboats you didn't have an account here before? Welcome! That's great to see you coming here and to see you giving many in-depth and very precise answers.

> Monads as implemented in pure functional programming languages like Haskell cannot usefully abstract over asynchronous and synchronous IO in Rust for a variety of reasons having to do with the way the type system exposes low level details by virtue of Rust being a systems programming language. I do not believe that `do` notation could be a useful mechanism for achieving either the ergonomics or the performance that async/await syntax will have in Rust.

Sorry, but I don't buy it. I had a half-baked, unfinished proposal for an effects system that would have allowed Rust to implement async/await just as efficiently (no stackful coroutines) along with any number of other effects [0]. Maybe it wouldn't have been a good idea due to stretching Rust's complexity budget too far, but that's very different from saying it's impossible. Having watched the development of Rust closely I really think that the design team just didn't understand the theory side well enough to be able explore the design space here. (I'm not being as critical as I might sound, PL theory is hard and the Rust devs have wielded it much more competently than the designers of any other non-research language).

[0] https://internals.rust-lang.org/t/start-of-an-effects-system...

The first part of your comment is unresponsive to mine; the last part is pretty rude & factually wrong (we are not motivated to implement an effect system right now; we understand the theory).

Sticking to the first part: an effect system is not what the user I was responded to was talking about. They were talking about building do notation on top of type classes with higher kinded polymorphism, which cannot effectively abstract over the monadic operations in Rust.

> The first part of your comment is unresponsive to mine;

I interpreted OP's comment as complaining about the lack of more general abstractions in Rust that would allow you to implement async/await. Your comment specifically mentioned Haskell-style monads (eg. a `Monad` trait), but that's not the only way to implement something like this.

> the last part is offensive & wrong

Quoting steveklabnik:

> it’s an open research problem if do notation can work in Rust. Until that’s solved at all, we’re just not sure it’s possible. ... "Open question" doesn't mean "impossible", mind you. But nobody has ever come up with a design. In the meantime, we have users to support...

Isn't this what I was saying? "We don't know how to do it, so we're going with the easier option."

Edit: To be clear, I don't think async/await we've ended up with is necessarily in the wrong direction. But I also don't think that "we thoroughly explored the design space of do/monads/effects and concluded that they were impossible to implement ergonomically/efficiently" is really true.

"impossible" is a highly contextual term here. Adding this to Rust isn't "impossible", of course it isn't. We can "just" slowly turn Rust into Haskell using the edition mechanism. Done.

When folks say something is "impossible" in such a context, they mean "given the constraints", which include goals the lang team has for the language. An effects system is pretty heavyweight and may violate these goals.

I think that there is not a definition of the Monad trait - not just undesirable, not possible - that can abstract over all Futures and Iterators as implemented in Rust. You would have to use some kind of trait object & lose the incredible inlining benefits that Rust gets from how these interfaces are designed today.

This is separate from effect systems, which I never said was not possible. rpjohnst's parallel response sums up the key differences between monads and an effect system.

A Rust-flavored effect system is quite a bit different from do-notation. You're probably right that such a thing could achieve the same ergonomics and efficiency as built-in async/await, but you're also probably right that it would be a huge amount of complexity.

When people say that monads and do-notation don't work in Rust, they're talking about a user-level Monad trait and a simple CPS transform built on top of it:

- Such a monad trait is impossible to write even with HKT because it would have to abstract over both Option/Result (type constructors) and Iterator/Future (traits)

- Such a CPS transform would be extremely limited (not composable with built-in loop structures) and/or extremely tricky around TCE, lifetimes, and allocation (the typical type for `>>=` would involve `Fn` trait objects...).

Effects bypass this by leaving the CPS transform in the compiler, instead only exposing delimited continuations to userspace. Which is basically what async/await does, just non-generically.

I'm scratching my head at the premise of this comment. The grandparent is positing that monads/do-notation would not be useful in Rust; this one appears to be trying to accuse it of saying that an effect system in Rust is impossible? Nowhere does withoutboats say anything about an effect system, or that anything is impossible. Did you reply to the wrong comment?

> Having watched the development of Rust closely I really think that the design team just didn't understand the theory side well enough to be able explore the design space here.

You might want to do a Google Scholar search on Niko Matsakis and Aaron Turon before making silly claims like this.

Didn't mean to bash the lang design team at all, actually i was kinda hoping for you folks to reply interesting and tricky stuff about how things are not so simple.

This is probably only because you didn't develop the answer fully but i still struggle to see how monads (or other structures in that family) couldn't apply here: they aren't implemented in any way and just provide interface (eg not caring about rust at all, the semantic of that feature here is very monadic, it should mostly behave like the CPS monad). Anyway, i'm gonna stop arguing, look at how it is/will be implemented and hopefully wait for that essay of yours, to have a broader picture.

Here are three problems:

Higher kinded polymorphism results in trivially undecidable type inferences without something like currying; the restrictions needed to support it would be arbitrary and weird given that Rust does not have currying (essentially some rules to reconstruct the restrictions of currying in type operator context).

Instances of both Future and Iterator do not implement the Monad type class as defined in Haskell, because the "fmap" operator does not return the "self" type parameterized by a new type, it returns it own new type. This is because the state machine they represent is leaked through their function signature.

Do notation doesn't work with the imperative control flow that Rust has, which other people have already discussed.

You don't need HKTs to implement 'do' notation. A good example is LINQ query syntax from C#! You actually have full blown monadic comprehension that you can use to easily write 'flattened' (ie, no async pyramid of doom) Future/Promise code with.

A better example would be computation expressions in F#, the async {} and query {} builders are super easy to work with and don't rely on HKT's to work (since there's no such thing in .Net). I think such a design would work pretty well in rust, and doesn't require adding a bunch of single-purpose keywords - something I wish the C#/.Net team did considering F# had async first.

async blocks require keyword in rust because it conflicts with a struct constructor.

F# works around this by having expression builders be normal types, `async` is just an alias for Control.AsyncBuilder (actually, it's an instance of it if I want to be technical), it's not even a reserved word in the language specification. This is why I feel such an implementation would be a great fit for Rust, the parser already has to figure out different contexts curly braces could be used (struct initializers, lexical scoping constructs, closures, the list goes on) - you can avoid adding an extra reserved keywords and get support for more than just async expressions.

Async is strictly more limited than the more generic LINQ comprehension syntax.

Actually in F# computation expressions are way more powerful, as they can define their own "keywords" within given semantics. This is for example, how `query{}` computation expression works - and unlike linq it can support things like left joins natively just because entire sql-like syntax is defined by library, not hardcoded into language. Same for async, yield generators etc.

Have you considered algebraic effects and handlers? If you add a linearity restriction on the return continuations (easily doable with the existing type system of Rust) their implementation is no harder than async/await, yet they can express many useful monadic abstractions.

...I saw this thread too late, hopefully you will still see this comment. I'm genuinely curious.

There's a sibling subthread about this. https://news.ycombinator.com/item?id=17538191

Supporting do notation or not isn’t some sort of position we’re taking as a language; it’s an open research problem if do notation can work in Rust. Until that’s solved at all, we’re just not sure it’s possible.

(Previous version of this comment said "HKT" but that's not purely right; we have a path forward for something at least HKT-like, but do notation is the bigger question.)

Yeah, sure, i understand that, hn comments just need to be a bit spicy (btw, any ref of papers or other stuff in that area? i didn't follow closely but didn't see too much moving, actually i don't even know what the big question marks are). Although i really believe it's not about if but how, so let's hope that when the time comes Rust will be able to take the tough changes necessary to unify the different branches that split off.

Like what is the real road-blocker, since we're talking here about abstractions that are gonna be monomorphised (at most into lifetime-polymorphic function, which anyway get erased) and known statically, right? Is it only a problem of getting the typing rules consistent and robust?

There's multiple issues. The biggest ones that I can recall, off the top of my head:

First off, do notation desugars to closures. But Rust has three different kinds of closures. How does that work?

Furthermore, Rust has imperative control structures. How does all of this interact with each other? Are you now no longer allowed to use those constructs inside of do notation? That feels inconsistent.

I don't know of any languages that have something like do notation but don't have everything boxed. It makes everything easier, but that's not generally acceptable in Rust. For example, we can use async/await with no dynamic allocation. Could we with do notation?

"Open question" doesn't mean "impossible", mind you. But nobody has ever come up with a design. In the meantime, we have users to support...

Thanks, that's interesting, i should dive a bit more into how async is implemented. On "which closure kind to choose" i feel like that's not the worst part (closure syntax already infers which trait to implement), but the fact that it is a closure and how it fares with allocation seems not trivial.

For the moment, you can see the progress on empowering the type system in the RFC for generic associated types, which is intended both to be the simplest extension to the type system that allows for some important patterns (e.g. streaming iterators and collection traits) and to be forward-compatible with any additional extensions in the direction of HKT. Importantly, it's also intended to be intuitive for users who have no prior experience with higher-kindedness and usable without (hopefully) requiring anyone to learn anything about type theory. The RFC text can be read at https://github.com/rust-lang/rfcs/blob/master/text/1598-gene... and comments can be left on the tracking issue at https://github.com/rust-lang/rust/issues/44265 .

Note also that HKT and do notation are their own separate things; you can have HKT without do notation. That's all HKT stuff, not do notation stuff.

If you have HKT then isn't do notation a piece of cake? It just desugars into monadic bind and return operators. Or is there something specific to rust that would mess with that?

Imperative control flow, for one. Think about how you would implement "break" that can break out of multiple nested loops in do-notation…

Please see my comment here: https://news.ycombinator.com/item?id=17537878

I thought I had read at some point that generic associated types we're equivalent to HKTs in terms of what they can express. Or maybe that they were theorized to be so. Is that not the case? (Not critical, just curious)

I have been doing programming, including functional programming for more than two decades, I still don't really know what a "monad" is. Each time someone explains it to me, I understand something different.

The way I accepted it after years of confusion, and without still understand the word: A monad is any type which supports 2 specific operations. One maps an type into it's monadic form, and the other allows to apply functions to monadic types and returns the monadic type again. The latter is sometimes called bind or flatmap.

For Future types, the first thing could be called MakeReadyFuture(type), the second one Future.then(result => functionWhichReturnsANewFuture).

... which allows a generic composition enabling imperative programming in a purely functional language. Haskell has do notation, that sugars the syntax to look like one is writing imperative code, even though it's all about composing Monads.

Monads are containers for which .map, and .flatMap (>>= in Haskell) make sense.

Future, Option, List, State/IO, etc.

And the do-notation that some comments mention become a long list of flatMap/filter/map invocations.

  do {
    futRecord <- getDBrecord(username, passw) 
    uid = futRecord.map(record -> record.id)
    username = futRecord.map(record -> record.name)
    futResult <- setUserLastLoggedIn(uid, now())
    futResult <- checkUserACL(uid, operation.roles)
  } yield username

This is just an abstraction, and it's not exactly a pretty one, but better than the flatMap hell in functional languages.

The do-notation uses the same monad throughout, in this example the Future one. The final yield is a map, the "<-" lines all represent a flatMap.

Finally, Monads are very much like Vector Spaces in Maths. You have Axioms for both, and if the object satisfies them, it's a Monad or Vector Space!

https://devth.com/2015/monad-laws-in-scala

https://en.wikipedia.org/wiki/Vector_space#Definition

I would remove "containers" from the first line. In my reading it is ANYTHING for which monad laws hold.

For better or worse, "container" is the most intuitive concept to use when trying to explain monads. Yes, there are monad instances that don't really fit the container model, but they're not important at first. Definining "monad" as a thing for which monad laws hold is exactly the sort of almost-tautological non-explanation that makes people roll their eyes at FP aficionados.

However, I agree that the important step in understanding monads as an abstraction is realizing how map and flatmap make sense for many things other than lists.

I guess flatMap is very misleading to newcommers. Probably simply calling it chaining, composition, or even "then" would help.

That's true, although it's better than "bind".

I like chaining, that's a good analogy.

I feel like, now that I have a certain level of intuitive understanding of what bind does, to me, the `>>=` symbol best represents what the operation does. It just looks like some kind of physical gadget that extracts a thing from a container, does something to it, and injects it into the next container. This is pretty ironic given Haskell's (somewhat deserved) reputation as impenetrable symbol soup. I don't know whether I'd endorse trying to use an intuitive mnemonic like this to explain monads to FP beginners.

I know a lot of symbols, but I still get irritated when I encounter a new one, and I can't search for it. (At least math got a nice list: https://en.wikipedia.org/wiki/List_of_mathematical_symbols )

For math it's kind of okay. Because there the point is to talk about that theory. You introduce definitions, and theorems, and use them in proofs. Or in calculations.

And even in math proofs usually come with a lot of explanation. (At least the better ones.)

In software engineering maintainability is important.

And, sure, we can just accept that Haskell is something that you can't learn by looking at real world Haskell code. After all, you can't really learn real world "research math" by looking at it.

But I think real world code, especially one that is looking for maintainers should not err on the side of indecipherability and inapproachability.

I continue to chastise Scalaz for its bad naming and documentation convention. (Haskell is ... well, it's irredeemable.)

And TypeScript is getting into this mess too. The documentation for new releases with new type system goodies (and I really mean it, I like powerful type systems, I just don't want to spend my life on understanding them, I'm happy to use them to get particular jobs done), but with barely enough documentation to let serious TS users with many years of experience understand it.

> Definining "monad" as a thing for which monad laws hold is exactly the sort of almost-tautological non-explanation that makes people roll their eyes at FP aficionados.

Thank-you for crystallizing and articulating a frustration I have often, as a beginner to intermediate Haskeller.

They have something in them (sometimes just a very fuzzy non-explicit state, maybe a seed for a RNG, but there's something there, otherwise it'd be just a value). Every monad is a [type] constructor, wrapping something.

Or could you show a counterexample please?

Several people found my blog entry on this enlightening: http://blog.reverberate.org/2015/08/monads-demystified.html

Just to add more different explanations, since that'll help.

http://blog.sigfpe.com/2006/08/you-could-have-invented-monad...

This one is my favourite, and does it well by example and walking through three different cases, then generalizing.

Reply on news.ycombinator.com