HOAS pattern example from reference doesn't compile as given

[abeppu]

I find that a HOAS pattern matching example in the scala 3 reference does not compile.
The example is here https://docs.scala-lang.org/scala3/reference/metaprogramming/macros.html#hoas-patterns-1
I have wrapped this in a minimal dummy macro as a scaffolding exercise it (providing quotes, etc), and find that it fails.

I originally asked about this on SO, with the assumption that something must be wrong with my setup; the only responder at time of writing also attempted variants on this without success. https://stackoverflow.com/questions/77718835/why-does-this-scala-3-macros-reference-example-of-hoas-fail-with-type-must-be-f?r=SearchResults

Compiler version

3.3.1
(but also reproduced on 3.0.0)

Minimized code

In ExprmatchingPlayground.scala

package exprmatch
import scala.quoted.*

object ExprMatchingPlayground {

  inline def foo(): Int = ${ scrutinizeHoas }

  def scrutinizeHoas(using qctx: Quotes): Expr[Int] = {
    // example from https://docs.scala-lang.org/scala3/reference/metaprogramming/macros.html#hoas-patterns-1
    // see stack overflow question https://stackoverflow.com/questions/77718835/why-does-this-scala-3-macros-reference-example-of-hoas-fail-with-type-must-be-f

    val w = '{ ((x: Int) => x + 1).apply(2) } match {
      case '{ ((y: Int) => $f(y)).apply($z: Int) } =>
        // f may contain references to `x` (replaced by `$y`)
        // f = (y: Expr[Int]) => '{ $y + 1 }
        f(z) // generates '{ 2 + 1 }
      case _ => '{ 0 } // allow us to notice if compile succeeds but match fails
    }
    println(s"w = ${w.asTerm.show(using Printer.TreeCode)}")

    '{ 2 }
  }
}

in ExprMatchingDemo.scala

package exprmatch

object ExprMatchingDemo extends App {

  ExprMatchingPlayground.foo()

}

(see also this gist: https://gist.github.com/abeppu/2fa3af1e2a92c9d2ec666229781d0b20 )

Output

Compiling and using scalac -explain I get:

-- Error: ExprMatchingPlayground.scala:13:28 ---------------------------------------------------------------------------------------------------------------------------------------------------------------
13 |      case '{ ((y: Int) => $f(y)).apply($z: Int) } =>
   |                            ^
   |                            Type must be fully defined.
   |                            Consider annotating the splice using a type ascription:
   |                              ($<none>(y): XYZ).
-- [E006] Not Found Error: ExprMatchingPlayground.scala:16:8 -----------------------------------------------------------------------------------------------------------------------------------------------
16 |        f(z) // generates '{ 2 + 1 }
   |        ^
   |        Not found: f
   |--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   | Explanation (enabled by `-explain`)
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   | The identifier for `f` is not bound, that is,
   | no declaration for this identifier can be found.
   | That can happen, for example, if `f` or its declaration has either been
   | misspelt or if an import is missing.
    --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-- [E006] Not Found Error: ExprMatchingPlayground.scala:16:10 ----------------------------------------------------------------------------------------------------------------------------------------------
16 |        f(z) // generates '{ 2 + 1 }
   |          ^
   |          Not found: z
   |--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   | Explanation (enabled by `-explain`)
   |- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   | The identifier for `z` is not bound, that is,
   | no declaration for this identifier can be found.
   | That can happen, for example, if `z` or its declaration has either been
   | misspelt or if an import is missing.
    --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3 errors found

Expectation

The pattern matching section here was copy-pasted directly from a reference example: https://docs.scala-lang.org/scala3/reference/metaprogramming/macros.html#hoas-patterns-1

For that reason, as documented, I expect that:

• the whole match should compile
• the pattern case '{ ((y: Int) => $f(y)).apply($z: Int) } should not require further annotations
• as implied by the comment // f = (y: Expr[Int]) => '{ $y + 1 }, f should have type Expr[Int] => Expr[Int]
• the associated expression f(z) should, as explicitly commented in the reference example, generate '{2 + 1}
  • and thus f and z must be bound at that point

Further notes

Because this is a reference example, I believe I should not need to add further type annotations to make it compile. However, if I do add further annotations, and helper methods, I find that:

• case '{ ((y: Int) => $f(y): Int).apply($z: Int) } is enough to resolve the "Type must be fully defined" error
• However, it's implied from the comment and use that f: Expr[Int] => Expr[Int]. I cannot get this to be true; with the annotation above, I havef: Expr[Int => Int]. I cannot find an annotation which I can apply inside the '{...}which lets f: Expr[Int] => Expr[Int]; if there's a different annotation which would give this desire result, please let me know!
  • for this reason, trying to do f(z), as in the reference, yields an error that f does not take parameters (b/c f is not a function; it is an Expr of a function)
  • In the comments from the reference example, f(z) has the behavior of returning an expression in which occurrences of y are replaced with z, generating '{2 + 1}. While I see a way to recover an Expr[Int] => Expr[Int] described in the docs in the staged lambdas section, it doesn't allow us to generate '{2 + 1} in this at macro-time. We can create an expression in which the function f expresses is called, and we can beta-reduce the whole output. It seems that the mismatch between f: Expr[Int] => Expr[Int] in the reference vs f: Expr[Int => Int] which I can get to at least compile, meaningfully changes what one can do with the it.

object ExprMatchingPlayground {

  inline def foo(): Int = ${ scrutinizeHoas }

  def scrutinizeHoas(using qctx: Quotes) = {
    new Helper(using qctx).scrutinizeHoasHelper()
  }

  class Helper(using qctx: Quotes) {
    import qctx.reflect.*
    
    def nowWithBeta[T: Type, U: Type](f: Expr[T => U]): Expr[T] => Expr[U] =
      (x: Expr[T]) => Expr.betaReduce('{ $f($x) })

    def now[T: Type, U: Type](f: Expr[T => U]): Expr[T] => Expr[U] =
      (x: Expr[T]) => '{ $f($x) }

    def scrutinizeHoasHelper(): Expr[Int] = {
      // example from https://docs.scala-lang.org/scala3/reference/metaprogramming/macros.html#hoas-patterns-1
      // see stack overflow question https://stackoverflow.com/questions/77718835/why-does-this-scala-3-macros-reference-example-of-hoas-fail-with-type-must-be-f

      val w = '{ ((x: Int) => x + 1).apply(2) } match {
        case '{ ((y: Int) => $f(y): Int).apply($z: Int) } =>
          // f may contain references to `x` (replaced by `$y`)
          // f = (y: Expr[Int]) => '{ $y + 1 }
          println(s"f = ${f.asTerm.show(using Printer.TreeCode)}") // f = ((y: scala.Int) => y.+(1))
          val g = now[Int, Int](f) // can also use `nowWithBeta`
          g(z)
        case _ => '{ 0 }
      }
      // if we just use `now`, we print `w = ((y: scala.Int) => y.+(1)).apply(2)`
      // if we use `nowWithBeta`, we just print `w = 3`
      println(s"w = ${w.asTerm.show(using Printer.TreeCode)}") 

      w
    }
  }
}

I am not well-versed in scala 3 or especially in scala 3 macros, and it's possible I've made some error. But how is one to learn, if the material in the official reference do not work as described?

[nicolasstucki]

This example comes from a pre-3.0.0 version of the HOAS pattern. I will update the example. @abeppu, as far as I can tell, your understanding of the system is correct. Just note that now will also beta-reduce, but it will happen after the macro has expanded (in some later optimization phase).

There is also a bug in the error message that needs to be fixed ($<none>(y): XYZ). It should have printed ($f(y): XYZ).