189 Expert

Introduction to Algebraic Effects

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Introduction to Algebraic Effects" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Algebraic effects are a modern alternative to monads for structuring side effects. Key difference from OCaml: 1. **Native vs. simulated**: OCaml 5 has native effect handlers with efficient stack manipulation; Rust requires explicit continuation

Tutorial

The Problem

Algebraic effects are a modern alternative to monads for structuring side effects. Unlike free monads (which build heap-allocated trees), algebraic effects are handled at the runtime level — the effect is "thrown" and a handler "catches" it, potentially resuming the computation. OCaml 5 introduced native effect handlers. Rust simulates them using closures and callbacks. Effects are used in async runtimes (every await is an effect), error handling, non-determinism, and resource management.

🎯 Learning Outcomes

• Understand algebraic effects as a mechanism for suspending and resuming computations

• Learn how effects differ from free monads: effects are operational, free monads are denotational

• See a simple simulation using Rust's closures and callback-based resumption

• Understand why algebraic effects require native language support for full efficiency

Code Example

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* OCaml 5 algebraic effects: define effects, perform them, handle them.
   Like resumable exceptions with a continuation. *)

(* Note: requires OCaml 5.0+ *)

effect Print : string -> unit
effect Readline : string

(* A program that uses effects — pure in itself *)
let interactive_program () =
  perform (Print "What is your name?");
  let name = perform Readline in
  perform (Print ("Hello, " ^ name ^ "!"));
  name

(* Handler 1: real I/O *)
let run_io program =
  match program () with
  | result -> result
  | effect (Print msg) k ->
    print_endline msg;
    continue k ()
  | effect Readline k ->
    let line = input_line stdin in
    continue k line

(* Handler 2: pure simulation with list of inputs *)
let run_pure inputs program =
  let buf = Buffer.create 64 in
  let inputs = ref inputs in
  match program () with
  | result -> (result, Buffer.contents buf)
  | effect (Print msg) k ->
    Buffer.add_string buf (msg ^ "\n");
    continue k ()
  | effect Readline k ->
    let line = List.hd !inputs in
    inputs := List.tl !inputs;
    continue k line

let () =
  let (result, output) = run_pure ["OCaml 5"] interactive_program in
  Printf.printf "Output:\n%s" output;
  Printf.printf "Got name: %s\n" result

Key Differences

Native vs. simulated: OCaml 5 has native effect handlers with efficient stack manipulation; Rust requires explicit continuation-passing simulation.

Stack vs. heap: OCaml's effect continuations are captured stack frames — efficient; Rust's simulation uses heap-allocated closures.

Multi-shot continuations: OCaml's continue k can call k multiple times (non-determinism); Rust's FnOnce callbacks can only be called once.

Composability: OCaml effects compose naturally via nested handlers; Rust simulations require manual composition.

OCaml Approach

OCaml 5's native effect handlers:

effect Read : string
let with_reader env program =
  match_with program ()
    { retc = (fun v -> v)
    ; exnc = raise
    ; effc = fun (type a) (eff : a eff) ->
        match eff with
        | Read -> Some (fun (k : (a, _) continuation) ->
            continue k env)
        | _ -> None }

The handler intercepts Read effects, provides a value, and resumes the computation via continue k env. This is purely functional with no heap-allocated trees — the runtime manages the stack frames.

Full Source

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* OCaml 5 algebraic effects: define effects, perform them, handle them.
   Like resumable exceptions with a continuation. *)

(* Note: requires OCaml 5.0+ *)

effect Print : string -> unit
effect Readline : string

(* A program that uses effects — pure in itself *)
let interactive_program () =
  perform (Print "What is your name?");
  let name = perform Readline in
  perform (Print ("Hello, " ^ name ^ "!"));
  name

(* Handler 1: real I/O *)
let run_io program =
  match program () with
  | result -> result
  | effect (Print msg) k ->
    print_endline msg;
    continue k ()
  | effect Readline k ->
    let line = input_line stdin in
    continue k line

(* Handler 2: pure simulation with list of inputs *)
let run_pure inputs program =
  let buf = Buffer.create 64 in
  let inputs = ref inputs in
  match program () with
  | result -> (result, Buffer.contents buf)
  | effect (Print msg) k ->
    Buffer.add_string buf (msg ^ "\n");
    continue k ()
  | effect Readline k ->
    let line = List.hd !inputs in
    inputs := List.tl !inputs;
    continue k line

let () =
  let (result, output) = run_pure ["OCaml 5"] interactive_program in
  Printf.printf "Output:\n%s" output;
  Printf.printf "Got name: %s\n" result

Deep Comparison

OCaml vs Rust: Effect Intro

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement a with_logger handler that intercepts Log(message) effects and stores them in a Vec<String>.

Simulate non-determinism: an Amb(choices: Vec<A>) effect that a handler interprets by trying all choices.

Compare the performance of a free monad interpreter vs. the effect simulation for a program with 10,000 operations.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust