guard/or commutativity about trivia HOT 12 CLOSED

I've added a note to the wiki page noting this behaviour,
https://github.com/guicho271828/trivia/wiki/Logic-Based-Patterns

Doesn't seem like there are others that might be counter-intuitive.

(Edit: Closing).

from trivia.

Re: commutativity --- I'm not sure this is the exact thing that is happening.
I think you are expecting that, once a branch of an or pattern is matched, it should not backtrack to consider other branches when the guarding failed.

The semantics of or is different. or represents a nondeterministic decision (as in prolog) and it does backtrack. That's why, after the guard (eql var 'x) failed, it reconsiders the second branch of or, matches var with (the thing x), then checks (not (eq var 'x)) (which is satisfied).

The current design comes from Optima.

I believe you can just write it without the guard pattern as follows. Note that the choice never backtracks to the previous clause.

(match '(the thing x)
  ((guard (list 'the _ var) (not (eql var 'x))) var))
  ((guard var               (not (eql var 'x))) var))

from trivia.

oops, the code above has the same error. I now realized that you just need to specify the type of var as a symbol.

(match '(the thing x)
  ((guard (or (list 'the _ var)
              (and (symbol) var)) ; (type symbol) also works
          (not (eql var 'x)))
    var))

from trivia.

this is more versatile

(match '(the thing x)
           ((guard (or (list 'the _ var)
                       (and var
                            (not (list 'the _ _))))
                   (not (eql var 'x)))
            var))

from trivia.

Sorry, by 'commutativity' I was referring in particular to how
(guard (or <pat1> ... <patn> ) <pred>)
is equivalent to
(or (guard <pat1> <pred>) ... (guard <pat1> <pred>)

I just found the semantics surprising. I'd have read (guard <pat> <pred>) as

• "satisfies <pat> then satisfies <pred>" as opposed to,
• "satisfies <pat> such that <pred> is T"

Either way is fine I suppose; are there other cases which could lead to such behaviour with guard ?

from trivia.

Here https://github.com/guicho271828/trivia/blob/master/level2/impl.lisp#L334 is the basic lift operation implemented in optima for guard patterns. I tried to replicate the behavior as much as possible. honestly it was tricky especially around the combination with not pattern. You can observe the struggle from e.g. https://github.com/guicho271828/trivia/blob/master/level2/derived.lisp#L60 .
The operation seems to come from a standard ML programming textbook which I don't know.

from trivia.

I discussed this issue with @marcoheisig and I proposed perhaps the guard pattern should be deprecated / removed or reimplemented.

Currently the guard pattern is not implemented based on pure pattern expansion, but by inserting the condition to an additonal meta-field in guard1 pattern. This is preventing using the balland2006 optimizer as the default compiler strategy. It seems to me like @akssri you are the only person who is actively using guard pattern. You can replace guard patterns with a sufficient number of custom conditioning and fail/skip/next macro.

from trivia.

I mostly use the guard1 schema of applying a predicate to a variable, so these changes shouldn't affect me much. Thanks for letting me know.

from trivia.

ok

from trivia.

I refactored the entire guard pattern compilation pass. I also identified a bug/difference from Optima. This is now all corrected, and moreover, it no longer uses the meta-information!
@marcoheisig

from trivia.

going to merge balland2006 optimizer in a couple of days

from trivia.

Wow, this is great news! Thank you very much for your effort!

from trivia.