An extensible Syntax for effects like e.g. async-await

See also this article: There Is No Thread. Just because you're using async/await doesn't mean you have multiple threads. The asynchronous thing you're waiting on may not use a thread at all.

1 Like

Thanks, I'll also shamelessly plug my article about event loops here, which is a part of a longer cycle about generators and coroutines. I don't think my pitches in those areas were successful, but it certainly was helpful for me personally to understand how crucial event loops are for concurrency, and how frequently multi-threading is conflated with concurrency (causing a lot of confusion that way).

There's a lot to cover since I last wrote something, but some things have already been addressed by others in this thread.

@QuinceyMorris this case, there has to be a wait of some kind and the wait cannot block the thread on which the code is running. A monad solution doesn't intrinsically satisfy that requirement, so you still need compiler magic (e.g. coroutines) to make this possible.

I agree insofar as I see the need to be able to de-sugar things. As I said in my original proposal:

Would calling throwing functions without try now be legal? After all, they would simply return a Result then. Under which circumstances should there be a compiler warning and when should it be fine? This is mostly a discussion about communicating the intended use, at the type level there is no problem.

The real question is how we prevent confusion. For example, if await f(a) outside an async function just returned the monad that has been used to implement async-await, the g(b) simply wouldn't compile for type reasons. But would everyone understand why that is? This is something that really needs some further discussion as the idea matures.

@sveinhal I see your point. However, what is the likelihood for programmers that want to get things done to over-use that feature? I mean, Java provides annotations and a rich reflection API (and in a restricted form, Swift does too now), but how many frameworks use that in a way that one could say these uses aren't justified? Sure, people are going to experiment with the new feature - as they have done with property wrappers. I would even encourage them to! But only few real use cases actually stick, and most of the time these are very much justified. From what I can see, the Swift community has been very responsible with new language features so far.

Your question regarding other keywords has been answered by @pthariensflame, I hope that helps.

@Max_Desiatov Sorry, I should have mentioned Haskell style do-notation and for comprehensions known from other languages. However, in these designs, all monads just get the same 'syntactic sugar'. Also, the do-model might fit the state monad or asynchronous monads, but is it a good fit for arrays for instance? Conversely, for comprehensions are great for async stuff and arrays, but how am I supposed to parse the reader monad with for comprehension?

The keyword-based variation that treats monads as effects is actually something that is currently actively explored, for example by the experimental Eff programming language, but there are also Scala frameworks. I personally like the approach because the keywords kind of tell you what is going on (if you read the documentation).

I agree though that I should have mentioned the other approaches. If this idea matures to the point that I make an official proposal (as far as I understand the intention of the Pitches section, this is more about testing the waters), I will put these in the 'alternatives considered' section.

Circling back to @adamkemp :

I'm honestly not sure what problem this proposal is trying to solve. My original question is "where is the code that actually controls the compiler transform, and how does this feature allow that to be extended?" I haven't seen an answer to that question so far. How does using monads solve any of the actual challenges with coroutines or async/await specifically? And if it doesn't solve those challenges then what does it solve?

Ok, let's try again.

My concern with the async-await feature that is sometimes requested is how it would fit into Swift from a syntactical point of view and when it comes to the way it is implemented. I mean, there were times when error handling wasn't a feature that was syntactically supported in most languages. Async-await is another feature that many languages adopted only way later. When people see these concepts, they often think that they were always around, but there really is a progression. Say, in 10 years we get another effect and in 20 years yet another one and say each of these features had their own syntax (like in Kotlin where async functions look very differently from throwing functions) and the poor people implementing the feature had to inject the new syntax and how it should be handled every time. That can lead to a lot of confusion for developers and a less clear language design.

What I propose is simply a general tool to write those effects. Obviously, each monad still has to be implemented - but injecting them into the language in a clear and readable way without long map and flatMap chains is then simple.

Note that I changed the title to 'An extensible Syntax for effects like e.g. async-await'. I haven't touched the specific challenges of async-await here much, other than delivering a oversimplified implementation of promises and referring to RxSwift. Since async-await is a feature that many people would want to see, I would like the new syntax feature to ship alongside async-await (and it can be implemented with monads, just like any effect) which would showcase the generality and simplicity of the monadic approach.

@all There's another monad that just came to my mind: randomness. In Haskell, all functions are pure - meaning that the same input always produces the same output. To express randomness, they have a monad that in essence provides some primitive operations to produce random results, but forcing you to tell users of that function that you do random stuff via the type system. In Swift, you can always do random stuff freely (just like you can do IO or asynchronous stuff using GCD or even manipulate references), but introducing a random monad and keywords like 'random/flip/rerandom' could cause people to consider freely doing random stuff a code smell. Just like the introduction of the IO monad and keywords like 'io/show/reIOs' could make free IO actions a code smell.

Speculation: I could actually even imagine splitting Haskell's IO monad in Swift into an Input monad and an Output monad. If you write a controller class and create a delegate protocol for that, you could then specify that delegate methods may only do outputs, not inputs, thereby promoting unidirectional data flow at the type level.

You still haven't connected the dots for me regarding how using monads actually helps in the implementation of async/await, though. As I've already covered, async/await cannot be implemented by just converting a function into a chain of calls so it really does require an AST-aware transformation of source code. What does the monad add to that? The best I can tell is that you only want to be able to use monads to enforce the rules about what can call what, but even then I'm not sure it applies to async/await (there must inherently be a root that is not async in the call chain of an async function).

The AST-aware transformation would apply to all monads that implement the syntactic sugar protocol. The question thus becomes: is it possible to implement async-await semantics with monads? If by async-await you understand something similar to what RxSwift (GitHub - ReactiveX/RxSwift: Reactive Programming in Swift) is doing, then the answer is definitely 'yes'. I am not sure what could be meant by async-await that cannot be expressed in a monadic way. Monads are a really powerful tool: flatMap and map can hand your continuations to almost arbitrary parts of your code that can almost arbitrarily decide what to do with them, the only requirement being that the sequential-looking code you write actually has sequential semantics.

Your point that

there must inherently be a root that is not async in the call chain of an async function

is, if I understand you correctly, probably related to my note that there needs to be some way to 'get back' the underlying monad, in the case of async-await in order to actually start async execution or in the case of the Result monad in order to handle errors. I admit that this is weakest point in my design so far - which is why I would love suggestions. Currently, my answer would be that if you call e.g. async functions inside non-async functions or you call them without the appropriate keyword, you would simply get back the monad (in case of the monad used for implementing async-await, you could then call some 'startExecution' function) and I admitted that this might be confusing and that it conflicts with the established language design around throws-try. Suggestions are very much welcome.

Thinking about the Eff programming language, it just crossed my mind that interaction with the monad itself could be achieved via do-throw-catch.

Effectively, do-throw-catch has two responsibilities: intervening in the control flow and turning monadic functions into normal ones. Do here’s a rough sketch of the idea:

Monads implementing the syntactic sugar protocol can declare multiple mutating „onThrow“ functions. These are no protocol requirements because it is unknown how many of these functions there will be - the design is more comparable to the @_functionbuilder design.

The signature of these functions is:

mutating func onThrow(thrown: A, continuation: @escaping (B) -> Void) -> C

where A, B and C are arbitrary types. The compiler will then allow the user of the monad to write code like

do{
let b : B = throw A(...)
}
catch c : C{
...
}

It is left to the implementing monad if the continuation is invoked or not. The continuation simply encapsulates the code below the throw statement. Since the implementation of onThrow is known, it should still be possible for the compiler to check if a throw statement means „don’t continue“ (i.e. the closure isn’t called and isn’t actually escaped) so guard statements with throw would still be legal in those cases. (One could also have two different keywords for disambiguation)

That way, you can further customize control flow and pass arbitrary information back and forth. The catch clause for the reader monad can pass back the environment if C is simply the continuation. One can introduce recoverable errors to the Result monad by passing appropriate continuations. It might even be possible to use this as a handy syntax for fully interpreted monads.

I don't really understand the functional aspects being discussed here, but I also don't understand the basis for the pitch. Every async/await proposal I've seen expects to be implemented via coroutines. Having some kind of meta-programming way to add keywords doesn't help the compiler rewrite code to create coroutines and continuations.

1 Like

Coroutines and continuations are high level concepts. Continuations are already a public part of Swift and coroutines can be emulated in any programming language. How exactly code with keywords would be transformed into code with coroutines/continuations is an entirely different discussion that would probably require some deep dive into the existing Swift compiler or at least preprocessing tools like Sourcery.

We definitely should have that discussion at some point if we are ever going to have the feature in the language, but I am not sure if we can say we already settled on semantics and/or syntax.

Edit: oops, I thought this was the other async/await thread.

That's not what we want. We want the compiler transforming code. We don't want to emulate it. If that were the goal, we'd have standardized on one of the competing implementations and not be continuously proposing it be added as a language feature.

I disagree. If you don't have even a theory for how it could work, this doesn't belong as a pitch. It's akin to asking us to consider some feature X, to be implemented by magic.

I am not suggesting that you must have an implementation. That's for the proposal phase. But I don't think it's worthwhile to discuss the introduction of a feature that cannot be implemented.

How does this get transformed into a simple chain of calls using monads?

func asyncThrowing() async throws -> Int {
...
}

func asyncCaller() async throws -> Int {
    var result = -1
    while result < 0 {
        let result = try await asyncThrowing()
    }
    return result
}

Take property wrappers as an example. They allow for developers to define new types that modify the behavior of properties. The compiler contains rules for how the rewriting will happen, and those rules are followed the same way for every usage of a wrapper.

To follow the same model for your extensible effects, you would need rules that the compiler can follow in every instance. If you have a different model in mind, you should propose it.

1 Like

Other languages have implemented it, so what should the problem be here?

All in all, it should be doable by some relatively simple automated code transformations - precisely because we can do this stuff on the high level. Note that a huge part of Swift is written in Swift itself, so there's no reason why not to use high level code. There is no need to go really low level.

The tricky bits come in when the information needed to run the continuation in the expected way leave the boundaries of a single scope. @adamkemp provided a great example where this can be hard: a while loop.

In @QuinceyMorris's pitch on async/await, I demonstrated an example how to resolve an if-clause and I speculated that while-clauses could be done with some recursive scheme, provided we find some compiler directive that ensures tail-call elimination.

Let me try:

func asyncCaller(base: Int = -1, continuation: @escaping (Int) -> Void) -> Int{
var result = base
if result < 0{
asyncThrowing{//also parsed into something with a continuation
result = $0
if result < 0{
asyncCaller(base: $0, continuation: continuation)
}
else{
continuation(result)
    }
  }
 }
else{
continuation(result)
}
}

Note that this is something I just made up right now. I do have to think about correctness and optimality for some time.

Edit: in an earlier version, I messed up the recursion. Not sure yet if it is correct, no time to think about it right now.

The standard library is written in Swift. The compiler is all C++.

Again, there are already libraries written in Swift to implement async/await. We know it can be done. What we want are the benefits of letting the compiler do the heavy lifting, so we can get optimizations.

1 Like

In fact, they have optimized the shit out of the standard library ;) Swift is really pretty high performance if you know what you are doing.

For a proposal, I guess a Swift implementation should be enough? Also, what do you think about above code example?

The point is that in order to do a transform like that you have to be aware of the AST. It's not a simple transformation into a chain of calls, and it can't be done in a way that's generic for any effect-like-thing. To implement async/await in general you need compiler support. You need code generation that's aware of the AST, and you need to be able to do things like hoist locals into fields of a synthesized object. This is the kind of stuff that the compiler does when you use a closure. You couldn't add closures to the language without compiler support, and you're not going to be able to add async/await without specific compiler support even if we had your proposed feature.

I also want to be pedantic here for a second:

You can't do "async/await" with libraries. You can do asynchronous programming with libraries, and there are plenty of options available. async/await is a syntax. It's inherently a language feature. You can make async/await interoperate with asynchronous programming libraries (like C# does), but you can't build async/await as just a library.

Similarly, C# had IEnumerable for a very long time before yield return came around. You couldn't build yield return as a library feature, though. It's a compiler feature that interoperates with an existing library feature. You could implement everything you can do with yield return without that language feature, but it was a huge pain to do so. The language feature made the code simpler and yet just as powerful as before.

That's what async/await does. It turns complex code into easier to understand code. If you try to write that simple throwing example with a while loop using callbacks it gets really complicated and hard to understand, and yet the async/await version is just as clear as the synchronous version would be and does the same thing. It's simpler and yet just as powerful. That's what we want, and we can't get it by just using monads.

1 Like

I'm not sure what more generality you could want (assuming that the above code transformation is correct now). Applying it to general monads is the easiest step.

So, I'll try again.

In general, if you have some function with an effect (indicated by the keyword you have to use), you would call flatMap:

func foo(_ x: X) arbitrary -> Y{
...
y = arbiTry bar(x)
...
}

is

func foo(_ x: X) -> Arbitrary<Y>{
bar(x).flatMap{localX in ...}
}

Any variable above flatMap that is needed below would have to be captured.

The problem you describe arises when the effect is thrown from some local scope, like some while clause:

func foo(_ x: X) -> Arbitrary<Y>{

while ... {

bar(x).flatMap[//indicates what the scope *should* be

}//ouch

]//flatMap only ends after while

}

As indicated above, one would have to re-write the while loop, possibly in a recursive way. Generalizing your above code example:

func foo(base: Int) -> Arbitrary<Int>{
var result = base

if result < 0{
arbitraryThrowing().flatMap{//needs to contain *all* branching logic of while
result = $0//could be optimized by just passing $0 to arbitraryCaller
return arbitraryCaller(base: result)//recursion instead of while loop
}
}
else{
return .pure(result)
}
}

I am sure if we discuss this long enough, we figure out the general rules for all possible code transformations. Swift doesn't have too many control flow statements, and they can partially be reduced to other control flow statements. I have no idea how to actually write code that does code transformation, however I think even I could figure out a correct set of rules to do that in a way that it can be actually implemented. I mean, other languages (Eff!) have done something very similar.

To reiterate: monads are nothing else than continuations with type-specific invocation semantics. Any code you could write to make async/await syntactically possible (and it really only is syntax, not semantics) just needs to be slightly generalized in order to make really arbitrary monadic effects possible - and then you have a huge extensible feature almost for free.

There is no inherent difference between what needs to be done to make your above code example work and making, e.g., the following work:

var result = -1
while result < 0{
result = log foo()//writer monad
}
return result 

or

var result = -1 
while result < 0{
result = read foo()//reader monad that injects implicit arguments to a function 
}
return result 

or

var result = -1
while result < 0{
result = maybe foo()//optional monad. enclosing function may or may not return a value, depending on the success of this call to foo
}
return result

or

var result = -1
while result < 1{
result = interpret foo() //Free monad that can be used to inject arbitrary semantics 
}
return result 

All of these have an obvious operational semantics that could be achieved by having the compiler rewrite that a little bit - but structurally in the same generic way.

Hello Markus,

First of all, please accept my apologies for bumping your topic after a week or so. I realise that much has happened in the intervening time with regard to your suggestion.

In any case, I found your post fascinating, and would like to let you know that it prompted me on to further reading. I was intrigued to learn more about this idea of 'Algebraic Effects', and some of the people who have been involved in its development and discussion over recent years are nothing less than luminaries in their field.

In particular, I have stumbled upon a pair of articles which discuss a generalised implementation of this idea, with the bold program of unifying notions such as exceptions, state resumption, iterators, domain specific effects and, yes, even asynchronous programming.

These papers provide a formal discussion, as well as an implementation example (in Koka).

I thought this may interest you, and wish you all the very best.

From Monads to Effects and Back
Niki Vazou and Daan Leijen:

Algebraic Effects for Functional Programming
Daan Leijen, 2016:

6 Likes

Ahhh, thanks! Koka was that other experimental language that I forgot about. I remember a rather enlightening talk about that topic on youtube, but I can't find it right now.

Maybe the YouTube video you mean is the one in this post from another thread?

1 Like

That does look familiar, thanks.

So, this thread started accumulating some sources that suggest that in principle, this whole thing might actually be possible. All that was really suggested here are a swifty syntax to create algebraic effects.

The questions really are: how desirable would such a feature be and how to move forward?

1 Like