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

> Learn how to automatically implement Scala functions using type signatures with the Curry-Howard library. Effortlessly generate code from types at compile time.

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

---

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

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

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

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

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

```scala
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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/LJT.scala) | Sequent calculus rule definitions (invertible and non-invertible) |
| [`src/main/scala/io/chymyst/ch/TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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.