Tagless final architecture — algebras, constraint sets, parametricity, interpreters at the edge

Why architecture matters here

The architectural payoff is that the constraint set becomes a reviewable interface. When a pull request adds Clock[F] to a function's constraints, that is a visible, diffable event: this code now depends on the current time. When it adds UserRepo[F], that is a new dependency on the database, in the signature, where a reviewer sees it without reading the body. Compare this with the same code written against IO directly, where anyone can reach for IO(System.currentTimeMillis()) anywhere in a five-hundred-line file and no signature changes at all. The dependency graph stops being something you discover by grepping and becomes something the compiler maintains.

It matters for testing, but with a sharper edge than the usual pitch admits. The value is not that you can substitute a test interpreter — you can always mock an interface. The value is that under parametricity a test interpreter is sufficient. If the function's constraints are Monad[F] and UserRepo[F], then supplying a UserRepo backed by a Map is a complete environment: there is nothing else the code could reach for, so there is nothing else to stub. Tests that pass against the in-memory interpreter are not passing because you guessed the dependencies correctly; they are passing because the type system enumerated them for you.

It matters for controlling the blast radius of an effect-system decision. A codebase that mentions IO in every signature has that library in its public API surface, in every module, permanently. Migrating it — to a different effect type, to a different version with different semantics, to direct-style with virtual threads — is a rewrite. A codebase that mentions F[_] and binds it in Main has that decision in one file. This is not a hypothetical: the Scala effect landscape has shifted repeatedly, and it is the codebases with the concrete type smeared through them that could not move.

And it matters because it makes 'what layer am I in?' a type-level question rather than a naming convention. A domain function constrained to Monad[F] alone is provably pure logic. One constrained to UserRepo[F] is provably persistence-touching and nothing more. One constrained to Async[F] can do essentially anything and has told you so. The layering that architecture diagrams assert and codebases quietly violate becomes something the compiler checks on every build.

The architecture: every piece explained

An algebra is the unit of capability. It is a trait parameterised by the effect type: trait UserRepo[F[_]] { def find(id: UserId): F[Option[User]]; def save(u: User): F[Unit] }. Notice that it says nothing about how any of this happens — no SQL, no connection, no transaction. It says only that finding a user is an effect that yields an optional user. The name 'algebra' is doing real work: this is a set of operations and their signatures, deliberately free of any commitment to what they mean.

A program is a function generic in F[_] that demands its capabilities as implicit constraints: def promoteUser[F[_]: Monad: UserRepo](id: UserId): F[Boolean]. That signature is the whole contract. It says: give me any effect type that can sequence and that has a user repository, and I will give you back a boolean in that effect. It cannot log, because there is no Logger[F]. It cannot sleep, because there is no Temporal[F]. The list of what it can do is exactly as long as the list after the colon.

An interpreter is an instance of an algebra at a concrete type: UserRepo[IO], implemented with a real connection pool and real SQL. This is where the meaning lives, and it is the only place in the codebase that knows about either. A second interpreter — UserRepo[StateT[Eval, Map[UserId, User], *]], or something simpler — is what tests use. Both satisfy the same algebra, so the same program runs against both without recompilation of the program itself. The program does not know or care which one it got.

The constraint set is the real type signature, and this is the piece to internalise. Everything after the colon in [F[_]: Monad: UserRepo: Clock] is a sugar for an implicit parameter, and collectively it is a machine-checked declaration of dependencies. Adding to it is a widening of what the code may do; removing from it is a narrowing. Both are visible in a diff. The discipline that makes tagless final worthwhile is refusing to widen casually — every added constraint is a capability granted for life.

The wiring is the edge. In Main, or in a thin composition module, F is bound to a concrete type, the real interpreters are constructed, and the polymorphic program is instantiated. This is the one place the effect library appears, and it is why the whole structure holds together: the abstraction is not maintained by discipline distributed across the codebase, it is maintained by the fact that nowhere else has a concrete type to reach for. MTL-style classes — MonadError[F, E] for typed failure, Ask[F, Config] for read-only context — extend the same idea to capabilities that would otherwise force you to reach for the concrete type.

End-to-end flow

Follow a request. It arrives at an HTTP route, which is at the edge and therefore already concrete: the server library hands you an IO-shaped handler. The route decodes the body into a domain type and calls a service method. That call is the boundary crossing — from here inward, nothing is concrete. The service method is generic in F[_], and the compiler is at this moment resolving F := IO and supplying the implicit instances that were constructed in Main.

Inside the service, the program composes. It calls UserRepo[F].find, gets back an F[Option[User]], and sequences it with flatMap — available because Monad[F] was demanded. It branches, calls another algebra, maybe raises a typed error through MonadError[F, DomainError]. At no point does it know that F is IO. At no point can it know. The code being executed is the code that was compiled against an opaque type constructor, and its behaviour is bounded by the constraints it declared.

What actually happens at runtime is worth being precise about, because this is where the abstraction meets the machine. The implicit instances are objects. The calls into UserRepo[F] are virtual calls through a trait. The flatMap calls are virtual calls through the Monad instance. All of this is ordinary JVM dispatch, and because F is a type parameter the JIT sees call sites that may be megamorphic — many implementations flowing through one site — which is the case it optimises worst. The abstraction is not free; it is paid for in indirection.

The result comes back as an F[Response], which the route — being concrete — knows is an IO[Response]. It hands it to the server, which runs it. The effect that was described by the whole polymorphic call chain executes exactly once, at the outermost edge, on the runtime's thread pool. Everything inward of the route was building a description; nothing ran until the edge ran it.

Now run the same service method in a test. Nothing about the method changes and nothing is recompiled. The test supplies a different implicit UserRepo, backed by a mutable map, and a different F — often something as simple as Either or a state monad, chosen because it is synchronous and inspectable. The program runs, and because parametricity guaranteed it could not reach past its constraints, the in-memory environment is not an approximation of the real one. It is a complete one. There is no hidden clock read to make the test flaky and no hidden network call to stub, because the compiler would have rejected either.

The thing to hold onto across both paths is that the program is a single artefact and the meaning is supplied from outside. That is the inversion tagless final performs, and it is why the structure survives contact with change: a new interpreter — an instrumented one that records every repository call, a caching one that wraps the real one, a failing one that injects errors for chaos testing — is a new object satisfying an existing trait, added at the edge, with no modification to any logic. The programs do not need to know they are being observed, cached, or sabotaged, because they were never allowed to know what F was in the first place.

Failure modes and mitigations

• Constraint creep. The commonest decay path. Someone needs a timestamp, adds Clock[F]; someone needs a log line, adds Logger[F]; six months later half the codebase is constrained to Async[F] and the signatures guarantee nothing at all. Treat every added constraint as an API change and review it as one.
• Binding to Async[F] by default. Async can construct arbitrary effects, so a function constrained to it can do anything. It is IO wearing a type parameter. Every parametricity guarantee evaporates and you are paying the abstraction's costs for none of its benefits.
• Compile-time collapse. Implicit resolution over deep constraint sets is not free, and it compounds superlinearly with nesting and with the number of type classes in scope. Large tagless codebases routinely hit builds that take minutes. Measure it, and treat a slow build as a design signal, not a fact of life.
• Megamorphic dispatch in hot paths. Every operation goes through an instance the JIT may not be able to devirtualise. In genuinely hot inner loops this is measurable. The fix is boring: monomorphise the hot path, keep the abstraction where the decisions are, and stop pretending the cost is zero.
• Incoherent instances. Two implicit instances of the same type class for the same type, in scope in different places, means the same code has different behaviour depending on where it was called from — and it compiles. This is the failure mode that produces genuinely baffling bugs. Define instances in companion objects and nowhere else.
• The abstraction that never pays out. One interpreter, one binding, forever. If F is only ever IO and the test interpreter was never written, the parametricity argument is real but unexercised, and you have bought the compile times for nothing. Either write the second interpreter or drop the abstraction.
• Error messages nobody can read. A missing implicit deep in a constraint chain produces a diagnostic that names types nobody wrote. This is a genuine cost, it falls hardest on new team members, and no amount of elegance offsets it. Budget for it in onboarding.

Operational playbook

• Keep algebras small and domain-shaped. An algebra should name a capability the domain has, not a library you use. UserRepo is an algebra; PostgresClient is an interpreter wearing an algebra's clothes and it will leak the database into every signature that mentions it.
• Demand the weakest constraint that compiles. The discipline is to reach for Functor before Monad, Monad before Concurrent, and never Async in domain code. The strength of the guarantee is exactly the weakness of the constraint.
• Bind F in exactly one file. If more than Main mentions the concrete effect type, the boundary has already leaked. Make this a lint rule or a review checklist item, because it erodes one convenient exception at a time.
• Write the second interpreter early. It is the proof that the abstraction is real. A codebase that has never instantiated F with anything but IO has an untested claim, and the first attempt will surface every place the boundary was violated.
• Define instances in companion objects only. Implicit scope is the mechanism that makes coherence tractable. Orphan instances in random files are how you get two interpretations of the same type and a bug that reproduces only in one module.
• Measure compile time as a first-class metric. Track it per module in CI the way you track test duration. Tagless codebases degrade slowly and nobody notices until the build is five minutes and refactoring has stopped happening.
• Monomorphise deliberately at the edges. Where profiling shows dispatch cost, fix F to a concrete type at that boundary and keep the polymorphism outside it. This is an optimisation, it should be justified by a measurement, and it should be commented as such.