How to Create Fresh Variable Terms for Lambda-Calculus Expressions Using `freshVar`

Use the freshVar[T] macro from io.chymyst.ch to generate compile-time fresh VarE instances with unique names and specified types, ensuring no variable capture in lambda terms.

The curryhoward library by Chymyst implements the Curry-Howard correspondence for Scala, enabling automatic generation of lambda-calculus terms from types. When constructing these terms programmatically, you must create fresh variable terms to avoid name collisions. The library provides a robust mechanism through the freshVar macro and supporting utilities.

The freshVar Macro API

The primary entry point for creating fresh variables is the freshVar method defined in the package object.

In src/main/scala/io/chymyst/ch/package.scala (lines 91-96), the macro is declared:

def freshVar[X]: VarE = macro Macros.freshVarImpl[X]

When invoked as freshVar[Int] or freshVar[A => B], this macro expands at compile time to produce a VarE instance with a guaranteed unique name string and the corresponding type expression.

Macro Implementation and Fresh Name Generation

The actual logic for generating unique identifiers resides in src/main/scala/io/chymyst/ch/Macros.scala around line 327. The freshVarImpl method utilizes Scala's compiler API to create non-colliding names:

// Simplified representation of the macro expansion
val name = c.freshName("x")   // Produces strings like "x$macro$1", "x$macro$2"
VarE(name, typeExpr[X])

The c.freshName call ensures that even within complex macro expansions or nested term constructions, the generated VarE will not shadow existing variables in the lexical scope.

The VarE Case Class

Fresh variables are represented as instances of the VarE case class, defined in src/main/scala/io/chymyst/ch/TermExpr.scala (line 653). This class encapsulates:

case class VarE(name: String, t: TypeExpr) extends TermExpr

• name: The unique identifier string generated by freshVar
• t: The TypeExpr representing the variable's type in the lambda calculus

VarE extends TermExpr, allowing fresh variables to be used directly in term construction via LamE (lambda abstraction) and AppE (application).

Runtime Fresh Identifier Generation with FreshIdents

For scenarios requiring fresh names at runtime rather than compile time—such as within the theorem prover or sequent calculus components—the library provides the FreshIdents class in src/main/scala/io/chymyst/ch/Sequent.scala (line 28):

class FreshIdents(prefix: String) {
  private var counter = 0
  def fresh(): String = {
    counter += 1
    s"$prefix$counter"  // e.g., "x1", "x2", "x3"
  }
}

This utility is particularly useful when constructing Sequent instances where premise variables need unique but human-readable names during proof search.

Practical Code Examples

Creating Fresh Variables for Lambda Abstractions

import io.chymyst.ch._

// Generate a fresh variable of type Int => Int
val f = freshVar[Int => Int]
// f: VarE = VarE("x$macro$1", TypeExpr(Int => Int))

// Create a lambda term: λf. f (f x)
val x = VarE("x", typeExpr[Int])
val term = LamE(f, AppE(f, AppE(f, x)))

Using Fresh Variables in Theorem Proving

import io.chymyst.ch._

// Initialize a sequent with fresh identifier generator
val sequent = Sequent(Nil, typeExpr[Int], new FreshIdents("x"))

// Extract premise variables (automatically fresh)
val premises: List[VarE] = sequent.premiseVars
// premises might contain: List(VarE("x1", TypeExpr(Int)))

Combining Compile-Time and Runtime Fresh Names

import io.chymyst.ch._

// Compile-time fresh variable
val compileTimeVar = freshVar[String]

// Runtime fresh variable for dynamic term construction
val runtimeGen = new FreshIdents("y")
val runtimeName = runtimeGen.fresh() // "y1"
val runtimeVar = VarE(runtimeName, typeExpr[String])

Summary

• freshVar[T] is a compile-time macro in package.scala that generates unique VarE instances via Macros.freshVarImpl.
• Fresh name generation uses c.freshName to guarantee uniqueness during macro expansion, preventing variable capture.
• VarE (defined in TermExpr.scala) represents variables as name-type pairs and serves as the building block for lambda terms.
• FreshIdents (in Sequent.scala) provides runtime fresh name generation for theorem proving and dynamic term construction.
• Both mechanisms ensure that lambda-calculus expressions constructed programmatically maintain alpha-equivalence without accidental name collisions.

Frequently Asked Questions

What is the difference between freshVar and FreshIdents?

freshVar is a compile-time macro that generates fresh VarE instances during Scala compilation using the macro system's c.freshName. FreshIdents is a runtime class used during program execution to generate sequential unique names (like "x1", "x2") for theorem proving or dynamic term construction. Use freshVar when writing macro-based code generation; use FreshIdents when working with the Sequent prover at runtime.

How does freshVar prevent name collisions with existing variables?

The macro implementation in Macros.scala utilizes the Scala compiler's c.freshName API, which generates identifiers guaranteed to be unique within the current compilation context. These names typically follow the pattern x$macro$1, x$macro$2, etc., ensuring they cannot clash with user-defined variables or other generated names in the same scope.

Can I use freshVar with polymorphic or higher-kinded types?

Yes, freshVar accepts any type parameter X and will generate a VarE with the corresponding TypeExpr. For polymorphic types like freshVar[List[A]] or function types like freshVar[Int => String], the macro correctly captures the type structure and creates a variable term with the appropriate type representation for use in lambda abstractions or applications.

Where is the VarE case class defined and what does it contain?

The VarE case class is defined in src/main/scala/io/chymyst/ch/TermExpr.scala at line 653. It extends TermExpr and contains two fields: a name of type String (the unique identifier) and a t of type TypeExpr (the variable's type in the lambda calculus). This structure allows fresh variables to participate fully in term construction via LamE for abstractions and AppE for applications.

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