Limitations of CurryHoward When Dealing With Recursive Types: A Deep Dive Into the Scala Macro Implementation

CurryHoward's Scala macro-based theorem prover can only handle simple self-referential types like List[A] and fails for mutual recursion, higher-kinded fixed points, and nested recursive constructors due to its atomic RecurseT node design.

The chymyst/curryhoward library generates Scala code automatically via the implement macro, applying the Curry-Howard correspondence to construct type inhabitants. While it supports basic recursive algebraic data types, the limitations of curryhoward when dealing with recursive types become apparent in more complex scenarios involving mutual references, higher-kinded fixpoints, or deep nesting.

How CurryHoward Detects Recursion (and Where It Stops)

The macro-based engine recognizes recursion by maintaining a typesSeen set during type expression construction. In src/main/scala/io/chymyst/ch/Macros.scala, the buildTypeExpr method (line 94) creates a RecurseT node only when the current type name has already been encountered in the traversal.

This design works for direct self-recursion—where a type constructor refers to itself with identical type parameters—but the implementation treats RecurseT as an atomic leaf. Once the prover encounters this node, it stops structural reasoning about the type's internals. According to the source code, this atomic treatment is a deliberate performance safeguard, but it prevents the engine from unfolding or analyzing recursive structures during proof search.

Critical Limitations of the Recursive Type System

Mutual Recursion Is Not Supported

The macro only recognizes recursion when it encounters the same type name twice in a single branch of the type tree. Mutually recursive types—where type A refers to type B and vice versa—never trigger the RecurseT creation logic.

In Macros.scala (lines 124-170), the sealed trait handling logic inspects direct subclasses to build a DisjunctT representation. However, when case classes B and C reference each other as members, the macro treats them as independent ConstructorT nodes. Without RecurseT markers, the theorem prover cannot detect the cyclic dependency required to generate inhabitants.

sealed trait A
case class B(x: C) extends A
case class C(y: B) extends A   // Mutual recursion between B and C

// This will not compile - the macro never produces a RecurseT for the cycle
def bad: A ⇒ A = implement   // ❌ Compilation fails

Higher-Kinded Recursive Constructors Are Rejected

CurryHoward cannot reason about type constructors that take recursive type constructors as parameters. The algorithm examines matchedTypeArgs but never descends into them to discover recursive occurrences of parameterized types.

In src/main/scala/io/chymyst/ch/TypeExpr.scala (line 48), the RecurseT definition lacks the machinery to track recursion through higher-kinded parameters. Consequently, fixed-point types like Fix[F[_]] are treated as plain ConstructorT instances rather than recursive structures.

type Fix[F[_]] = F[Fix[F]]
type Nat = Fix[Option]   // Recursive higher-kinded type

// Treated as ConstructorT, not RecurseT - no inhabitant generated
def nat: Nat = implement   // ❌ Fails to compile

Recursive Values Are Explicitly Filtered From Scope

Even when recursive values exist in the surrounding lexical scope, CurryHoward deliberately excludes them from the pool of available symbols to avoid exponential blow-up in the theorem prover.

In Macros.scala (line 65), the inhabitImpl method filters the symbol table before passing it to the prover. This means you cannot rely on an existing recursive function or value to help construct a new recursive implementation automatically.

Alpha-Conversion and Nested Recursion Performance Issues

The source code contains developer comments (lines 31-33 in Macros.scala) admitting that alpha-conversion for recursive type variables is only a "palliative" fix. This temporary measure may fail for deeper recursion levels or types requiring bound variable renaming during unification.

Additionally, each RecurseT occurrence forces the prover to treat the type as opaque. When dealing with nested recursion—such as recursively nested sums or products—the search space explodes combinatorially because the engine cannot use structural induction. The test suite in RecursiveTypesSpec.scala only covers shallow cases like List[A], confirming the library's limitations with complex recursive patterns.

Code Examples: What Works and What Fails

Working: Simple Self-Recursive Types

Standard single-parameter ADTs like List work because they trigger the typesSeen check and produce a valid RecurseT node.

def f[A]: List[A] ⇒ List[A] = implement
f(List(1, 2, 3))   // → List(1, 2, 3)

Failing: Explicit Non-Recursive Wrappers

Attempting to simulate recursion through type aliases or explicit wrappers does not circumvent the higher-kinded limitation.

sealed trait ListF[+A, +R]
case object NilF extends ListF[Nothing, Nothing]
case class ConsF[+A, +R](head: A, tail: R) extends ListF[A, R]

type MyList[A] = Fix[({ type λ[α] = ListF[A, α] })#λ]

// Still fails - the engine cannot unfold higher-kind fix-points
def myList[A]: MyList[A] ⇒ MyList[A] = implement   // ❌

Summary

• Direct self-recursion only: The macro creates RecurseT nodes exclusively for types that reference themselves, preventing support for mutual recursion between distinct types.
• Higher-kinded blind spot: Type constructors like Fix[F[_]] are treated as atomic ConstructorT instances, blocking inhabitants for recursive schemes (catamorphisms, anamorphisms).
• Scope exclusion: Recursive values are filtered from inhabitImpl (line 65) to prevent combinatorial explosion, limiting available proof terms.
• Structural opacity: RecurseT acts as a terminal node, preventing the prover from performing structural induction on nested recursive types.
• Alpha-conversion fragility: The current variable renaming implementation is acknowledged as temporary and unreliable for deep recursion.

Frequently Asked Questions

Can CurryHoward generate code for mutually recursive ADTs?

No. The buildTypeExpr logic in Macros.scala only detects recursion when it encounters the exact same type name twice in a single path. Mutually recursive types like case class B(c: C) and case class C(b: B) are processed as independent constructors without RecurseT markers, causing the prover to fail when attempting to generate inhabitants.

Why does Fix[Option] fail to compile with implement?

CurryHoward does not descend into type arguments of type constructors to detect recursive patterns. In TypeExpr.scala, the RecurseT definition handles direct type names but not higher-kinded parameters. Therefore, Fix[Option] is categorized as a plain ConstructorT rather than a recursive structure, and the prover cannot generate code for it.

Is there a workaround for recursive value generation?

No direct workaround exists within the automatic derivation. The inhabitImpl method explicitly removes recursive symbols from the available scope at line 65 of Macros.scala to prevent infinite loops during proof search. You must implement recursive functions manually or use non-recursive helper structures that curryhoward can inhabit.

Where is the recursion detection logic implemented?

The primary detection occurs in src/main/scala/io/chymyst/ch/Macros.scala within buildTypeExpr (line 94), which checks the typesSeen set to determine whether to create a RecurseT node. The definition of RecurseT itself resides in src/main/scala/io/chymyst/ch/TypeExpr.scala (line 48), while test coverage for supported recursive cases appears in src/test/scala/io/chymyst/ch/unit/RecursiveTypesSpec.scala.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}