Correspondence variables

[timothypratley]

Problem

The current options for matching or substituting the same thing twice are insufficient.

Minimal Example

Consider a vector of numbers that should consist of pairs of matched numbers:

(m/rewrite [1 1 2 2 3 3]
  [!n !n ...]
  [!n !n ...])
;;=> [1 1 2 2 3 3]

This is an incorrect solution because memory variables have no correspondence. They naively collect and disperse directly to matches with no observance of their corresponding scope marked by ... in this case.

(m/rewrite [1 2 3 4 5 6]
  [!n !n ...]
  [!n !n ...])
;;=> [1 2 3 4 5 6]

This is surprising behavior as it runs against the intuition of symbols unifying.

Current tools for solving

The most direct solution to pairing is to use recursion in some form:

(m/rewrite [1 2 3 4 5 6]
  []
  []
  [?n ?n & ?more]
  [?n ?n & (m/cata ?more)])
;;=> FAIL

(m/rewrite [1 1 2 2 3 3]
  []
  []
  [?n ?n & ?more]
  [?n ?n & (m/cata ?more)])
;;=> [1 1 2 2 3 3]

Already we start to lose the visual advantage and fall back to a linguistic description of recursive behavior with base cases and self-reference. It is not possible to pass any context via m/cata so if you want to do that, you must use m/app and split out a separate function which even further obscures the structure.

Proposed solution

A new concept, a "correspondence variable":

(m/rewrite [1 2 3 4 5 6]
  [.n .n ...]
  [.n .n ...])
;;=> FAIL

(m/rewrite [1 1 2 2 3 3]
  [.n .n ...]
  [.n ...])
;;=> [1 2 3]

.n is a correspondence variable. It behaves like a logic variable and unifies in the expression.
It binds to multiple values, but only once per recursive scope.

These semantics are less surprising and more powerful.

Implementation

I have very little idea on how to implement this.

One thought though is that correspondence variables could either be fully expanded as padded memory variables or indexed by their corresponding ... form.

Consider that [[.n [.m ...]] ...] can be annotated as [[.n [.m ...M]] ...N],
and in the expression [[.n [.n .m ...M] ...N] logically .n unifies in the scope of ...N (which encompasses ...M), while .m unifies in the scope of ...M.

One curveball here is what if you wanted to reverse the scopes between the match pattern and the substitute pattern? To support that users would have to annotate the ... forms manually.

The existing constructs ..?n and ..?m are sufficient to ensure symmetric partitioning, but insufficient to provide logical partitioning.

One can simulate correspondence variables using m/and in conjunction with memory variables and mutable variables:
[(m/and !k !k*) ...] => [!k !k* ...] is the pattern to "duplicate" a binding, and you can force correspondence with a mutable variable:

[(m/and *k !k) [(m/and !k2 (m/let [!k* *k])) ...] ...]

Here the mutable variable ensures correspondence by creating a padded memory variable !k* that aligns with !k2 but additionally unifies with the outer value !k. Evidence that scope correspondence is possible.

Motivation

I've presented very simple examples to focus on the desired behavior, but these are not imaginary scenarios.
I have regularly come across this problem when processing schemas, often in the form of nested maps. One large example is the HappyGAPI project https://github.com/timothypratley/happygapi which takes Googles declarative API schema and turns it into a Clojure API. The examples presented here focus on vectors because maps are syntactically disadvantaged... I'll open a separate issue to discuss that disadvantage and how maps and sets can also make use of correspondence.

There have been several threads in Slack about how to do grouping and scoping that I believe are actually more elegantly solved with correspondence. For example the reshaping of nested maps by value. I believe this is an opportunity to leverage logic programming in a powerful and intuitive way.

[timothypratley]

Here is an example of how "correspondence" and "syntax disadvantage" conspire together...
Given a match and substitution pattern for a rewrite:

{:objects
      {!k {:description !user
           :fields      {!k2 {:resolve !resolve
                              & !more}}}}}
{:objects
      {!k {:description !user
           :fields      {!k2 {:resolve (m/app #(or %1 (keyword (str %2 %3))) !resolve !k !k2)
                              & !more}}}}}

Can you guess what I want to happen here? I just want to conditionally update the :resolve of an inner map. If it exists, leave it there, if not replace it with a name that depends on the outer key and the inner key. Pretty obvious? But this is not valid Meander.

A valid Meander solution is:

(s/rewrite
    {:objects
     {& (m/seqable [(m/and *k !k)
                    {:description !user
                     :fields      {& (m/seqable (m/and (m/let [!k* *k])
                                                       [(m/and !k2 !k2*) {:resolve !resolve & !more}]) ..!n)}}] ..?m)}}
    {:objects
     {& ([!k {:description !user
              :fields      {& ([!k2 {:resolve (m/app #(or %1 (keyword (str %2 %3))) !resolve !k* !k2*) & !more}] ..!n)}}] ..?m)}})

We lost the ability to see the shape of the problem because we need to resort to tricks to preserve correspondence and unspecified keys map syntax disadvantage causes spurious s-expressions.

[csharon]

Another example which might be related to that issue:

[{:ids    [1 2]  
  :patch "p1"}
 {:ids    [3]
  :patch "p2"}
 {:ids    [4 5]
  :patch "p3"}] => 
{:ids       [1 2 3 4 5]
 :id->patch {1 "p1" 2 "p1"
             3 "p2"
             4 "p3" 5 "p3"}}