Algebraic Effects — Brief ☧

"In whom are hid all the treasures of wisdom and knowledge."

— Colossians 2:3 (KJV)

Q: When you order food at a restaurant, you describe what you

want ("I will have the pasta"), but you do not walk into the kitchen

and cook it yourself. The waiter carries your description to the kitchen,

and the chef handles the actual execution. The description and the

execution are completely separate. Does this separation show up in

programming?

A: It does, and it has a name: algebraic effects. An effect

is a declared operation — think of it as raising your hand and saying

"I need something done." A handler is the code that actually does it.

Your program describes what should happen; the handler decides how.
# For God so loved the world that he gave his only begotten Son,
# that whoever believes in him should not perish but have eternal life.
# John 3:16

# Effect description (just a declaration, no execution)
class ReadFileChirho:       # "I need to read a file"
    pass

class WriteLogChirho:       # "I need to write a log entry"
    pass

# Handler 1: Actually reads from disk and writes to a log file
# Handler 2: A test stub that returns mock data and discards logs
# Same program, different interpretations!
Q: Why is this separation useful? I could just call the function

directly.

A: Because it makes your code incredibly flexible and testable.

With direct calls, your program is locked to one behavior. With effects,

you can swap handlers without changing the program. Want to test without

hitting a database? Swap in a mock handler. Want to run the same logic

on a GPU instead of a CPU? Swap the handler. The program itself never

changes. This is especially powerful for things like nondeterminism

(exploring multiple possibilities), error handling, and state management.

Q: What is a "free monad" and how does it relate?

A: A free monad is one way to build an effect system. Imagine

writing a to-do list of instructions on a scroll — "do A, then B,

then C" — without actually performing any of them. The free monad

captures that sequence of steps as a data structure.

Later, a handler reads the scroll and executes each step. You get to

describe a complex workflow and defer all the real work to interpretation

time.

Key Concepts

Concept	Meaning	Our Project
Algebraic effect	A declared side effect	Nondeterminism (conde), failure (==)
Free monad	Build effects from a functor	miniKanren as a free monad over Goal
Handler	Interpret effects into results	Stream handler vs FPGA tensor handler
Effect row	Track multiple effects in types	`{Nondet, State, Fail}`

The four concepts in this table build on each other in a natural progression. An algebraic effect declares what needs to happen without specifying how. A free monad captures a sequence of such declarations as a data structure that can be examined and interpreted. A handler provides the actual interpretation -- the "how" that was deferred. And an effect row tracks which effects a piece of code uses, so the type system can verify that every effect has a handler. This separation of "what" from "how" is not just elegant; it is profoundly practical for systems that need to run the same logic on different hardware.

Connection to our project: Our search tree is essentially

a free monad over the nondeterminism effect. When a miniKanren program says conde (explore multiple branches), it is performing the nondeterminism effect -- it declares "I need to try multiple possibilities" without specifying how those possibilities should be explored. The FPGA backend is one handler

(eager tensor ops that AND-intersect domain bitmasks in parallel); the CPU backend is another (lazy streams that explore branches one at a time using interleaving). Same

algorithm, different execution strategies — the

separation of description from execution is what makes this possible. This architecture means we can develop and test our logic on the CPU with the lazy stream handler, then deploy it on the FPGA with the tensor handler, confident that the results will be identical because both handlers interpret the same free monad.

Learn more in the deep version

Related: Type Classes | Curry-Howard

Soli Deo Gloria