How to Resolve Compile-Time Errors When Multiple CurryHoward Implementations Have Equal Information Loss

When CurryHoward's theorem prover finds multiple proof terms with identical information-loss scores, the macro aborts with a compile-time error that can be resolved by making types more specific, providing literal arguments, or using allOfType to retrieve all implementations.

The curryhoward library by chymyst uses macro-based helpers like implement and ofType to automatically synthesize Scala code through Curry-Howard correspondence. When you request an implementation, the library's theorem prover ranks all possible proofs using an information-loss heuristic—but when multiple candidates share the same minimal score, the macro fails with a compile-time ambiguity error.

Understanding the Information-Loss Heuristic

How the Theorem Prover Ranks Implementations

In src/main/scala/io/chymyst/ch/TheoremProver.scala, the findProofs method (lines 69-75) generates all possible proof terms for the requested type. Each candidate receives an information-loss score calculated by TermExpr.informationLossScore in src/main/scala/io/chymyst/ch/TermExpr.scala. This score measures:

• How many function arguments remain unused
• How many tuple parts are discarded
• Structural mismatches via unequalTupleSize and unusedArgs

The prover retains only the group of terms with the smallest score.

When Equal Scores Trigger Compile-Time Failures

If multiple terms share the minimal score, the inhabitInternal method (lines 22-33 in TheoremProver.scala) cannot deterministically select a winner. According to the source code, the macro aborts compilation and reports the ambiguous implementations with their identical scores.

Identifying the Root Cause of Ambiguity Errors

The compile-time error message follows this pattern:

type X ⇒ A ⇒ X ⇒ X can be implemented in 2 inequivalent ways:
  λx.λa.λx2.x   [score: 0.0];
  λx.λa.λx2.x   [score: 0.0].

This occurs in src/test/scala/io/chymyst/ch/unit/ApiSpec.scala (lines 83-86), which demonstrates the failure case. The ambiguity arises when:

• Two arguments share the same type and are interchangeable (e.g., X appears multiple times in the type signature)
• Unused arguments or tuple components can be discarded in multiple equivalent ways

Strategies to Resolve Equal Information-Loss Ambiguities

Make Types More Specific

Replace generic type parameters with concrete types to give the prover a unique shape. In ApiSpec.scala, the ambiguous generic signature:

def f1[X, A, B]: X ⇒ A ⇒ X ⇒ X = implement   // compile-time error

Becomes resolvable when specialized:

def f1Concrete: Int ⇒ String ⇒ Int ⇒ Int = implement   // compiles

Provide Literal Arguments with ofType

Supply concrete values to break symmetry. The ofTypeImplWithValues method in src/main/scala/io/chymyst/ch/Macros.scala (lines 83-101) accepts literal arguments that the macro uses to fix specific parameters:

def f1WithValue = ofType[Int ⇒ String ⇒ Int ⇒ Int](42)   // compiles

This eliminates ambiguity by grounding one of the Int parameters to the value 42.

Use allOfType to Retrieve All Implementations

When you need every valid proof, use allOfType instead of implement. The allOfTypeImplWithValues method (lines 104-112 in Macros.scala) returns a Seq[U] containing all minimal-score implementations:

val allF1 = allOfType[Int ⇒ String ⇒ Int ⇒ Int]   // returns Seq[Int ⇒ String ⇒ Int ⇒ Int]
val chosen = allF1.head   // manually select the first implementation

This bypasses the single-selection requirement entirely.

Refactor to Eliminate Unused Arguments

Remove arguments that are never referenced in the type structure. If your type signature contains unused parameters that create symmetrical discard patterns, simplify the type to remove the ambiguity source.

Advanced: Custom Information-Loss Hints

For fine-grained control, modify how the prover calculates loss scores. The TermExpr class in src/main/scala/io/chymyst/ch/TermExpr.scala (lines 271-285) exposes unequalTupleSize and unusedArgs penalties. Adjusting these values biases the search toward specific term structures, though this requires recompiling the library with modified heuristics.

Summary

• CurryHoward's implement macro selects proofs using an information-loss heuristic that minimizes unused arguments and discarded tuple parts.
• When multiple proofs share the same minimal score, TheoremProver.inhabitInternal aborts with a compile-time ambiguity error.
• Resolve these errors by:
  • Making types concrete to eliminate interchangeable generic arguments
  • Providing literal values via ofType to break symmetry
  • Retrieving all implementations with allOfType for manual selection
  • Refactoring types to remove unused arguments that create ambiguity

Frequently Asked Questions

What does "information loss" mean in CurryHoward?

Information loss measures how much data a proof term discards. The TermExpr.informationLossScore method calculates penalties for unused function arguments (unusedArgs) and discarded tuple components (unequalTupleSize). A lower score indicates a more "efficient" implementation that preserves more input data.

Why does CurryHoward refuse to compile when implementations are equally optimal?

The library guarantees deterministic code generation. When TheoremProver.findProofs identifies multiple terms with identical minimal information-loss scores, inhabitInternal cannot arbitrarily choose between them without violating determinism. Instead, it reports the ambiguity as a compile-time error in src/main/scala/io/chymyst/ch/TheoremProver.scala (lines 22-33).

Can I disable the information-loss heuristic?

No, the heuristic is fundamental to the theorem prover's operation in src/main/scala/io/chymyst/ch/TheoremProver.scala. However, you can bypass single-selection failures by using allOfType, which returns all minimal-score implementations as a sequence, allowing you to apply your own selection logic.

How do I choose between multiple valid implementations manually?

Use allOfType[T] to retrieve a Seq[T] containing every proof with the minimal information-loss score. For example, val implementations = allOfType[Int ⇒ String ⇒ Int ⇒ Int] returns all valid functions. You can then select by index (implementations.head), apply a custom filter, or present the options to the user for manual choice.

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