~technomancy/fennel#132: More general match patterns

I propose that there be less restrictions on (where) and (or) guards in patterns.

Right now, the match macro's patterns support the following at the top level of the pattern only:

(where pat guard1 guard2 ...)
(where (or pat1 pat2 ...) guard1 guard2 ...)
(pat ? guard1 guard2 ...) (legacy)

I propose this could be more general. What I would like to see different:

(where) and (where (or)) can appear anywhere in a pattern
new (or pat1 pat2) form without the where, that can be placed anywhere except for inside a (where).

The new form's restriction is there to prevent the problem of combinatorial explosion, where a failing guard would need to backtrack instead of continuing on to the next pattern.

Here are some examples to help explain:

(match ["a" 5]
  ;; new (or) rule
  [(or "a" "b" "c") (or 1 2 3)]
  true
  ;; (where) inside a pattern
  [(where x (= (type x) :string))
   (where y (= (type y) :number))]
  true
  ;; mix and match
  [(where x (= (string.lower x) x))
   (or 1 3 (where n (= (% n 2) 0)))]
  true)

(match [[3 5] [1 5] [3 4]]
  ;; Not allowed, matching this pattern requires complex backtracking
  (where [(or [x _] [_ x]) (or [y _] [_ y]) (or [z _] [_ z])]
         (= (+ x y z) 10))
  true)

The legacy ? forms would remain the same.

Status: REPORTED
Submitter: ~xerool
Assigned to: No-one
Submitted: 9 months ago
Updated: 8 months ago
Labels: enhancement

~technomancy 8 months ago

I think the suggestions are good improvements; the main reason we haven't done this is that I've suspected it would be difficult to add without making the implementation even more convoluted and hard to follow. But if you want to take a shot at it, be my guest!

~technomancy 8 months ago

The new form's restriction is there to prevent the problem of combinatorial explosion

Actually I'm having trouble understanding this part. Do you mean it as an implementation detail, or is this something the user needs to be aware of? It seems like with the two rules combined, from the user's perspective there is no restriction on where or can appear, which is what makes me think it describes an implementation detail, but I may be misunderstanding.

~technomancy added enhancement 8 months ago

~andreyorst 8 months ago*

I guess the combinatorial explosion in this context means that if a user writes
(match data
  [(or :a :b :c) (or 1 2 3)] body)
in the current way of how we expand or it would produce:
(match data
  [:a 1] body
  [:b 1] body
  [:c 1] body
  [:a 2] body
  [:b 2] body
  [:c 2] body
  [:a 3] body
  [:b 3] body
  [:c 3] body)
Or should really expand to a guar clause instead of duplicating body branches:
(match data
  (where [a_0_ a_1_]
    (and (or (= a_0_ :a) (= a_0_ :b) (= a_0_ :c))
         (or (= a_1_ 1) (= a_1_ 2) (= a_1_ 3)))) body)
I've implemented or in where the way it currently is because branch duplication is not that big of a problem on its own since only one branch will be ever executed, but it can generate a lot of code. This can be hard with complex match patterns inside or though.