Pattern Matching, 2023-07-10

proposal.md

Pattern Matching Rewrite

Intro

This proposal has several parts:

1. A new syntax construct, the "matcher pattern", which is an elaboration on (similar to but distinct from) destructuring patterns.

   Matcher patterns allow testing the structure of an object in various ways, and recursing those tests into parts of the structure to an unlimited depth (similar to destructuring).

   Matcher syntax intentionally resembles destructuring syntax but goes well beyond the abilities and intention of simple destructuring.

2. A new binary boolean operator, is, which lets you test values against matchers. If the matcher establishes bindings, this also pulls those bindings out into the operator's scope.

3. A new syntax construct, the match() expression, which lets you test a value against multiple patterns and resolve to a value based on which one passed.

Matcher Patterns

Destructuring matchers:

• array matchers:

  • [<matcher>, <matcher>] exactly two items, matching the patterns
  • [<matcher>, <matcher>, ...] two items matching the patterns, more allowed
  • [<matcher>, <matcher>, ...let <ident>] two items matching the patterns, with remainder collected into a list bound to <ident>. (Can use const or var as well; see "binding matchers". Only binding matchers allowed in that position; not anything else.)

• object matchers:

  • {<ident>, <ident>} has the ident keys (in its proto chain, not just own keys), and binds the value to that ident. Can have other keys. (aka {a} is identical to {a: let a})
  • {<ident>: <matcher>, <ident>: <matcher>} has the ident keys, with values matching the patterns. Can have other keys.
  • {<ident>: <matcher>, ...let <ident2>} has the ident key, with values matching the pattern. Remaining own keys collected into an object bound to <ident2>.

• binding matchers:

  • let <ident>/const <ident>/var <ident>. Binds the matchable to the ident. (That is, [let a, let b] doesn't test the items in the array, just exposes them as a and b bindings.)
  • (To bind a matchable and apply more matchers, use and to chain them: let a and [b, c].)

Value-testing matchers:

• literal matchers:

  • 1,
  • "foo",
  • etc. All the primitives, plus (untagged only?) template literals.
  • also unary plus/minus
  • -0 and +0 test for the properly-signed zero, 0 just uses === equality.
  • NaN tests for NaN properly.

• variable matchers

  • <plain-or-dotted-ident> evaluates the name.

    If the name has a custom matcher (see below), it passes the matchable to the custom matcher function and matches if that succeeds. Otherwise, it just matches based on equality. (Uses === semantics, except that NaN is matched properly.)

  • <plain-or-dotted-ident>(<matcher-list>) evaluates the ident, grabs its Symbol.matcher property, then invokes it on the matchable. (Throws if it doesn't have a Symbol.matcher property, or it's not a function.) If that succeeds, it further matches the result against the arglist, as if it was an array matcher.

     Option.Some(foo) examples goes here
    

• regex matchers:

  • /foo/ matches if the regex matches. Named capture groups establish let bindings.
  • /foo/(<matcher-list>) is identical to custom matcher - if the regex matches, then the match result (the regex match object) is further destructured by the matcher list.

Boolean matcher logic:

• <matcher> and <matcher>: Tests the matchable against both matchers (in order), succeeds only if both succeed. Accumulates bindings from both. If first fails, short-circuits.
• <matcher> or <matcher>: Tests the matchable against both matchers (in order), succeeds if either succeeds. Accumulates bindings from both, but values only from the first successful matcher (other bindings become undefined). If first succeeds, short-circuits.
• not <matcher>: Tests the matchable against the matcher, succeeds only if the matcher fails. No bindings.
• Matchers can be parenthesized, and must be if you're using multiple keywords; there is no precedence relationship between the keywords, so it's a syntax error to mix them at the same level.

Using Matchers

• New match(){} expression:

   match(<val-expr>) { 
   	when <matcher>: <result-expr>; 
   	default: <result-expr>;
   }

  Find the first "arm" whose matcher passes, given the val. Evaluates to the corresponding result for that arm. The matcher can produce bindings that are visible within the matcher and within the result; they don't escape the arm they're established in. (Are var matchers allowed or disallowed?)

  default arm always matches. If no arm matches, throws.

• New is operator

   <val-expr> is <matcher>

  Evaluates to true/false if val passes the matcher or not. If the matcher has binding patterns, within the matcher they behave as normal; see below for behavior outside of the matcher.

  Doing it manually with match() would be:

   let passes = match(<val-expr>) {
   	when <matcher>: true;
   	default: false;
   }

• When is is used and the matcher establishes bindings:

  • In if(), the bindings are lifted to a scope immediately outside the if() block, encompassing the following else as well. (Likely, we define an analogous scope to what for(of) uses.) Lexical bindings are TDZ if the matcher doesn't match. var bindings simply don't set a value if the matcher doesn't match.

    (Bindings will often not be useful in the else, but will be in cases like if(!(x is <matcher>)){...}else{...}, where the matcher successfully matches but the if fails.)

  • In while() and do{}while(), same behavior. (In do{}while(), lexical bindings are TDZ on the first iteration.)

  • In for-of, the bindings exist in the current outer for scope, same as any other bindings established in the for head.

    (TODO: write an example of for-of usage; I'm not clear how it's supposed to work.)

(We've lost matchers in plain let/etc statements, which I guess also means we lose matchers in function arglists. Unfortunate.)

Also, this is more specific to the pattern syntax, but what will we use to test for the presence of a property without introducing a binding or testing for a value? Essentially, the pattern equivalent of "x" in y. In other pattern languages you might use _ as a discard, but I don't think we'll be able to use _ given reticence around using any potential identifier name:

match (node) {
  when { left: _, op: let op, right: _ }: ...; // doesn't work if we can't use `_`
}

that said, _ could be used as a discard by a third-party package:

// discard.js
export const _ = { [Symbol.match]() { return true; };

// main.js
import { _ } from "./discard.js";
match (node) {
  when { left: _, op: let op, right: _ }: ...; // works
}

[naming stuff]

Sure, I'm being a little loose here because we didn't need precision to communicate with each other. I agree with your naming suggestinos.

[plain ident in an object pattern]

Ah, no, I'd just forgotten to update that to the new binding syntax. {a} should be equivalent to {a: let a}. Same with the ... bit.

<dot-qualified-name>

Sure. I would like it if [] access was allowed - I hate introducing these sort of restrictions to the language unnecessarily. But no parens, as obviously it would clash with the parens of the invocation.

Is this to avoid repetition?

No, it's to let named groups work at all, if we say that the match result is the regexp match object. If that is indeed the case, then you only have access to the integer groups via the arglist, as the regexp result is an array-like.

We could instead say that the result of a regexp pattern is an iterator containing just the regexp match object; that way the code you wrote would work, and you could get at the positional groups like /(f..)(b.r)/([_, f, b]). Hm, that might indeed be better.

It also reminds me too much of RegExp.$1

I don't see the connection. RegExp.$1 is mutable global state. This is local lexical bindings.

might want to introduce a property binding shorthand for object patterns

Nah {middle} is fine there, as noted above. (We could still allow let/const/var there, if we feel a need to make it the type of binding specificiable in the shorthand, but as you can do so by just repeating the name, and let is the most obvious default choice, I think it's fine as-is.)

I want to be sure we're still considering the if clause in some way,

I'd removed it from the patterns, as I got pushback on it last time, but I'm happy to add it back in. I agree that it's good as a pattern rather than as an addition to the when clause, as it makes it usable in is and generally keeps the test close to where the binding is established.

Also, I wonder whether we should use ; or , here.

I assume we want wide-open expressions grammar on the RHS of the colon, which precludes using , as that's a valid expression operator.

The analog would be for(;;)

Ah kk, thanks.

I haven't been quite as concerned about let, since you could do something like:

Auuuggghhhh I hate that so much >_<

but we could still consider a keyword or token opt-in

Yeah it's that array pattern ambiguity that bit me last time. I'm fine with putting it to the side for now and thinking about it for a level 2. Proper integration with function parameters might end up wanting to be fancier, anyway.

catch will is a bit easier since we can inject syntax near catch

Yeah, I presume catch when <pattern> {...} is what we'll end up with, it reads well and is exactly analogous to the match() arms. If it's objectionable to have consecutive catch blocks, then the catch match { when ...; } syntax seems like the obvious second choice.

but what will we use to test for the presence of a property without introducing a binding or testing for a value?

Currently the answer is "you can't" - you have to use a let _ binding pattern and just have your linter know to ignore that variable.

The _ custom matcher is cute, tho. ^_^

Ah, no, I'd just forgotten to update that to the new binding syntax. {a} should be equivalent to {a: let a}. Same with the ... bit.

I'm not sure I agree. Having {a} differ from {a:a} seems like the wrong direction as it is inconsistent with both shorthand property assignments and shorthand assignment/binding patterns, and makes it less clear where the bindings are. I think if we're going to do let, we should just do let.

I don't think ... auto-bind is a good idea either, since I'm actually more likely to want to use ...items in a pattern than even {a}, for instance:

const NORTH_WEST = ['north', 'west'];
const NORTH_EAST = ['north', 'east'];

match (action) {
  when ['move', ...NORTH_WEST]: x++, y--; // move coordinates
  when ['move', ...NORTH_EAST]: x++, y++;
  ...
}

It's especially important to have these be consistent if we, for instance, allowed a nested pattern after ... like you can in destructuring/assigment:

match (record) {
  when ['LoadGlobalIC', ...({ length: 3 } and let rest)]: ...;
}

No, it's to let named groups work at all, if we say that the match result is the regexp match object. If that is indeed the case, then you only have access to the integer groups via the arglist, as the regexp result is an array-like.

For an extractor, I would suggest that it be a single-argument extractor into an array/object, i.e.:

match (x) {
  // match array elements
  when /a(?<foo>[^b]+)b/([let input, let foo]): ...;

  // or, match group names
  when /a(?<foo>[^b]+)b/({ groups: { foo: let foo } }): ...;
  
  // or, we could return something that is not the exec() result...
  when /a(?<foo>[^b]+)b/({ foo: let foo }): ...;
  // where RegExp.prototype[Symbol.match] is:
  //
  // RegExp.prototype[Symbol.match] = function (value) {
  //   const match = this.exec(value);
  //   if (match) {
  //     return {
  //       match: true,
  //       value: [{
  //         [Symbol.iterator]() { return match.values(); },
  //         ...match.groups
  //       }]
  //     };
  //   }
  // }
  //
  // allowing us to use both [] and {} destructuring (but not element access via { 0: pattern })
}

Auuuggghhhh I hate that so much >_<

It's more like an abuse of the syntax, imo, though technically legal. It looks much better in cases like this though:

if (p is Point(let x, let y)) {
  console.log(x, y);
}
else {
 throw Error("Not a point");
}

• the ...let <ident> bit in array and object should be loosened to ...<matcher>, this actually matches destructuring better

• to keep the syntax space open for a little bit longer, might want to specialize template literals to just "NoSubstitutionTemplate" production. (TypeScript has a sort of simple regex via template literals.) Or just disallow template strings for now - only benefit over normal strings, if subbing isn't allowed, is the different escapes.

• ACTION Matt Gaudet to discuss with team about the -0 and +0 matchers being explicitly signed.

• {a} becoming {a: let a} still makes it awkward to just test for property existence. Bring back a "discard matcher"? Spell it void or let void (the latter might link up with using)

• Jack suggests rather than making irrefutable matchers, having a specialized let <ident> if <matcher> syntax which can be used in place of matchers. (Currently this would be spelled let <ident> and <matcher>.)

• Just having regex matchers return the exec object itself seems fine. You can pull the groups out by using an array matcher inside it.

• can probably remove the "named capture groups create bindings" from regexes, matching {groups} is easy (this would mean that there's no difference between regex literals and regex variables, which is nice)

• Jack would really like us to rename Symbol.matcher to move it further from Symbol.match. (I have no opinion on the name, it only gets written occasionally.)

As mentioned at the end of the meeting, one option for a name to replace Symbol.matcher is Symbol.unapply, which is what I was originally going to use for Extractors.

• can probably remove the "named capture groups create bindings" from regexes, matching {groups} is easy (this would mean that there's no difference between regex literals and regex variables, which is nice)

I would feel comfortable with "named capture groups create bindings" for regexes, but only if it were somehow opt-in, i.e., via a special RegExp flag that is only valid in pattern matching (but ignored or an error in a normal RegExp literal or via the RegExp constructor). That way a refactor of:

// NOTE: using 'L' as a substitute for the flag to mean "introduce a 'let' binding"
if (x is /(?<foo>foo|bar)/L) {
  foo; // either "foo" or "bar"
}

const reFoo = /(?<foo>foo|bar)/L; // error, cannot use `L` flag
if (x is reFoo) {
  foo; // error
}

As we don't want RegExp patterns to become the new with and arbitrarily change the lexical environment based on an expression.

// NOTE: using 'L' as a substitute for the flag to mean "introduce a 'let' binding"
if (x is /(?<foo>foo|bar)/L) {
  foo; // either "foo" or "bar"
}

const reFoo = /(?<foo>foo|bar)/L; // error, cannot use `L` flag
if (x is reFoo) {
  foo; // error
}

I could imagine an automatic refactoring in an editor that would refactor this via two steps:

1. Refactor /(?<foo>foo|bar)/L into an extractor pattern:

   // from:
   // if (x is /(?<foo>foo|bar)/L) ...
   // to:
   if (x is /(?<foo>foo|bar)/({ groups: { foo: let foo } })) ...

2. Extract the RegExp into a local variable:

   // from:
   // if (x is /(?<foo>foo|bar)/({ groups: { foo: let foo } })) ...
   // to:
   const reFoo = /(?<foo>foo|bar)/;
   if (x is reFoo({ groups: { foo: let foo } })) ...

Results from 21-08-2023 discussion:

• talked about predicate vs the default class matcher - default class is intended to be installed on Function.prototype right now, which blocks us form invoking functions directly.

  • option 1 - have class syntax install a default matcher, like it installs a default constructor. Then functions without a Symbol.matcher method are just invoked directly.
  • option 2 - bless one of the cases directly, have a keyword that invokes the other
  • Plan is to put 1 in the spec, with 2 listed as an alternate in case of objections

• Jordan concerned about if-bindings being visible to else, we had some pushback on previous attempts with doing bindings in if heads tc39/proposal-Declarations-in-Conditionals#3

  • Tab thinks this is the right behavior, both for matchers and for if-head bindings in general, so we should push for this.
  • Jordan is okay with this but we should be prepared to have to change things.

• Bikeshedding name of Symbol.matcher

  • Jordan hates Symbol.unapply
  • Symbol.extract is a maybe (since this is also used by extractors), tho extractors are the one use of this that doesn't have a name showing up in the syntax
  • Symbol.is is too close to Object.is
  • Settled on Symbol.customMatcher for now - unambiguous and not too long. Will leave a bikeshedding note in the spec with other option names.

• Inclined to drop the "named groups establish bindings" from regexes, now that they're easy to get from the extractor syntax, since the committee gave some pushback last time.

  • Jordan conditionally okay. Wants to see examples of both numberd and named groups in the spec.

I wrote a long, almost identical proposal in an issue on the original repo. Now that I've seen this, I would like to propose two small modifications and a few questions:

Let's use ... in Object matchers too?

[<matcher>, <matcher>] matches arrays with exactly two elements. [<matcher>, <matcher>, ...] can be used to match any array with at least two elements.

However, {<ident>: <?matcher>, <ident>: <?matcher>} matches any object with at least those two keys. I understand things get a bit complicated with prototypes, but I feel like this matcher should not match for objects that have additional "own" keys.

e.g. {name: 'John Doe', age: 30} should not match the matcher { name } since it has additional "owned" and "enumerable" keys. { name, ... } should be allowed to match objects that may contain extra keys.

This change makes the whole system more consistent IMO.

Syntax for matching instances of classes

We should support a matcher that looks like Person { name } which works exactly the same as the object matcher { name } but it also checks that the value being matched is instance of Person.

All proposed changes

Here's what I would add to the proposal above:

• object matchers:

  • {<ident>, <ident>} has the ident keys (in its proto chain, not just own keys), and binds the value to that ident. Can not have other own keys. (aka {a} is identical to {a: let a})
  • {<ident>, <ident>, ...} has the ident keys (in its proto chain, not just own keys), and binds the value to that ident. Can have other own keys
  • {<ident>: <matcher>, <ident>: <matcher>} has the ident keys, with values matching the patterns. Can not have other own keys.
    • This should also work with "getter function" keys
  • {<ident>: <matcher>, <ident>: <matcher>, ...} has the ident keys, with values matching the patterns. Can have other own keys.
  • {<ident>: <matcher>, ...let <ident2>} has the ident key, with values matching the pattern. Remaining own keys collected into an object bound to .

• class matchers:

  • <ident> <object-matcher> matches the <object-matcher and is an instance of <ident>

Patterns are meant to mimic destructuring as much as possible; it doesn't make sense to me to ever care if an object doesn't have extra keys, especially since you can foo: not x or similar to ban a specific key.

instanceof semantics are terrible and should never be further cemented into the language; the current plan is to make class syntax create a default matcher that approximates the semantics of ensuring a private field exists on the receiver.

Patterns are meant to mimic destructuring as much as possible; it doesn't make sense to me to ever care if an object doesn't have extra keys.

I don't disagree and this was my proposal in the long issue I wrote. My concern is that I think destructuring should be consistent across Arrays and objects.

Another solution is to change Array matchers to allow extra elements by default:

• array matchers:

  • [, , void] exactly two items, matching the patterns
  • [, ] two items matching the patterns, more allowed
  • [, , ...let ] two items matching the patterns, with remainder collected into a list bound to . (Can use const or var as well; see "binding matchers". Only binding matchers allowed in that position; not anything else.)

instanceof semantics are terrible and should never be further cemented into the language

I'm not sure I agree. Would you elaborate your reasons for essentially deprecating instanceof?

the current plan is to make class syntax create a default matcher that approximates the semantics of ensuring a private field exists on the receiver.

Even if this is the plan, I believe the Person { name } syntax should be adopted (if viable) instead of Person(let name) that I have seen above. How it works behind the scenes is less important. If it feels like instanceof it won't really matter what it really does to make things work.

Some other questions about syntax:

1. Is there no way to re-use parts of the switch-statement syntax? Instead of match {when} could we use match { case <matcher> } instead? Does doing something like this enforce it to become a statement or something?

2. I like using void to suggest the absence of something!

3. Would { let: let let } be a valid matcher?

In if(), the bindings are lifted to a scope immediately outside the if() block,

Why are we not scoping the bindings to within the if() {...} block? You can't currently create new bindings to variables within an if condition so there's no prior art here about how a variable should be scoped. Is there a syntactic limitation?

{a} becoming {a: let a} still makes it awkward to just test for property existence.

Let's not make { a } become {a: let a} then? Let { a } simply check for the existence of a key a and require the use of {a: let a} when a binding is needed? I don't think our goal should be the most terse syntax possible. We should try to avoid confusion. Let's not have any object key punning in object matchers at all:

• { a } checks if the key a exists. That's it.
• { a: a } checks if the key a exists and is equal to the value of the variable a
• { a: let a } checks if the key a exists and captures its value in a new variable a

instanceof can be easily faked via Symbol.hasInstance, and it doesn't provide accurate results for cross-realm builtins.

The proposal explicitly and intentionally avoids reusing any part of switch syntax, to increase googleability, and so that switch can finally be put to rest.

so that switch can finally be put to rest.

It can never be put to rest since JS is append-only. And I suggested match-case instead of switch-case to reduce creating two new keywords and just create one. case as a word makes just as much sense as when so unless there's a technical reason for implementation, I think we should try to minimize the number of new things we introduce.

instanceof can be easily faked via Symbol.hasInstance ... cross-realm builtins

Fair enough, let's not use instanceof semantics, but the Person { name } syntax can still work regardless.

with has been put to rest, despite that it will never be removed from the language. switch will too, since it's horrifically terrible.

Have you read the "priorities" in the readme?