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

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

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:

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]:

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:

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, are invaluable for debugging complex type inhabitation failures.

Key Source Files and API Reference

File	Description
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	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	Provides runtime debugging flags including "prover" and "trace" for inspecting rule applications.
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 (rule definitions) and 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. 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 and are essential for debugging complex type inhabitation failures.

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