# LJT Sequent Calculus Theorem Prover in curryhoward: Implementation and Usage Guide

> Explore LJT sequent calculus theorem prover in curryhoward. Learn how it synthesizes Scala type proof terms using recursive rules and memoization for efficient theorem proving.

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

---

**The curryhoward library implements a cut-free intuitionistic sequent calculus called LJT that automatically synthesizes proof terms for Scala types through recursive rule application and memoization.**

The **LJT sequent calculus theorem prover** serves as the core inference engine of the `chymyst/curryhoward` repository, a Scala library that exploits the Curry-Howard correspondence to synthesize programs from type specifications. This implementation follows the LJT calculus defined by Galmiche and Larchey-Wendling (1998), providing a complete, cut-free proof search strategy for intuitionistic logic that operates entirely in-memory without external solvers.

## What Is the LJT Sequent Calculus?

LJT is a **cut-free intuitionistic sequent calculus** introduced by Galmiche and Larchey-Wendling in 1998. Unlike classical sequent calculi that require cut elimination as a post-processing step, LJT is designed to be constructive from the ground up, making it ideal for automated theorem proving in intuitionistic logic.

In the context of the Curry-Howard correspondence, LJT provides the logical foundation for transforming type specifications into executable lambda terms. Each inference rule in the calculus corresponds to a term constructor, ensuring that every proof yields a valid program that inhabits the specified type.

## Architecture of the LJT Theorem Prover Implementation

The implementation cleanly separates **logical rules** from **search strategy**, residing in two primary objects within the `io.chymyst.ch` package.

### The LJT Object: Rule Definitions and Axioms

Located in [`src/main/scala/io/chymyst/ch/LJT.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/LJT.scala), the `LJT` object defines the complete sequent calculus including axioms, inference rules, and sequent manipulation utilities.

The core function `followsFromAxioms` attempts to close a sequent immediately using the **Id** or **T** axioms. When axioms do not apply, the object provides categorized rule sets:

- **`invertibleRules`**: Rules that can be applied deterministically without branching (e.g., left rules for conjunction and disjunction). The first applicable rule terminates this phase because invertible rules never require backtracking.
- **`invertibleAmbiguousRules`**: Invertible rules that may generate several sub-sequents; their proofs are concatenated using `obtainAndConcatProofs`.
- **`nonInvertibleRulesForSequent`**: Non-invertible rules (such as implication right) that require backtracking search when invertible rules exhaust.

### The TheoremProver Object: Proof Search and Memoization

The `TheoremProver` object in [`src/main/scala/io/chymyst/ch/TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TheoremProver.scala) orchestrates the proof search. It exposes the primary API methods `findProofs` and `findTermExprs`, along with `inhabitInternal` for type-class-like synthesis.

The prover implements several critical optimizations:

- **Memoization**: The `sequentsAlreadyProved` cache stores results for completed sequents to avoid redundant computation across different proof branches.
- **Loop detection**: The `sequentsAlreadyRequested` set prevents infinite recursion when future extensions add looping rules.
- **Information-loss scoring**: After simplification with `simplifyWithEtaUntilStable`, proofs are grouped by score and the minimal-score terms are returned.

## How the LJT Prover Works: Execution Flow

The proof search follows a deterministic seven-step pipeline:

1. **Sequent creation**: The prover builds an initial `Sequent(Nil, typeExpr, freshVar)` representing the goal type in an empty context.
2. **Axiom verification**: `followsFromAxioms` checks if the sequent closes immediately via identity or truth axioms.
3. **Invertible rule application**: The system first applies `invertibleRules` deterministically; the first applicable one stops further search because invertible rules never branch.
4. **Ambiguous invertible handling**: If `invertibleAmbiguousRules` apply, the prover generates all sub-sequents and concatenates their proofs.
5. **Non-invertible exploration**: When invertible rules exhaust, `nonInvertibleRulesForSequent` triggers backtracking search.
6. **Recursive descent**: Each new sub-sequent is processed by `findTermExprs`, with loop detection via `sequentsAlreadyRequested` and memoization via `sequentsAlreadyProved`.
7. **Result selection**: After exploring all branches, the prover collects every `TermExpr`, simplifies it, groups by information-loss score, and returns the minimal-score proofs.

## Practical Code Examples

### Proving the Identity Type (A → A)

The simplest proof generates the identity function:

```scala
import io.chymyst.ch.{TheoremProver, TP}

// Define the type A → A
val t = TP("A") ->: TP("A")

// Search for proofs
val (best, all) = TheoremProver.findProofs(t)

// Output the lowest-score proof term
println(best.head)
// CurriedE(List(VarE("x", TP("A"))), VarE("x", TP("A")))

```

The prover returns a `CurriedE` term representing the lambda expression `λx.x`.

### Generating the K Combinator (A → B → A)

To generate the constant function:

```scala
val t = TP("A") ->: TP("B") ->: TP("A")
val (best, _) = TheoremProver.findProofs(t)

println(best.head)
// CurriedE(List(VarE("x", TP("A")), VarE("y", TP("B"))), VarE("x", TP("A")))

```

This yields the term `λx.λy.x`, correctly discarding the second argument.

### Implementing Option Constructors

The prover can inhabit polymorphic types like `Option[X]`:

```scala
def implement[X]: X => Option[X] = 
  TheoremProver.inhabitInternal[Option[X]].right.get._2

// Test the generated implementation
println(implement(42))   // Some(42)

```

The `inhabitInternal` method returns the synthesized function directly, leveraging the Curry-Howard correspondence to convert the type specification into executable code.

### Debugging Rule Applications

To trace the prover's execution, enable debugging flags:

```scala
import io.chymyst.ch.Macros

Macros.options += "prover"   // Enable basic logging
Macros.options += "trace"    // Show detailed rule applications

val (_, all) = TheoremProver.findProofs(TP("A") ->: TP("A"))
// Console output shows rule names (+L, ->R, etc.) and sub-sequents

```

These flags, defined in [`src/main/scala/io/chymyst/ch/Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Macros.scala), are invaluable for debugging complex type inhabitation failures.

## Key Source Files and API Reference

| File | Description |
|------|-------------|
| [`src/main/scala/io/chymyst/ch/LJT.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/LJT.scala) | Defines the LJT calculus including `followsFromAxioms`, `invertibleRules`, `invertibleAmbiguousRules`, and `nonInvertibleRulesForSequent`. |
| [`src/main/scala/io/chymyst/ch/TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TheoremProver.scala) | Implements proof search via `findProofs`, `findTermExprs`, and `inhabitInternal`, with memoization through `sequentsAlreadyProved` and loop detection via `sequentsAlreadyRequested`. |
| [`src/main/scala/io/chymyst/ch/Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Macros.scala) | Provides runtime debugging flags including `"prover"` and `"trace"` for inspecting rule applications. |
| [`src/test/scala/io/chymyst/ch/unit/LJTSpec.scala`](https://github.com/chymyst/curryhoward/blob/main/src/test/scala/io/chymyst/ch/unit/LJTSpec.scala) | Contains unit tests demonstrating typical usage and verifying rule correctness. |

## Summary

- The **LJT sequent calculus theorem prover** in `chymyst/curryhoward` implements a cut-free intuitionistic logic based on Galmiche and Larchey-Wendling (1998).
- The architecture separates concerns between [`LJT.scala`](https://github.com/chymyst/curryhoward/blob/main/LJT.scala) (rule definitions) and [`TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/TheoremProver.scala) (search strategy), making the system extensible.
- The prover categorizes rules into **invertible**, **invertible ambiguous**, and **non-invertible** sets, applying them in priority order to minimize backtracking.
- **Memoization** via `sequentsAlreadyProved` and **loop detection** via `sequentsAlreadyRequested` ensure termination and efficiency during proof search.
- The system generates **typed lambda terms** (e.g., `CurriedE`, `VarE`, `MatchE`) that serve as constructive proofs of the corresponding types under the Curry-Howard correspondence.

## Frequently Asked Questions

### What is the LJT sequent calculus used for in curryhoward?

The LJT sequent calculus provides the logical inference engine that powers automatic program synthesis in curryhoward. It serves as a constructive proof system that determines whether a given Scala type is inhabited, and when it is, generates a typed lambda term representing a valid implementation. This bridges the gap between type theory and functional programming, allowing developers to obtain implementations directly from type signatures.

### How does the TheoremProver avoid infinite loops during proof search?

The `TheoremProver` employs two defensive mechanisms defined in [`TheoremProver.scala`](https://github.com/chymyst/curryhoward/blob/main/TheoremProver.scala). The `sequentsAlreadyRequested` set tracks sequents currently being processed to detect cycles when recursive rules are applied. Additionally, the `sequentsAlreadyProved` cache stores completed proofs, ensuring that if the same sequent appears in a different branch of the search tree, the prover reuses the cached result rather than re-exploring the sub-proof.

### What types of proof terms does the LJT prover generate?

The prover generates instances of `TermExpr`, a sealed trait representing typed lambda calculus expressions within the library. Common constructors include `CurriedE` for lambda abstractions (function literals), `VarE` for variables, and `MatchE` for pattern matching or elimination forms. These terms are fully typed Scala ASTs that witness the constructive proof of the corresponding logical proposition, ready for evaluation or code generation.

### How can I enable debugging to see which rules are applied?

To trace the prover's execution, import `io.chymyst.ch.Macros` and add debugging flags to the `options` set. Setting `Macros.options += "prover"` enables basic logging of proof attempts, while `Macros.options += "trace"` provides detailed output showing each LJT rule name (such as `+L` or `->R`) and the resulting sub-sequents generated during the search process. These flags are defined in [`src/main/scala/io/chymyst/ch/Macros.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Macros.scala) and are essential for debugging complex type inhabitation failures.