188: Operational Monad

// Operational Monad — Instructions and Programs
//
// Similar to the free monad but more explicit: the instruction set is a
// separate enum (the "operation"), and programs sequence instructions with
// continuations.  The interpreter walks the program tree.
//
// DSL: a simple IO language with Read (get a line) and Write (emit a line).

// ── Instruction set ──────────────────────────────────────────────────────────

enum Instr {
    Read,
    Write(String),
}

// ── Programs: an instruction followed by a continuation, or a return value ──

enum Prog<A> {
    Return(A),
    Instr(Instr, Box<dyn FnOnce(InstrResult) -> Prog<A>>),
}

// Instruction results (what each instruction "returns" to the continuation)
enum InstrResult {
    ReadResult(String),
    WriteResult,
}

// ── Smart constructors ───────────────────────────────────────────────────────

fn prog_return<A>(x: A) -> Prog<A> {
    Prog::Return(x)
}

fn prog_read<A: 'static, F: FnOnce(String) -> Prog<A> + 'static>(f: F) -> Prog<A> {
    Prog::Instr(
        Instr::Read,
        Box::new(move |r| match r {
            InstrResult::ReadResult(s) => f(s),
            _ => panic!("expected ReadResult"),
        }),
    )
}

fn prog_write<A: 'static>(s: impl Into<String>, next: Prog<A>) -> Prog<A> {
    let s = s.into();
    Prog::Instr(
        Instr::Write(s),
        Box::new(move |r| match r {
            InstrResult::WriteResult => next,
            _ => panic!("expected WriteResult"),
        }),
    )
}

// ── Monadic bind ─────────────────────────────────────────────────────────────

fn bind<A: 'static, B: 'static, F: FnOnce(A) -> Prog<B> + 'static>(
    m: Prog<A>,
    f: F,
) -> Prog<B> {
    match m {
        Prog::Return(x) => f(x),
        Prog::Instr(instr, cont) => {
            Prog::Instr(instr, Box::new(move |r| bind(cont(r), f)))
        }
    }
}

// ── Pure interpreter: list as stdin, buffer as stdout ────────────────────────

fn run_pure<A>(inputs: &[&str], prog: Prog<A>) -> (A, String) {
    let mut buf = String::new();
    let mut inputs: std::collections::VecDeque<String> =
        inputs.iter().map(|s| s.to_string()).collect();

    fn go<A>(
        prog: Prog<A>,
        inputs: &mut std::collections::VecDeque<String>,
        buf: &mut String,
    ) -> A {
        match prog {
            Prog::Return(x) => x,
            Prog::Instr(Instr::Read, cont) => {
                let line = inputs.pop_front().unwrap_or_default();
                go(cont(InstrResult::ReadResult(line)), inputs, buf)
            }
            Prog::Instr(Instr::Write(s), cont) => {
                buf.push_str(&s);
                buf.push('\n');
                go(cont(InstrResult::WriteResult), inputs, buf)
            }
        }
    }

    let result = go(prog, &mut inputs, &mut buf);
    (result, buf)
}

// ── Example programs ─────────────────────────────────────────────────────────

fn hello_program() -> Prog<String> {
    bind(prog_write("Enter name:", prog_return(())), |_| {
        prog_read(move |name| {
            let msg = format!("Hello, {}!", name);
            bind(prog_write(msg, prog_return(())), move |_| prog_return(name))
        })
    })
}

fn echo_twice_program() -> Prog<()> {
    prog_read(|line| {
        let out = format!("Echo: {}", line);
        bind(prog_write(out.clone(), prog_return(())), move |_| {
            prog_write(out, prog_return(()))
        })
    })
}

fn main() {
    // ── Hello program ─────────────────────────────────────────────────
    let prog = hello_program();
    let (result, output) = run_pure(&["Alice"], prog);
    println!("Output:\n{}", output.trim());
    println!("Result: {}", result);

    println!();

    // ── Echo twice ────────────────────────────────────────────────────
    let prog2 = echo_twice_program();
    let (_, output2) = run_pure(&["Rust is great"], prog2);
    println!("Echo output:\n{}", output2.trim());
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_hello_program_output() {
        let prog = hello_program();
        let (result, output) = run_pure(&["Bob"], prog);
        assert_eq!(result, "Bob");
        assert!(output.contains("Hello, Bob!"));
        assert!(output.contains("Enter name:"));
    }

    #[test]
    fn test_echo_twice_output() {
        let prog = echo_twice_program();
        let (_, output) = run_pure(&["hello"], prog);
        // "Echo: hello" appears twice
        let count = output.matches("Echo: hello").count();
        assert_eq!(count, 2);
    }

    #[test]
    fn test_pure_interpreter_no_real_io() {
        // The interpreter uses a list; no stdin/stdout touched
        let prog = prog_read(|line| prog_return(line.len()));
        let (len, _) = run_pure(&["abcde"], prog);
        assert_eq!(len, 5);
    }

    #[test]
    fn test_bind_chains_correctly() {
        let prog = bind(prog_write("a", prog_return(())), |_| {
            bind(prog_write("b", prog_return(())), |_| prog_return(42i32))
        });
        let (val, out) = run_pure(&[], prog);
        assert_eq!(val, 42);
        assert!(out.contains('a') && out.contains('b'));
    }
}