Early version of RFC: Pattern matching ?

[alehander92]

Pattern matching for Nim

Pattern matching can be a good addition to the stdlib/fusion. It seems it becomes more mainstream:

• Rust : https://doc.rust-lang.org/book/ch18-03-pattern-syntax.html
• Python : https://www.python.org/dev/peps/pep-0622/
• Ruby : https://rubyreferences.github.io/rubyref/language/pattern-matching.html

This is an early version of a RFC: we need to decide what to do before having a more complete document.

We already have several pattern matching libraries :

• patty by Andrea Ferretti https://github.com/andreaferretti/patty
• ast-pattern-matching by Arne Doring https://github.com/krux02/ast-pattern-matching
• gara by myself https://github.com/alehander92/gara/ (not well maintained)
• possibly others? maybe case statement macro dsl-s? please write a comment if you want to add something

A first question is, what do we want:

• just keep it in third party libraries
• standartize one and put it in fusion
• invent a new dsl based on case stamenets/better research of other languages and put it in fusion
• standartize one and put it in stdlib
• invent a new dsl based on case stamenets/better research of other languages and put it in stdlib

Motivation

• Easier to write complicated conditions
• Easier to extract values
• More flexible syntax

TODO

case a:
of Circle(r: @b):
  echo b
of c@Other:
  echo c
else:
  discard

Many more examples in gara, ast_pattern_matching and patty's docs: TODO when a general approach is decided on

Constraints

• compile time: ast and other values : as @krux02's ast-pattern-matching
• runtime for most nim types
• extensible
• zero/low overhead
• exhaustiveness checking
• maybe: make it easily swapable for other pattern matching lib
• maybe: make it support binary matching like Erlang/Elixir

Research

It would be useful to research a bit more Rust, Haskell, OCaml, Python, Ruby, Scala, Erlang, Prolog, Elixir

We can also compare several possible designs like the Python folks did in their preparation for the feature.

Next steps

• Decide on general direction
• Offer 1 or more designs in a more detailed version of the RFC
• Implement

Future directions

Not sure

Disclaimer

I am the author of one of the libs gara, so I might be biased.

pinging @krux02 and @andreaferretti which probably have something to say on the topic

[andreaferretti]

I have nothing in particular to add, except for the fact that pattern matching is often done on algebraic data types. Nim today has almost algebraic data types, via variant objects, but:

• with an ugly syntax
• with a limitation that two different variants cannot have fields with the same name

If pattern matching lands in stdlib, it would be nice if at least the second of these issues is solved. If I remember correctly there is another RFC for that.

Other than this, I would be happy with just putting gara in the stdlib, as it seems the most complete option today

[Varriount]

Ideally, pattern matching should work well with AST manipulation, since recognizing structural patterns in the AST tends to be 50% of a macro's job.

That being said, I've only ever needed the kind of pattern matching provided by something like py-good. I can't recall ever having needed it anywhere else.

[haxscramper]

Additional arguments in favor of pattern matching in stdlib

A lot of popular programming languages (almost all with exception of Go/C that position themselves as "simple" languages with very few functional features) either already have support for pattern matching or existing proposals.

• rust
• python
• even java (proposal for openjdk)
• C++ (proposal)
• Kotlin (proposal)
• C#
• ruby
• crystal
• ada-spark
• And of course any functional language such as haskell, ocaml etc.

I'm not a big functional programmer myself, but i think Nim is already a really good functional programming language - closures, sum types, optional types etc. Support for custom operators and UFCS makes transition even more seamless. Pattern matching is an important addition to the list if features that would allow nim to position itself as a functional programming language.

Use caseStmtMacro

I think pattern matching in stdlib should be implemented using caseStmtMacros that are currently experimental, but quite usable (I tried implementing pattern matching and there was no immediate issues). The reason - this way pattern matching would be just an extension of case statement and won't introduce any new concepts/keywords to the language. Can be added as another feature in sugar module.

Set of features should be relatively small

Second - I think it is important to keep list of supported features relatively small - e.g. no predicate validation (match field only if it satisfies some kind of predicate), unification etc. The reason - due to potential number of extensions to concept of pattern matching it is very easy to end up with feature creep where macro creates whole new semantics for case statement. Although some additions to pattern matching would certainly be useful. For example - allowing abitrary predicate extensions seems like a little too much for me, but checking if value is in set kind: in {enEE, enEE1} will certainly be useful in a lot of situations.

It is also important to not require any modifications to existing types - reuse existing len and `[]` overloads as well as kind fields. This makes certain assumptions about what functions are implemented for object, but I would argue this is a good thing. E.g. further promoting idea that all int-indexable (arrays, sequences etc.) shoud implement `[]` and len, all case objects should have kind etc. as it would only lead to more consistent API across all code.

Pattern matching on key-value pairs

Pattern matching on key-value tables (json for example) might be really practical in a lot of scenarios. Possible syntax:

    assertEq "000", case %{"hello" : %"world"}:
           of {"999": _}: "nice"
           of {"hello": _}: "000"
           else: "discard"

NimNode

One of the main use cases for pattern matching in nim is macros. NimNode probably the most used case object and large portion of macro is just re-parsing of input structures. Pattern matching should account for this.

In addition to making nim node pattern matching easier it will also make macros more declarative (for simple macros): it would be easier to understand what kind of input is expected and what will be generated from it.

My implementation

I'm currently working on my own pattern matching library based on case statement macros. You can see example tests here - https://github.com/haxscramper/hmisc/blob/master/tests/tMatching.nim

I originally wanted to PR it as a stdlib module but then decided to first ask for feedback on general idea/syntax. Right now it is a little over-engineered and has dependencies on other part of hmisc. If it can be accepted as stdlib module I will make it self-contained and PR it into stdlib.

Examples

    case [1,2,3,4]:
      of [_]: fail()
      of [_, 3, _]: fail()
      of [_, 2, 3, _]:
        discard

Support for regular elif branches in case stmts

    assertEq "default fallback", case (a: 22, b: 90):
           of (_, b: 91): "900999"
           elif "some other" == "check": "rly?"
           elif true: "default fallback"
           else: raiseAssert("#[ not possible ! ]#")

Todo list

There are some things that I still have on todo list such as

• Trailing zero-or-more (*<patt>) for lists
• Use *(<patt>) in non-trailing format - [$a, *_, $b] to match first and last element in sequence.
• exact and prefix match for sequences: right now matching using [] pattern requires len to be equal - in a lot of situations it is necessary to just check first couple of items. Can be implemented using *_ with special treatment for this pattern (e.g. just don't check anything) but I would like to have something closer to [ , ] ... with trailing ellipsis. But that is just preference mostly.
• List variables - similar to nimtrs where I have distinction between $scalarVariable that can only be assigned once and @listVariable which will store all appended elements.
• Other suggestions?
  • Pattern matching on data streams ?
  • Maybe adapt some syntax ideas from rust pattern matching for macros: link. Pattern matching for NimNode is a most common use case, so it might be a good idea to adapt some solutions from rust.
  • Another potential source of syntax ideas are term rewriting macros

[juancarlospaco]

More programming languages using Pattern Matching:

• Scala, Scala-Native, ScalaJS.
• Swift.
• F Sharp.
• ML.
• Haskell.
• D.

[alehander92]

@haxscramper cool! but please take a look at impl-s of patty/ast-pattern-matching/gara . They do some of those, so this might be cool. Also please keep in mind the goal of zero overhead : expanded code should be usually similar to hand-written condition/extraction(not always happening in those libs tho)

Awesome!

[alehander92]

@haxscramper thanks and Also: can you write down a bit more detailed test spec/proposal here or in your own rfc : that was one of the goals of the rfc in my mind, to discuss a more official dsl

[haxscramper]

@alehander92

After some thinking I came to conclusion it is not necessary to specifically annotate captured variables with prefix since it really differs from any other nim dsl in stdlib. I started with $capturedVar but now I think it is not really necessary. Type of matched variable can be inferred based on pattern context - e.g. variable is assigned (=) if used in regular pattern and appended (.add) if it is inside of repetition *(<pattern>) although I've done this in nimtrs and current version of matching I think it is not that good of a solution in general.

Capture and submatch can be done using infix is, equality comparison (any other prefix?) will be rewritten in infix notation, e.g. fld: == SomeVal to match field against value will be rewritten into ... .fld == SomeVal. Capture and match can be written as fld: captured == SomeVal for infix operator checks (in, ==) or as fld: capt is SomePattern( ... )

Although I think this is a really slippery slope because there will be a lot of different behaviors of the match depending on written expression (e.g. == Val vs var == Val vs var is Patt) so it is necessary to be really careful here. As I already mentioned it is really easy to just sit for a while and come up with dozens of possible nice things that can be added (regex pattern extraction, custom unpackers, predicatess, regex-like pattern matching for sequences (like in nimtrs) and so on).

One thing I think that is really necessary is to make it look closer to pattern matching in functional language and not enum case-of v2.0. Default nim convention for enum naming is to have abbrValueName and ObjectName. I think it should be possible to omit the abbr prefix. Eg. I want to write IfStmt instead of nnkIfStmt etc.

More examples

Create value to compare against

    macro e(body: untyped): untyped =
      case body[0]:
        of ForStmt([$ident, _, $expr]):
          quote do:
            9
        of ForStmt([$ident, Infix([%ident(".."), $rbegin, $rend]),
                    $body]):
          quote do:
            `rbegin` + `rend`
        else:
          quote do:
            90


    let a = e:
      for i in 10 .. 12:
        echo i

    assertEq a, 22

I would prefer to write `expr` instead of %expr but right now it seems it is not possible to add arbitrary expressions inside of quoted part. Syntax is just taken from nimtrs. Since it is not possible to differentiate newValue() from KindOfCaseObject() I decided to just prefix it with % for now.

Iflet macro

    macro ifLet2(head: untyped,  body: untyped): untyped =
      case head[0]:
        of Asgn([$lhs is Ident(), $rhs]):
          quote do:
            let expr = `rhs`
            if expr.isSome():
              let `lhs` = expr.get()
              `body`
        else:
          head[0].assertNodeKind({nnkAsgn})
          head[0][0].assertNodeKind({nnkIdent})
          head[0].raiseCodeError("Expected assgn expression")

    ifLet2 (nice = some(69)):
      echo nice

    ifLet2 (`nice` = some(69)):
      echo nice

It uses some of my own node kind assertions, but this can be removed when design is finalized. Although due to complexity of pattern matching I think having something like this to show errors would be nice. But that is a topic for another RFC/PR.

Unexpected node kind. Expected one of {nnkIdent} but found nnkAccQuoted

 112          echo nice
 113    
 116:12     ifLet2 (`nice` = some(69)):
                    ^~~~~~
                    |
                    nnkAccQuoted

Non-goals

• Support for variable unification - even though it is really nice it have in some cases it adds too much complexity to the implementation (e.g. when you have alternatives that each bind the same variable). I think it is a good idea to completely disallow
• High extensibility - pattern matching is complex enough on it's own and I would prefer to have more simple implementation that forces end user to provide all additional checks either via if/else or using nested pattern matches. Some things are used often enough (check if in set or equal to some specific value) so they should be supported out of the box.

Other goals

make it easily swapable for other pattern matching lib

If case statement macro will be moved to 'stable' part of the language (e.g. no longer hidden behind experimental switch) this can be done quite easily I think.

Some comments on other libraries

Patty

I don't think matching non-tuple types by position only is a good idea as it makes matches really fragile in case new fields are added (which is much more likely to happen than with regular anonymous tuple).

ast-pattern-matching

Supports only nim nodes

[haxscramper]

@alehander92 just addition to whatever I wrote above to RFC comment for pattern matching - I think it is better to just take as much potential ideas for syntax and features and then sort through them to determine if this is really necessary. But what I'm really certain about several things

1. Pattern matching should be an extensio of case
2. Unification is overkill in most cases
3. Special syntax for variable captures should be carefully considered - is it really necessary or will it only make code less readable
4. Omitting abbreviated enum name when matching kind is a huge plus for readability.

[Araq]

The only thing I really care about is supporting if conditions with the pattern like so:

case n.kind
of foo and n.len == 4:
  actionA
else:
  actionB

This might require a language extension as a macro can only support it well via code duplication.

[haxscramper]

@Araq, This is already supported thanks to UFCS - I just generate access path to the field in object, without differentiating between fields and function calls

    macro e(body: untyped): untyped =
      expandMacros:
        case body:
          of Bracket(len: in {3 .. 6}):
            newLit(expr.toStrLit().strVal() & " matched")
          else:
            newLit("not matched")

    echo e([2,3,4])
    echo e([3, 4])

Generated code

block:
  let expr = body
  if kind(expr) == nnkBracket and contains({3..6}, len(expr)): newLit(
      strVal(toStrLit(expr)) & " matched")
  else:
    newLit("not matched")

[alehander92]

@haxscramper thanks!

Pattern matching should be an extensio of case

sounds good

Unification is overkill in most cases

iirc it seemed not hard to implement, but this is not a top goal indeed

Special syntax for variable captures should be carefully considered - is it really necessary or will it only make code less readable

makes sense: I'll look at the bigger comment later

Omitting abbreviated enum name when matching kind is a huge plus for readability.

yep!

[alehander92]

please keep in mind that probably nim nodes should work in a similar way to other variant types(even if nim nodes are defined as a more special type): we don't want to overspecialize for one case !

Also, exhaustiveness checking would be useful even if not for all possible situations 👍

[haxscramper]

@alehander92

There is zero specific distinction for Nim node in a way I currently implement it - I have a little hack that just takes .kind type implementation and determines correct prefix that should be added if necessary.

https://github.com/haxscramper/hmisc/blob/f58838040170547e19c01bd6b9f3e42a16811f91/src/hmisc/macros/matching.nim#L44

Exhaustiveness check is possible in theory but only for simpler patterns and it would make things more complicated as it would be necessary to either write custom checker or somehow lift kind fields and do more sophisticated rewrite to take advantage of case checks. Right now this is a simple rewrite to series of if branches with no specific checks.

[alehander92]

iirc exhaustiveness checking isn't really that hard . Also we want to take advantage of generation of case if possible: pattern matching should be zero overhead. Of course those are not top priorities, so probably they don't need to be implemented now

[alehander92]

basically for compound patterns you need to compose the simpler checks and if you already have those: this might not be too hard, but this is just old brainstorming, so I might be very wrong about it