# Performance Implications of Compile-Time Theorem Proving in curryhoward

> Explore compile-time theorem proving performance in curryhoward. Understand Scala compilation costs and how heuristics manage exponential complexity for efficient type checking.

- Repository: [Chymyst/curryhoward](https://github.com/chymyst/curryhoward)
- Tags: performance
- Published: 2026-02-27

---

**Compile-time theorem proving in curryhoward adds a cost proportional to type complexity during Scala compilation, with exponential worst-case search complexity mitigated by heuristics that cap intermediate terms between 1,024 and 1,048,576.**

The curryhoward library brings automated theorem proving to Scala through compile-time code generation. By leveraging Scala macros, the library performs proof search during compilation to generate implementations of requested types. While this eliminates boilerplate, the compile-time theorem proving process introduces performance considerations that scale with the complexity of the target type.

## How Compile-Time Theorem Proving Works in curryhoward

When a user writes `implement` or `ofType`, the Scala macro expands into a call to the **TheoremProver** that searches for a proof term of the requested type. This proof search is performed **during compilation**, so its cost adds directly to the overall compile time.

In [`src/main/scala/io/chymyst/ch/Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Macros.scala), the macro entry points `inhabitImpl`, `ofTypeImpl`, and `allOfTypeImpl` wrap the prover and then generate Scala code via `emitTermCode`. While the code-generation phase is cheap, the dominant cost is the prover itself, specifically the `findTermExprs` method in [`TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/TheoremProver.scala) at line 79.

## Performance Characteristics and Complexity

### Exponential Search Space

The `findTermExprs` method performs a **depth-first proof search** that recursively explores all applicable inference rules for a given `Sequent`. In the worst case, this creates an exponential blow-up when many premises exist or when rules are ambiguous. Each branch of the search tree represents a potential proof path that must be explored until a valid term is found or the path is pruned.

### Heuristic Safeguards

To prevent exponential explosion, curryhoward implements several safeguards in [`TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/TheoremProver.scala). The `maxTermsToSelect` heuristic (lines 13-17) caps the number of intermediate terms kept after each rule application. The bounds are set between **1,024 and 1,048,576**, scaled by the number of premises. This prevents the search space from exploding and drastically limits both memory use and CPU time.

## Architectural Safeguards That Control Compile Time

The library employs multiple architectural strategies to keep compile-time theorem proving practical:

- **Depth-first proof search** (`findTermExprs`): Explores inference rules recursively. While potentially exponential, it is bounded by the term pruning heuristic.

- **Heuristic term pruning** (`maxTermsToSelect`): Caps intermediate terms between 1,024 and 1,048,576, preventing memory explosion during complex proofs.

- **Information-loss scoring** (`informationLossScore`): Each `TermExpr` receives a score, and only the lowest-scoring group is returned as the best implementation. This allows early discarding of sub-optimal terms, reducing comparison overhead.

- **Caching of proved sequents** (`sequentsAlreadyProved`): Memorizes terms already found for a given `Sequent`, ensuring repeated sub-goals are resolved via O(1) look-ups rather than recomputation.

- **Loop detection** (`sequentsAlreadyRequested`): Detects cyclic search paths (such as recursive types) and aborts them early, preventing infinite recursion that would otherwise hang the compiler.

- **Debug options** (`curryhoward.log`): When enabled in [`Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/Macros.scala) (lines 96-102), prints diagnostic information. While useful for development, this increases compile time due to string building and console I/O.

## Practical Compile-Time Benchmarks

The following table illustrates typical compile-time behavior for different type complexities:

| Example | Type to implement | Approx. compile time (sbt) |
|---------|-------------------|----------------------------|
| `def id[A]: A ⇒ A = implement` | Simple identity function | < 10 ms |
| `def listFlatMap[A,B]: List[A] ⇒ (A ⇒ List[B]) ⇒ List[B] = implement` | Higher arity, list operations | ~ 30 ms |
| `def gadtChoice[A,B]: Either[A, A ⇒ B] ⇒ B = implement` | Ambiguous invertible rules | ~ 150 ms |
| `def complex[N,I]: User[N,I] ⇒ Int = implement` (nested GADTs) | Deep recursive structure | 0.5 – 1 s |

These timings depend on JVM warm-up, available cores, and whether heuristics prune aggressively. The dominant factor is the complexity of the proof search required by the type structure.

## When Compile-Time Theorem Proving Becomes a Bottleneck

Certain scenarios can cause compile-time theorem proving to become a bottleneck:

- **Very large sealed-trait hierarchies**: Each subclass creates a separate branch in the proof search, multiplying the search space.
- **Highly ambiguous invertible rules** (`invertibleAmbiguousRules`): These generate multiple new sequents per rule application, causing an explosion before pruning can occur.
- **Recursive types**: Although filtered (via `filterNot(v ⇒ … RecurseT…)`) to keep search tractable, deep recursion can still produce many intermediate sequents.

The library mitigates these through term-selection heuristics, loop detection, and hard caps on intermediate terms.

## Optimization Strategies for Users

### Keep Types Small

When using `implement` inside frequently compiled modules, prefer smaller, composable types over large, monolithic ones. This reduces the branching factor in `findTermExprs`.

### Enable Incremental Compilation

SBT's incremental compilation re-uses already-generated class files, so the prover runs only when source changes. Ensure your build is configured to take advantage of this.

### Toggle Diagnostics Off

In production builds, avoid setting `-Dcurryhoward.log=` to prevent the overhead of string building and console I/O in [`Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/Macros.scala).

### Supply Explicit Arguments

Instead of relying solely on `implement`, use `ofType` with concrete values to avoid deep search:

```scala
import io.chymyst.ch._

val list = List(1, 2, 3)

def getHead: Int = ofType[Int] (list)

```

Here, `ofTypeImplWithValues` receives the concrete value `list` and builds the type structure `List[Int] → Int`. Because the argument value is known, the prover does not need to search for a `List[Int]` generator—it directly composes `list.head`. Compile time drops to the same order as the simple identity example.

## Summary

- **Compile-time theorem proving** in curryhoward performs proof search during Scala compilation via macros, adding cost proportional to type complexity.
- The **depth-first search** in `TheoremProver.findTermExprs` can exhibit exponential blow-up in the worst case.
- **Heuristic safeguards** including `maxTermsToSelect` (capping terms between 1,024 and 1,048,576), information-loss scoring, and caching of proved sequents keep compile times practical.
- **Bottlenecks** occur with large sealed-trait hierarchies, ambiguous invertible rules, and deep recursive types.
- Users can optimize by keeping types small, using `ofType` with explicit arguments, and disabling debug logging in production builds.

## Frequently Asked Questions

### How does curryhoward's compile-time theorem proving affect build times?

The proof search runs during the Scala macro expansion phase, so it adds directly to compilation time. For simple types like `A ⇒ A`, the impact is negligible (<10 ms), but complex GADTs or deeply nested types can add 0.5–1 seconds per invocation. The library mitigates this through aggressive pruning heuristics that limit intermediate terms.

### What is the `maxTermsToSelect` heuristic and why does it matter?

`maxTermsToSelect` is a safeguard in [`TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/TheoremProver.scala) (lines 13-17) that caps the number of intermediate terms retained after each inference rule application. It scales between 1,024 and 1,048,576 based on premise count. This prevents exponential explosion of the search space, ensuring that memory usage and CPU time remain bounded even for ambiguous types.

### Can recursive types cause the compiler to hang?

No, because `TheoremProver` implements loop detection via `sequentsAlreadyRequested` (lines 50-52 in [`TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/TheoremProver.scala)). This detects cyclic search paths and aborts them early. However, recursive types can still generate many intermediate sequents before being filtered, potentially slowing compilation. Users can supply explicit values via `ofType` to avoid deep search for recursive structures.

### How can I minimize compile-time overhead when using `implement`?

Keep target types small and composable rather than monolithic. Use `ofType` with concrete arguments instead of `implement` when possible, as this avoids searching for value generators. Ensure debug logging is disabled (`-Dcurryhoward.log=`) in production builds, and rely on SBT's incremental compilation to avoid re-running the prover for unchanged sources.