How to Automatically Implement Scala Functions Using Type Signatures with Curry-Howard

The curryhoward library uses Scala macros to automatically generate function implementations from type signatures alone by applying the Curry-Howard correspondence at compile time.

Automatically implementing Scala functions using type signatures with Curry-Howard is made possible by the chymyst/curryhoward library, which embeds an automated theorem prover into the Scala compiler. By treating types as logical propositions and programs as proofs, the library generates runnable Scala code from purely declarative type signatures.

The Three-Layer Architecture of curryhoward

The implementation pipeline consists of three tightly integrated layers that transform a Scala Type into executable code.

Type-to-AST Translation

The first layer converts Scala reflection types into an internal representation called TypeExpr. In src/main/scala/io/chymyst/ch/Macros.scala, the method buildTypeExpr (line 48) traverses the compiler's c.Type structure, mapping function arrows to ConjunctT #->, case classes to NamedConjunctT, and sealed traits to DisjunctT.

Proof Search via Sequent Calculus

The second layer performs automated proof search using the LJT (Intuitionistic Sequent Calculus) system. In src/main/scala/io/chymyst/ch/TheoremProver.scala, the findProofs method (line 52) constructs a sequent Γ ⊢ τ and applies invertible and non-invertible rules from LJT.scala until a closed term is found. The prover scores proof terms by information loss and returns the minimal group.

Code Generation and Lambda Wrapping

The third layer emits Scala syntax trees. In Macros.scala, the returnTerm method (line 52) receives a TermExpr and uses emitTermCode to render it into a c.Tree. Curried functions are wrapped in concrete lambda classes (Function1Lambda, Function2Lambda, etc.) so the result behaves like native Scala functions.

Step-by-Step Implementation Flow

When you write implement[U] or ofType[U], the macro executes the following pipeline:

1. Macro Entry Point – The public API in src/main/scala/io/chymyst/ch/package.scala forwards implement calls to Macros.inhabitImpl and ofType calls to Macros.ofTypeImpl.

2. Type Detection – inhabitImpl inspects the enclosing definition via c.internal.enclosingOwner.typeSignature to obtain the target type U.

3. TypeExpr Construction – buildTypeExpr handles primitives, function arrows, case classes, and recursive types (filtering RecurseT to ensure termination).

4. Theorem Proving – TheoremProver.findProofs applies LJT rules recursively, combining sub-results via explode and selecting proofs with minimal information loss.

5. Code Emission – returnTerm generates the Scala AST, wrapping curried terms in appropriate lambda classes.

6. Splicing – The macro splices the generated tree back into the call site, producing a concrete implementation indistinguishable from hand-written code.

Practical Code Examples

Simple Identity Function

For a pure type signature with no external inputs, implement generates the obvious proof term:

def id[A]: A ⇒ A = implement

The macro infers U = A ⇒ A, builds ConjunctT(A) #-> ConjunctT(A), finds the trivial proof λx. x, and emits a Function1Lambda wrapping the identity function.

Function Composition with Existing Values

Use ofType to supply existing values as premises for the proof search:

val f: Int ⇒ String = _.toString
val g: String ⇒ Boolean = _.nonEmpty

def compose: Int ⇒ Boolean = ofType[Int ⇒ Boolean](f, g)

The prover receives f and g as available terms in context Γ, builds the sequent f: Int⇒String, g: String⇒Boolean ⊢ Int⇒Boolean, and constructs the term x => g(f(x)).

Enumerating All Implementations

When multiple proofs exist, allOfType returns every minimal implementation:

val all: Seq[Option[Int] ⇒ Option[Int]] = allOfType[Option[Int] ⇒ Option[Int]]

This triggers Macros.allOfTypeImpl, which enumerates all proof terms with minimal information loss, such as the identity function and the map application, returning them as a Seq for inspection.

Working with Case Classes

Case classes are automatically decomposed into conjunctive types:

case class Pair[A, B](a: A, b: B)

def makePair[A, B]: (A, B) ⇒ Pair[A, B] = implement

The macro recognizes Pair as a NamedConjunctT and constructs the proof term λx. λy. Pair(x, y) directly.

Handling Recursive Types Safely

Recursive types are detected and filtered to prevent infinite proof search:

sealed trait ListF[+A]
case object NilF extends ListF[Nothing]
case class ConsF[+A](head: A, tail: ListF[A]) extends ListF[A]

def listIdentity[A]: ListF[A] ⇒ ListF[A] = implement

The prover filters out RecurseT occurrences during the search phase, ensuring termination while still generating a correct recursive implementation.

Key Source Files in the Repository

File	Role
src/main/scala/io/chymyst/ch/package.scala	Public API exposing implement, ofType, allOfType, typeExpr, and freshVar
src/main/scala/io/chymyst/ch/Macros.scala	Core macro implementation including buildTypeExpr, inhabitImpl, ofTypeImpl, and returnTerm
src/main/scala/io/chymyst/ch/TheoremProver.scala	LJT proof search, sequent construction, and proof scoring via findProofs
src/main/scala/io/chymyst/ch/LJT.scala	Sequent calculus rule definitions (invertible and non-invertible)
src/main/scala/io/chymyst/ch/TermExpr.scala	Algebraic data type for proof terms (lambda, application, case analysis)
src/main/scala/io/chymyst/ch/TypeExpr.scala	Internal type representation system

Summary

• Curry-Howard correspondence enables the curryhoward library to treat Scala types as logical propositions and programs as proofs.
• Three-phase pipeline: Type-to-AST translation (Macros.buildTypeExpr), LJT proof search (TheoremProver.findProofs), and Scala code generation (Macros.returnTerm).
• Public API: Use implement for direct synthesis, ofType to supply existing values as premises, and allOfType to enumerate all possible implementations.
• Compile-time execution ensures generated code is type-safe and indistinguishable from hand-written Scala functions.

Frequently Asked Questions

What is the Curry-Howard correspondence in the context of Scala programming?

The Curry-Howard correspondence is a direct relationship between formal logic and type systems where propositions correspond to types and proofs correspond to programs. In the curryhoward library, this means a Scala type signature like A ⇒ B is treated as the logical implication "if A then B," and the library searches for a proof term that inhabits this type, automatically generating the corresponding Scala function implementation.

How does the library prevent infinite loops when dealing with recursive types?

The library detects recursive type occurrences during the buildTypeExpr phase and filters them out during proof search. Specifically, when TheoremProver.findProofs encounters a RecurseT node, it excludes these occurrences from the active search space. This ensures the LJT proof search terminates while still allowing the generation of correct recursive implementations, as demonstrated with the ListF example where recursive identity functions are synthesized safely.

What is the difference between implement and ofType in the public API?

implement synthesizes a function from its type signature alone, requiring no additional inputs. It inspects the enclosing method's return type using c.internal.enclosingOwner.typeSignature and generates the proof term automatically. In contrast, ofType allows you to provide existing values as premises to the theorem prover. You pass these values as arguments (e.g., ofType[Int ⇒ Boolean](f, g)), and the prover includes them in the context Γ when searching for a proof, enabling function composition and reuse of existing implementations.

Can the library generate multiple different implementations for the same type?

Yes, the allOfType method enumerates all inequivalent implementations with minimal information loss. When invoked, it triggers Macros.allOfTypeImpl, which calls the theorem prover to find all proof terms that satisfy the type. The prover scores terms by information loss and returns the minimal group, allowing you to inspect different valid implementations. For example, allOfType[Option[Int] ⇒ Option[Int]] returns both the identity function and mapping operations, giving you a sequence of alternative implementations to choose from.

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