# How Information Loss Heuristics Work in CurryHoward for Implementation Selection

> Discover how CurryHoward ranks Scala implementations using its information loss score. Learn how to prefer proof terms that discard fewer arguments and minimize runtime permutations for better selection.

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

---

**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`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TermExpr.scala).

## How the Information Loss Score Is Calculated

The `informationLossScore` method in [`TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TheoremProver.scala). The `findProofs` method enumerates all proof terms for a type, then groups them by their `informationLossScore`:

```scala
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`](https://github.com/chymyst/curryhoward/blob/main/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.

```scala
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:

```scala
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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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.