In this project, I worked on expanding the capability of HOAS patterns of quote pattern matching feature under the mentorship by Nicolas Stucki. In addition to several bugfix PRs, I made a PR that allows HOAS patterns to hold type arguments. This feature will enable quote patterns to analyze the structure of polymorphic functions/methods, which is not feasible in the current quote pattern matching.
Scala 3 macros support quote patterns that allow programmers to compare a quoted code fragment to another or to analyze its structure. When one analyzes the structure of a code fragment, one must be aware of binding structures: which variables occur freely in the code fragment and which don't. Higher-order abstract syntax (HOAS) patterns manages such information of binding structures.
'{ (y: Int) => y * 2 + 1 } match
// f binds to '{ (x: Int) => x * 2 } and '{ $f(3) } will be
// '{ ((x: Int) => x * 2)(3) }, which beta-reduces to '{ 3 * 2 }
case '{ (x: Int) => $f(x) + 1 } => '{ $f(3) }
case _ => ...In the example, the HOAS pattern $f(x) carries a pattern variable f and an argument x. It states that this pattern should match a code fragment with the occurrence of x, and f will have '{ (x: Int) => x * 2 } where the free variable x is expressed as a function argument. Then the example returns $f(3), which replaces the occurrence of x with 3; hence the returned code fragment '{ ((x: Int) => x * 2)(3) } will not have undefined variables.
You can find a detailed description of HOAS patterns in my project proposal.
In this project, my goal was to extend HOAS patterns to support type arguments like the following example.
'{ [A] => (x: A, y: A) => (x, y) } match
case '{ [B] => (a: B, b: B) => $f[B](a, b) }
=> '{ $f[Int](1, 2) }
case _ => ...This example analyzes an expression of a polymorphic function [A] => (x: A, y: A) => (x, y). The first case uses a HOAS pattern $f[B](a, b) with type arguments, which allows occurrences of the type variable B in addition to a and b. The current implementation does not allow type arguments; hence, we cannot analyze the body of polymorphic functions.
This extension requires modification of two parts of the dotty compiler: type checker and quote pattern matcher. The design of such an extension is provided in Nicolas Stucki's Ph.D. thesis, and I planned to make an implementation based on the theory.
The code changes for the enchantment of HOAS patterns are almost done and are under review in the PR below. When the PR passes the code review, it will be merged as an experimental feature.
#18271 Support HOAS pattern with type variables for quote pattern matching
This PR includes the following changes:
- Experimental flags to enable this feature
- Extension to type checker (static semantics)
- Extension to quote pattern matcher (dynamic semantics)
- Tests for the new feature and regression tests for backward compatibility
- Documentation
In addition to this main PR, I worked on several bug fixes of quote patterns and reported issues. Especially, #17567 Make HOAS Quote pattern match with def method capture and #18040 Inhibit typer to insert contextual arguments when it is inside arguments of HOAS patterns were non-trivial issues that required deep understanding of compiler internals. Working on those issues helped me understand the internals of the dotty compiler.
- #17567 Make HOAS Quote pattern match with def method capture
- #18040 Inhibit typer to insert contextual arguments when it is inside arguments of HOAS patterns
- #18203 Fix debug print of QuoteMatcher to work on match failure
- #18191 Cleanup the unused symbol Definitions.QuotedRuntimePatterns_patternHigherOrderHole
- #17905 Type error with HOAS quote pattern with contextual method capture (Fixed by #18040)
- #17933 Quote pattern match failure due to optimization (Resolved as intended behavior)
- #18144 Type error when using HOAS pattern with arguments that have dependency
- #18308 Wrong staging level is inferred when a variable is used in a HOAS pattern over splice/quote redex
- #18462 Undescriptive error message for HOAS patterns with type parameters
During this project, I got several ideas that will improve the capability of quote patterns in the future and discussed them with Nicolas. I summarize them below for future reference.
The extension developed in this project will support type variables that don't have type bounds. For example, the following quote patterns won't be typed because the type parameter A has an upper bound Int.
body match
case '{ [A <: Int, B] => (x : A, y : A) => $b[A](x, y) : A } =>
'{ b[Int](1, 2) }
case _ => Expr("not matched")This limitation inherently comes from the base type system. We want to generalize the type system to support type parameters with bounds and prove its soundness. Then, we can safely extend this feature to allow type parameters with bounds.
As reported in #18144 Type error when using HOAS pattern with arguments that have dependency, the current HOAS patterns doesn't work when its parameters have dependencies.
// the class DSL, IntDSL is defined in another file
body match
case '{ (x: DSL) => (y: x.N) => { x.next($a(x, y) : x.N) } } => '{ $a(IntDSL, IntDSL.zero) }
case _ => ...In this example, the HOAS pattern $a(x, y) has two variables where the type of y is x.DSL with dependency on x. For such a case, we want to have a HOAS pattern like $a(x)(y) and expect a to have the type (x : DSL) => x.N => x.N . Or, we can consider an even more complex case where type parameters depend on dependent types. The code below shows a case where A depends on x and y depends on A.
case '{ (x: DSL) => [A <: x.N] => (y: A) { $a(x)[A](y) } }Those examples give us insight that we might want to generalize HOAS patterns with multiple value/type parameters to support variables with complex dependencies.
This project was a valuable opportunity to engage with compilers that are actually used in the industry. During the project, I learned many things:
- Scala 3 language features
- Internals of the dotty compiler
- Implementation of quoted code and quote patterns
Understanding the implementation of quoted code and quote patterns was enjoyable because my research topic is metaprogramming. The insights I got from this project will benefit my future research.
First, I want to thank Nicolas Stucki for all his support during this GSoC project. He helped me improve my project proposal, guided me on Dotty development, and provided weekly meetings to discuss many topics. I had great fun with those discussions and got many insights about Scala, type systems, and language design. Also I want to thank Anatolii Kmetiuk and Scala Center for organizing GSoC projects. I appreciate peer reviews on my project proposals by Yuichi Nishiwaki, Keiichi Watanabe and Masaki Waga. Last but not least, I would like to express my gratitude to Google for providing this wonderful opportunity to be part of OSS development.