How Information Loss Heuristics Work in CurryHoward for Implementation Selection

CurryHoward ranks generated Scala implementations using a five-component lexicographic tuple called the information loss score, preferring proof terms that discard fewer arguments, waste fewer tuple parts, and minimize runtime permutations.

CurryHoward is a Scala library that synthesizes implementations of type expressions through automated theorem proving. When the prover discovers multiple valid proof terms for a given type, it must select the most desirable one to emit as code. The library solves this selection problem using information loss heuristics that quantify how much structural information each candidate implementation discards.

What Are Information Loss Heuristics?

In CurryHoward, every generated proof term is represented as a TermExpr that can be converted into executable Scala code. When multiple implementations exist for a type, the library ranks them by assigning each TermExpr an information loss score—a tuple of integers that measures undesirable properties like unused arguments, wasted tuple components, and argument duplication. Lower scores indicate better implementations. This heuristic is implemented in src/main/scala/io/chymyst/ch/TermExpr.scala.

How the Information Loss Score Is Calculated

The informationLossScore method in TermExpr.scala constructs a five-component tuple. Each component penalizes specific inefficiencies, and the tuple is compared lexicographically, meaning earlier components dominate the ordering.

Component 1: Unused Arguments

The most significant factor is the count of function arguments that never appear in the term body. The unusedArgs method in TermExpr.scala (lines 27-35) identifies these, and the score's first element is unusedArgs(this).size. An implementation that ignores an input parameter receives a higher penalty than one that uses all arguments but wastes some tuple parts.

Component 2: Unused Tuple Parts and Match Variables

The second component penalizes tuple components that are never accessed and match-clause variables that go unused. It combines unusedTupleParts and unusedMatchClauseVars, then applies roundFactor (which multiplies by 10,000 and rounds to an integer) to maintain integer tuple comparison.

Component 3: Permutation Penalties

The third component discourages implementations that require expensive runtime reordering of conjunctions or disjunctions. It sums conjunctionPermutationScore and disjunctionPermutationScore, then applies roundFactor. This favors implementations that use tuple elements in their natural order and avoid swapping arguments.

Components 4 and 5: Argument Reuse Counts

The final two components count how many times arguments are reused, distinguishing between shallow and deep usage. Component 4 uses argsMultiUseCountShallow(this) to count arguments used more than once directly as arguments. Component 5 uses argsMultiUseCountDeep(this) to count reuse deeper inside the term, such as through currying. Both prefer implementations that use each argument exactly once.

The Selection Algorithm in TheoremProver

The ranking logic resides in src/main/scala/io/chymyst/ch/TheoremProver.scala. The findProofs method enumerates all proof terms for a type, then groups them by their informationLossScore:

val chosenTerms = allTermExprs
  .groupBy(_.informationLossScore)
  .toSeq.sortBy(_._1)
  .headOption.map(_._2.toList).getOrElse(List())

This groups candidates by their five-component score, sorts lexicographically, and selects the lowest-scoring group. If exactly one term exists in this group, Macros.inhabitOneInternal returns it as the definitive implementation. If multiple terms share the lowest score, the macro reports an ambiguity error.

Using Information Loss Heuristics in Practice

The public API exposes these heuristics through two macro entry points in src/main/scala/io/chymyst/ch/Macros.scala:

• allOfTypeImpl[U] – Returns the single best implementation according to the information loss score, failing at compile time if the heuristic cannot identify a unique winner.
• anyOfTypeImpl[U] – Returns all valid implementations ordered by information loss score (lowest first).

Both delegate to inhabitAllInternal, which controls whether to return only the lowest-scoring group or all proof terms.

import io.chymyst.ch._

// Request the best implementation (fails if ambiguous)
val best = allOfTypeImpl[Option[Int] => List[Int]]

// Request all implementations, ordered by score
val all = anyOfTypeImpl[Option[Int] => List[Int]]

For debugging, you can inspect the scores directly using the internal API:

def showScores[T: c.WeakTypeTag]: Unit = {
  val t = buildTypeExpr(c.weakTypeOf[T])
  val (best, all) = TheoremProver.findProofs(t)
  println("Best score: " + best.headOption.map(_.informationLossScore))
  all.foreach(t => println(s"${t.prettyRenamePrint} → ${t.informationLossScore}"))
}

Running this prints tuples like (0,0,0,0,0) for optimal implementations that waste no arguments, tuple parts, or permutations.

Summary

• CurryHoward ranks generated implementations using a five-component information loss score that penalizes unused arguments, wasted tuple parts, expensive permutations, and argument reuse.
• The score is calculated in TermExpr.scala and compared lexicographically, with unused arguments being the most significant factor.
• TheoremProver.findProofs groups candidates by score and selects the lowest-scoring group as the best implementations.
• The public macros allOfTypeImpl and anyOfTypeImpl expose this heuristic to users, providing either the single best implementation or all candidates ordered by information loss.

Frequently Asked Questions

What happens if two implementations have the same information loss score?

If multiple proof terms share the identical lowest score, allOfTypeImpl will fail at compile time with an ambiguity error. The library expects the information loss heuristic to identify a unique best implementation. You can use anyOfTypeImpl to retrieve all candidates with the lowest score and manually select one.

Why are unused arguments weighted more heavily than tuple part waste?

Unused arguments occupy the first position in the lexicographic tuple, making them the primary sorting key. This reflects the design principle that a function ignoring its inputs is more "lossy" than one that uses all inputs but discards some tuple components. The ordering ensures that fully utilized argument lists are preferred before considering tuple efficiency.

Can I customize the information loss heuristic to prefer different trade-offs?

The current implementation in TermExpr.scala uses a fixed five-component tuple with hardcoded weights. While you cannot override the heuristic through the public API, you can fork the library and modify the informationLossScore method to adjust component ordering or add new penalties. The roundFactor multiplier (10,000) can also be tuned to change the granularity of non-integer penalties.

How does the permutation penalty affect real-world code generation?

The permutation penalty (component 3) discourages implementations that reorder tuple elements or swap disjuncts in case statements. In generated Scala code, this favors patterns like case (a, b) => f(a, b) over case (b, a) => f(a, b) that would require runtime swapping. This produces more idiomatic, efficient code that follows the natural structure of the input types.

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