Support compile-time pattern / spec composition

[jvantuyl]

Very often, I find myself needing to be able to create a sort of "compound pattern match" programmatically. MatchSpecs, being a data-structure to represent matches, seem to be the perfect-building block for this.

Adapter Example

For example, I currently have code with "adapters" that convert between different types of data. The heart of this adapter system is a gnarly, hard-to-understand, probably-not-well-performing function. What it does is:

• discovers all of the adapters that have been defined (via Behaviour.Reflection)
• loops over the adapters
• calls a function that performs a part of the match
• finds the first one that "matches" and executes a different function to do that actual adaption

This works, but it's pretty unwieldy. Notably, the first version would try the pattern matches and then catch the FunctionClauseError. This turned out to be both slow (because exceptions) and error prone (because it couldn't easily distinguish between top-level match failures easily). Instead I now require the functions each have a catch-all match that returns false. Practical, but it makes for complexity all over the codebase without any real benefit.

Proposed Feature

Matcha has neither the performance problems nor the unneeded complexity. I would like to use it as a basis to compose patterns. I could build this with something as easy as Matcha.Spec.or([specs]). While or is what I need, I'd imagine that and would come in handy, too.

I suspect this isn't much harder than combining the clauses somehow and recompiling the matchspec. Any idea how hard this would be?

Long-Term Goal

In the long run, I'd love to build something more like a protocol, like this:

import Matcha, only: [defspec: 2]

defmodule MyApp.ImageConverter do
  defspec convert(src, dst)
end

defmodule TiffAdapter do
  use MyApp.Adapter.Spec

  @specimpl adapt: 2
  def adapt(%TiffImage{}, %RawImage{}) do
    ...
  end
  def convert(%TiffImage{}, %GifImage{}) do
    ...
  end
end

defmodule PngAdapter do
  ...
end

defmodule ClientCode do
  def do_stuff() do
    ...
    MyApp.ImageConverter.convert(img1, img2)
    ...
  end
end

This would essentially be using Matcha at the core of a multi-type dispatch system. Something like what you find in ObjectiveC and the like.

[christhekeele]

This is a very cool idea, and I like it a lot!

I'm in the process of picking back up a partially-complete major refactor of Matcha for a v0.2.0 that should solidify both the internal and public APIs! I think that'll be a better base from which to think through what this implementation might look like. So probably more thoughts to come as I work through that!

[jvantuyl]

One other thought. Since I've written this, I've run into the question of "What happens if two clauses using that spec overlap?"

Thinking about how this is handled in normal matches, it takes the first one defined. That seems to be a bit unwieldy here, since moving around which is defined first can be difficult between different files. In that case, I'd propose adding an order or precedence value that you could sort them. This may require some sort of "consolidation" like protocols do, but that's not really a bad thing, IMO.

It may also be beneficial to see if any of them overlap and just forbid it without ordering. Is there a function to determine if two patterns overlap? If there was, that would be useful here. (And probably elsewhere, I'd suspect.)

I may work on the macro side of this a little bit. When I see a v0.2.0 release or prerelease, I'll circle back on this.

[christhekeele]

Is there a function to determine if two patterns overlap? If there was, that would be useful here.

Not really, therein lies the complexity. What Matcha does with your elixir code at compile time is convince the compiler that it is building a group of clauses out of it, let it issue compiler warnings/errors (like overlapping clauses), then not build a function and transform the AST into Matcha.Spec data structure literals for use at runtime, instead.

There's nothing stopping you from taking those runtime data structures and combining them at runtime, as you've discovered! But you lose all the guarantees that Elixir's compiler gives you.

Right now there is support for validating a spec at runtime, which calls the underlying erlang matchspec validation/test function. That's a whole nother set of guarantees, though. (The macro also ensures this is invoked this at run time.) I'm not sure what it does in the overlapping clause scenario. You could find out, try (on branch latest):

spec1 = Matcha.spec...
spec2 = Matcha.spec...
spec3 = %Matcha.Spec{source: spec1.source ++ spec2.source, context: Matcha.Context.Table}
Matcha.Spec.validate!(spec3)

To get composable specs with compile-time guarantees, we'd have to bring those spec's AST together at compile time and do the same convince-Elixir-we're-a-function trick, with all source code on hand. That becomes tricky because matchspecs also allow you access lexical scope (because they just become data structures in the scope they are built, supporting variable references). They aren't closures on their own, and can rely on the surrounding environment, so it's hard to decide how we'd compose them at one call site, then combine them at another.

TL;DR: it's easy to combine specs at runtime today, but there's not a good way to support that without losing a lot of the value Matcha tries to provide, like pattern overlapping, since that's driven by the Elixir compiler.

---

It does sound like you are mostly wanting to merge specs at compile-time, however. That use-case sounds easier to support, we should be able to support a composition API that looks more like this:

@spec1 Matcha.spec...
@spec2 Matcha.spec...
@spec3 Matcha.Spec.merge([@spec1, @spec2])

In this context the "lexical scoping" is already the module's compile-time context, so there's no fuzziness going on about what runtime variables are available where you happen to insert @spec3 into your code. I think the only change needed to support that would be having the resultant spec data structs created by Matcha.spec also carry its AST source code with it, so the Matcha.Spec.merge macro could build a new pseudo-case-clause to submit to the Elixir compiler for validation.

Does this scenario match with how you are thinking about using Matcha? Remember, you can still insert them into runtime logic (in this case by referencing different module attributes, say within a case block).

---

The alternative is trying to find a way to wrap specs in something that acts like a closure. This is actually why everything implemented so far has been in terms of macros called Matcha.spec; so that in the future we can provide something like defspec name(pattern), do: body on top of them. That's something further out on the ol' roadmap, as they have a different set of considerations to think through.

[jvantuyl]

(This is long and speculative. I think it's useful, but don't take anything here to be implied as particularly well-thought-out.)

My pet use-case is selective receive. That's the one place that composable matches could (IMHO) revolutionize Erlang and Elixir.

Consider GenServer. Why can't you just use selective receive? It makes a lot of things easier. You can just listen for what you need and let other messages build up to be handled when it's convenient. Why doesn't it just let you do that?

It doesn't because there's no way to compose its receive needs with your receive needs.

Notably GenStateMachine actually tries to solve this. And... it's a nightmare pretty unwieldy. You have a generic event model now, you can "postpone" them, to do it right you often end up with some pretty crazy pattern matching. And it's hard to inspect the internal mailbox to make sense of things. The list goes on.

Let's imagine a better way to do this. Probably not within Matcha but maybe in another package building on it.

defmodule MagicServce do
  @moduledoc """
  a contrived example to show composible receive
  """
  use Matcha.ZenServer

  @type t() :: %__MODULE__{}

  # a struct for state
  defstruct []

  # probably a bunch of API stuff here

  @impl ZenServer
  @spec handle_call(call_info, ZenServer.from(), t()) :: ZenServer.return_or_future()
  def handle_call({:blocking_thing, timeout}, _from, state) when is_integer(timeout) do
    capture_receiver do
      {:some_match, stuff} when precedence(1) ->
        {:reply, {:ok, stuff}, state}
    after
      timeout ->
        {:reply, {:error, :timeout}, state}
    end
    |> ZenServer.system_receiver()
  end
end

Maybe that's a bit convoluted because there's likely a macroverse of madness going on in there... but the general idea is build a match, compose it with other matches, and then somehow selectively receive on the whole thing.

Maybe this isn't the best way to do this, but the general ability to combine pattern matches is killer in so many places. This is an area where I think the compiler's errors / warnings would be necessary but not sufficient. Given that, I'd expect some validation logic might be helpful. (That said, maybe leave that for the 2.0 version of this feature.)

[christhekeele]

My pet use-case is selective receive. That's the one place that composable matches could (IMHO) revolutionize Erlang and Elixir.

That's an interesting notion indeed. One observation I made in my ElixirConf US 2022 talk is that MSs are only truly valuable where the erlang VM has special support for them (today: tracing and ETS) where it is already dealing with a bunch of pseudo-contiguous in-memory data living in C++ land.

There are relatively few places where this is applicable, but the process mailbox is indeed one of them. It would be pretty cool if there was some native API for providing an MS to receives, allowing the BEAM to leverage the raw pattern matching engine with them in C++ land before ever passing a response back into your erlang/Elixir program's memory space...

As is, this is only possible via manually invoking :ets.match_spec_test (or Matcha's Matcha.Spec.call) inside a recieve block, when the VM has already passed the message over from C into our language's runtime. Essentially,

receive do
  any_message ->
    match_result = Matcha.Spec.call!(composed_ms, any_message) 
    if match_result do
      handle_receive_match(result)
    else
      somehow_re_enqueue_message(any_message)
    end
end

Of course, this loses all the benefits of using MSs to pattern match in raw C land before pushing the data into our lang's runtime. If some match_spec_receive existed, this could instead become something like:

match_spec_receive(Matcha.spec do
  pattern when guards -> body
end.source)

or

composed_ms = Matcha.Spec.somehow_compose(...)
match_spec_receive(composed_ms.source)

or, with macro support,

Matcha.receive do
  pattern when guards -> body
after
  timeout -> other
end

[jvantuyl]

The big thing I want is the whole "waiting if nothing matches" behavior (i.e. selective receive). That style of programming is a lot simpler.

Consider GenServer. It has to receive messages with no real knowledge of what they might be. So, when it blocks, it receives its sys-messages then throws anything else at handle_info. As a consequence, it's got to be handled right now. GenStateMachine runs into this, too. The whole reason they have a pending action queue and the whole "postpone" action is to emulate this.

So you now leak the details of all messages into your code. You can't build any abstractions on it. It would be a lot handier to accumulate those messages instead. But without the ability to provide an external pattern to match-and-dispatch, there's no mechanism to do so.

Two places this pops up that stick out for me are :gen_tcp and Task. If you use either of these in a GenServer, you have to deal with their internal messages rather than calling nice API functions that selectively consume messages. With :gen_tcp, you basically can't use passive mode and expect it to be useful. With Task, you basically catch the raw response to the monitors used by Task internally (see here).

Imagine if you could do something like this...

defmodule MagicServer do
  use GenServer

  dispatch_info Task.handle_info/2
  # internally, there's already: dispatch_info __MODULE__.handle_info/2)

  def handle_info(...), do: ...
end

The idea there is that Task can now plug in to receive its own messages. Presumably it can then do something when dispatched it can do something like send(self(), {:task_exit, {%Task{}, reason}) instead of exposing its guts.

What's more interesting, though, is that now GenServer is doing the same thing with the handle_info/2. So it can just not receive messages that aren't handled. Then libraries and the like can consume those messages when called and abstract the message passing away from the user's concerns.

It would get even cooler with GenStateMachine, since you could dispatch to different combinations of handlers in different states. And you wouldn't consume messages that other states care about. So you no longer need a :postpone action.

Under the hood, these things would just be collecting functions and composing all of their matches. Something like:

# assume we have the functions we might dispatch into collected in the handler_funcs variable
receive do
  :normal_match -> ...
  :other_match -> ...
  :some_match = msg into handler_funcs as [func | _] ->
    Logger.debug("dispatching #{inspect(msg)} to #{inspect(func)}")
    func(msg)
  :low_prio_match -> ...
end

So you basically would have a way to snag the function heads you've been provided and get back a list of function heads that would match. Then you can dispatch into them and handle their return values as you see fit. And you reclaim all of the benefits of selective receive because you can now compose receivers and block on things that you don't want to receive yet.