Skip to content
Fixen

What is FPOP?

Fixed-Point-Oriented Programming (FPOP) is a programming paradigm designed to streamline the implementation of problems involving cycles, self-reference, and iterative computation. It provides a high-level, declarative abstraction that enables concise and expressive problem formulations while the underlying solver handles the mechanics of fixed-point computation.

The Problem

Section titled “The Problem”

Problems involving cycles or self-reference are pervasive in computer science. Examples include:

  • Graph algorithms — shortest paths, strongly connected components, dominators
  • Static analysis — data-flow analysis, type inference, abstract interpretation
  • Parsing — context-free grammars, Earley parsers, CYK, LR parser generation
  • Automata — minimization, reachability, equivalence checking
  • Distributed systems — conflict-free replicated data types (CRDTs), distributed fixed-point computations
  • Type systems — type inference, constraint solving, effect systems

These problems are fundamentally about computing the least fixed point of a monotone function. The standard solution is a work-queue (or work-list) algorithm: iteratively apply inference rules until no new facts can be derived.

Unfortunately, implementing work-queue algorithms in traditional programming paradigms is laborious, error-prone, and brittle against changes to problem specifications. The boilerplate code for queue management, fact tracking, and stale-entry discarding often obscures the essence of the algorithm. Consider Dijkstra’s shortest-path algorithm in Haskell:

Dijkstra's Algorithm in Haskell
module Dijkstra where


import Data.HashMap.Strict (HashMap)
import Data.HashMap.Strict qualified as HashMap
import Data.PQueue.Min (MinQueue (..))
import Data.PQueue.Min qualified as MinQueue
import Numeric.Natural


type Vertex = String
type Dist = Natural


dijkstra :: Vertex
         -> HashMap Vertex [(Vertex, Dist)]
         -> HashMap Vertex Dist
dijkstra start edges = go HashMap.empty (MinQueue.fromList [(0, start)])
  where
    go :: HashMap Vertex Dist
       -> MinQueue (Dist, Vertex)
       -> HashMap Vertex Dist
    go dists Empty = dists
    go dists ((d, v) :< work)
      | Just d' <- HashMap.lookup v dists
      , d' <= d = go dists work
      | otherwise =
          let dists' = HashMap.insert v d dists
              newWork =
                fmap
                  (\(v', d') -> (d + d', v'))
                  (HashMap.findWithDefault [] v edges)
              work' = MinQueue.union (MinQueue.fromList newWork) work
           in go dists' work'

All of this code express only two key ideas: the distance to the source is 0, and the triangular distance property. The rest is queue management.

The FPOP Mental Model

Section titled “The FPOP Mental Model”

FPOP shifts the programmer’s focus from how to iterate to what facts follow from existing facts. In FPOP, you express computation through two constructs:

  • Relations — declare what facts look like (e.g., Edge v1 v2 d, DistTo v d)
  • Rules — declare how new facts derive from existing ones (e.g., “if there is a path to v1 with distance d1, and an edge from v1 to v2 with distance d2, then there is a path to v2 with distance d1 + d2”)

A solver applies the rules iteratively, computing the set of all inferable facts until a fixed point is reached. The programmer specifies what is true; the solver determines how to compute it.

The same Dijkstra’s algorithm in an FPOP language requires just two executable lines (this is not Fixen; we show how to express Dijkstra’s algorithm in Fixen in later sections):

rule init: DistTo start 0
rule addDist: DistTo v1 d1, Edge v1 v2 d2 => DistTo v2 (d1 + d2)

With just these two lines, the full shortest-path algorithm is defined. To achieve Dijkstra’s optimal performance, a single optimization directive ensures shorter distances are processed first. That is all.

How It Works

Section titled “How It Works”

FPOP computations are grounded in order theory. The key concepts are:

  1. Partial orders — a relation that is reflexive, transitive, and antisymmetric. Not every pair of elements needs to be comparable.

  2. Lattices — a partial order where every pair of elements has a least upper bound (join, ) and a greatest lower bound (meet, ). Lattices provide the structure needed to combine facts.

  3. Monotonicity — a function is monotonic if implies . This guarantees that applying rules never “undoes” previously derived facts.

  4. Fixed points — a value such that . The least fixed point represents the complete set of facts inferable from the initial data and rules.

  5. Kleene’s fixed-point theorem — for a monotone function over a suitable lattice, the least fixed point can be computed by iterating starting from the bottom element () until convergence.

In FPOP, the domain represents the lattice (equipped with the partial order) over which relations operate and the rules compute the consequences of inference. Combined with optimizations to apply only rules affected by newly learned facts, this yields the classic work-queue algorithm, but expressed declaratively.

Why FPOP Matters

Section titled “Why FPOP Matters”

FPOP offers three key advantages over traditional implementations:

Concision — Complex algorithms can be expressed in a fraction of the code. Graph distances require two lines instead of a hundred. This reduction in boilerplate makes the core algorithmic ideas immediately visible.

Maintainability — Changes to problem specifications require modifying only the relevant relations and rules, not the entire control flow. The solver handles iteration, fact management, and subsumption automatically.

Optimization — Algorithm-level optimizations (e.g., processing order, indexing strategies) are expressed as separate directives, not interwoven with the problem logic. This lets programmers prototype quickly, then optimize without rewriting core logic.

About Fixen

Section titled “About Fixen”

Fixen is a fixed-point-oriented domain-specific language (DSL). Presently, Fixen is a research language and is currently under active research and development.

Fixen brings FPOP to Haskell and is a vehicle for introducing novel FPOP language features; we discuss the novel features that Fixen implements in this site. Haskell developers can use Fixen as part of any project to:

  1. Define fixed-point computation in Fixen program(s)
  2. Use the Fixen compiler to generate Haskell source code (to be incorporated with part of a larger project) that implements the specified fixed-point computation.

Fixen is suitable for research and exploration into FPOP theory, implementation and application for Haskell developers.

Next Steps

Section titled “Next Steps”