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

> Learn to create fresh variable terms for lambda-calculus expressions with the io.chymyst.ch `freshVar` macro. Generate unique Vars at compile time, preventing variable capture. Avoid name clashes effectively.

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

---

**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`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/package.scala) (lines 91-96), the macro is declared:

```scala
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`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Macros.scala) around line 327. The `freshVarImpl` method utilizes Scala's compiler API to create non-colliding names:

```scala
// 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`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TermExpr.scala) (line 653). This class encapsulates:

```scala
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`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/Sequent.scala) (line 28):

```scala
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

```scala
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

```scala
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

```scala
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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/TermExpr.scala)) represents variables as name-type pairs and serves as the building block for lambda terms.
- **`FreshIdents`** (in [`Sequent.scala`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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`](https://github.com/chymyst/curryhoward/blob/main/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.