0
$\begingroup$

Given two terms x and y of unknown types, is there a way in Lean 4 to coerce one term to the type of the other term?

I know that one can convert a term x to a known type (e.g. String) by writing (x : String), if the proper Coe instance exists. But I need to convert x to the type of another term y, whose type is not known in advance.

In the simplified example below, the macro add2 should add two terms that are convertible to the same type.

syntax (name := test2) "add2 " term : term
macro_rules (kind := test2)
| `(add2 $x $y) => `($x + $y)

instance : Coe String Nat where
  coe := String.toNat!

This works when the two terms are of the same type:

#eval add2 1 1

But fails when they are of different type, even though a Coe exists:

#eval add2 1 "2"   -- failed to synthesize HAdd Nat String ?m.1

However, explicit type conversion works:

#eval add2 1 ("2": Nat)

This works because I know the type of 1 in advance (Nat). But I cannot hard code Nat into the macro, because the types of the input terms are not known in advance. So, what should be used in writing the conversion ($y : ??) as in the (non-working) code below?:

syntax (name := test2) "add2 " term : term
macro_rules (kind := test2)
| `(add2 $x $y) => `($x + ($y : ??))

Unless there is typeof operator in Lean 4, I guess a different technique is needed.

Hence the question here:

Is there a general way to convert the type of one term to match the type of a target term?

(This is with Lean 4.23.0)

$\endgroup$
4
  • $\begingroup$ I think you are mixing up type hints with type coercion. I don’t think there is the concept in lean of an “unknown type”. $\endgroup$ Commented Oct 15 at 21:27
  • $\begingroup$ …or maybe it is me who is mixed up… $\endgroup$ Commented Oct 15 at 21:35
  • $\begingroup$ You can use def typeof {A : Sort u} (a : A) : Sort u := A or something like open Lean Lean.Elab in elab "typeof%" σ:term : term => do Meta.inferType (← Term.elabTerm σ none) as your typeof. $\endgroup$ Commented Oct 16 at 12:29
  • 1
    $\begingroup$ This looks like an instance of the XY problem. What are you really doing? The class HAdd already allows for heterogenous addition, does that fit the bill? $\endgroup$ Commented Oct 16 at 13:42

1 Answer 1

0
$\begingroup$

First, this isn't really about macros or notation, or even coercion. It is about how Lean elaborates terms.

When Lean elaborates the following:

#check 123 + (-456)

It has to go through a bunch of type class inference to figure out what types are involved. For example, when it sees 123 it doesn't see a Nat. What it sees is a special un-elaborated set of numeral symbols. It directly converts these numerals to some type using the OfNat typeclass. (Despite its name, OfNat is not the same thing a coercion from Nat. For example, there is an OfNat instance for UInt16, but not a coercion from Nat to UInt16, since the coercion goes the other way.) So to elaborate 123 + (-456), Lean has to make a bunch of guesses, as to what type the whole expression is, what type 123 and 456 are, what type - is, and what types + refers to. You can see all the different paths it takes (most of them failures) by turning the following option on:

set_option trace.Meta.synthInstance true
#check 123 + (-456)

(The output of synthInstance is hard to read, and too long to put in this answer, but the main point is that it goes through lots of cases before it finds the right one.)

Now in your situation, let's consider your example but using + instead of your new notation.

#check 1 + "2"

The elaborator gets stuck. It is really trying to convert the numeral 1 to a string. Elaboration failure isn't an uncommon situation in Lean. If Lean can't figure out the type from context, then give Lean a type hint. In this case, it is enough to hint to Lean that 1 is Nat (because again, Lean doesn't know that it should treat 1 as a Nat) or that the type of the whole expression is Nat. All of these work, either via type hints or type context.

#check (1 : Nat) + "2"
#check (Nat.succ Nat.zero) + "2"
#check (Nat.max 0 1) + "2"
#check (1 + "2" : Nat)
#check 1 + "2" = (3 : Nat)
#check Nat.max 0 (1 + "2")

Also, this isn't really about Lean expecting (or not expecting) the terms to be of the same type. For example, these both fails even though Lean clearly expects both arguments to be the same type:

def add3 {α : Type} [HAdd α α α] (x y : α) : α := x + y
#check add3 1 "2"

def add4 {α : Type} [Add α] (x y : α) : α := x + y
#check add4 1 "2"

Here is another example which doesn’t use existing type class instances. Even in this case you see how Lean sometimes gets stuck.

class Foo (A: Type)

inductive Bar
| mk : Bar

instance : Inhabited Bar := ⟨Bar.mk⟩
instance : (Foo Bar) := ⟨⟩

def foo {A : Type} [Foo A] [Inhabited A] (a b : A) : A := Inhabited.default

instance : Coe String Bar := ⟨fun _ => Bar.mk⟩
#check foo "a" "b"  -- fails
#check foo "a" ("b": Bar)  -- fails
#check foo ("a": Bar) "b"  -- checks
#check (foo "a" "b" : Bar)  -- checks

instance (n : Nat) : OfNat Bar n := ⟨Bar.mk⟩
#check foo 1 2  -- fails
#check foo (1 : Bar) 2  -- checks
#check foo 1 (2 : Bar)  -- checks
#check (foo 1 2 : Bar)  -- checks

Again, note that notation like (1 + "2" : Nat) is not necessarily type coercion. It is type hinting. Lean has lots of options to make a type hint work. Implicit coercion is just one method, but there are others (usually involving the type class system), such as using OfNat. For example, in (1 + 2 : Int), there is no coercion. If you click in the infoview on the 1 you see it is @OfNat.ofNat Int 1 instOfNat : Int. In (1 + "2" : Nat) there is coercion, but on "2", even though the type hint is on the outer expression. This is a subtle point, but might help clear up some confusion.


Also, in the comments Andrej makes a good point about the XY problem. It isn't clear what you are trying to do. If it is just fighting with Lean's type system, the best answer is to give more type hints. If it is something more specific, it might help to ask another more specific question (in a new post).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.