~technomancy/fennel#133: 
Non-unifying pattern matching (matchless)

One of the most common problems with match is that people reuse locals which are already bound, leading to an accidental unification causing a mismatch.

We should make this easier to avoid. One approach would be to add it to match but I haven't thought of a way to do this that I really like; I think adding a new matchless form that's just like match but without unification seems better.

Status
REPORTED
Submitter
~technomancy
Assigned to
No-one
Submitted
2 months ago
Updated
14 days ago
Labels
enhancement

~rktjmp 20 days ago

Should the implementation be more complex than passing an option around? Just a POC.

match's default behaviour is impacting a macro for me, so I guess I am selfishly +1'ing this feature.

I think the name is a bit awkward, and I think explaining the differences is probably awkward too. Probably a good extension to have available when it really is needed though when locals or patterns cant be renamed.

How would it look if it were an option to match instead? After the match value "reads" better to me and is sort of inline with *collect options.

(match [a b] &scoped ;; &nolocals?
  [1 2] 3)

(match &less [a b]
  [1 2] 3)

Anyway here's a patch, probably not the patch. Do you have an implementation in mind? Instead of (or opts (})'ing everywhere I just elected to (?. opts key) where needed.

diff --git a/src/fennel/macros.fnl b/src/fennel/macros.fnl
index f2b7980..12d9c99 100644
--- a/src/fennel/macros.fnl
+++ b/src/fennel/macros.fnl
@@ -390,18 +390,18 @@ Example:
 
 ;;; Pattern matching
 
-(fn match-values [vals pattern unifications match-pattern]
+(fn match-values [vals pattern unifications match-pattern opts]
   (let [condition `(and)
         bindings []]
     (each [i pat (ipairs pattern)]
       (let [(subcondition subbindings) (match-pattern [(. vals i)] pat
-                                                      unifications)]
+                                                      unifications opts)]
         (table.insert condition subcondition)
         (each [_ b (ipairs subbindings)]
           (table.insert bindings b))))
     (values condition bindings)))
 
-(fn match-table [val pattern unifications match-pattern]
+(fn match-table [val pattern unifications match-pattern opts]
   (let [condition `(and (= (_G.type ,val) :table))
         bindings []]
     (each [k pat (pairs pattern)]
@@ -409,7 +409,7 @@ Example:
           (let [rest-pat (. pattern (+ k 1))
                 rest-val `(select ,k ((or table.unpack _G.unpack) ,val))
                 subcondition (match-table `(pick-values 1 ,rest-val)
-                                          rest-pat unifications match-pattern)]
+                                          rest-pat unifications match-pattern opts)]
             (if (not (sym? rest-pat))
                 (table.insert condition subcondition))
             (assert (= nil (. pattern (+ k 2)))
@@ -431,13 +431,13 @@ Example:
                                            (not= `& (. pattern (- k 1)))))
           (let [subval `(. ,val ,k)
                 (subcondition subbindings) (match-pattern [subval] pat
-                                                          unifications)]
+                                                          unifications opts)]
             (table.insert condition subcondition)
             (each [_ b (ipairs subbindings)]
               (table.insert bindings b)))))
     (values condition bindings)))
 
-(fn match-pattern [vals pattern unifications]
+(fn match-pattern [vals pattern unifications opts]
   "Take the AST of values and a single pattern and returns a condition
 to determine if it matches as well as a list of bindings to
 introduce for the duration of the body if it does match."
@@ -445,10 +445,11 @@ introduce for the duration of the body if it does match."
   ;; know we're either in a multi-valued clause (in which case we know the #
   ;; of vals) or we're not, in which case we only care about the first one.
   (let [[val] vals]
-    (if (or (and (sym? pattern) ; unification with outer locals (or nil)
-                 (not= "_" (tostring pattern)) ; never unify _
-                 (or (in-scope? pattern) (= :nil (tostring pattern))))
-            (and (multi-sym? pattern) (in-scope? (. (multi-sym? pattern) 1))))
+    (if (and (not (?. opts :matchless?))
+             (or (and (sym? pattern) ; unification with outer locals (or nil)
+                      (not= "_" (tostring pattern)) ; never unify _
+                      (or (in-scope? pattern) (= :nil (tostring pattern))))
+                 (and (multi-sym? pattern) (in-scope? (. (multi-sym? pattern) 1)))))
         (values `(= ,val ,pattern) [])
         ;; unify a local we've seen already
         (and (sym? pattern) (. unifications (tostring pattern)))
@@ -462,21 +463,21 @@ introduce for the duration of the body if it does match."
         ;; guard clause
         (and (list? pattern) (= (. pattern 2) `?))
         (let [(pcondition bindings) (match-pattern vals (. pattern 1)
-                                                   unifications)
+                                                   unifications opts)
               condition `(and ,(unpack pattern 3))]
           (values `(and ,pcondition
                         (let ,bindings
                           ,condition)) bindings))
         ;; multi-valued patterns (represented as lists)
         (list? pattern)
-        (match-values vals pattern unifications match-pattern)
+        (match-values vals pattern unifications match-pattern opts)
         ;; table patterns
         (= (type pattern) :table)
-        (match-table val pattern unifications match-pattern)
+        (match-table val pattern unifications match-pattern opts)
         ;; literal value
         (values `(= ,val ,pattern) []))))
 
-(fn match-condition [vals clauses]
+(fn match-condition [vals clauses opts]
   "Construct the actual `if` AST for the given match values and clauses."
   (if (not= 0 (% (length clauses) 2)) ; treat odd final clause as default
       (table.insert clauses (length clauses) (sym "_")))
@@ -484,7 +485,7 @@ introduce for the duration of the body if it does match."
     (for [i 1 (length clauses) 2]
       (let [pattern (. clauses i)
             body (. clauses (+ i 1))
-            (condition bindings) (match-pattern vals pattern {})]
+            (condition bindings) (match-pattern vals pattern {} opts)]
         (table.insert out condition)
         (table.insert out `(let ,bindings
                              ,body))))
@@ -513,6 +514,12 @@ introduce for the duration of the body if it does match."
     ;; many values as we ever match against in the clauses.
     (list `let [vals val] (match-condition vals clauses))))
 
+(fn matchless* [val ...]
+  ;; identical to match* but for match-condition options
+  (let [clauses [...]
+        vals (match-val-syms clauses)]
+    (list `let [vals val] (match-condition vals clauses {:matchless? true}))))
+
 ;; Construction of old match syntax from new syntax
 
 (fn partition-2 [seq]
@@ -636,4 +643,5 @@ returned as the value of the entire expression."
  :macrodebug macrodebug*
  :import-macros import-macros*
  :match match-where
+ :matchless matchless*
  :match-try match-try*}
diff --git a/test/macro.fnl b/test/macro.fnl
index 51c193c..7cb47e1 100644
--- a/test/macro.fnl
+++ b/test/macro.fnl
@@ -239,6 +239,20 @@
   (== (match nil _ :yes nil :no) "yes")
   (== (let [_ :bar] (match :foo _ :should-match :foo :no)) "should-match"))
 
+(fn test-matchless []
+  (== (let [a 10
+            b 20]
+        (matchless [1 2]
+          [x y] [x y a b]))
+      [1 2 10 20]
+      nil "matchless without a shadow")
+  (== (let [a 10
+            b 20]
+        (matchless [1 2]
+          [a x] [a x b]))
+      [1 2 20]
+      nil "matchless with a shadow"))
+
 (fn test-match-try []
   (== (match-try [1 2 1]
         [1 a b] [b a]
@@ -330,4 +344,5 @@
  : test-disabled-sandbox-searcher
  : test-expand
  : test-match-try
+ : test-matchless
  : test-literal}

~rktjmp 16 days ago

Probably something you've already thought about, but in my own macro I have used something similar to Elixir's Ecto library which lets you explicitly "pin" a value to an outer value in queries with the ^ symbol.

In match it might look something like

(local var 10)
(match x
  ^var true
  _ false)

Using an in-scope symbol without ^ is an compile error, using ^ on a symbol that is not in scope is also an error.

Obviously this is a breaking change, not really appropriate (2.0? I think the opt-in behaviour is a lot clearer.) but maybe something to think about - opt in on the symbol level instead of all or nothing.

Adding an opt-out syntax wouldn't be breaking but not as useful, you still have the accidental-match occurrences which is what you're trying to avoid.

~technomancy 14 days ago

Sorry for the lack of communication on this one! Unfortunately I think we may have some conflict here since ~xerool has been working on this in his branch here: https://git.sr.ht/~xerool/fennel/commit/32d8f6f21ca0479fe57886a6bdbba7120b96bc83

Register here or Log in to comment, or comment via email.