Without boats, dreams dry up

The problem of effects in Rust

In a previous post, I shortly discussed the concept of “effects” and the parallels between them. In an unrelated post since then, Yosh Wuyts writes about the problem of trying to write fallible code inside of an iterator adapter that doesn’t support it. In a previous discussion, the users of the Rust Internals forum hotly discuss the notion of closures which would maintain the so-called “Tennant’s Correspondence Principle” - that is, closures which support breaking to scopes outside of the closure, inside of the function they are in (you can think of this is closures capturing their control flow environment in addition to capturing variables).

I think it may not be obvious, but these discussions are all deeply related. They all arise from what is, in my opinion, one of the biggest problems with the design of the Rust language: its failure at 1.0 to give good support for handling common effects related to program control flow.

What is an effect?

The term “effect” in this context comes from the notion of an effect system, a category of type system extensions developed to help users manage side effects. Rust has an excellent system for managing effects related to mutation and memory: this is what ownership and borrowing is all about, and it beautifully guarantees soundness even in the presence of concurrent mutation. Rust’s solution to this problem is genius, and it’s why Rust is a truly remarkable language, and not merely a useful advance on the state of the industry (I say this having had no part in this development, giving credit to earlier contributors to Rust and the theorists working on other projects whose ideas those contributors built upon).

But Rust at 1.0 provided no native facility for managing effects related to control flow. In particular, three “control flow effects” have emerged as common in Rust programs, for which programming patterns, and some amount of syntax, have been introduced. Indeed, these three effects show up in most programs in most languages:

  • Falliblity: The effect of a section of code failing to complete and evaluate to its expected value (in Rust, think Result)
  • Multiplicity: The effect of a section of code being evaluated multiple times, yielding many values or operating over many values (in Rust, think Iterator)
  • Asynchrony: The effect of a section of code yielding control when it cannot immediately progress, to allow other sections of code to progress instead (in Rust, think Future)

At 1.0 we had some syntactic support for multiplicity through loops, and we have since gained some support for fallibility (through ?) and for asynchrony (through async/await). Though the development history of all these items is distinct, we have entered into a pattern of developing library-based abstractions for these features and then promoting syntactic sugars for the effectful points of these operations.

This is what that section of my previous blog post discussed. But I want to reiterate for the purpose of this post that control flow effects involve three conceptual “hooks” or “effect points”:

  • The point where the effect is introduced (throwing an error, yielding control, yielding a value)
  • The point where the effect is forwarded (forwarding an error, awaiting a future, forwarding a yield)
  • The point where the effect is captured (catching an error, blocking on a future, processing a yielded value)

This allows the user to write their logic independent of its effectfulness, identifying (or not, depending on the language) each point at which an effect passes through the program, and then processing the effectful component of that code in a particular location in the program dedicated to that purpose. Essentially every industry language has, in some form, faculties for this purpose.

What are the common ways to handle effects?

I want to briefly talk about the dreaded Monad. A monad is a way to abstract a control-flow effect, so that users write a series of pure functions sequences between the effect points of their program. So instead of writing a section of code which contains effect points embedded in it, monads allow users to write a series of pure functions strung together across those effect points. Monads have other properties, in particular their relation to a branch of math called category theory, which many programmers have found useful. But experience has shown that monads are also quite a challenging concept for users to understand in many cases.

Most languages do not use monads to manage control flow effects. Instead, they have built-in facilities for these patterns of control flow, like Rust does, which allow users to abstract those control flow operations away from their particular domain logic. In some cases, these facilities are completely implicit at one or more sort of effect point, usually the “forwarding” point - think greenthreads (which provide asynchrony with no demarkation of yielding control) and unchecked exceptions (which provide fallibility with no demarkation of forwarding an error).

Rust has fallen into this latter camp, but with some interesting quirks:

  1. Rust’s expression-oriented type system has, inevitably, resulted in the reification of these patterns into a monadish type (e.g. Option, Result, Iterator, Future). Though Rust does not use monadic abstraction as its central thesis, it does provide a limited analog to the fmap operator on all of these types.
  2. Rust’s design philosophy has landed on the principle that all effect points should be marked in the program source, including forwarding, so that users can more easily reason about the control flow of their program.

However - and this is where the link to fallible iterator adapters and TCP-preserving closures comes in - Rust’s design failed to consider carefully the integration between its control flow effects and its support for higher order functions.

Effects and higher order functions

Both of the quirks I listed above imply that the type signature of an effectful function is different from the type signature of a noneffectful function:

  • By virtue of the reification of effects, a function with an effect will return the effect type, abstracted over its logical return type, rather than simply its logical return type.
  • It is exactly this reification that makes it trivial to check that all forwarding points are properly marked, because the forwarding marker is an operator which transformed the reification into its interior type (e.g. ? transforms Result<T, E> into T).

However, this integrates quitely poorly with higher order functions, which must define the type singature of the functions they take as arguments. In consequence, a higher order function cannot support both effectful and non-effectful operations. Thus we see, in some cases, the proliferation of try_foo and async_foo variations on foo adapters. In Yosh’s blog post mentioned above, he basically advocates for adding more try_ adapters to the Iterator trait to support the fallible effect in these cases. (I’m not interested in touching on whether that should be done, just identifying the connection between the motivation and this design problem.)

There are two ways that I know of to resolve this problem.

The first is to integrate some kind of abstract “effect system” into the language, so that a higher-order function can be abstract over the effects of its argument, as a first-class type variable. All types could be abstract over effects, so for example the Iterator::filter adapter would be abstract over effect, and return Filter iterator that would be abstract over effects, until ultimately the consumer (e.g. Iterator::all) would evaluate to a value enclosed by the effect (so all would return bool if was over an iterator parameterized by the null effect, and Result<bool, E> if it were over an iterator parameterized by the fallible effect).

The other way to resolve the problem is, precisely, closures which preserve the Tenant’s Correspondence Principle for all control flow effects. Such closures would necessarily be distinctly marked from closures which do not have that property, but they would essentially allow transparent forwarding within closure functions to their surrounding control flow environment. In such closures, return, ?, await, and so on capture the control flow of their surrounding scope, just as all closures can capture the variables of their surrounding scope. This property has been used to great effect in some languages, of which Kotlin is the most successful statically typed example I’m aware of.

To give a better taste of the idea, these sorts of closures are sometimes proposed to be demarkated by sitting outside of the function arguments (as they do in Kotlin), like this for example:

collection.iter().filter() do |elem| {
    // the `?` here returns early from the function this
    // expression is contained in:
    elem.get_foo_bar()? == bar
}

This has the advantage of making these control flow preserving closures look more like most other blocks in the same control flow scope, by putting them outside of the parens.

In the abstract, I think this is the most promising system for integrating effects with higher order functions, but I think it is would run into pretty serious obstacles for Rust. For example, I don’t know how to integrate this property with external iterators, like Rust uses - I believe that internal iteration would be necessary. However, I want to add that implementing the first-class effect system described previously, and integrating it backwards compatibly with the language, would be no small feat either. I have very little optimism that either of these avenues will ever be pursued by Rust itself.

Conclusion

I’ll add that Rust has had relatively weak facilities for control flow effects for well-founded reasons. The primary cause is Rust’s commitment to “zero-cost” abstractions, which must be highly optimizable, be local in their performance impact, and give a high degree of control to the programmer. None of the elements of stronger effect facilities in widespread use (unwinding, greenthreads, internal iteration, boxed callbacks, etc) were able to meet this constraint. Rust experimented with all of these concepts at some point in its history, it wasn’t out of ignorance that they were excluded.

To some extent, we have been able to introduce stronger facilities for control flow effects within the language’s design constraints. The ? operator and async/await are the primary examples of this, but I would also cite our ability to have for elem in iter style for loops at all, which compile to very tight loops, as a real remarkable success of the language.

I don’t see an improvement to Rust’s integration between higher order functions and control flow effects anywhere on the horizon for Rust itself. But I would encourage anyone exploring the design for a different language’s control flow effects to seriously consider the impact of TCP-preserving closures. I think a combination of explicit effect operators, closures which properly preserve the control flow environment, and an ownership/borrowing system to manage some memory and IO effects, would be the ideal type system pattern for a concurrency-forward imperative programming language.