Exploration: Library-based Pattern Matching

[gilfusion]

Exploration: Library-based Pattern Matching

I'm not sure how this fits in here, but with all the discussion about adding new syntax to support pattern matching (#337, #124, among others), I decided to do some tinkering to see how much could be done with the existing syntax and what we be the absolute minimum to get as many of the proposed pattern matching concepts working as possible.

Examples

(I have a prototype where these actually run.)

Dim data As (x As Integer, y As Integer)
Do
    Console.Write("Enter x: ")
    data.x = CInt(Console.ReadLine())
    Console.Write("Enter y: ")
    data.y = CInt(Console.ReadLine())

    Select Case data
        Case Tuple(Value = 0, Value = 0)
            Console.WriteLine("Origin")
        Case Tuple(Value = 0, Anything)
            Console.WriteLine("Y Axis")
        Case Tuple(Anything, Value = 0)
            Console.WriteLine("X Axis")
        Case Tuple(Value > 0, Value > 0)
            Console.WriteLine("Quadrant I")
        Case Tuple(Value < 0, Value > 0)
            Console.WriteLine("Quadrant II")
        Case Tuple(Value < 0, Value < 0)
            Console.WriteLine("Quadrant III")
        Case Tuple(Value > 0, Value < 0)
            Console.WriteLine("Quadrant IV")
    End Select
Loop

Do
    Dim data As New List(Of String)
    Dim line As String
    Do
        Console.Write("Enter something:")
        line = Console.ReadLine()
        If line = "" Then
            Exit Do
        Else
            data.Add(line)
        End If
    Loop
    If data Like Enumerable(Match("A*"), Match("B*"), Match("C*"), Anything) Then
        Console.WriteLine("Are you going through the letters of the alphabet?")
    ElseIf data Like Enumerable(Match("*1"), Match("*2"), Match("*3"), Anything) Then
        Console.WriteLine("These seem to be numbered")
    Else
        Console.WriteLine("Could find nothing")
    End If
Loop

How it works

Pattern classes

There are a bunch of classes that implement an IPattern interface, overload the Like operator, and also overload the = operator (for Select Case support).

Convenience factory methods

Tuple(x, y) looks a little friendlier than New TuplePattern(x, y), so I implemented factory methods for most of the patterns I created so far.

This makes it simple to differentiate between a tuple pattern and a list/enumerable pattern, or between a constant string pattern (here called Value), a regex string pattern, and a classic VB Like string pattern (here called Match). This is a proof-of-concept prototype, so the names are very much not final.

All of these methods are kept in a Patterns module, actually using the fact that VB auto-imports module contents. (Most of the time, I wish VB didn't do that, but here I can see the point.)

The pattern that matches anything is a singleton object access through the Anything property.

Comparison patterns using a "marker" object

There is no rule that says overloaded comparison operators need to return Boolean.

The Value property is a singleton object of a ValueMarker class, whose overloaded comparison operators could return ComparisonPattern objects. The expression Value < 0 could return the same object as New ComparisonPattern(0, Comparison.LessThan).

Actually, in the current prototype, Value < 0 returns New RangePattern(Integer.MinValue, 0, excludeStart:=False, excludeFinish:=True), but that's an implementation detail.

Similarly, while my current prototype doesn't do this at the moment, it should be possible to overload the Not, And, and Or operators of each of the patterns to create more complex patterns.

Type check patterns using generic type arguments

The function Type(Of T)() returns a New TypePattern(Of T)() which handles the type checking pattern. I already like

Select Case obj
    Case Type(Of Foo)
        '...
    Case Type(Of Bar)
        '...
    Case Else
        '...
End Select

a little more than

If TypeOf obj Is Foo Then
    '...
ElseIf TypeOf obj Is Bar Then
    '...
Else
    '...
End If

Not functional: Assignment patterns

If we go the factory-method route, the simplest-seeming way to implement variable-extracting patterns is using a ByRef parameter in the factory method/constructor. Instead of a variable pattern, we would have an assignment pattern. If (a big if these days, I know), VB ever got Out variables (#60), this would become a variable pattern without any additional work.

Why doesn't it work? Well, although the target is passed ByRef into the factory/constructor, there's no way to use that reference from the Like operator, since it's a completely separate method. Implementing this pattern using a ByRef-like type might work, but it sounds like that's off the table, too. (Not to mention, making this pattern ByRef-like means it couldn't implement an IPattern interface, which, in this prototype, all the composite patterns use behind the scenes.)

Semi-functional: Nothing

myData Like Nothing might not work. You can hack around it using CObj(myData), since the built-in Like handler works for Object (and String, of course), and it does handle the Nothing case, but if your left-hand side is almost any other data type, Nothing won't help with the overload resolution, and you will likely get a compiler error.

The prototype also has some tricks to enable Nothing inside composite patterns.

What it needs from the language (or what people can try to hack around)

The absolute minimum I would ask from the language team, if we could get it, would be the ability to at least use, if not create, ByRef-like types (#297), so we could try to implement the assignment pattern.

Second on the list would be Out variables (#60).

Third would be some sort of Case Like feature for Select Case. The prototype gets Select Case working using the = operator, but I'd rather not enable = for the general case (the point is to steer people toward Like), and implementing = requires also implementing <>, which, again we don't need for pattern matching.

Beyond that, I could imagine LINQ-like syntax for creating these patterns and compiler optimizations that rewrite the pattern factory and Like operator into more straightforward code, like what C#'s pattern matching employs. I would also fit exhaustiveness checking and Select Case expressions into that imagined future.

Wrapping up

I don't know if this wall of text is helpful to anyone--maybe it could help the community effort to kickstart VB advancement again, maybe it could be useful to Project Mercury--but I figured I'd push out these thoughts on how to stretch the existing VB language with new concepts as we look into the future.

[VBAndCs]

In my opinion, this is how should tuple pattern be:

    Select Case data
        Case (0, 0)
            Console.WriteLine("Origin")
        Case (0, *)
            Console.WriteLine("Y Axis")
        Case (*, 0)
            Console.WriteLine("X Axis")
        Case (> 0, > 0)
            Console.WriteLine("Quadrant I")
        Case (< 0, > 0)
            Console.WriteLine("Quadrant II")
        Case (< 0, < 0)
            Console.WriteLine("Quadrant III")
        Case (> 0, < 0)
            Console.WriteLine("Quadrant IV")
    End Select
Loop

[gilfusion]

@VBAndCs , I rather like that design, too. When I first came up with the Value > 0 design, it was just supposed to be a placeholder until > 0 could become a reality. Since #497, I'm not sure it is going to become a reality, for VB itself, that is. Also, < 0 might clash with XML literals.

Also, since VB has historically favored keywords over punctuation, I had been curious what keyword would make a good equivalent for *, and Anything has a nice symmetry with Nothing.

And I'm still wondering if there's a way to implicitly convert a tuple of patterns to a tuple pattern in a way that doesn't break implicit conversions or overload resolution completely.

[VBAndCs]

VB already uses < in Cases. It just automatically adds Is (Is < 0) which can be done here too.
also * is already used in VB (in like and regex patterns) with the meaning anything.
So, I did nothing new. I just saved you one new breaking keyword.

[gilfusion]

Good points. It might be possible to make the syntax work.

[rskar-git]

@gilfusion I think it's great to see what can be presently done for all our pattern matching needs.

Here's a cheap and easy way to extend Select Case for a lot of things, including Tuples:

Structure Comparable
    Private ReadOnly Instance As Object
    Private Sub New(o As Object)
        Instance = o
    End Sub
    Public Shared Function Create(o As IComparable) As Comparable
        Return New Comparable(o)
    End Function
    Public Shared Operator =(x1 As Comparable, x2 As IComparable) As Boolean
        Return System.Object.Equals(x1.Instance, x2)
    End Operator
    Public Shared Operator <>(x1 As Comparable, x2 As IComparable) As Boolean
        Return Not System.Object.Equals(x1.Instance, x2)
    End Operator
    Public Shared Operator >(x1 As Comparable, x2 As IComparable) As Boolean
        Return x2.CompareTo(x1.Instance) < 0
    End Operator
    Public Shared Operator <(x1 As Comparable, x2 As IComparable) As Boolean
        Return x2.CompareTo(x1.Instance) > 0
    End Operator
    Public Shared Operator >=(x1 As Comparable, x2 As IComparable) As Boolean
        Return x2.CompareTo(x1.Instance) <= 0
    End Operator
    Public Shared Operator <=(x1 As Comparable, x2 As IComparable) As Boolean
        Return x2.CompareTo(x1.Instance) >= 0
    End Operator
End Structure
Module Extensions_Comparable
    <Extension> Function ToComparable(o As IComparable) As Comparable
        Return Comparable.Create(o)
    End Function
End Module

And then the "Quadrant" problem could be dealt with like so:

With data
    Select Case (Math.Sign(.x), Math.Sign(.y)).ToComparable()
        Case (0, 0) : WriteLine("Origin")
        Case (0, 1) : WriteLine("Y Axis")
        Case (1, 0) : WriteLine("X Axis")
        Case (1, 1) : WriteLine("Quadrant I")
        Case (-1, 1) : WriteLine("Quadrant II")
        Case (-1, -1) : WriteLine("Quadrant III")
        Case (1, -1) : WriteLine("Quadrant IV")
    End Select
End With

[rskar-git]

@gilfusion Proper pattern matching for data types is a tad messier. But here's a way, utilizing these:

Module TryAs
    Structure TryAsResult(Of T)
        Public ReadOnly Value As T
        Public ReadOnly HasValue As Boolean
        Private Sub New(x As Object)
            If TypeOf x Is T Then
                Value = DirectCast(x, T)
                HasValue = True
            Else
                Value = Nothing
                HasValue = False
            End If
        End Sub
        Public Shared Function Create(x As Object) As TryAsResult(Of T)
            Return New TryAsResult(Of T)(x)
        End Function
    End Structure
    Function TryAs(Of T)(x As Object) As TryAsResult(Of T)
        Return TryAsResult(Of T).Create(x)
    End Function
End Module

And with some lambda magic:

Call Sub(x)
         With TryAs(Of Foo)(x)
             If .HasValue Then
                 ' Do Foo stuff; .Value is of type Foo.
                 Dim hash = .Value.GetHashCode()
                 ' ... etc. ...
                 Return
             End If
         End With
         With TryAs(Of Bar)(x)
             If .HasValue Then
                 ' Do Bar stuff
                 ' ... etc. ...
                 Return
             End If
         End With
         With TryAs(Of SomeOtherType)(x)
             If .HasValue Then
                 ' ... etc. ...
                 Return
             End If
         End With
         ' With TryAs... etc. ...
         ' At this point, maybe the "Case Else" bit?
         ' ... etc. ...
     End Sub(xIn) ' xIn is some expression

[rskar-git]

@gilfusion Proper pattern matching for reference types could be done via TryParse and lambdas and this .Me extension:

Module Extensions_WithStatement
    <Extension> Function [Me](Of T)(x As T) As T
        Return x
    End Function
End Module

And do it like so:

Call Sub(x)
         With TryCast(x, Foo)
             If .Me IsNot Nothing Then
                 ' Do Foo stuff; .Me is of type Foo.
                 Dim hash = .Me.GetHashCode()
                 ' ... etc. ...
                 Return
             End If
         End With
         With TryCast(x, Bar)
             If .Me IsNot Nothing Then
                 ' Do Bar stuff
                 ' ... etc. ...
                 Return
             End If
         End With
         With TryCast(x, SomeOtherType)
             If .Me IsNot Nothing Then
                 ' ... etc. ...
                 Return
             End If
         End With
         ' With TryCast... etc. ...
         ' At this point, maybe the "Case Else" bit?
         ' ... etc. ...
     End Sub(xIn) ' xIn is some expression

[Padanian]

Would that be really what you would use for detecting in what quadrant a point is? Instead of using 4 if’s?

[pricerc]

Would that be really what you would use for detecting in what quadrant a point is? Instead of using 4 if’s?

It is helpful to illustrate some new concept with simple contrived examples, like these.

On the other hand, one does wonder whether a 'pattern-based' version would be easier to understand and/or maintain over the long term.

Or how it would perform. I don't know under what context you'd want to use a 'quadrant check', but a game seems likely. Or some other system that needs high performance. I just don't see a compiler figuring out how to turn those patterns into efficient run-time code.

[AdamSpeight2008]

A With Clause could be use for recursive pattern-matching

Select Case thisPersion
       Case With
            {
              .Gender = Male
            }
End Select

[AdamSpeight2008]

@rskar-git rewritten your example, to TypeClause and IntoDeclarations

Select Case x
       Case Is Foo Into thisFoo
            ' Do Foo stuff; .Me is of type Foo.
             Dim hash = thisFoo.GetHashCode()
             ' ... etc. ...
             Return
       Case Is Bar Into thisBar
            ' Do Bar stuff
            ' ... etc. ...
           Return
       Case Is SomeOtherType Into thisSomeOtherType
            ' ... etc. ...
       Case Else
            ' At this point, maybe the "Case Else" bit?
            ' ... etc. ...
End Select

[gilfusion]

Here's another method that could be used to pattern-match types:

Function TryCastTo(Of TSrc, TDest As TSrc)(src As TSrc, ByRef dest As TDest) As Boolean
	If TypeOf src Is TDest Then
		dest = CType(src, TDest)
		Return True
	Else
		dest = Nothing
		Return False
	End If
End Function

We could then use it in some way like this:

Dim obj As Object = SomeFunc()
Dim int As Integer, bool As Boolean, str As String
If TryCastTo(obj, int) Then
	'Integer-specific code
ElseIf TryCastTo(obj, bool) Then
	'Boolean-specific code
ElseIf TryCastTo(obj, str)
	'String-specific code
Else
	'General code
End If

We would have to pre-define the variables for each of the cases, but we already have to deal with stuff like that when we use TryParse methods. (And there's another reason why #60 is on my wish list.)

[rskar-git]

(This is fun!) Yet another types pattern-match scheme.

( @AdamSpeight2008 BTW, I do like Case Is ... Into syntax. )

<Extension> Function [Call](Of T)(x As T, op As Action(Of T)) As Boolean
    op(x) : Return True
End Function

Function TryCastTo(Of T As Structure)(x As Object) As T?
    Return If(TypeOf x Is T, DirectCast(x, T), DirectCast(Nothing, T?))
End Function

...

    Dim o1 As ICollection = New List(Of String)
    Dim o2 As ICollection = {Now.Hour, Now.Minute, Now.Second}

    Dim o = (New Object() {o1, o2, 123, 1.23})(Now.Millisecond And 3)

    If TryCast(o, ICloneable)?.Call(
        Sub(oClone)
            ' Clone stuff
            WriteLine($"Clone {oClone.ToString()}")
        End Sub) Then
    ElseIf TryCast(o, IList)?.Call(
        Sub(oList)
            ' List stuff
            WriteLine($"List {oList.ToString()}")
        End Sub) Then
    ElseIf TryCastTo(Of Integer)(o)?.Call(
        Sub(oInt)
            ' Integer stuff
            WriteLine($"Integer {oInt.ToString()}")
        End Sub) Then
    Else
        ' Other stuff
        WriteLine($"Other {o.ToString()}")
    End If

No need to pre-declare the "type-cast" variables; lambda parameters can do the trick!

[AdamSpeight2008]

I'm trying to reuse exist syntax or forms before creating something new, eg the ... Into ... is borrowing the syntax from linq query. From x In g GroupBy x.GroupName InTo theseGroups

... Into variable would automagically create the instance, if the variable isn't declared, but it would only vaild within that Case block section. If the variable does exist it would attempt to cast the the result of the typecast into the variable, otherwise report an error.

It was also designed to play well with When ... statements.

Select Case obj
       Case Is Int32 InTo i
            When i < 0
                 Return "Negative Integer"
            When i = 0
                 Return "Zero"
            When i > 0
                 Return "Positive Integer"
            Else
                 Return "..."
       Case Is Decimal InTo d
            When d = 0
                 Return "Decimal Zero
            When d = 1
                 Return "Decimal One"
            Else 
                 Return "..."
       Case Else
            ....
End Select   

[gilfusion]

@AdamSpeight2008, so that's where that's from! I don't use LINQ query syntax often, so that's why I didn't recognize it.

@rskar-git, If you throw lambdas into the game, we can do type checking by itself with this

Sub TypeCase(Of TSrc, T1 As TSrc, T2 As TSrc, T3 As TSrc)(value As TSrc, action1 As Action(Of T1), action2 As Action(Of T2), action3 As Action(Of T3), actionElse As Action)
	If TypeOf value Is T1 Then
		action1?.Invoke(CType(value, T1))
	ElseIf TypeOf value Is T2 Then
		action2?.Invoke(CType(value, T2))
	ElseIf TypeOf value Is T3 Then
		action3?.Invoke(CType(value, T3))
	Else
		actionElse?.Invoke()
	End If
End Sub

which would simplify your last example to

Dim o1 As ICollection = New List(Of String)
Dim o2 As ICollection = {Date.Now.Hour, Date.Now.Minute, Date.Now.Second}

Dim o = (New Object() {o1, o2, 123, 1.23})(Date.Now.Millisecond And 3)

TypeCase(o,
    Sub(oClone As ICloneable)
        ' Clone stuff
        Console.WriteLine($"Clone {oClone.ToString()}")
    End Sub,
    Sub(oList As IList)
        ' List stuff
        Console.WriteLine($"List {oList.ToString()}")
    End Sub,
    Sub(oInt As Integer)
        ' Integer stuff
        Console.WriteLine($"Integer {oInt.ToString()}")
    End Sub,
    Sub()
    	' Other stuff
        Console.WriteLine($"Other {o.ToString()}")
    End Sub)

If lambda performance is good enough, we could probably use them to emulate a lot of things.

That's ultimately the reason I opened this issue--if Microsoft, as the blog post said, never adds another language feature to official VB ever again, could we use the features we already have to emulate the ones we wish we had?