Inlining partial pattern matches

Learning
1

Is there any way to define a set of pattern matches separately and then combine such that they match cases are inlined and we recover the performance of the combined match?

As a (contrived) example, let’s say I have a simple arithmetic expression language

type t =
  | Neg of t
  | Add of t * t
  | Mul of t * t
  | Lit of string

I want to modify expressions in this language so that -1 * n is always expressed as ~-n, 1 * n is expressed as n and 0 + n is always expressed as n.

Writing this as a single match:

let rec single t =
  match t with
  | Mul (Lit "-1", n) | Mul (n, Lit "-1") -> manual (Neg n)
  | Add (Lit "0", n) | Add (n, Lit "0") -> manual n
  | Mul (Lit "1", n) | Mul (n, Lit "1") -> manual n
  | _ -> t
;;

I can see, for instance, that the two cases matching on Mul will be compiled so that we only test for the tag once, as expected:

ocamlopt -dlambda   ./single.ml

...
case tag 2:
 (let (n/283 =a (field_imm 0 t/274))
   (catch
     (catch
       (catch
         (switch n/283
          case tag 3:
           (stringswitch (field_imm 0 n/283)
            case "-1": (exit 1 (field_imm 1 t/274))
            default: (exit 8))
          default: (exit 8))
        with (8)
         (let (*match*/293 =a (field_imm 1 t/274))
           (switch *match*/293
            case tag 3:
             (stringswitch (field_imm 0 *match*/293)
              case "-1": (exit 1 n/283)
              default: (exit 7))
            default: (exit 7))))
      with (7)
       (switch n/283
        case tag 3:
         (stringswitch (field_imm 0 n/283)
          case "1": (exit 3 (field_imm 1 t/274))
          default: (exit 6))
        default: (exit 6)))
    with (6)
     (let (*match*/296 =a (field_imm 1 t/274))
       (switch *match*/296
        case tag 3:
         (stringswitch (field_imm 0 *match*/296)
          case "1": (exit 3 n/283)
          default: (exit 4))
        default: (exit 4)))))
case tag 3: (exit 4))
...

Now suppose instead I want to define each rewrite as a separate function and then compose them:

let partial_1 = function
  | Mul (Lit "-1", n) | Mul (n, Lit "-1") -> Some (Neg n)
  | _ -> None
;;

let partial_2 = function
  | Add (Lit "0", n) | Add (n, Lit "0") -> Some n
  | _ -> None
;;

let partial_3 = function
  | Mul (Lit "1", n) | Mul (n, Lit "1") -> Some n
  | _ -> None
;;

let rec composed t =
  match partial_1 t with
  | Some t -> composed t
  | _ ->
    (match partial_2 t with
     | Some t -> composed t
     | _ ->
       (match partial_3 t with
        | Some t -> composed t
        | _ -> t))
;;

Looking at the lambda output, this will never “see through” the function applications and recombine the now separate matches, leading to repeated inspection of tags.

Is there anyway to coerce the compiler into doing this or an alternative way to decompose matches?

1 Like
2

Not exactly what you asked, but this is the typical use-case of “smart constructors”. Instead of construcing your values with Mul and Add you would define “smart constructors”

let mul n m =
  match n, m with
  | Lit "-1", n | n, Lit "-1" -> Neg n
  | Lit "1", n | n, Lit "1" -> n
  | n, m -> Mul (n, m)

let add n m =
  match n, m with
  | Lit "0", n | n, Lit "0" -> n
  | n, m -> Add (n, m)

and use add instead of Add and mul instead of Mul. That way, every value is guaranteed to never contain terms of the form “(-1) * n” or “1 * n” or “0 + n”, etc and you do not need to do any a posteriori simplification.

Cheers,
Nicolas

2 Likes
3

Not in vanilla OCaml, but there’s been some work on it… Specifically in MetaOCaml:
BER MetaOCaml make_match

It’s a special case of active patterns, see e.g. Active Patterns - F# | Microsoft Learn

1 Like
4

That would certainly work for the example but, unfortunately, my real-world use case has a pair of scrutinees which are constructed separately so I don’t know which simplifications should apply at the point they are constructed

5

Yeah, I think Active Patterns are pretty much what I’m looking for. I guess it’s back to a single match for now

6

Are you saying that you would expect F# to compile the active pattern version of this code to roughly as efficient pattern matching code as what ocamlopt does for the single match version in the OP? It has been some time since I used F# in anger and inspected the generated code, but when I did before active patterns compiled to method calls and would be not as good as even the chained option version. Have things changed?

1 Like
7

Well, I’m saying I want a language feature which allows me to treat matches as first-class. I don’t know whether F# Active Patterns do this efficiently or not.

8

I just checked on SharpLab what does F# emit for matches with inline partial active patterns (non-inline are of course just a tree of method calls), and sadly the inlining still doesn’t result in a merged decision tree.

If we just wanted to reuse this particular set of patterns, a total active pattern does keep the decision tree merged (we wrote it that way), but then an additional match on an intermediate ChoiceOf* value is done, even when inlined. Honestly, I expected the F# compiler to handle inline patterns a bit more efficiently than it actually does, but at least partial ones can now be written without allocations.

2 Likes