Datafun: A Functional Language That Turns Datalog Into Declarative Fixed‑Point Computation

Datafun is a small but powerful language that reimagines the classic logic‑programming paradigm of Datalog through the lens of functional programming. Conceived by Neel Krishnaswami and collaborators, it is pure, total, and total functional, and its core novelty lies in treating fixed points of monotone maps on semilattices as first‑class, declaratively‑expressible constructs.

The Language Design

At its heart, Datafun is a typed language whose type system distinguishes monotone functions from arbitrary ones. This distinction is enforced via a modal type system that, while still a work in progress, allows developers to write code that is guaranteed to preserve monotonicity without manual proofs. The language supports set comprehensions, higher‑order functions, and a small, well‑defined core of primitive operations that operate over semilattices.

A minimal example of a Datafun program that computes the transitive closure of a directed graph looks like this:

let rec closure (edges : Set (Int × Int)) : Set (Int × Int) =
  edges ∪ { (a, b) ∈ closure edges × edges | a = b }

The rec keyword denotes a fixed point, and the body is a monotone function over the lattice of all edge sets. The language’s type checker guarantees that this definition is well‑typed and will terminate.

Fixed‑Point Superpower

Unlike traditional Datalog engines that rely on iterative evaluation, Datafun exposes the fixed point as an abstraction that can be manipulated directly. The 2016 ICFP paper introduced this idea and positioned Datafun as a generalization of Datalog, extending it to arbitrary semilattices:

Datafun allows the concise, declarative expression of fixed points of monotone maps on semilattices.

The language’s semantics are grounded in the theory of complete lattices, and the type system is designed to guarantee monotonicity, ensuring termination.

Incremental Evaluation and Seminaïve Optimization

A major breakthrough came with the 2020 POPL paper, which demonstrated how to compute these fixed points faster by incrementalizing the inner loop. The authors generalized Datalog’s seminaïve evaluation to the broader setting of Datafun:

By maintaining a delta set of newly derived facts, we can avoid recomputing everything at each iteration.

This incremental approach reduces the cost from quadratic to near‑linear in many practical cases. The paper also provided a formal proof that the derivative of a fixed point is the fixed point of its derivative, a key insight that underpins the incremental algorithm.

The incremental algorithm is implemented in the Datafun compiler and can be invoked via a simple flag. Benchmarks on classic graph problems show speedups of an order of magnitude compared to naïve evaluation.

Modal Types for Monotonicity

In late 2017 the team explored a modal type system that would allow more flexible handling of monotonicity. Although the work was never fully published, the notes and talks presented at ICFP 2018 and S‑REPLS 9 outline a promising direction: a type system that tracks monotonicity as a modal property, enabling developers to write more expressive code without sacrificing safety.

Mini‑Version in Racket

For those who want to experiment quickly, a 60‑line Racket implementation is available on GitHub. It implements set comprehensions and fixed points but omits the full monotonicity checks and seminaïve optimization. The lightweight implementation serves as an educational tool and a proof of concept for the language’s core ideas.

Practical Implications

Datafun’s approach to declarative fixed‑point computation has several implications for the wider software ecosystem:

  1. Data‑centric Programming – Developers can express complex graph algorithms, database queries, and dataflow analyses as succinct fixed‑point definitions.
  2. Incremental Computation – The seminaïve evaluation strategy aligns with modern incremental computation frameworks, potentially improving performance in reactive systems.
  3. Type‑Safe Monotonicity – By embedding monotonicity guarantees into the type system, Datafun reduces the risk of infinite loops and non‑terminating queries.

These features make Datafun an attractive research platform for exploring new optimizations in logic programming and for teaching advanced concepts in functional programming.

Where to Find More

Datafun remains a niche but potent tool for those willing to explore the intersection of functional programming, logic, and incremental computation. Its concise syntax and strong theoretical foundations provide a compelling case study for the future of declarative data‑centric languages.