Abstracting over Type[_] constraints needed for staging in Dotty (answering https://gitter.im/lampepfl/dotty?at=5e33235c3aca1e4c5f4d2aec)

stagingHoas.scala

import scala.quoted._
import scala.quoted.staging.{run, Toolbox}

trait Lambda[Rep[_], Cons[_]] {
  def lam[A: Cons, B: Cons](f: Rep[A] => Rep[B]): Rep[A => B]
  def app[A: Cons, B: Cons](f: Rep[A => B], repA: Rep[A]): Rep[B]
}
// Boilerplate exposing Lambda's methods to the top-level, hopefully can be improved upon.
def lam[Rep[_], Cons[_], A: Cons, B: Cons](f: Rep[A] => Rep[B])(given l: Lambda[Rep, Cons]): Rep[A => B] = l.lam(f)
def app[Rep[_], Cons[_], A: Cons, B: Cons](f: Rep[A => B], repA: Rep[A])(given l: Lambda[Rep, Cons]): Rep[B] =
  l.app(f, repA)

def testSummon[A, B](given tpAB: Type[A => B]): Unit = {
  val tpA: Type[A => B] = summon[Type[A => B]]
}

given stage (given qctx: QuoteContext): Lambda[Expr, Type] = new  {
  def lam[A: Type, B: Type](f: Expr[A] => Expr[B]): Expr[A => B] = '{
    (a: A) => ${ f('a) }
  }

  def app[A: Type, B: Type](f: Expr[A => B], repA: Expr[A]): Expr[B] =
    Expr.betaReduce(f)(repA)
}

// Demonstrate (polymorphic) usage.
// Code in Scala:
def sFst[A, B]: A => B => A = x => y => x
def sHo_Apply[A, B]: (A => B) => A => B = f => x => f(x)
def sApplyFst[A, B]: A => B => A = arg => sHo_Apply(sFst(arg))

// Staged versions:
def fst[Rep[_], Cons[_], A: Cons, B: Cons](given Lambda[Rep, Cons])(given Cons[B => A]): Rep[A => B => A] =
  lam(x => lam(y => x))
def snd[Rep[_], Cons[_], A: Cons, B: Cons](given Lambda[Rep, Cons])(given Cons[B => B]): Rep[A => B => B] =
  lam(x => lam(y => y))
def ho_apply[Rep[_], Cons[_], A: Cons, B: Cons](given Lambda[Rep, Cons])(given Cons[A => B]): Rep[(A => B) => A => B] =
  lam(f => lam(x => app(f, x)))
// Tests both abstraction and application
def applyFst[Rep[_], Cons[_], A: Cons, B: Cons]
  (given Lambda[Rep, Cons])(given Cons[B => A], Cons[(B => A) => B => A]): Rep[A => B => A] = {
    lam(arg => app(ho_apply, app(fst, arg)))
}

given Toolbox = Toolbox.make(getClass.getClassLoader)

//@main def Runner = {
object stagingHoas {
  def timeStamp(log: String) = println(s"$log; Now is ${java.time.LocalTime.now()}")
  def main(args: Array[String]): Unit = {
    timeStamp("Start")

    // The only acceptable calls for these functions need named type arguments,
    // but the SIP committee is not yet convinced by the proposal. See alternative calls below.
    val compiledApplyFst = run(applyFst[A = Int, B = String](given stage))
    timeStamp("Compiled applyFst")
    val compiledSnd = run(snd[A = Int, B = String](given stage))
    timeStamp("Compiled snd")

    timeStamp("Calling applyFst")
    println(compiledApplyFst(1)("hi"))
    println(compiledApplyFst(2)("hi"))
    println(compiledApplyFst(3)("hi"))
    timeStamp("Calling snd")
    println(compiledSnd(1)("hi"))
    timeStamp("Ended")
  }

  // Tests for type inference
  // Worse: we must annotate the full return type, which repeats A (and could be more complex).
  def compiledApplyFst0 = run[Int => String => Int] (applyFst(given stage))

  // Worse: need all type arguments, even those that can be deduced from the explicit given argument.
  def compiledApplyFst1 = run (applyFst[Expr, Type, Int, String](given stage))

  // Worse: need all type arguments
  def compiledApplyFst2 = run (applyFst[Expr, Type, Int, String])

  def compiledApplyFst3 = run[Int => String => Int] {
    //Works, but no type argument of summon can be omitted. I can omit the
    //second given argument list, but only because I had the foresight to curry
    //the argument list in the first place.
    fst[Expr, Type, Int, String](given stage)(
      given summon[Type[Int]], summon[Type[String]], summon[Type[String => Int]])
  }
}