# How CurryHoward Converts STLC Terms into Scala Code via Macros

> Learn how CurryHoward converts STLC terms to Scala code using macros. Discover compile-time type expression building, LJT proofs, and Scala AST emission.

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

---

**CurryHoward's `implement` and `ofType` macros convert Simply-Typed Lambda Calculus (STLC) terms into Scala code at compile time by building type expressions, proving inhabitation via LJT sequent calculus, and emitting Scala ASTs.**

The [chymyst/curryhoward](https://github.com/chymyst/curryhoward) library leverages **Scala macros** to automatically generate implementations for purely functional interfaces. By exploiting the **Curry-Howard correspondence**, it converts STLC terms into Scala code via macros, enabling compile-time synthesis of programs from their types. This article examines the exact pipeline—from type inspection to AST emission—using the actual source code architecture.

## The Five-Stage Compilation Pipeline

The macro expansion follows a rigorous five-stage process that transforms a requested type into executable Scala code:

1.  **Type Inspection**: The macro retrieves the weak Scala type `U` using `c.weakTypeOf[U]`.
2.  **TypeExpr Construction**: The type is recursively analyzed and converted into a lambda calculus representation (`TypeExpr`).
3.  **Proof Search**: The **LJT sequent calculus** searches for a proof that the type is inhabited.
4.  **Term Extraction**: A lambda term (`TermExpr`) witnessing the proof is constructed.
5.  **AST Emission**: The lambda term is translated into a Scala abstract syntax tree (`c.Tree`) and spliced into the source.

This pipeline is implemented across three core files that handle distinct phases of the transformation.

## Core Source Files and Entry Points

The implementation is split between macro definitions, type analysis, and theorem proving:

-   **[`src/main/scala/io/chymyst/ch/package.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/package.scala)** (lines 28-30): Declares the public API methods `implement`, `ofType`, and `freshVar`, delegating expansion to the macro engine via `def implement[U]: U = macro Macros.inhabitImpl[U]`.

-   **[`src/main/scala/io/chymyst/ch/Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Macros.scala)** (lines 357-429): Contains the macro implementation logic, including `inhabitImpl`, the `buildTypeExpr` helper, and the `emitTermCode` translator.

-   **[`src/main/scala/io/chymyst/ch/TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TheoremProver.scala)** (lines 18-34 and 52-76): Houses the proof search engine with `inhabitInternal` and `findProofs`, which applies the LJT calculus to derive `TermExpr` values.

-   **[`src/main/scala/io/chymyst/ch/TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TermExpr.scala)**: Defines the algebraic data types representing lambda terms (e.g., `VarE`, `AppE`, `CurriedE`, `MatchE`).

## Building Type Expressions from Scala Types

When a user invokes `implement`, the macro first constructs a lambda calculus mirror of the Scala type. In [`Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/Macros.scala), the `buildTypeExpr` method (around lines 63-71) recursively traverses the Scala `c.Type` tree.

This conversion handles:
-   **Function types** (`A => B`) mapped to implication (`->:`).
-   **Case classes** and **sealed traits** representing product and sum types.
-   **Generic parameters** and Java-style tuples.

The result is a `TypeExpr` value that the theorem prover can manipulate using logical rules.

## Proof Search with LJT Sequent Calculus

The `TheoremProver.inhabitInternal` method (lines 18-34) initiates the proof search using the **LJT sequent calculus**, a variant of intuitionistic logic. The algorithm implemented in `findProofs` and `findTermExprs` (lines 52-76) attempts to construct a derivation for the judgment `Γ ⊢ A`.

The search strategy applies:
-   **Invertible rules** first to simplify the goal without branching.
-   **Ambiguous choices** only when necessary.
-   **Axiom rules** to terminate derivation with variables or provided terms.

If a unique "best" proof exists, the prover returns a `TermExpr`—a lambda term that represents the computational content of the proof.

## Translating Lambda Terms to Scala ASTs

Once a `TermExpr` is synthesized, `Macros.returnTerm` delegates to `emitTermCode` (lines 59-124) to perform the back-translation. This function pattern matches on the term structure:

-   `VarE` generates variable references.
-   `AppE` generates function application trees.
-   `CurriedE` generates lambda abstractions (`q"(${TermName(...)} : $t) => $body"`).
-   `MatchE` generates pattern matching expressions.

The nested `LiftedAST` object (lines 176-188) provides **Liftable** instances that allow the macro to embed `TermExpr` values directly as Scala AST literals using quasiquotes (`q"..."`). The final `c.Tree` is returned to the compiler, which splices it into the call site as if the programmer had written the expression manually.

## Practical Examples of Macro Expansion

### Identity Function Synthesis

```scala
def id[A]: A => A = implement

```

The macro expands this to:

```scala
def id[A]: A => A = (x: A) => x

```

Internally, the type `A => A` becomes `BasicT("A") ->: BasicT("A")`, the LJT `Id` rule applies immediately, and `emitTermCode` generates the eta-expanded identity lambda.

### Reusing Provided Values with `ofType`

```scala
val inc: Int => Int = x => x + 1
val double: Int => Int = ofType[Int => Int](inc)

```

Here, `inc` is added to the context `Γ` as an available term. The prover finds that `inc` itself inhabits the requested type, so `emitTermCode` returns a tree that simply references the existing `inc` value.

### Case Class Derivation

```scala
final case class User2[A](name: String, id: A) {
  def map[B](f: A => B): User2[B] = implement
  val generated: (Int, String, A) = implement
}

```

The macro expands `map` to:

```scala
def map[B](f: A => B): User2[B] = User2(name, f(id))

```

And `generated` expands to a tuple construction using available fields:

```scala
val generated: (Int, String, A) = (name.length, name, id)

```

These expansions are verified in the test suite at [`src/test/scala/io/chymyst/ch/unit/MacrosSpec.scala`](https://github.com/chymyst/curryhoward/blob/main/src/test/scala/io/chymyst/ch/unit/MacrosSpec.scala) (lines 76-89).

## Summary

-   **Type Conversion**: `buildTypeExpr` bridges Scala's type system and STLC via the Curry-Howard isomorphism.
-   **Proof as Program**: The LJT calculus in [`TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/TheoremProver.scala) guarantees that proofs correspond directly to lambda terms.
-   **AST Splicing**: `emitTermCode` and `LiftedAST` translate `TermExpr` nodes into compiler trees (`c.Tree`) using Scala's quasiquote syntax.
-   **Zero Runtime Overhead**: Because the entire pipeline runs at compile time, the generated code is indistinguishable from hand-written Scala with no reflection or runtime cost.

## Frequently Asked Questions

### How does the macro convert a Scala type into a lambda calculus expression?

The `buildTypeExpr` method in [`Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/Macros.scala) recursively analyzes the Scala type representation (`c.Type`) obtained via `c.weakTypeOf[U]`. It maps function arrows to implication types, case classes to products, and sealed traits to sums, producing a `TypeExpr` value that mirrors the logical structure of the original Scala type.

### What role does the LJT sequent calculus play in code generation?

The LJT calculus drives the proof search in `TheoremProver.findProofs` and `findTermExprs`. It searches for a derivation that the requested type is inhabited given the available context. When a proof is found, the structure of the derivation directly determines the shape of the `TermExpr` lambda term, which is then translated into executable Scala code.

### Which source file handles the actual emission of Scala ASTs from lambda terms?

[`src/main/scala/io/chymyst/ch/Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Macros.scala) contains the `emitTermCode` method (lines 59-124), which pattern matches on `TermExpr` constructors like `VarE`, `AppE`, and `CurriedE` to generate corresponding Scala trees. The `LiftedAST` object provides the necessary `Liftable` instances to embed these terms as literal AST nodes.

### Can `implement` reuse existing values provided as arguments?

Yes. When using `ofType[T](values*)`, the provided values are added to the proof context. The theorem prover treats them as axioms available for use in the derivation. If a provided term already inhabits the requested type, `emitTermCode` generates a reference to that existing value rather than constructing a new expression.