Skip to content

Instantly share code, notes, and snippets.

@zeptometer
Last active August 28, 2023 11:18
Show Gist options
  • Save zeptometer/ad414dda221a9f9f99e4135b6b5c1c3c to your computer and use it in GitHub Desktop.
Save zeptometer/ad414dda221a9f9f99e4135b6b5c1c3c to your computer and use it in GitHub Desktop.
GSoC Final Report: Enhancement of quote pattern matching in Scala 3

GSoC Final Report: Enhancement of quote pattern matching in Scala 3

Summary

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.

Introduction

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.

Goal of the Project

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.

Outcomes of the project

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.

Bugfixes (Merged)

Issues Reported

Future prospect

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.

Supporting bounded type parameters

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.

Supporting variables with dependencies

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.

Learnings

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.

Acknowledgement

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment