Algebraic Effects

[njlr]

I propose we ...

Add an Algebraic Effects system.

This is not a precise definition, just a sketch of what it might look like...

Define effects with an input type and an output type using a new effect keyword:

effect ConsoleRead of unit -> string 

effect ConsoleWrite of string -> unit 

Functions can perform effects with a new perform keyword:

let greet () =
  perform (ConsoleWrite "What is your name?")
  let name = perform (ConsoleRead ())
  perform (ConsoleWrite $"Hello %s{name}")

Functions are annotated with the set of effects they might perform during execution:

val greet : unit ->{ConsoleRead|ConsoleWrite} unit

And a normal function is equivalent to the empty set:

// String.length

val length : string -> int
val length : string ->{} int

Effect types propagate across function calls automatically:

let greetN (n : int) =
  for _ = 1 to n do
    greet ()

val greetN : int ->{ConsoleRead|ConsoleWrite} unit

And the effects of a function is the union of what it calls:

let read () =
  perform (ConsoleRead ())

let write (x : string) =
  perform (ConsoleWrite x)

let readAndWrite () =
  write (read ())

val read : unit ->{ConsoleRead} string

val write : string ->{ConsoleWrite} unit

val readAndWrite : unit ->{ConsoleRead|ConsoleWrite} unit

Effects can be given a concrete handler with a new handle keyword, thus removing the effect type from the annotation:

open System

[<EntryPoint>]
let main _ = 
  handle 
    greet ()
  with
  | (ConsoleRead ()) k ->
    let v = Console.ReadLine()
    continue k v
  | (ConsoleWrite v) k ->
    Console.WriteLine(v)
    continue k ()

  0

The compiler guarantees that the entry point has no effects. In other words, all effectful computations must be a concrete handler.

Different handlers can be given, depending on the scenario:

open Expecto

test "greet works as expected" {
  let output = ResizeArray<string>()

  handle 
    greet ()
  with
  | (ConsoleRead ()) k ->
    continue k "John Doe"
  | (ConsoleWrite v) k ->
    output.Add(v)
    continue k ()

  Expect.equal (Seq.toList output) [ "Hello John Doe" ] ""
}

A simulation of this feature might be possible with computation expressions and polymorphic variants.

The existing way of approaching this problem in F# is ...

• Impure code - convenient to write, but effects are unmanaged
• Monadic code - effect are managed, but code is inconvenient to write

Pros and Cons

The advantages of making this adjustment to F# are ...

• Convenience and approachability of impure code - "just write the thing"
• Encoding of effect information in the type-system
• Ability to write mock effect handlers for testing purposes
• Performance improvements over monadic and DI approaches, with appropriate inlining of handlers

The disadvantages of making this adjustment to F# are ...

• Language complexity
• Potential for increased indirection in library and application code

Extra information

Estimated cost (XS, S, M, L, XL, XXL): XXL

Related suggestions:

Effect propagation is related to polymorphic variants. Effect annotations relate to function purity analysis.

• Add polymorphic variants (ad-hoc Discriminated Unions) #40
• Pure Functions - "pure" keyword #201
• Erased type-tagged anonymous union types #538
• Anonymous DUs #728

Affidavit (please submit!)

Please tick these items by placing a cross in the box:

• This is not a question (e.g. like one you might ask on StackOverflow) and I have searched StackOverflow for discussions of this issue
• This is a language change and not purely a tooling change (e.g. compiler bug, editor support, warning/error messages, new warning, non-breaking optimisation) belonging to the compiler and tooling repository
• This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it
• I have searched both open and closed suggestions on this site and believe this is not a duplicate

Please tick all that apply:

• This is not a breaking change to the F# language design
• I or my company would be willing to help implement and/or test this

For Readers

If you would like to see this issue implemented, please click the 👍 emoji on this issue. These counts are used to generally order the suggestions by engagement.

[vzarytovskii]

Duplicate of #373

This probably falls under "already decided", during F# 1.0, so would put probably not for now, happy to discuss @T-Gro.

[njlr]

Duplicate of #373

This probably falls under "already decided", during F# 1.0, so would put probably not for now, happy to discuss @T-Gro.

Hmm I did search before posting, but this didn't come up! 🤦

Yes, this is probably a dupe; will have to dig out the linked paper (link now broken)...

Also might be worth revisiting since ~10 years later there have been quite a few developments (Koka, OCaml multi-core, Unison, Effekt, etc.)

Edit: https://tomasp.net/academic/papers/haskell-effects/haskell-effects.pdf ?

[T-Gro]

F# is a language that interops - be it with rest of .NET, or via Fable.
That means that some effects will always stay hidden behind function calls, and bypass any careful design.

Putting that aside - seeing the pseudocode samples written here, I immediately spotted similarity with the F# Free Monad recipe - https://blog.ploeh.dk/2017/08/07/f-free-monad-recipe/ . Especially when used with a computation expression, that can go quite far with domain-specific definitions of effectful actions.

[njlr]

Putting that aside - seeing the pseudocode samples written here, I immediately spotted similarity with the F# Free Monad recipe - https://blog.ploeh.dk/2017/08/07/f-free-monad-recipe/ . Especially when used with a computation expression, that can go quite far with domain-specific definitions of effectful actions.

I think that the free monad recipe falls down when composing different effect types. You must model all possible effects under one type for it to work.

Hopefully I haven't missed an easy solution here!

Setup

Definining the types, builders for two kinds of effects:

• Console read line, write line
• Read environment variables

// Command Line

type CommandLineInstruction<'a> =
  | ReadLine of (string -> 'a)
  | WriteLine of string * 'a

module CommandLineInstruction =

  let map f =
    function
    | ReadLine next -> ReadLine (next >> f)
    | WriteLine (x, next) -> WriteLine (x, next |> f)

type CommandLineProgram<'a> =
  | Free of CommandLineInstruction<CommandLineProgram<'a>>
  | Pure of 'a

module CommandLineProgram =

  let lift (x : 'a) : CommandLineProgram<'a> =
    Pure x

  let rec bind (f : 'a -> CommandLineProgram<'b>) (x : CommandLineProgram<'a>) : CommandLineProgram<'b> =
    match x with
    | Pure a -> f a
    | Free instr ->
      instr
      |> CommandLineInstruction.map (bind f)
      |> Free

  let readLine : CommandLineProgram<string> =
    Free (CommandLineInstruction.ReadLine Pure)

  let writeLine (x : string) : CommandLineProgram<unit> =
    Free (CommandLineInstruction.WriteLine (x, Pure ()))

type CommandLineBuilder() =
  member this.Bind(x, f) =
    CommandLineProgram.bind f x

  member this.Return(x) =
    CommandLineProgram.lift x

let commandLine = CommandLineBuilder()


// Env

type EnvInstruction<'a> =
  | ReadEnv of name : string * (string -> 'a)

module EnvInstruction =

  let map f =
    function
    | ReadEnv (name, next) -> ReadEnv (name, next >> f)

type EnvProgram<'a> =
  | Free of EnvInstruction<EnvProgram<'a>>
  | Pure of 'a

module EnvProgram =

  let lift (x : 'a) : EnvProgram<'a> =
    Pure x

  let rec bind (f : 'a -> EnvProgram<'b>) (x : EnvProgram<'a>) : EnvProgram<'b> =
    match x with
    | Pure a -> f a
    | Free instr ->
      instr
      |> EnvInstruction.map (bind f)
      |> Free

  let read (name : string) : EnvProgram<string> =
    Free (EnvInstruction.ReadEnv (name, Pure))

type EnvBuilder() =
  member this.Bind(x, f) =
    EnvProgram.bind f x

  member this.Return(x) =
    EnvProgram.lift x

let env = EnvBuilder()

The Limitation

Then attempting to compose these in one effectful workflow:

let readGreetingEnv =
  env {
    let! s = EnvProgram.read "GREETING"

    return s.Trim()
  }

let main =
  commandLine {
    let! greeting = readGreetingEnv // Cannot bind an EnvProgram into a CommandLineProgram

    do! CommandLineProgram.writeLine "What is your name?"

    let! name = CommandLineProgram.readLine

    do! CommandLineProgram.writeLine $"%s{greeting} %s{name}"
  }

Perhaps polymorphic variants would provide a way out?

[vzarytovskii]

Duplicate of #373

This probably falls under "already decided", during F# 1.0, so would put probably not for now, happy to discuss @T-Gro.

Hmm I did search before posting, but this didn't come up! 🤦

Yes, this is probably a dupe; will have to dig out the linked paper (link now broken)...

Also might be worth revisiting since ~10 years later there have been quite a few developments (Koka, OCaml multi-core, Unison, Effekt, etc.)

Edit: https://tomasp.net/academic/papers/haskell-effects/haskell-effects.pdf ?

I do like effect systems in languages, it just feels, as Tomas said, a bit alien to F# due to its tight interop with the .NET and JS/TS, where everything on the border will either always be "effectful"/impure or we're risking missing something.

[njlr]

everything on the border will either always be "effectful"/impure or we're risking missing something

This kind of "border" code, which is so common in F#, is my main motivation for effects 🙂

To give a concrete example, take these two .NET libraries:

• Npgsql
• Confluent.Kafka

Our application (or a library of bindings) could define the effects we care about, for example:

effect KafkaRead of unit -> KafkaMessage

effect KafkaCommit of KafkaMessage -> unit

effect PostgresExecuteQuery of PostgresQuery -> unit

With these, we can write code in a direct style:

let readAndUpsert () =
  let message = perform (KafkaRead ())

  perform PostgresExecuteQuery (upsertQuery message)

  perform KafkaCommit message

How I think most developers would write this today is:

let readAndUpsert (conn : DBConnection) (kafkaClient : KafkaClient) =
  async {
    let! message = kafkaClient.ReadMessageAsync()

    do! conn.ExecuteAsync(upsertQuery message)

    do! kafkaClient.CommitAsync(message)
  }

The effect version improves on this in a few ways:

1. We don't need to pass the context objects explicity. That can be done in the handler, which is usually close to main.
2. We can be more precise about the effects we use from the .NET libraries in the signature. There is a convention that we only perform managed effects; perhaps this could be enforced by a linter.
3. We can test the effectful version using special test handlers, without changing the method definition. For example we can test that the message is committed after upsert.

[T-Gro]

Perhaps polymorphic variants would provide a way out?

You are right, you would need to define another discriminated union as a choice over the effects you want to use (i.e. CommandLine | Environment ).

Which of course does not scale well if there are dozens of possible effect combinations that the application can use.