guicho271828 / trivia

Pattern Matcher Compatible with Optima
Other
334 stars 22 forks source link

guard example from the wiki: invalid number of arguments #125

Closed vindarel closed 3 years ago

vindarel commented 3 years ago

Hello,

This example:

(match (list 2 5)
  ((guard (list x y)     ; subpattern1
          (= 10 (* x y)) ; test-form
          (- x y) (satisfies evenp)) ; generator-form, subpattern2
   t))

from https://github.com/guicho271828/trivia/wiki/Logic-Based-Patterns

throws:

invalid number of arguments: 4
   [Condition of type SB-INT:SIMPLE-PROGRAM-ERROR]

Restarts:
 0: [REPLACE-FUNCTION] Call a different function with the same arguments
 1: [CALL-FORM] Call a different form
 2: [RETRY] Retry SLIME REPL evaluation request.
 3: [*ABORT] Return to SLIME's top level.
 4: [ABORT] abort thread (#<THREAD "repl-thread" RUNNING {1001BE1B63}>)

Backtrace:
  0: ((QUOTE GUARD) (LIST X Y) (= 10 (* X Y)) (- X Y) (SATISFIES EVENP)) [external]
  1: (TRIVIA.LEVEL2:PATTERN-EXPAND-1 (GUARD (LIST X Y) (= 10 (* X Y)) (- X Y) (SATISFIES EVENP)))
  2: (TRIVIA.LEVEL2:PATTERN-EXPAND (GUARD (LIST X Y) (= 10 (* X Y)) (- X Y) (SATISFIES EVENP)))
  3: (TRIVIA.LEVEL2:PATTERN-EXPAND-ALL (GUARD (LIST X Y) (= 10 (* X Y)) (- X Y) (SATISFIES EVENP)))
  4: (TRIVIA.LEVEL2.IMPL::PATTERN-EXPAND-ALL/LIFT0 (GUARD (LIST X Y) (= 10 (* X Y)) (- X Y) (SATISFIES EVENP)))
  5: (TRIVIA.LEVEL2.IMPL::PATTERN-EXPAND-ALL/LIFT (GUARD (LIST X Y) (= 10 (* X Y)) (- X Y) (SATISFIES EVENP)))
  6: (TRIVIA.LEVEL2.IMPL::EXPAND-MULTIPATTERNS ((GUARD (LIST X Y) (= 10 #) (- X Y) (SATISFIES EVENP))))
  7: (TRIVIA.LEVEL2.IMPL::EXPAND-CLAUSE (((GUARD # # # #)) T))
  8: ((MACRO-FUNCTION TRIVIA.LEVEL2:MATCH2*+) (TRIVIA.LEVEL2:MATCH2*+ ((LIST 2 5)) (T) ((#) T) ((TRIVIA.LEVEL2.IMPL::_) NIL)) #<NULL-LEXENV>)
  9: ((FLET SB-IMPL::PERFORM-EXPANSION :IN MACROEXPAND-1) #<FUNCTION (MACRO-FUNCTION TRIVIA.LEVEL2:MATCH2*+) {22F466EB}> NIL)
 10: (MACROEXPAND (MATCH (LIST 2 5) ((GUARD # # # #) T)) #<NULL-LEXENV>)

How should it be fixed?

Best,

SBCL 1.4.5-debian, QL dist "2020-12-20"

guicho271828 commented 3 years ago

generator-form and subpattern2 in guard is no longer supported in the current guard implementation, due to the difficulty in correctly characterising its behavior. This is reflected in the docstring, but unfortunately not in wiki.

Imagine the following case:

(match (list 1 (list 2 5) 2)
  ((list a
         (guard (list x y)     ; subpattern1
                (= 10 (* x y a b)) ; test-form
                (list (- x y) (- a b)) ; generator-form,
                (satisfies evenp)) ; subpattern2
         b)
   t))

What is the correct scope of test-form? Optima and guard forms in ML langs in general support referencing outside variables, which is implemnted by lifting of guard clauses.

This is ok, but when it comes to generator-form, you notice that the form must be evaluated after evaluating test-form, therefore generator-form must also be put in a scope where all variables x y a b are visible.

When multiple guard forms are nested, then this means that there is a sequence of tests, generation, matching. When multiple generator-forms are present, which one should be evaluated first? My brain stopped around here and I decided not to implement it rather than providing an ill-defined implementation.

vindarel commented 3 years ago

OK, thanks for the explanation.

I'll change the wiki the example to this simpler form:

(match (list 2 5)
  ((guard (list x y)     ; subpattern1
          (= 10 (* x y))) ; test-form
   t))