🍵 Matcha - first-class match specifications for Elixir

DEVLOG.md 2023-10-04

I thought I’d share a concept I’m finally playing with for Matcha: first-class filters!

For the sake of these snippets, assume we have:

krillin = %{name: "Krillin", age: 28, power: 1_770}
goku = %{name: "Son Goku", age: 27, power: 3_000_000}
saiyans = [krillin, goku]

:tea: Matcha Filters

This is actually one thing that prompted me to begin investigating building Matcha (:stopwatch: :eyes: over four years ago?!), something in-between a first-class match pattern and a full match specification.

Matcha Specs

For context, a Matcha.Spec is similar to a deferred case statement you can pass around as a variable, and match against when you want instead of immediately. It has native support in :ets via the :ets.select_* APIs, and Matcha makes it easy to use them against arbitrary in-memory data as well (without the nice performance you get in :ets applications, a little slower than an equivalent Enum.map and more limited).

As I dig into in my matchspec talk, a match spec is essentially a data structure that looks like this:

match_spec = [
  {pattern, guards, body},
  {pattern, guards, body},
  # ...
]

This mirrors an equivalent case statement, but without an immediate match target:

case target do
  pattern when guards -> body
  pattern when guards -> body
  # ...
end

You can execute a deferred match specification against an in-memory target like so:

Matcha.Spec.call(match_spec, target)

Most of the cool stuff with match specs comes from the fact that you can hand this match specification to :ets.select_* (with match_spec.source) and it will test every object in a table against your specification, and for any successful match, return a transformed result, much more efficiently than loading the entire table into a process’s memory and doing this all yourself with Enum.filter + Enum.map or for comprehensions.

Matcha Patterns

Matcha also has support for a Matcha.Pattern construct. This acts like just a stand-alone pattern part of a match spec, and you can think of it as a deferred pattern match/destructuring. That is, if you have code like:

%{name: name, age: 27} = target

Then you will get a MatchError if target is not a map with the provided keys, and if target’s age does not match 27 exactly; otherwise it captures the name of only 27-year-olds in a variable called name. Matcha lets you build deferred matches like so:

match_pattern = Matcha.pattern(%{name: name, age: 27})

Matcha.Pattern.match?(match_pattern, krillin)
#=> false
Matcha.Pattern.match?(match_pattern, goku)
#=> true
Matcha.Pattern.matched_variables(match_pattern, goku)
#=> %{name: "Son Goku"}

Matcha.Pattern.matches(match_pattern, saiyans)
# => [%{name: "Son Goku", age: 27, power: 3000000}]
Matcha.Pattern.variable_matches(match_pattern, saiyans)
# => [%{name: "Son Goku"}]

There are, of course, better ways to do this in your Elixir programs with in-memory data. But :ets also lets you leverage match patterns against an entire table at once, returning only objects that match the pattern, via the :ets.match_* APIs (providing them the match_pattern.source). Matcha supports this :ets usecase with Matcha.Patterns.

Matcha Filters

Running with the above example, what if we wanted to only match people on inexact criteria? Say, people who had more than some exact quality?

Match patterns alone aren’t expressive enough to do this. Match specifications are, but they use a special syntax to do it, that we can’t really convert Elixir code into—one of the key goals of Matcha.

What we really want is to support a first-class deferred pattern when guards construct, and that’s exactly what “filters” are intended to be:

match_filter = Matcha.filter(%{name: name, power: power} when power > 9_000)

Matcha.Filter.match?(match_filter, krillin)
#=> false
Matcha.Filter.match?(match_filter, goku)
#=> true
Matcha.Filter.matched_variables(match_pattern, goku)
#=> %{name: "Son Goku", power: 3000000}

Matcha.Filter.matches(match_pattern, saiyans)
# => [%{name: "Son Goku", age: 27, power: 3000000}]
Matcha.Filter.variable_matches(match_pattern, saiyans)
# => [%{name: "Son Goku", power: 3000000}]

The overarching goal is to:

  • Provide an API that allows using all features of :ets match specs, including :"$$" and :"$_", from syntactically valid Elixir code
  • Provide a new mode of querying :ets tables tersely when re-mapping matched objects is not a requirement, akin to a hypothetical set of :ets.filter_* functions
  • Further my Macro Crimes :tm: in my two personal projects where I convert Elixir code into both Elixir functions, and compatible :ets queries, where having first-class :ets-compatible functions heads is a boon

Higher-level Query Support

The main reasons why I haven’t much popularized the Matcha.Pattern APIs and the higher-level Matcha.Table APIs are because:

  • The Matcha.Filter support for guards is sufficiently more powerful I may deprecate Matcha.Pattern or downplay it but still support it for :ets.match_* equivalents
  • The Matcha.Table APIs may get more powerful variants that know how to navigate either patterns or filters agnostically, and I don’t want to commit to them just yet

As an example, in tandem with my Matcha.Filter experiments, I have the following code snippet working mostly as expected:

over_nine_thousand = Matcha.Table.query( 
  {_id, %{name: name, power: power}} when power > 9_000
) 
alias Matcha.Table.Query

for saiyan <- Query.where(table, over_nine_thousand) do
  IO.puts("Scanning #{saiyan.name}, #{saiyan.age} years old...")
end
for %{name: threat} <- Query.select(table, over_nine_thousand), threat == "Son Goku" do
  IO.puts("#{threat}'s power level is OVER 9_000!")
end

All still a rough work in progress, but interested in early feedback!

- Much :tea:, Chris

5 Likes