Proposal-pattern-matching: Ergonomics of "with" keyword in deeply-nested patterns

[JosephJNK]

The user-extensible patterns are awesome, but I think the use of the with keyword obscures pattern's intent when patterns are nested.

I propose syntax sugar for the following situation: Identifier\[...] desugars into ^Identifier with [...].

Here I'm going to present some FP-style code for balancing a red-black tree. There are four examples: Two using my proposed syntax sugar and two using the with keyword. (and a fifth example at the end, for funsies.) I'm presenting two for each case to show an example of what the patterns would look like if they were manually spaced for aesthetics and clarity and an example of what they might look like compressed by an autoformatter.

First, the setup that these examples depend on:

class Red {
  constructor(value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }

  static [Symbol.matcher](matchable) {
    if (!matchable instanceof Red) {
      return { matched: false };
    }

    return {
      matched: true,
      value: [matchabe.value, matchable.left, matchable.right]
    }
  }
}

class Black {
  constructor(value, left, right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }

  static [Symbol.matcher](matchable) {
    if (!matchable instanceof Black) {
      return { matched: false };
    }

    return {
      matched: true,
      value: [matchabe.value, matchable.left, matchable.right]
    }
  }
}

function rotate(x, y, z, a, b, c, d) {
  return new Red(y,
    new Black(x, a, b),
    new Black(z, c, d))
}

Now, here's the logic to rebalance a tree after inserting a node. This is based on the StandardML implementation here. The full algorithm is elided; the goal is to show the level of nesting that might be present in a functional-programming-style algorithm.

function balance(tree) {
  return match (tree) {
    when Black\[z,
                Red\[y,
                     Red\[x, a, b],
                     c],
                d]
                { rotate(x, y, z, a, b, c, d) }

    when Black\[z,
                Red\[x,
                     a,
                     Red\[y, b, c]],
                d]
                { rotate(x, y, z, a, b, c, d) }

    when Black\[x,
                a,
                Red\[z,
                     Red\[y, b, c],
                     d]]
                { rotate(x, y, z, a, b, c, d) }

    when Black\[x,
                a,
                Red\[y,
                     b,
                     Red\[z, c, d]]]
                { rotate(x, y, z, a, b, c, d) }    

    else { tree }
  }
}

And the compressed version:

function balance(tree) {
  return match (tree) {
    when Black\[z, Red\[y, Red\[x, a, b], c], d]
         { rotate(x, y, z, a, b, c, d) }

    when Black\[z, Red\[x, a, Red\[y, b, c]], d]
         { rotate(x, y, z, a, b, c, d) }

    when Black\[x, a, Red\[z, Red\[y, b, c], d]]
         { rotate(x, y, z, a, b, c, d) }

    when Black\[x, a, Red\[y, b, Red\[z, c, d]]]
         { rotate(x, y, z, a, b, c, d) }    

    else { tree }
  }
}

The code is somewhat dense but it serves to show a realistic use-case for deeply nested patterns. In my opinion the patterns do a decent job of communicating the actual structure of the tree that is being drilled into, and in the dense form it closely resembles the shape of the trees, were they expressed as algebraic data types.

Here's what this example looks like using the with keyword:

function balance(tree) {
  return match (tree) {
    when ^Black with [z,
                      ^Red with [y,
                                 ^Red with [x, a, b],
                                 c],
                      d]
         { rotate(x, y, z, a, b, c, d) }    

    when ^Black with [z,
                      ^Red with [x,
                                 a,
                                 ^Red with [y, b, c]],
                      d]
         { rotate(x, y, z, a, b, c, d) }    

    when ^Black with [x,
                      a,
                      ^Red with [z,
                                 ^Red with [y, b, c],
                                 d]]
         { rotate(x, y, z, a, b, c, d) }    

    when ^Black with [x,
                      a,
                      ^Red with [y,
                                 b,
                                 ^Red with [z, c, d]]]

          { rotate(x, y, z, a, b, c, d) }    

    else { tree }
  }
}

Manually formatted, it uses a ton of additional horizontal space. Here's what it looks like formatted densely:

function balance(tree) {
  return match (tree) {
    when ^Black with [z, ^Red with [y, ^Red with [x, a, b], c], d]
         { rotate(x, y, z, a, b, c, d) }    

    when ^Black with [z, ^Red with [x, a, ^Red with [y, b, c]], d]
         { rotate(x, y, z, a, b, c, d) }    

    when ^Black with [x, a, ^Red with [z, ^Red with [y, b, c], d]]
         { rotate(x, y, z, a, b, c, d) }    

    when ^Black with [x, a, ^Red with [y, b, ^Red with [z, c, d]]]
         { rotate(x, y, z, a, b, c, d) }    

    else { tree }
  }
}

Personally I find this less readable; it's less concise and there are three keywords per line interspersed with the information that's actually semantically relevant. The worst part for me is that I have to read this semi-procedurally: Extensible matchers let us pretend that we're working with constructors for algebraic data types and that we are matching structurally when we're actually matching "virtually". Using "with" breaks this, and makes it explicit that we're applying a function. I think this is counterproductive in nested cases.

Regardless of syntax, this is prickly code. I think that makes it a good case to examine where various syntaxes might break down.

---

In case anyone is curious about the non-extensible structural matching version, here's what it looks like if we added a color fields to the Red and Black classes and matched on them. I've formatted this example like Prettier formats standard object literals. Aside from the limitations of structural matching (such as being unable to work with lazy data structures) I would consider this verbosity a complete non-starter for this use-case:

function balance(tree) {
  return match (tree) {
    when {
        color: "black",
        value: z,
        left: {
            color: "red",
            value: y,
            left: {
                color: "red",
                value: x,
                left: a,
                right: b
            },
            right: c },
         right: d
      } { rotate(x, y, z, a, b, c, d) }

    when {
        color: "black",
        value: z,
        left: {
            color: "red",
            value: x,
            left: a,
            right: {
                color: "red",
                value: y,
                left: b,
                right: c
            }
         },
         right: d
      } { rotate(x, y, z, a, b, c, d) }

    when {
        color: "black",
        left: a,
        right: {
            color: "red",
            value: z,
            left: {
                color: "red",
                value: y,
                left: b,
                right: c
            },
            right: d
        }
    } { rotate(x, y, z, a, b, c, d) }

    when {
        color: "black",
        left: a,
        right: {
            color: "red",
            value: y,
            left: b,
            right: {
                color: "red",
                value: z,
                left: c,
                right: d
            }
         }
    } { rotate(x, y, z, a, b, c, d) }    

    else { tree }
  }
}

[treybrisbane]

I was thinking about this last night, and was thinking about proposing a similar thing.

I think this is the key insight (emphasis my own):

Extensible matchers let us pretend that we're working with constructors for algebraic data types and that we are matching structurally when we're actually matching "virtually". Using "with" breaks this, and makes it explicit that we're applying a function.

To state it in my own way: I don't feel that the conceptual model for custom matchers should be "When Foo matches Bar _and then Bar's result matches SomePattern_". Instead, I feel it should be something like "When Foo matches _Bar's definition of SomePattern_".

I feel that

match (tree) {
  when ^Red with [value, left, right] { ... }
  else { ... }
}

very much aligns with the former, whereas something like

match (tree) {
  when Red\[value, left, right] { ... }
  else { ... }
}

brings things much closer to the latter (and is my preference).

As far as syntax goes, I honestly wish we could just do this:

class Box {
  constructor(value) {
    this.value = value;
  }

  static [Symbol.matcher](matchable) {
    if (!matchable instanceof Box) {
      return { matched: false };
    }

    return { matched: true, value: [matchabe.value] };
  }
}

class Record {
  constructor(field1, field2) {
    this.field1 = field1;
    this.field2 = field2;
  }

  static [Symbol.matcher](matchable) {
    if (!matchable instanceof Record) {
      return { matched: false };
    }

    return {
      matched: true,
      value: {
        field1: matchable.field1,
        field2: matchable.field2,
      },
    };
  }
}

// Can almost thing of these as "tagged patterns"
match (...) {
  // Haskell-style ADT match
  when Box[value] { ... }

  // Typed record match (i.e. _not_ just structural)
  when Record{ field1, field2 } { ... }

  else { ... }
}

But unfortunately it creates an ambiguity with tagged template strings:

match (...) {
  // Is Foo a custom matcher, or a tag for the template string?
  when Foo`some template string` { ... }

  else { ... }
}

So I think you're right in that we'd need a known delimiter. You obviously went with \, but there are also other potential candidates such as ::, @, etc.

[ljharb]

This is a lot to digest, but let me give it a shot.

First of all, bindings must never appear when they're not syntactically present in the code. It doesn't _seem_ like this issue violates that, but I wanted to point it out just in case.

@treybrisbane it's very important that patterns be the primary syntax, and that expressions (which includes anything with a custom matcher) be distinct. So your examples all would need a pin operator in front of them.

Third, with is just a way to chain patterns (which can also create bindings); as is the preferred way to create bindings from a matched value.

I find your examples using \ incredibly confusing, to be honest - could you write them using the current proposal's syntax (using as, not with, unless you're trying to chain patterns), so I can get a better sense of the difference that you're suggesting?

[treybrisbane]

Ok, let me take a step back for a second. Let's say you have the following:

class Record {
  constructor(field1, field2) {
    this.field1 = field1;
    this.field2 = field2;
  }

  static [Symbol.matcher](matchable) {
    if (!matchable instanceof Record) {
      return { matched: false };
    }

    return {
      matched: true,
      value: {
        field1: matchable.field1,
        field2: matchable.field2,
      },
    };
  }
}

Assuming my understanding of the syntax is correct, if you only want to match Record instances (but not constrain or bind any of their fields), you'd currently do this:

match (...) {
  // Just match a `Record`; don't bind or constrain any fields
  when ^Record { ... }
  else { ... }
}

If you wanted to also bind (but not constrain) any fields, you'd currently do this:

match (...) {
  // First match a `Record`, _then_ bind `field1` and `field2`
  when ^Record as { field1, field2 } { ... }
  else { ... }
}

And finally, if you wanted to contain (and potentially also bind) any fields, you'd currently do this:

match (...) {
  // First match a `Record`, _then match the chained pattern_ that binds `field1` and constrains `field2`
  when ^Record with { field1, field2: 'some value' } { ... }
  else { ... }
}

The thing I don't like about the last two is that using the custom matcher _syntactically_ involves two sequential constructs:

1. Match with Record custom matcher
2. Destructure (for as) or chain match (for with) using the subsequent pattern

What I'm proposing (and also what I believe @JosephJNK is proposing) is that use of custom matchers should _syntactically_ only involve one construct. E.g.

match (...) {
  // Match a `Record` whose `field2` is `'some value'` while also binding its `field1`
  // (Again, think of this as tagging a structural pattern with a custom matcher, similarly to how we can tag template strings)
  when ^Record{ field1, field2: 'some value' } { ... }
  else { ... }
}

Conceptually, when ^Record{ field1, field2: 'some value' } { ... } would do the exact same thing as what when ^Record with { field1, field2: 'some value' } { ... } currently does, first matching with Record, then chain matching the structural pattern. But _syntactically_, it would be represented as a single construct (a "tagged pattern" in a sense).

This allows users to think of custom matchers as things that _change how a structural pattern applies to a value_.

Does that make more sense?

[fuunnx]

My two cents: as a final user, I agree I didn't understand the difference between with and as until this comment. I believed that with and as had the same meaning, and using both in the examples were oversights from a previous draft

[ljharb]

@treybrisbane thanks, that does make more sense.

However, if the pattern is visually attached to the custom matcher, then i (and i think users) would expect that the matcher protocol conveys information about the pattern used to the matcher protocol function. In other words, I think the visual separation is necessary for clarity, because custom matchers do not, in fact, change how a structural pattern applies to a value - they use "any JS logic" to determine a match, and provide a result value for you to explicitly bind, if you choose.

[tabatkins]

Third, with is just a way to chain patterns (which can also create bindings); as is the preferred way to create bindings from a matched value.

No, with and as are completely distinct things. with matches against the return value of the custom matcher; as binds the matchable value before it goes into the custom matcher. (Identical to how when ([a,b] as list) ... binds the whole list to list, before it's ripped apart for the a and b bindings.)

[j-f1]

maybe use = instead of with?

match (tree) {
  when [value, left, right] = ${Red} { ... }
  when ${Red} as { value, left, right } { ... }
  else { ... }
}

[ljharb]

@tabatkins right, but when (/a/) with <something else> would also apply to the binding value produced by the regex literal pattern, despite no custom matcher being applied, so it still seems more accurate to me to think of with as a chain or pipeline of patterns, versus as which solely handles bindings. as also doesn't alter which value goes into a custom matcher when it's used outside of a when - it alters which bindings are available to the RHS (an in-place as perhaps works as you say)

[ljharb]

@j-f1 i think = is too similar to assignment.

[JosephJNK]

However, if the pattern is visually attached to the custom matcher, then i (and i think users) would expect that the matcher protocol conveys information about the pattern used to the matcher protocol function. In other words, I think the visual separation is necessary for clarity, because custom matchers do not, in fact, change how a structural pattern applies to a value - they use "any JS logic" to determine a match, and provide a result value for you to explicitly bind, if you choose.

@ljharb This is part of the problem I have with the current syntax. Yes, the syntax accurately conveys the execution semantics involved in evaluating a pattern match, but the point of a pattern is not to express procedural evaluation or refinement. A pattern exists to declaratively describe the "shape" of the data that's entering the matching construct. To be more specific, from a (Scala or ML family) functional programming perspective, the "shape" which we are describing is a tree of constructors from an algebraic data type. This is the historical root of pattern matching and one which I hope will be treated as first-class in JS. (While JS does not have algebraic data types explicitly, it's common and easy to simulate them.)

Using @treybrisbane 's approach we can see the essential parts of an FP-style pattern match:

when ^Record{ field1, field2: 'some value' } { ... }

We have the data constructor, Record, and the data inside of this constructor, { field1, field2: 'some value' }. When we match on Record, we "unpack" the data inside of it, and further match that data against any more deeply nested patterns. (I think of field2: 'some value' as a nested pattern.) In the presence of extensible patterns, whether or not Record is the "real" constructor of the data, or whether { field1, field2 } are the data that's actually "inside of" the Record are irrelevant and are abstracted from the site of the pattern's usage.

Were we in a purely functional language this abstraction would be cool because now we can have OO-style encapsulation without giving up functional idioms. From my perspective as a user of a hybrid language this abstraction is cool because now we can have functional idioms at all. I'm not excited for extensible patterns because they let me apply custom transformation logic inside of a procedural control-flow construct; I'm excited because obscuring the fact that such logic exists behind a declarative interface is the only way to express FP-style pattern matching in a hybrid language.

The with keyword doesn't completely prevent this; in my initial example I was still able to describe the shape of a red/black tree despite the syntactic noise. Doing so required that I work against the language, though. When writing the code it felt like I was misusing the feature by nesting it (and I may have been, since I don't think there were any examples of nested extensible matches in the README.) Handing users a syntax that directly expresses procedural evaluation semantics will make it easier for them to think in terms of those semantics when they first try to learn how the feature works, but it will also strongly encourage them to continue thinking about patterns in procedural terms over the long haul. In my opinion, this undermines the declarative mindset that pattern matching is supposed to encourage and sidelines more traditional functional usages of patterns.

[ljharb]

This proposal isn't purely about pattern matching, only primarily. It's meant to be able to handle shapes, but also any arbitrary matching logic, via custom matchers, guards, and special literal forms. The historical root of pattern matching is noted, but won't be constraining this proposal, since it needs to match the idiomatic needs of _this_ language regardless of the needs of other languages with a similar feature. The "pattern" part of "pattern matching" is indeed first-class, but first-class doesn't mean "only", it means "primarily" :-)

I agree that it's important, with the Record example, to be able to match both against the matchable's shape, as well as apply whatever custom matching logic Record wants to provide. However, the logic to match the shape has to be static/hardcoded/built-in to the language, since it wouldn't be tenable to try (LINQ-like) to convey to userland code (custom matcher functions) the semantics the user is requesting. Being able to combine ^Record with "a pattern" allows you to achieve the use case, regardless of how the syntax looks - and I'm still not sure how pretending the two are connected (beyond, of course, their use together in the same clause) helps.

[tabatkins]

but when (/a/) with <something else> would also apply to the binding value produced by the regex literal pattern, despite no custom matcher being applied,

Hm, in my original proposal version with only worked on custom matchers; a regex literal wouldn't allow the clause. Regex literals have a reasonable interpretation of how with could work, sure, but I don't think this applies more widely to the other non-custom matchers. Are you intending this to be the only non-custom matcher allowing the with clause?

[ljharb]

I think that perhaps the champion group needs to get on the same page about with - we kept it mostly out of the readme for that reason. Let's maybe hold off on further discussion of it on threads until our next meeting (which I'll send out a doodle for today)?