How CurryHoward Handles Tuples and Functions with Arity Greater Than 2

CurryHoward represents both tuples and multi-argument functions in a curried normal form, encoding tuples as named conjunctions (NamedConjunctE) and functions with arity greater than 2 as nested CurriedE terms that store a list of bound variables and a body expression.

The chymyst/curryhoward library implements the Curry-Howard correspondence for Scala, automatically generating proof terms for type signatures. Understanding how curryhoward handles tuples and functions with arity greater than 2 is essential for debugging generated code and optimizing proof search heuristics. The library normalizes all arities through currying and named conjunctions, maintaining a uniform term language regardless of argument count.

Tuple Representation via Named Conjunctions

NamedConjunctT and NamedConjunctE Encoding

In src/main/scala/io/chymyst/ch/TypeExpr.scala, tuple types are represented as NamedConjunctT, a case-class-like type constructor. When constructing a tuple term, TypeExpr.apply creates a NamedConjunctE that stores the component values.

// TypeExpr.apply creates a tuple term from a NamedConjunctT
// → NamedConjunctE(args, nct)               // src/main/scala/io/chymyst/ch/TypeExpr.scala#L15-L22

The concrete term that stores the tuple values is a NamedConjunctE (see the case class definition in src/main/scala/io/chymyst/ch/TermExpr.scala at lines 714-718).

Accessing Components with ProjectE

Individual tuple elements are accessed via ProjectE defined in src/main/scala/io/chymyst/ch/TermExpr.scala. The projection extracts the i-th component from the wrapped list inside NamedConjunctE.

// ProjectE(index, term) extracts the i-th part of a tuple
// → term.t match { case NamedConjunctT(_, _, _, wrapped) ⇒ wrapped(index) }  // src/main/scala/io/chymyst/ch/TermExpr.scala#L44-L52

Tuple Usage Statistics for Proof Optimization

The implementation tracks unusedTupleParts and usedTuplePartsSeq to calculate informationLossScore, guiding the LJT proof search heuristics. This addresses the limitation that Ordering is undefined on tuples with more than 9 elements (see the comment "Need to split the tuple into parts because Ordering[] is undefined on tuples > 9" in src/main/scala/io/chymyst/ch/TermExpr.scala at lines 48-50).

Curried Representation for Functions with Arity Greater Than 2

The CurriedE Case Class

Multi-argument functions normalize to CurriedE(heads: List[VarE], body: TermExpr) in src/main/scala/io/chymyst/ch/TermExpr.scala. The heads list contains bound variables for each argument, and the type is constructed by folding left-to-right over reversed heads.

final case class CurriedE(heads: List[VarE], body: TermExpr) extends TermExpr   // src/main/scala/io/chymyst/ch/TermExpr.scala#L682-L687

Applying Arguments with applyCurried

The helper method applyCurried in TermExpr.scala handles application of curried functions to multiple arguments sequentially, using AppE nodes for each application step.

// Apply this curried function to a number of arguments at once.
def applyCurried(curriedFunction: TermExpr, args: Seq[TermExpr]): TermExpr =
  args.foldLeft[TermExpr](curriedFunction) { case (prev, arg) ⇒ AppE(prev, arg) }   // src/main/scala/io/chymyst/ch/TermExpr.scala#L99-L102

AppE creates a regular application node; repeated folding yields the fully applied term.

Integration with Proof Search

The curried representation integrates deeply with the proof engine. Sequent.substituteInto uses applyCurried to instantiate premises (see src/main/scala/io/chymyst/ch/Sequent.scala at lines 16-17), while src/main/scala/io/chymyst/ch/LJT.scala constructs curried terms during proof building at lines 121, 155, 241, 376, and 378.

Interaction Between Tuples and Multi-Argument Functions

When a function expects a tuple as a single argument, the system uses NamedConjunctE directly. For multiple distinct arguments, CurriedE represents the function, and ProjectE can extract tuple components to feed into curried functions. This unified approach allows the prover to treat argument groups consistently regardless of whether they are packaged as tuples or separate parameters.

import io.chymyst.ch._

// 1️⃣ Tuple (named conjunction) -------------------------------------------------
case class Pair[A, B](a: A, b: B)               // a case class becomes a NamedConjunctT
val pairType: TypeExpr = NamedConjunctT("Pair",
  List(TP("A"), TP("B")), List("a", "b"), List(TP("A"), TP("B")))

val tup: TermExpr = pairType.apply(VarE("x", TP("A")), VarE("y", TP("B"))) // → NamedConjunctE(...)
println(tup.prettyPrint)   // Pair(x, y)

// Project the first component
val fst = tup.apply(0)      // same as ProjectE(0, tup)
println(fst.prettyPrint)   // x

// 2️⃣ Multi‑argument function (arity > 2) ---------------------------------------
val tA = TP("A"); val tB = TP("B"); val tC = TP("C")
val fBody = VarE("x", tA) ->: VarE("y", tB) ->: VarE("z", tC) ->: VarE("x", tA) // λx.λy.λz. x
val curriedF = CurriedE(List(VarE("x", tA), VarE("y", tB), VarE("z", tC)), fBody)

// Apply three arguments at once
val applied = TermExpr.applyCurried(curriedF,
  Seq(VarE("p", tA), VarE("q", tB), VarE("r", tC)))
println(applied.prettyPrint) // (p q r) → p

// 3️⃣ Function taking a tuple as a single argument -----------------------------
val gBody = VarE("t", pairType) ->: VarE("t", pairType).apply(0) // λt. fst(t)
val curriedG = CurriedE(List(VarE("t", pairType)), gBody)

val result = TermExpr.applyCurried(curriedG, Seq(tup))
println(result.prettyPrint)   // fst(Pair(x, y))  → x

Summary

• CurryHoward normalizes all tuples to NamedConjunctE terms and NamedConjunctT types, with component access via ProjectE.
• Functions with arity greater than 2 are represented as CurriedE containing a list of bound variables (heads) and a body expression.
• The applyCurried helper method chains AppE applications to fully instantiate curried functions.
• Proof search integration in Sequent.scala and LJT.scala relies on these representations to build valid proof terms.
• Tuple usage statistics (unusedTupleParts, informationLossScore) guide heuristics in the LJT prover, addressing Scala's Ordering limitations on large tuples.

Frequently Asked Questions

How does curryhoward represent a Scala function with three arguments?

It converts the function to a CurriedE term containing three bound variables in the heads list. The type is constructed by nesting function arrows right-associatively, effectively representing A => B => C => D internally while preserving the association between variables and their types.

What is the difference between NamedConjunctE and CurriedE in curryhoward?

NamedConjunctE represents product types (tuples) where all components exist simultaneously as a single value, while CurriedE represents functions where arguments are applied sequentially. A tuple is a single value containing multiple accessible parts via ProjectE, whereas a curried function is a chain of single-argument functions built via applyCurried.

How does the library handle tuple projection for large arities?

The ProjectE class extracts components by index from the wrapped list inside NamedConjunctE. For tuples with more than nine elements, the implementation avoids Scala's built-in Ordering limitation by tracking usage statistics (unusedTupleParts) to calculate informationLossScore, which guides proof search heuristics without requiring lexicographic ordering comparisons.

Where does the proof search engine construct curried terms?

The LJT prover in src/main/scala/io/chymyst/ch/LJT.scala constructs CurriedE terms at lines 121, 155, 241, 376, and 378 during proof building. Additionally, Sequent.substituteInto in src/main/scala/io/chymyst/ch/Sequent.scala uses applyCurried to instantiate premises with found proof terms, ensuring consistent handling of multi-argument functions throughout the proof search process.

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