Tagless Final

The Tagless Final pattern (sometimes called Finally Tagless) is a well-known approach in the functional programming community for defining domain-specific languages (DSLs). It replaces the free monad's data structure encoding with a direct encoding using interfaces (type classes in Haskell). This is version 4 of our program, and it represents a radical simplification over V3.

The Core Idea

In the initial (or tagged) encoding (V2 and V3), we represent programs as data structures — discriminated unions, instruction classes — that are later interpreted. In the final (or tagless) encoding, we represent programs as functions parameterized by an interface (the "algebra") that describes the available operations.

Aspect	Initial Encoding (V2/V3)	Final Encoding (V4)
Program type	ADT: Stop | Effect of ...	Function: 'ins -> Async<'ret>
Instructions	Union cases + Effect classes	Interface methods
Interpretation	Recursive pattern match	Direct invocation of interface implementation
Adding operations	Add union case, effect class, helper	Add interface method
Type parameters	Program<'ret>	Program<'ins, 'ret>

In Haskell, this is achieved with type classes; in F#, we use interfaces — which serve the same role of abstracting the algebra of operations.

Why Move from V3 to V4?

The Variance Problem

V3's IProgramEffect<'a> interface required a Map method returning IProgramEffect<'b>:

// V3 — problematic
[<Interface>]
type IProgramEffect<'a> =
    abstract member Map: f: ('a -> 'b) -> IProgramEffect<'b>

This design made the type a functor — sufficient for sequential let! ... let! composition. However, to support parallel execution via the applicative syntax let! ... and! ..., we need a map2 function:

// Would need something like:
let map2 f (effA: IProgramEffect<'a>) (effB: IProgramEffect<'b>) : IProgramEffect<'c> = ...

This is effectively impossible in F# because:

1. The Map method's return type IProgramEffect<'b> is covariant in 'b, but the effect implementations wrapping domain-specific instruction types are invariant.

2. F#'s .NET generics enforce strict variance checking — unlike Haskell's type classes, which are structurally flexible.

3. Implementing MergeSources (the CE method backing and!) on Program<'ret> = Stop of 'ret | Effect of IProgramEffect<Program<'ret>> would require composing two effects that know nothing about each other.

This made parallel instruction execution essentially impossible with the V3 architecture.

The Boilerplate Problem

V3 required a 5-step recipe per instruction:

1. Type alias (GetPricesQuery<'a>)

2. Union case (GetPrices of GetPricesQuery<'a>)

3. Effect interface (IProductEffect<'a>)

4. Effect class (4 lines each: GetPricesEffect<'a>)

5. Helper function (let getPrices = Program.effect GetPricesEffect GetPricesQuery)

For 5 instructions, that's ~50 lines of boilerplate before writing any workflow logic.

V4: The Tagless Final Solution

Program = Async Reader

The entire Program type collapses to a single type alias:

type Program<'ins, 'ret when 'ins :> IProgramInstructions> = 'ins -> Async<'ret>

A program is simply a function that:

• Takes 'ins — an instruction set (an interface inheriting IProgramInstructions)

• Returns Async<'ret> — an asynchronous result

This is the ReaderT monad pattern: the "environment" being read is the set of instructions.

Instructions = Interface Methods

Each domain defines its instructions as a plain interface:

[<Interface>]
type IProductInstructions =
    inherit IProgramInstructions
    abstract member GetPrices: (SKU -> Async<Prices option>)
    abstract member SavePrices: (Prices -> Async<Result<PreviousValue<Prices>, Error>>)
    // ...

Each member's type is a function 'arg -> Async<'ret>, making each member essentially a single instruction. This is the Tagless Final algebra — no union type, no effect class, just interface methods.

Defining Programs from Instructions

A helper type makes defining programs from instructions ergonomic:

type private DefineProgram = DefineProgram<IProductInstructions>

let getPrices sku = DefineProgram.instruction _.GetPrices(sku)
let savePrices prices = DefineProgram.instruction _.SavePrices(prices)

Under the hood, DefineProgram.instruction is just the identity function — it's a DevExp aid that triggers IntelliSense on the instruction interface, using F#'s shorthand lambda syntax (_.Method(args)).

Benefits

Simplicity

• 1 type alias instead of the free monad ADT

• 1 interface instead of union + effect classes + aliases

• 1 line per instruction in the helper module

• No interpreter loop — the CE builder directly composes async functions

Monadic Bind Without Functor

The bind function — essential for the program CE's let! syntax — illustrates why V4 is fundamentally simpler.

V3 relied on Program<'ret> being an ADT (Stop | Effect). Its bind had to recursively traverse this tree, calling Map on the effect at each node:

// V3 — recursive, requires IProgramEffect.Map (functor)
let rec private bind f program =
    match program with
    | Stop x -> f x
    | Effect effect -> effect.Map(bind f) |> Effect

The effect.Map(bind f) call is what forced every instruction type to implement IProgramEffect<'a>.Map — i.e., to be a functor. This was the root cause of the variance problem described above: Map had to return IProgramEffect<'b>, which imposed covariance constraints incompatible with F#'s strict generic variance checking.

V4 replaces the ADT with a function 'ins -> Async<'ret>. Binding two programs is just function composition, with sequencing delegated to Async's own bind (let!):

// V4 — non-recursive, no functor needed
let bind (f: 'a -> Program<'ins, 'b>) (prog: Program<'ins, 'a>) : Program<'ins, 'b> =
    fun ins -> async {
        let! a = prog ins
        return! f a ins
    }

The instructions ('ins) are simply threaded through as a reader environment — no Map, no recursion, no functor constraint. The monadic plumbing is entirely handled by the Async computation expression.

Parallel Execution

Since Program<'ins, 'ret> is just 'ins -> Async<'ret>, implementing map2 is trivial:

let map2 (f: 'a -> 'b -> 'c) (progA: Program<'ins, 'a>) (progB: Program<'ins, 'b>) : Program<'ins, 'c> =
    fun ins ->
        async {
            let! childTaskA = Async.StartChild(progA ins)
            let! b = progB ins
            let! a = childTaskA
            return f a b
        }

This enables the applicative let! ... and! ... syntax in the program CE:

program {
    let! resA = Program.addProduct product
    and! resB = Program.addPrices (Prices.Initial(sku, currency))
    return Result.zip resA resB |> Result.ignore
}

Both instructions run concurrently — something impossible in V3.

Extensibility

The reader-based design naturally supports:

• Undo / Saga pattern: The instruction preparer wraps each instruction with tracking and undo capabilities, without modifying the program type.

• Observability: Logging, metrics, and timing are injected at the instruction preparation level.

• Testing: Mock the instruction interface — no interpreter to stub.

Complementary Resource

• Series Tagless Final in F# by John Azariah 🐸

What's Next

The following sections detail the Program project implementation, then show how domain workflows use this pattern in practice.