# Understanding Eta-Contraction and Alpha-Conversion in CurryHoward's Term Simplification

> Learn how eta-contraction and alpha-conversion simplify terms in CurryHoward's theorem prover, eliminating redundant arguments and preventing variable capture for clean lambda terms.

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

---

**Eta-contraction eliminates redundant curried arguments while alpha-conversion prevents variable capture during type unification, together ensuring clean λ-terms in the CurryHoward theorem prover.**

The `curryhoward` library implements the Curry-Howard correspondence by representing logical propositions as typed λ-terms. Before these terms reach the theorem prover, they undergo a simplification phase where **eta-contraction and alpha-conversion in curryhoward** remove redundant abstractions and prevent naming collisions during type inference.

## What Are Eta-Contraction and Alpha-Conversion?

In λ-calculus, **eta-contraction** (η-contraction) simplifies terms of the form `λx. f x` to `f` when `x` does not appear free in `f`. This eliminates unnecessary argument passing in curried functions.

**Alpha-conversion** (α-conversion) renames bound variables to avoid name clashes. In CurryHoward, this applies specifically to type variables during unification to prevent accidental capture when substitutions are applied.

## Eta-Contraction in CurryHoward

### How It Works

CurryHoward represents curried terms using the `CurriedE(heads, body)` case class, where `heads` are the lambda-bound variables and `body` is the resulting expression. Eta-contraction triggers when the body is an application `f a` where the argument `a` matches the last head variable.

The transformation follows this logic:

- If `body` equals `AppE(f, lastHead)` and `f` does not contain `lastHead` as a free variable, the term contracts to `CurriedE(heads.init, f)` or just `f` if no heads remain.

### Implementation Details

The contraction logic resides in [`src/main/scala/io/chymyst/ch/TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TermExpr.scala) within the `simplifyOnceInternal` method of the `CurriedE` class (lines 89–102):

```scala
// In CurriedE.simplifyOnceInternal (TermExpr.scala)
case AppE(fHead, fBody) if withEta &&
  headsLength > 0 && {
    val lastHead = heads(headsLength - 1)
    lastHead === fBody &&                     // heads.last = argument
    !fHead.freeVarNames.contains(lastHead.name) // safety check
  } =>
  if (headsLength > 1)
    CurriedE(heads.slice(0, headsLength - 1), fHead) // drop last head
  else
    fHead                                            // no heads left

```

The safety check `!fHead.freeVarNames.contains(lastHead.name)` prevents invalid contractions where the variable appears free in the function body, ensuring semantic preservation.

### Code Example

The following example demonstrates eta-contraction on a curried term:

```scala
import io.chymyst.ch._

// Define a curried term: (x4:B → x5:A → x4:B) applied to a value y:B
val f1 = CurriedE(
  List(VarE("x4", TP("2")), VarE("x5", TP("1"))),
  VarE("x4", TP("2"))
)                     // type: B → A → B
val t1 = AppE(f1, VarE("y", TP("2")))

// Simplify once → eta‑contracted
val simplified = t1.simplifyOnce()
assert(simplified == CurriedE(List(VarE("x5", TP("1"))), VarE("y", TP("2"))))

```

This test case, verified in [`src/test/scala/io/chymyst/ch/unit/TermExprSpec.scala`](https://github.com/chymyst/curryhoward/blob/main/src/test/scala/io/chymyst/ch/unit/TermExprSpec.scala) (lines 151–156), confirms that the redundant argument `x4` is eliminated while preserving the term's type structure.

## Alpha-Conversion in CurryHoward

### Preventing Variable Capture

During type inference, CurryHoward unifies type expressions to find compatible substitutions. When a type variable appears only on the left-hand side of a unification equation, it remains unmapped in the substitution set. If these variables later become bound through other substitutions, they could capture free occurrences accidentally.

Alpha-conversion addresses this by renaming unmapped type variables to fresh identifiers before they can clash with existing bound variables.

### Implementation in Type Unification

The conversion logic resides in [`src/main/scala/io/chymyst/ch/TypeExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TypeExpr.scala) within the `leftUnify` method (lines 191–199):

```scala
// In TypeExpr.leftUnify (TypeExpr.scala)
val usedVars = substitutions.values.map(allTypeParams).foldLeft(Set[TP]())(_ ++ _)
val unmappedVars = (usedVars intersect allTypeParams(fullSrc)) -- substitutions.keySet
val alphaConversions: Map[TP, TypeExpr] = unmappedVars.toSeq.map {
  _ → TP(freshTypeVarIdents())
}.toMap
substitutions ++ alphaConversions

```

The algorithm:
1. Collects all type parameters already used in the substitution values (`usedVars`)
2. Identifies unmapped variables in the source type that intersect with these used variables
3. Generates fresh identifiers (e.g., `Z1`, `Z2`) for each conflicting variable
4. Adds these mappings to the substitution set

This ensures the resulting type expression is **α-equivalent** to the original but avoids naming collisions during subsequent unification steps.

### Code Example

The following example demonstrates automatic alpha-conversion during type unification:

```scala
import io.chymyst.ch._

// Two polymorphic type expressions
val t1 = TP("A") ->: TP("B")          // A ⇒ B
val t2 = TP("X") ->: TP("Y")          // X ⇒ Y

// Unify left side (t1) with right side (t2)
val result = TypeExpr.leftUnify(t1, t2, t1)

result match {
  case Right(subst) =>
    // `subst` will contain fresh names for X and Y because they were unmapped
    println(subst)   // e.g. Map(X -> Z1, Y -> Z2)
  case Left(err) => println(s"Unification failed: $err")
}

```

The automatic insertion of fresh type variables is performed by the `alphaConversions` map inside `leftUnify`. The surrounding unification logic is exercised in the "automatic alpha-conversions" test of [`TermExprSpec.scala`](https://github.com/chymyst/curryhoward/blob/main/TermExprSpec.scala) (lines 72–90).

## Key Source Files

| File | Purpose |
|------|---------|
| [`src/main/scala/io/chymyst/ch/TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TermExpr.scala) | Contains the term hierarchy (`VarE`, `AppE`, `CurriedE`) and the **eta-contraction** logic inside `CurriedE.simplifyOnceInternal` (lines 89–102). |
| [`src/main/scala/io/chymyst/ch/TypeExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/src/main/scala/io/chymyst/ch/TypeExpr.scala) | Defines the type expression hierarchy and implements **alpha-conversion** during left-unification (`leftUnify`, lines 191–199). |
| [`src/test/scala/io/chymyst/ch/unit/TermExprSpec.scala`](https://github.com/chymyst/curryhoward/blob/main/src/test/scala/io/chymyst/ch/unit/TermExprSpec.scala) | Unit tests demonstrating eta-contraction (lines 151–156) and automatic alpha-conversion (lines 72–90). |
| [`src/test/scala/io/chymyst/ch/unit/MoreMatchTypeSpec.scala`](https://github.com/chymyst/curryhoward/blob/main/src/test/scala/io/chymyst/ch/unit/MoreMatchTypeSpec.scala) | Additional test coverage for eta-contraction behavior in nested match expressions. |

## Summary

- **Eta-contraction** in CurryHoward eliminates redundant curried arguments by detecting when a lambda's body immediately applies the bound variable, shortening terms like `λx. f x` to `f` when safe.
- The transformation lives in `CurriedE.simplifyOnceInternal` within [`TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/TermExpr.scala), guarded by a free-variable check to preserve semantics.
- **Alpha-conversion** prevents type variable capture during unification by renaming unmapped variables to fresh identifiers (e.g., `Z1`, `Z2`) before they clash with existing bindings.
- This renaming occurs automatically in `TypeExpr.leftUnify` within [`TypeExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/TypeExpr.scala) during the unification process.
- Together, these transformations ensure that CurryHoward operates on clean, normalized λ-terms and type expressions, preventing variable collisions and eliminating syntactic noise before theorem proving begins.

## Frequently Asked Questions

### What is eta-contraction in lambda calculus?

Eta-contraction is a reduction rule that simplifies terms of the form `λx. f x` to `f`, provided that `x` does not appear free in `f`. This transformation identifies and removes redundant argument passing, effectively recognizing that the lambda merely passes its input directly to another function without modification. In CurryHoward, this optimization shortens curried terms before they reach the theorem prover.

### Why does CurryHoward need alpha-conversion?

CurryHoward uses alpha-conversion to prevent variable capture during type unification. When unifying two type expressions, some type variables may appear only on the left-hand side and remain unmapped in the substitution set. If these variables later become bound through other substitutions, they could accidentally capture free occurrences in the resulting type. By renaming unmapped variables to fresh identifiers (like `Z1`, `Z2`) during the `leftUnify` process, CurryHoward maintains α-equivalence while avoiding naming collisions.

### How does eta-contraction differ from beta-reduction?

While both are fundamental λ-calculus operations, they target different syntactic patterns. **Beta-reduction** applies a function to its argument, reducing `(λx. M) N` to `M[x := N]` (substituting `N` for `x` in `M`). **Eta-contraction**, by contrast, does not involve application or substitution; it simply recognizes that `λx. f x` denotes the same function as `f` when `x` is not free in `f`, and removes the redundant lambda wrapper. CurryHoward performs eta-contraction during term simplification to prune unnecessary currying layers after beta-reduction steps have occurred.

### Where can I find the term simplification logic?

The term simplification logic is distributed across two primary files in the `src/main/scala/io/chymyst/ch/` directory. **Eta-contraction** is implemented in [`TermExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/TermExpr.scala) within the `simplifyOnceInternal` method of the `CurriedE` class (lines 89–102), which detects redundant trailing arguments in curried expressions. **Alpha-conversion** resides in [`TypeExpr.scala`](https://github.com/chymyst/curryhoward/blob/main/TypeExpr.scala) inside the `leftUnify` method (lines 191–199), where it generates fresh identifiers for unmapped type variables during unification. Comprehensive tests for both transformations are available in [`src/test/scala/io/chymyst/ch/unit/TermExprSpec.scala`](https://github.com/chymyst/curryhoward/blob/main/src/test/scala/io/chymyst/ch/unit/TermExprSpec.scala).