---
title: "Meetup 2024: Effects and associated effects"
tags: ["T-lang", "design-meeting", "minutes"]
date: 2024-09-10
url: https://hackmd.io/Oc8QQ8yGRcKvkicLh7kisg
---

# Meetup 2024: Effects and associated effects

## Background

Effects are, maybe, going to be the "next big thing" in programming languages.

They're compelling for a few different reasons. One is that they give a type-based way to represent powerful control flow concepts (e.g. `shift`/`reset`, `call/cc`). E.g., from RFC 3513, here's how Koka represents generators:

effect yield<a>
  fun yield(x : a) : ()

fun odd_dup(xs : list<int>) : yield<int> ()
  match xs
    Cons(x,xx) ->
      if x % 2 == 1 then
        yield(x * 2)
      odd_dup(xx)
    Nil -> ()
 
fun main() : console ()
  with fun yield(i : int)
    println(i.show)
    if i == 7: return // (presumably this causes control to return from `main`, not just a return back into `odd_dup`)
  list(1,20).odd_dup

(There is no library being used here and that `yield` is not a keyword or feature of the language.)

Those are "effect handlers".

What's we're more immediately interested in for Rust are "effect types" or "capabilities". That is, we want a way to express what the body of a function is allowed to do. E.g.:

- `total`: The function is deterministic, cannot panic or loop indefinitely, etc.
- `div`: The function may diverge.
- `exn`: The function may panic.
- `pure`: The function may panic or diverge.
- `ndet`: The function is non-deterministic.
- `gen`: The function may yield synchronously.
- `async`: The function may yield asynchronously.
- `nconst`: The function may rely on a runtime.
- etc.

There are number of effectful languages, e.g.:

- [Koka](https://koka-lang.github.io/koka/doc/book.html)
- [Ante](https://antelang.org/) (written in Rust)
- [Flix](https://flix.dev/)

## Syntax matters

Much of the pushback on effects in Rust has been, in my view, due to syntax proposals that have been very noisy.

## Associated effects

The Flix folks recently wrote a paper about [associated effects](https://dl.acm.org/doi/pdf/10.1145/3656393).

class Foldable [t : Type ] {
  type Aef : Eff // An associated effect synonym .
  type Elm : Type // An associated type synonym .
  def foldLeft (f: (b, Elm ) -> b \ ef , s: b, t: t): b \ Aef + ef
  def foldRight (f: (Elm , b) -> b \ ef , s: b, t: t): b \ Aef + ef
}

In Rust, something like:

trait Fold<T> {
  effect E1;
  type Item;
  fn fold_left<B, F>(self, init: B, f: F) -> B + (Self::E1 + F::E2) 
  where
    Self: Sized,
    F: FnMut<effect E2>(B, Self::Item) -> B + F::E2;
  ...
}

## Niko's "maximally minimal" do-based idea

https://nikomatsakis.github.io/rust-of-my-dreams/effects.html

I'm also, in some sense, less principled, in that I want to think of an effect as a "monad-like" combo of

* a transformation that takes place on the signature
* a transformation that takes place on the call to "undo" (possibly propagating) the
* restrictions and/or extra ops on the body

fn foo() -> u32
foo()

async fn foo() -> u32
foo().await : u32

const fn foo() -> u32
foo() /* no-op */

gen fn foo() -> u32
for _ in foo() { .. }

try fn foo() -> u32 // anyhow::Result<u32>
foo() -> anyhow::Result<u32> // (desugared form)
foo()? : u32                 // (nicer natural sugar)

// assumption: fully arbitrary orders of combinations
// of above are not useful, but there exist specific 
// useful orders, as shown below

async try fn foo() -> u32
foo() -> impl Future<Output = anyhow::Result<u32>>
foo().await?

fn map<T, U>(
    v: Vec<T>,
    f: impl FnMut(T) -> U,
) -> Vec<U> {
    v.into_iter()
        .map(|x| f(x))
        .collect()
}

async fn async_map<T, U>(
    v: Vec<T>,
    f: impl async FnMut(T) -> U,
) -> Vec<U> {
    v.into_async_iter()
        .map(async |x| f(x).await)
        .collect()
        .await
}

const fn const_map<T, U>(
    v: Vec<T>,
    f: impl const FnMut(T) -> U,
) -> Vec<U>{
    v.into_const_iter()
        .map(const |x| f(x))
        .collect()
}

do fn map<T, U>(
    v: Vec<T>,
    f: impl do FnMut(T) -> U,
) -> Vec<U> {
    v
        .into_iter()
        .map(do |x| f(x).do)
        .collect().do
}

do trait Iterator {
    do fn next(&mut self) -> Self::Item;

    do fn map<U>(
        self, 
        f: impl do FnMut(Self::Item) -> U
    ) -> impl do Iterator<Item = U>;

    fn size_hint(&self) -> usize;
}

Makes me think of all the non-try versions we implement using <https://stdrs.dev/nightly/x86_64-unknown-linux-gnu/core/ops/try_trait/struct.NeverShortCircuit.html> and calling the try versions.

You can write things as `do` to be generic over the details.

You can express combinators (e.g., fold) like this

trait Fold<T> {
  type Item;

  do fn fold_left<B>(
      self, 
      init: B,
      f: impl do FnMut(B, Self::Item) -> B,
  ) -> B
  where
    Self: Sized;
}

you could desugar this (not an actual syntax I think we need) conceivably to *something* like this

trait Fold<effect E, T> {
  type Item;

  E fn next(&mut self) -> B;

  E fn fold_left<B>(
      self, 
      init: B,
      f: impl E FnMut(B, Self::Item) -> B,
  ) -> B
  where
    Self: Sized;
}

I also want to have a simple set of possible effects that combine in predictable ways, roughly like so:

E = async? try(E)?+ const?

When you put an effect on a trait, it transforms all the methods in the trait equivalently.

Note: `const` is special (since its taking a effect/capability away, rather than adding one), and as part of its specialness, a definition that is meant to be generic over the const-effect needs to explicitly say so, e.g. via: `const do fn` (rather than just `do fn` as shown in all the cases above).

downsides:

* you cannot write a combinator with a function that takes a closure, calls it immediately (e.g., map), but doesn't capture it into the returned combinator
* Scott: A lot of `try_` variants on iterator change from `&self` to `&mut self`
* Because try_ variant wants to mark self as cancelled??
* Maybe we say do version is always `&mut self`, or something
* Might also come up with Fn* traits; we might want to change to a different variant

## do Fn supersedes async Fn

Josh: If we make `do Fn` / `do FnMut` / `do FnOnce` exist and work as expected, then that would justify having `async Fn` / `async FnMut` / `async FnOnce` syntax.

## Disentangling

There are a number of concepts here that can be disentangled.

- Effect handlers
- Contexts
- Capabilities
- User-defined capabilities
- Generic effects
- Generic `do` ("maybe async")
- Innovating here

TC: Different kinds of effect handlers:

- `for`: Handles an effect fully
- `?`: Handles and forwards an effect

## Non-goals (from Niko)

* gen as an effect
* taking a function that (a) has effects you want to be generic over but (b) which you will not immediately call (or at least you want to declare that you won't call)
* "removing" effects from the inputs ("handling them")

Precious comment from JT (regarding whether `gen` fits Niko's `do` model and it ending up being the List Monad): "just because it doesn't make sense doesn't mean Haskell hasn't done it"

## Maximally-maximally minimal

TC: Doing effect generics, with a fixed set of effects, and without `do` is more minimal.

The alternates here are:

- With `do` a single `impl` "magically" works for all effects.
- `impl do Trait for ...`
- `impl async Trait for T`
- `impl Trait for T`
- `impl const Trait for T`
- Without `do`, the same trait works with separate impls.

## Niko notes: what are our real goals?

Thinking about what we really want to get out of this...

* "Orthogonality"
* Iterators, `?`, and friends all work the same way in every context
* I want to be able to get back "yes you can have nice things" -- I want to use iterator APIs
* Oh and: const

try fn something() -> Vec<Result> {
    some_iter
        .iter()
        .map(|x| x.something_fallible()?)
        .collect()
}

libs-api really wants to not define `foo` and `try_foo` and `async_foo` and `async_try_foo` and...; libs-api has already rejected adding `try_*` variants of some methods because we're hoping for a better solution from lang.

## Breaking down the pieces

- `trait do Trait {}`
- `do fn foo()`
- `do async fn foo()`
- `impl Trait {} / impl async Trait {}`
- `impl do(!async) Trait for T {} / impl async do Trait for T {}`

## TC: What are the real goals?

TC: In my view, what we're most immediately trying to avoid is the `2^N` problem on traits, not on impls. If we do nothing, then we need `2^N` traits. Effect generics and associated effects avoid that.

The problem of `2^N` impls could be handled later by adding `do` on top of an effect generic design. But it's hard to me to see a world where we wouldn't need the ability to write separate specific impls anyway.

Josh: I see this often in concrete functions, not just traits. e.g. `Vec` methods, `HashMap` methods.

## TC: What's most natural for Rust?

TC: My feeling is that much of the negative feedback to date has been due to some really noisy syntax that has been proposed. It's hard to disentangle that.

TC: In terms of what's most natural for Rust, it seems the idea of traits defining a contract, for effects as they do elsewhere, and then having separate impls, is a natural framing.

TC: Conversely, the `do` is very magical, especially since it pushes against the idea of `Future`s as normal values in Rust. This is an area where we do have specific non-syntax negative feedback.

## Control flow?

Could we define the "try" effect in a sufficiently general way that it also allow's the caller's closure to call `return` or `break` or `continue`? That should be possible using `ControlFlow`?

(Feedback: yes.)

## Handling things that can return errors or panic

Josh: Could we have a way to specialize (please pretend that's not a terrifying word) for try vs non-try, or have a construct that runs different code in the try vs non-try case? In particular, could we allow saying "if we're try, then return an allocation failure, otherwise panic with an allocation failure"? This implies having more than one `try` effect, some controlled by the caller and one controlled by the callee. `try(AllocationError)` vs `try(E)`

Niko: Yeah, we can make that work. Let's talk separately.

## Some notes

* do syntax for traits
* what about default methods?
* ability to have...
* generic code for the easy case
* custom impls for specific cases
* `impl async Iterator for X { ... }`

### Layer 1

do trait Iterator {
    type Item;
    
    do fn next(&mut self) -> Option<Self::Item>;
    
    do fn map<U>(
        self,
        op: impl do FnMut(Self::Item) -> U,
    ) -> do Map<U> {
        //  ^^^^^^ in reality we will need this
        Map {
            base_iter: self,
            func: op,
        }
    }
    
    do fn for_each(
        &mut self,
        op: impl do FnMut(Self::Item),
    ) {
        while let Some(x) = self.next().do {
            op(x).do;
        }
    }
}

do struct Map<I, F> {
    base_iter: I,
    func: F,
}

impl<R> do Iterator for do Map<I, F>
where
    I: do Iterator,
    F: do FnMut(I::Item) -> R,
{
    type Item = R;

    do fn next(&mut self) -> Option<Self::Item> {
        if let Some(i) = self.base_iter.next().do {
            let j = (self.func)(i).do;
            Some(j)
        }
        None
    }
}