Dynamically generate a pattern matcher depending on some value

[akater]

(match '(0 . 1)
  ((list* x _)
   (match 2
     (x `(x-previously-matched-is-invisible (x = ,x)))
     (_ 'x-previously-matched-to-0-is-visible))))
=>
(X-PREVIOUSLY-MATCHED-IS-INVISIBLE (X = 2))

I believe it's natural to rather have internal x bound to 0 in this case.

Is there a reason to not inherit bindings in nested match forms?

[guicho271828]

that kind of construct is called unification. use eq pattern for that purpose (where the match fails, since it fails to unify 2 and 0)

[akater]

Right. I was staring at https://github.com/m2ym/optima/issues/57 before posting here, and yet missed it in in plain sight. Thank you.

[akater]

This won't do when the external variable is itself bound to a pattern:

(when-match x '(list f _)
    (match 'something
      ((equal x) `(x = ,x))
      (x `(x = ,x))))

I studied the sources, hoping to add some (pattern x) clause alongside (equal x) but couldn't find the spot to patch. Could you point me in the right direction?

[guicho271828]

(when-match x '(list f _)
  (match 'something
    ((equal x) `(x = ,x))
    (x         `(x = ,x))))
(X = SOMETHING)

This is an expected behavior because '(list f _) is not equal to 'something. What's the problem?

[akater]

I seek to match against a pattern bound by an external match-like form, not against a constant expression. equal is for a different purpose. My latter example merely demonstrates that neither (equal x) nor x would make match match against (list f _). Indeed, (equal x) matches against constant expression '(list f _), and x matches against arbitrary pattern which will bind its candidate to x if it matches, thus losing previous meaning of x.

Here is an ugly expression that evaluates as desired and reflects what I'm actually trying to write.

(if-match (rewriting-rule :pattern patt :rhs rhs) rule
  (eval `(match ',expr
            (,patt ,rhs)
            (_ 'something-else)))
  (error "Can't interpret ~S as as a rule" rule))

In the initial message of this issue, I was asking why wouldn't simple

(if-match (rewriting-rule :pattern patt :rhs rhs) rule
  (match expr
     (patt rhs)
     (_ 'something-else))
  (error "Can't interpret ~S as as a rule" rule))

have the same effect since patt is not free at the moment of expansion. I guess the answer is “because in Common Lisp we are generally unaware of lexical context when macroexpanding”. Anyway, since (equal x) knows what x was, then even “because it was so in Optima” would do as the answer, so let's forget it.

Since (equal x) knows about the external x, I want to program a similar form that would achieve the goal desired:

(if-match (rewriting-rule :pattern patt :rhs rhs) rule
  (match expr
     ((pattern patt) rhs)
     (_ 'something-else))
  (error "Can't interpret ~S as as a rule" rule))

where (pattern patt) expands to the value of patt, as found in the environment before match macroexpands. match then matches against the pattern that is the value of patt.

[guicho271828]

I finally see what you are trying to implement, which is to dynamically generate a pattern matcher depending on some value. And, that idea is orthogonal to or incompatible with pattern matching or compile-time operation (macroexpansion) in general. So your example using eval is a possible choice.

Performance-wise, a better option is to have something like this:

(defclass rewriting-rule (...)
   ((pattern ...)
    (rhs ...)
    (%function ...)))
(defmethod compile-rule (rule)
   (setf (%function rule)
           (compile
           `(lambda (expr)
               (match ',expr
              (,patt ,rhs)
              (_ 'something-else)) nil))))

The final and the most unlikely option is to support such a construct. As the author of the library I know it is possible. Check the level1 source code and how I am switching the binding form from let and symbol-macrolet using :place tag. You can additionally modify the code to support progv and write your high-level pattern pattern using the progv-based level1 guard1 pattern, although it could be ugly or slow.

[guicho271828]

BTW, I believe Optima does not support such a feature neither.

[akater]

If you say it's incompatible with pattern matching, I'm going to trust your judgement. The particular bit of functionality I want is easy to implement in a more natural way. Trying to write a strictly pattern-matching-based solution was a somewhat purist challenge. Thanks for letting me know the boundaries of this approach. My demands to pattern matching are formed by Mathematica which is insanely permissive when it comes to rewriting and metaprogramming, and given its closed nature it is difficult to see whether something in it was inherently slow or ugly.

I still hope to look into that level1 construction sometime. Thank you for your guidance.

[guicho271828]

Oh, please don't feel offended. I used the word "ugly" only because you referred your own eval-based code ugly. I think here eval makes perfect sense --- the sole purpose of eval is to interpret and execute new code dynamically, and to me ugliness is how much code is added, which is not a big deal in your case.

In contrast, slowness is inherent in dynamism, so it is unavoidable regardless of the language. If Mathematica also have such a construct, due to the inherent nature of dynamism it must be using eval or other interpreter-based approach, which is slow, or calling compile, which takes time in the first call but is faster in the subsequent calls, or the intermediate, hotspot JIT approach.

[guicho271828]

Well, just implemented a case that can handle a single variable. Supporting arbitrary pattern would require a bit more effort.

[akater]

I'm not offended in any way. Using straightforward eval is simply suspicious here. Term rewriting is itself a very general mechanism and could be used to implement a Lisp dialect from scratch. (Which is sort of what Mathematica does — though 1) we can't really know how non-Lispy it is inside, and 2) its UpValues feels too general to be a plain Lisp construction.) Hence, using an existing Lisp's eval in an implementation of a term-rewriting mechanism (with no way around it, at least) would be somewhat irresponsible.

[guicho271828]

It's 3:30 in the morning and my brain has stopped. Feel free to implement the rest.

[guicho271828]

in the progv branch.