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

A feature that is frequently requested in the broader community is async-await (e.g., https://gist.github.com/lattner/429b9070918248274f25b714dcfc7619). Personally, I would consider that a nightmare: a new feature with a distinct implementation and possibly entirely new syntax (e.g. putting 'async' in front of a function). So before that gains momentum, I wanted to bring up an idea how to unify throws-try, async-await and potentially many more in a way that it can even be customized.

The technology that everybody uses and that everybody is afraid of when someone names it is called 'monads'. To put it simply, monads are just a monoid in the category of endofunctors :stuck_out_tongue:

But hear me out. I promise I will actually keep it simple.

In many programming languages, a monad is implemented simply as a generic type with a few operators. First of all, there is 'map'. You may already have seen it in arrays, optionals, the generic result type or PromiseKit's promise. All it does is to transform a function

f : (A) -> B

to

map(f) : (F(A))-> F(B)

where F is the generic type. The important part here is that map should semantically preserve function composition:

map{f(g($0))}

should be the same as

map(g).map(f)

For instance, if you map over an array two times, you would expect the same result as if you had mapped over the composition of the two functions. Note that this is true only on a semantic level, mapping two times over an array will probably be slower.

The second function that a monad must have is flatMap. Say, our monad is a struct F. Then, flatMap has the form:

func flatMap<U>(transform: @escaping (Value) -> F<U>) -> F<U>

For instance, if you flatMap over an optional, the function that you flatMap can either return a value or nil. FlatMap will then take care of the unwrapping so you end up with Optional rather than Optional<Optional>.

In order to reason about flatMap, the order of evaluation of multiple chained flatMaps must be irrelevant. I'll explain later.

The third function that a monad must have is

static func pure(_ value: Value) -> Self

where Value is the generic type argument (or associated type if we think protocols). This should be a 'do nothing' operation. In other words:

monadicValue.flatMap(F.pure)

should (semantically) be exactly the same as

monadicValue

These rules seem arbitrary at first, but they are quite powerful. In fact, any effect you can think of can be safely wrapped into a monad. In Haskell, they even do IO with monads.

This last fact lead to the creation of a research topic called 'algebraic effects'. From all I can gather, this is just fancy syntactic sugar around things that are effectively monads. Which brings me back to async-await.

I propose

  1. a monad protocol (there are some difficulties here, see below).
  2. a 'syntactic sugar for monad' protocol inheriting from monad and defining something analogous to throws, try and rethrows (or async, await and reasync) for a monad.

Protocol 2 could look like this:

protocol Effect : Monad{
static var unbindKeyword : StaticString{get}
static var throwsKeyword : StaticString{get}
static var rethrowsKeyword : StaticString{get}
}

For this special protocol, an additional requirement enforced by the compiler would be that these StaticStrings can be used by at most one implementing type in the module.

Once you have a type implementing both protocols, the compiler should be able to generate from the given static strings new keywords that can appear in exactly the positions where throws, try and rethrows appear.

As a nice bonus, this would enable to switch back and forth between the two idioms

f : (A) -> Promise<B>

and

f : (A) async -> B

Here is how it would work. Say, you have the following definitions:


f : (A) async -> B
g : (B) async -> C

func h(a: A) async -> C{
let b = await f(a)
return await g(b)
}

Then, the compiler would simply transform this into:

f : (A) -> Promise<B>
g : (B) -> Promise<C>

func h(a: A) -> Promise<C>{
f(a).flatMap{b in g(b)}
}

The throws/rethrows mechanism would be implemented the following way: obviously, it is statically known if a closure actually produces an effect ('throws') or not; depending on that, the compiler inserts either a flatMap or simply a map. Simple!

This is a great point to clarify why it is important that the order of evaluation (not: execution) of flatMap should not matter. Say, you have the following code:

f : (A) throws -> B
g : (C) throws -> D
h : (B,D) throws -> E

func j(a: A, c: C) throws -> E{
let b = try f(a)
let d = try g(b)
return try h(b,d)
}

Obviously, you don't want that the result depends on wether you declare b first or d first.

There have been async-await proposals that even want something like 'throws async' - functions that can throw and will run asynchronously. Note that there is no obvious meaning to that, the order of keywords is relevant here. Result<Promise> is different from Promise<Result>. I personally don't like deep monad stacks precisely because of that reason, but if people want to toy with that, another protocol could enable that feature: monad transformers.

I just included the last paragraph for sake of completeness so everyone knows that there is no limitation here. If you are interested, you can read it up - there are even pseudo-swift articles about that.

This brings me to the hardest thing to implement: The monad protocol itself. Let's have another look at map and flatMap:

protocol Monad{

associatedtype Value 

static func pure(_ value: Value) -> Self //... works

func map<U>(transform: @escaping (Value) -> U) -> ??? 
func flatMap<U>(transform: @escaping (Value) -> ???) -> ???

}

The question marks indicate a problem here. You would want to write a Self there, but that isn't possible in Swift.

The ability to write that has been a long requested feature. Most of the time, people asked for so called higher kind types, but these are apparently difficult to harmonize with Swift's type system. I have seen a proposal that uses only a similarity relation, although I am not sure if this is any less invasive to the type system: https://gist.github.com/austinzheng/7cd427dd1a87efb1d94481015e5b3828

In any case, I hope the fact that I pitched monads from a practical point of view (consistency and extensibility of the 'effect system', in particular consistency between throw-try and a potential future async-await) sparks enough interest that we finally get this done.

Further intricacies are:

  1. Would it be reasonable to retrofit Result/throw/try to that approach? At the very least, I expect this effect to be as flexible as any other effect, but maybe this code transformation may yield less performant results than the current implementation (whatever that looks like).
  2. 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.
    So, what do you think?

Edit: If you are like me and jump to the latest answers after reading the pitch, I want to clarify how to actually implement async-await with the above approach.

Async-await is just syntactic sugar around Promises like in PromiseKit (https://github.com/mxcl/PromiseKit). To paraphrase and (brutally) oversimplify:

struct Promise<T>{

private let declaration : (@escaping (T) -> ()) -> Void //"produces" a T and calls the completion

init(declaration : @escaping (@escaping (T) -> ()) -> Void){...} //describes how to produce a T and call the completion

func call(_ handler: @escaping (T) -> ()){
declaration(handler) //actually produces a T and calls the completion that has been passed as a function argument 
}

static func pure(_ value: T) -> Promise<T>{
Promise{completion in completion(value)}
}

func map<U>(transform: @escaping (T) -> U) -> Promise<U>{
Promise<U>{completion in self.call{t in completion(transform(t))}}
}

func flatMap<U>(transform: @escaping (T) -> Promise<U>) -> Promise<U>{
Promise<U>{(completion : (U) -> Void) in
self.call{t in transform(t).call(completion)} //this is where the infamous pyramid of doom is safely hidden away from the eye of human readers 
}
}

}


What flatMap does is: it makes the promise produce a T and uses that T to produce a new promise that will then call the completion handler. So, if you make a network request to get some weather forecast, you can use flatMap in order to fetch the website of some online shop providing appropriate clothing and eventually, the completion block will be called. All automatically.

Production code would need to make sure that one can specify on which thread/queue the closures are executed. Also, there needs to be a mechanism to make sure that the completion handler is called exactly once - probably at runtime, as static analysis is complicated (at least on the monadic side; on the syntactic sugar side, it's easy).

In this design 'await' can only appear in functions that are async. Just like try can only appear in functions that throw. With try, there is the additional do-catch semantic that I haven't covered here. That's because I'm not sure how to best do this here. Most useful monads have some mechanism to produce 'pure' values, like reduce in Arrays or ?? in Optionals. Some languages implement a synchronous await function that actually waits for the result (rather than being syntactic sugar around inherently async code).

The issue here is not so much how to do it. The issue here would be to figure out syntax or a protocol that fits all monads imho.

Edit: The fact that the question comes up how to implement async-await with this approach is precisely why I wouldn't be too happy if there was just an async-await feature isolated from other possible effects. It misleads people to think this is some compiler magic, while in reality this is code that you and me could write - just enhanced with some syntactic sugar. Swift can and should do better and empower the community.

Edit Edit: I adjusted the title, because I want people to focus more on the extensible syntax part than on async-await that I only used as an example because it is a commonly requested feature. I am not an expert on async-await, but I think this would be an ideal candidate to showcase the proposed extensible syntax feature (assuming that implementing async-await is easier than settling for a syntax). And yes, probably I am using async-await as clickbait, but how else can I get you to read about the evil M-word from FP-land?

7 Likes

I'm confused. Say you had this feature in the compiler. How would you actually implement async/await with this feature? Where does the code that does the compiler transform for async/await live, and how exactly is it customized?

1 Like

Async-await is just syntactic sugar around Promises like in PromiseKit (https://github.com/mxcl/PromiseKit). To paraphrase and (brutally) oversimplify:

struct Promise<T>{

private let declaration : (@escaping (T) -> ()) -> Void //"produces" a T and calls the completion

init(declaration : @escaping (@escaping (T) -> ()) -> Void){...} //describes how to produce a T and call the completion

func call(_ handler: @escaping (T) -> ()){
declaration(handler) //actually produces a T and calls the completion that has been passed as a function argument 
}

static func pure(_ value: T) -> Promise<T>{
Promise{completion in completion(value)}
}

func map<U>(transform: @escaping (T) -> U) -> Promise<U>{
Promise<U>{completion in self.call{t in completion(transform(t))}}
}

func flatMap<U>(transform: @escaping (T) -> Promise<U>) -> Promise<U>{
Promise<U>{(completion : (U) -> Void) in
self.call{t in transform(t).call(completion)} //this is where the infamous pyramid of doom is safely hidden away from the eye of human readers 
}
}

}


What flatMap does is: it makes the promise produce a T and uses that T to produce a new promise that will then call the completion handler. So, if you make a network request to get some weather forecast, you can use flatMap in order to fetch the website of some online shop providing appropriate clothing and eventually, the completion block will be called. All automatically.

Obviously, in this design 'await' can only appear in functions that are async. Just like try can only appear in functions that throw. With try, there is the additional do-catch semantic that I haven't covered here. That's because I'm not sure how to best do this here. Most useful monads have some mechanism to produce 'pure' values, like reduce in Arrays or ?? in Optionals. Some languages implement a synchronous await function that actually waits for the result (rather than being syntactic sugar around inherently async code).

The issue here is not so much how to do it. The issue here would be to figure out syntax or a protocol that fits all monads imho.

Edit: Your question is precisely why I wouldn't be too happy if there was just an async-await feature isolated from other possible effects. It misleads people to think this is some compiler magic, while in reality this is code that you and me could write - just enhanced with some syntactic sugar.

Edit Edit: I put the important part of the answer into the original post, because apparently I confused people. Thanks for bringing that up.

1 Like

The thing you haven't said in this thread is: what is "await"?

[Hint: If await blocks the thread it runs on, you're solving the wrong problem.]

1 Like

await is whatever the implementing type (the monad) decides it to be. That’s the entire point.

2 Likes

The idea of using async/await is the complete opposite of building chains with map() and flatmap(). The main idea is to avoid using chains and minimize working with different wrappers like futures.

Moreover, async/await is not a syntactic sugar for futures. Most often it is implemented using coroutines. And in the case of combining futures and async/await, futures are wrappers over async/await but not vice versa.

While Apple has not yet added coroutines to Swift, you can use this library to try it - https://github.com/belozierov/SwiftCoroutine

2 Likes

Async-await is just syntactic sugar around Promises like in PromiseKit

No, it's not. It really is more complex than that. Async/await transforms a function into a coroutine, which requires creating a state machine, hoisting locals into fields on an object, etc. It's more similar to yield return, which is another coroutine feature Swift doesn't yet have.

Imagine a more complex case like this:

async func doSomething {
    var shouldContinue = true
    while (shouldContinue) {
        shouldContinue = await something();
    }
}

You can't simply transform that into a chain of promises. There are surely more complex cases than that, but the point is that async/await is much more than just a simple transformation into a chain of callbacks.

To get a better understanding of how it really works you should read an article like this explaining how the transform works in another language.

6 Likes

Well, I wouldn't say the idea is 'the complete opposite'. What the compiler does with promises and with coroutines can be very similar (depending on the particular implementation). In my proposal, map and flatMap only show up when you design a new effect. The new protocols would then allow people to transform map and flatMap to something more readable that can then be transformed back to monadic operations. Again: what the compiler eventually does with this (in the case of promises) can be effectively the same as with first class coroutines. I am open to any useful suggestions how to best implement the particular monad. My priority is to promote a consistent, extensible language design that invites you to look behind the scenes.

Well, it probably depends on the language then. There are languages (js I think?? not an expert) where async-await effectively is a promise and others where async-await really expresses coroutines. However, both can be expressed in a monadic fashion. Observables from rx are another example. Monads are the common denominator here - not only of asynchronous APIs, but of all kinds of effects.

The reason why I bring that up is not because I love monads (although of course I do), but because I want to promote a consistent language design without too much first class syntax clutter. Monads just do the job. Async-await is an obvious candidate (along with throw-try) that needs some kind of syntax. Why not combine the introduction (which I would encourage, people want it) with a simple public API for consistent 'syntax' creation? I definitely don't want Swift to look like Kotlin regarding effects.

1 Like

Time for another code example.

Say, we provide the Array monad the new syntactic sugar. That might look like that:

extension Array : Effect{
static var unbindKeyword = "iterate"
static var throwsKeyword = "enumerates"
static var rethrowsKeyword = "reenumerates"
}

func people(in city: City) enumerates -> Person{...}
func knownProgrammingLanguages(for person: Person) enumerates -> ProgrammingLanguage{...}
func keywords(in programmingLanguage) enumerates -> KeyWord{...}

func keyWordsOfLanguagesKnownByInhabitants(of city: City) -> KeyWord{
let person = iterate people(in city)
let lang = iterate knownProgrammingLanguages(for person)
return iterate keywords(in lang)
}

As you can see, we are expressing quite a complicated computation here. The variable 'person' is of type Person, but it stands for all people in the city. Hence, the code will actually run multiple times. The array 'effect' guides what the code actually does. It looks perfectly imperative, but the iterate keyword completely overrides and alters the normal control flow. That's the beauty of it.

You want to override control flow in a different way, for example to implement syntactic sugar for suspending, asynchronous state machines? You can do it! You want a keyword that automatically sets everything up according to some config file? You can do it using the reader monad! You want your functions to be logged and you want to be able to see that just from a keyword in the method signature? You can do it! There are even patterns out there to first name your effect, declare and even use some effectful functions that you need in your app and later inject an interpreter for that.

Edit:

Let me showcase the reader monad.

struct Reader<Env, T> : Effect{

private let read : (Env) -> T

static func pure(_ value: T) -> Self{
Reader{_ in value}
}

func map<U>(transform: @escaping (T) -> U) -> Reader<Env,U>{
Reader<Env,U>{env in transform(self.read(env))}
}

func flatMap<U>(transform: @escaping (T) -> Reader<Env,U>) -> Reader<Env,U>
Reader<Env,U>{env in transform(self.read(env)).read(env)}
}

func run(env: Env) -> T{read(env)}

static var unbindKeyword = „inject“
static var throwsKeyword = „dependent“
static var rethrowsKeyword = „injected“

}

...

func setUpAwesomeApp() dependent -> Bool where Env == MyConfig{ //where clause is necessary to bind the type variable Env; function could as well be generic over Env, if it only uses generic dependent functions; other syntaxes thinkable 

initialState = inject model()
view = inject loadView()
controller = inject createController(initialState, view)

}


All functions used in above function automatically have access to MyConfig. You would probably write some primitive functions in monadic Style to actually use MyConfig (or there could be additional syntax to grant access to monadic operations), but the seamless conversion I propose means that you can then use () -> Reader<Env, T> as () dependent -> T.

1 Like

Another example: Rx observables are monads. Say, they used the keywords "observe", "observable" and "streamed". You could then go ahead and write code like:

import RxSwift
import CoreMotion

extension CMMotionManager{

func accelerometer(active : () -> observable Bool) streamed -> (CMAccelerometerData?, Error?)

switch observe active(){

case false:
return Observables.empty() //not sure about the concrete syntax RxSwift uses, but you get the gist

case true:

return Observables.create{observer in 
self.startAccelerometerUpdates{data, error in 
observer.onNext(data, error)
}
return Disposables.create{
self.stopAccelerometerUpdates
}
}.shared()

}

}

My point being: Monads are really just an interface so you can describe arbitrary (!) invocation logic in a manner that you can think of it simply as an effect. Above code only runs when active() emits a new value - OR if you call the function with a pure () -> Bool (again: the "streamed" keyword indicates here, that the compiler looks at the given closure and decides wether to parse the code as flatMap or as map - or in this case, simply as a pure call to the function because there are no monads on the callstack so far). The returned observable will emit values whenever the accelerometer is active and emits a new value. In the reader example in my last answer, none of the code runs before you call run on the outermost Reader. The array code runs once for every value on the array. Optional code either runs or doesn't run, depending on whether you have a wrapped value.

Imagination really has no boundaries, and with a native syntactic support, the resulting code would become obvious and intuitive for many people who have no idea about monads.

I eventually found the explanation of await that my eyes slid over the first time (slightly edited here for brevity):

That's fine, except I think the word "simply" is … um … aspirational. In a slightly more complicated example:

func h(a: A) async -> C{
 let b = await f(a)
 let b1 = b + 1 // assume this makes sense
return await g(b1)
}

the transform is this:

func h(a: A) -> Promise<C>{
 f(a).flatMap{b in
  let b1 = b + 1
  g(b1) 
 }
}

Maybe that closure capture is "simple" for the compiler, but that's an argument you'd have to make.

However, there are two separate problems you haven't addressed.

The first is this:

func h(a: A) -> C{ // no `async`
 let b = await f(a)
return await g(b)
}

In 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.

The second problem is a requirement is that all of the code in function h has to run on the thread it started on and in the order it was written in source. If you break that requirement (by running some of the code on a completion handler thread, or on multiple threads), you introduce thread unsafety where no thread unsafety existed before.

It seems to me that you can solve the second problem with a considerably more complicated rewrite to the monad form, but the point is you're still depending on compiler behavior that is nothing to do with monads as such. And, you still don't have a solution to the first problem.

FWIW, AFAICT, of course.

1 Like

That example isn't allowed by the proposals so far on async/await. I don't know how every language does async/await, but I know it's not allowed in C# either. A function that uses await must be marked async.

4 Likes

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?

2 Likes

Well, that's why the C# design is broken. (I speak from sore experience.) I'm not prepared to accept a Swift design that doesn't solve this.

Our proposal says:

I don't see any technical reason why this restriction should exist.

Applying that logic, is JavaScript and Python design broken? Are there any languages with async/await that allow discarding async attribute from functions that use await in their body?

This restriction isn't technical, it's purely a type-checking constraint that allows providing a guarantee that there are no uncaught errors in code unless enforced by an explicit try! statement. Similarly, there's no technical restriction that disallows anyone passing Bool as an argument where Int is expected, but I don't think anyone ever seriously argued for Swift to become a dynamically typed language to lift that restriction. After all, you can use Any if you're so inclined (which is considered a code smell in a most codebases, as far as I'm aware).

Not sure if there ever would be a use case for a hypothetical await!, I'm not entirely sure what its semantic would be. Where an unhandled error with try! is equivalent to a fatal error, unhandled asynchrony with await! could lead to more obscure and hard to diagnose errors, e.g. completion callbacks not called.

2 Likes

Although I like the monadic approach in this proposal, I’m not sure I want all kinds of third party library provided monads to introduce their own keywords. I like the simplicity, elegance and generality of this approach, but I think it would quickly become unwieldy.

Do you have any other motivating examples of such keywords, apart from the iterating keyword (which I’m not sold on)?

1 Like

I totally agree with this.

I'm also not sure why an extensible do -notation has not been considered, similar to what Haskell, PureScript and Idris have already proved to be a practical approach. It doesn't require an introduction of new keywords, only an extension to the type system, namely higher-kinded types (HKT) to be able to express protocol Monad. I'm still convinced that HKT would be useful in its own right, while one could then build the extensible do-notation on top of that for any type that conforms to the Monad protocol.

4 Likes

I’ll note that I agree with you about the problems of proliferation of custom “keywords”, but for the sake of argument here are a couple of additional monads with natural enough “keyword” names:

  • Writer: log/logs/relogs
  • Free: wrap/builds/rebuilds
  • Omega: choose/distributes/redistributes
1 Like

JS async/await is built on generator functions, using yield in the way that @adamkemp mentioned

.

Terms of Service

Privacy Policy

Cookie Policy