How CurryHoward Converts STLC Terms into Scala Code via Macros

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 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 (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 (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 (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: 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, 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

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

The macro expands this to:

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

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

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:

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

And generated expands to a tuple construction using available fields:

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 (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 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 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 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.

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