Difference Between `implement` and `ofType` Macros in curryhoward: A Complete Guide

The implement macro auto-detects the target type from the left-hand side of your definition using only in-scope symbols, while ofType accepts an explicit type parameter and optionally allows you to supply concrete values to guide the theorem prover.

The curryhoward library for Scala brings automated theorem proving to type-level programming through powerful macros that generate implementations from types alone. Understanding the difference between implement and ofType macros in curryhoward is essential for choosing the right tool when deriving functions, proofs, or lambda terms. While both invoke the same Curry-Howard theorem prover backend, they differ fundamentally in how they receive type information and handle external values.

How Type Inference Works: implement vs ofType

Auto-Detection with implement

The implement macro determines the target type by inspecting the enclosing definition’s left-hand side. In src/main/scala/io/chymyst/ch/Macros.scala, the inhabitImpl method (lines 57-76) calls c.internal.enclosingOwner.typeSignature to extract the expected return type automatically.

This means you never specify the type explicitly when using implement. The macro looks at your method signature or value declaration and derives the implementation solely from that type and the symbols already visible in scope.

Explicit Type Parameters with ofType

The ofType macro, implemented in Macros.scala starting at line 78 (ofTypeImpl), requires you to provide the target type as an explicit type parameter (e.g., ofType[Int => Int]). The macro builds a TypeExpr from c.weakTypeOf[U] where U is your supplied type.

Alternatively, when called without arguments, ofType can also infer the type from the left-hand side similar to implement, but the primary use case is explicit type specification.

Passing Arguments: Scope Values vs Explicit Values

implement: Using In-Scope Symbols Only

The implement macro does not accept any user-provided arguments. It only uses values that are already in scope—the "available symbols" collected from the surrounding method or class parameters. This makes implement ideal for concise definitions where all necessary components are already visible in your local environment.

ofType: Supplying Concrete Values

The ofType macro provides two overloads defined in Macros.scala lines 83-101 (ofTypeImplWithValues):

1. ofType[U] — no extra arguments, uses scope only.
2. ofType[U](v1, v2, ...) — accepts concrete values that the theorem prover may reuse while constructing the implementation.

This allows you to guide the prover by supplying specific functions or values that should be incorporated into the generated term, giving you finer control over the synthesis process.

Extracting Lambda Terms and Advanced Usage

Both macros generate values wrapped in lambda wrapper classes (e.g., Function1Lambda). However, ofType provides easier access to the underlying λ-term through the WithLambdaTerm implicit defined in src/main/scala/io/chymyst/ch/package.scala (lines 81-88).

When you need to inspect or print the generated proof term, ofType allows:

val term = ofType[Int => Int].lambdaTerm
println(term.prettyPrint)  // Output: λx. x

While implement also attaches the term to the wrapper class, the WithLambdaTerm implicit makes extraction particularly ergonomic with ofType.

Code Examples: Practical Implementation

import io.chymyst.ch._

// 1. Using implement – type inferred from definition left-hand side
def compose[F, G, H](f: G => H, g: F => G): F => H = implement
// Macro inspects the signature F => H and builds composition automatically

// 2. Using ofType with explicit type parameter
val identity: Int => Int = ofType[Int => Int]

// 3. Using ofType with type inference from val declaration
val const42 = ofType[Int => Int]  // Same as above, type inferred from LHS

// 4. Supplying existing values to guide the prover
val plusOne: Int => Int = ofType[Int => Int]((x: Int) => x + 1)
// The supplied lambda may be reused in the constructed term

// 5. Extracting the underlying lambda term
val term: TermExpr = ofType[Int => Int].lambdaTerm
println(term.prettyPrint)   // → "λx. x"

// 6. Getting all possible implementations
val allIdentities: Seq[Int => Int] = allOfType[Int => Int]

Summary

• implement auto-detects the target type from the left-hand side of your definition using c.internal.enclosingOwner.typeSignature and uses only in-scope symbols without accepting user-provided arguments.
• ofType accepts an explicit type parameter (or infers from context) and provides overloads to supply concrete values that guide the theorem prover, implemented in ofTypeImpl and ofTypeImplWithValues.
• Both macros return single implementations by default, but ofType supports allOfType and anyOfType for retrieving multiple inequivalent terms.
• Lambda term extraction is streamlined with ofType through the WithLambdaTerm implicit defined in package.scala, while implement requires manual wrapper access.

Frequently Asked Questions

Can I pass explicit arguments to the implement macro?

No. The implement macro does not accept user-provided arguments. It relies solely on symbols already visible in the enclosing scope, as implemented in Macros.inhabitImpl. If you need to supply specific values to guide the theorem prover, use ofType[U](v1, v2, ...) instead.

How do I extract the underlying lambda term from generated code?

Use the WithLambdaTerm implicit provided in src/main/scala/io/chymyst/ch/package.scala. When using ofType, simply call .lambdaTerm on the result: val term = ofType[Int => Int].lambdaTerm. This returns a TermExpr that you can inspect with prettyPrint or analyze programmatically.

What happens when multiple inequivalent implementations exist?

Both implement and ofType fail at compile time if the theorem prover finds more than one inequivalent term and you requested a single result. To handle multiple implementations, use allOfType[U] or anyOfType[U], which return a Seq[U] containing all discovered terms rather than failing.

Can I use implement with an explicit type parameter?

No, implement does not support explicit type parameters. It exclusively uses type auto-detection from the left-hand side of the definition via c.internal.enclosingOwner.typeSignature. If your use case requires explicit type specification, use ofType[YourType] instead.

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