Pattern matching with substrings

[onetonfoot]

First off thanks for the package it works great. I'm not sure if this is and bug or the intended semantics (if so feel free to close) but when pattern matching on a String type the following works fine

x = ["a","b","c"]


@match x begin
    ["a", z, "c"] => :okay
    _ => :nomatch
end 
#:okay

But the same pattern fails on a SubString

y = split("a b c")

@match y begin
    ["a", z, "c"] => :okay
    _ => :nomatch
end
#nomatch

[thautwarm]

Hello!
This is a bug as we want to achieve a most intuitive design if possible.
The next release will fix this but might not come out very soon, thus you can use

@match y begin
    [&"a", z, &"c"] => :okay
    _ => :nomatch
end

as a workaround.

You might feel like to check Reference Pattern in MLStyle.jl, aka Pin operator in Elixir.

[inkydragon]

When I use Julia 1.0.* with MLStyle.jl v0.3.0 or master branch, it works well and print :okay.

And Julia 1.1.* do have this issue.

[thautwarm]

@inkydragon
In fact I'm not very sure that if we should use String literal "s" to match other object s when s satisfies s == "s".

Say, we can have an arbitrary ==,

abstract type AbstractMySpecificString end

eq = :(==)
@eval Base.$eq(::AbstractMySpecificString, ::Any) = false

@match AbstractMySpecificString() begin
    1 => true
    _ => false
end

What should the output be?

Initially I feel like to support some of the ==, but I also think it dangerous and inefficient to support all of them.

[thautwarm]

@inkydragon This behaviour is actually been aware of: https://github.com/thautwarm/MLStyle.jl/blob/master/src/Pervasives.jl#L19

However I also think matching SubString with String literals makes sense.

[oxinabox]

I also expected that SubStrings would match with string literals.
Caught me out on my first use

[thautwarm]

@oxinabox Understood. It's a problem, but I don't feel like to support matching SubStrings here unless we have solved the issue presented in #62 (comment)

If we support matching SubStrings and Strings with String literals directly, it'll raise consistency problems.

[oxinabox]

support anything that is isequal to a literal?
Misdefining isequal breaks common language constructs (like Sets and Dicts) anyway.
So if it also breaks MLStyle i don't see the issue.

Re: #62 (comment)

What should the output be?

Why would the output not be false ?

[thautwarm]

Misdefining isequal breaks common language constructs (like Sets and Dicts) anyway.
So if it also breaks MLStyle i don't see the issue.

After pondering for a while, I think there're still some issues.

I hope people could help me with following issues, because Julia programmers' mental model is more crucial than the technical parts.

Issues

1. Conventions among various implementations of pattern matching

In fact, other canonical languages with pattern matching like Haskell, OCaml and F# won't let you match
1 with 1.0:

case 1 of 1.0 -> 1

match 1 with 1.0 -> 1

They all failed when compiling, or produced a warning in REPL.

If we allow

@match 1 begin 1.0 => 1 end

in Julia according to isequal, it might cause some conflicts against the mainstream design.

However, Scala supports 1 match {1.0 => 1}, but it's also well-known that pattern matching in Scala is relatively awful.

2. Parametric pattern matching

A constructor might accept a single argument typed Int or Float64, however, in this case, the Int instance is not equivalent to the Float64 even if they are equivalent according to isequal.

For instance, pattern matching is super useful in compiler stuffs. We could use ANF via MLStyle's @data, to represent the constructs of a programming language:

@data Exp{T} begin
       Value(T)
       ...
end

Now, the intermediate representation of integer 1 literal is Value(1), and that of float 1.0 is Value(1.0). However, if we match literal patterns according to isequal , pattern Value(1) will cover pattern Value(1.0), which will be counterintuitive:

function mytransformation(ir::Exp{T}) where T
    @match ir begin
      Value(1) =>  ...
      Value(1.0) =>  ...
    end
end

Proposals

We can keep literal patterns as simple as possible, and make Int(Int64), Float64, Char, UIntX or BigInt and other Julia grammatical literals solely matchable according to ===. In this case, we can just ignore the influences from overloading.

We can use the reference pattern/pin operator @match 1 begin &1.0 => 1 end, or introduce a specific pattern IsEqual to have @match 1 begin IsEqual(1.0) => 1 . In this case, we can just take advantage of isequal.

[onetonfoot]

In my mental model I naturally assumed pattern matching would use ==, since in cases where I care about a specific type I'd just use the explicit type syntax.

x = 10

@match x begin
    10::Float64 => :float
    10::Int => :int
    _ => :no_match
end

I guess you could argue this is more natural since it relies on the type syntax Julia users should already be familiar with, rather than having to introduce additional syntax such as Value.

This also aligns with how matching seems to work on a Dict currently, it doesn't care if the key is a SubString or a String.

d = Dict( k => i for (i , k) in enumerate(split("a b c")))

@match d  begin
    Dict("a" => a ) =>  :substring_key
    _ => :no_match
end

Side note - following this logic I'd expect the following to work but it currently doesn't.

@match d  begin
    Dict{SubString,Int}("a" => a ) =>  :match
    _ => :no_match
end
#LoadError: PatternUnsolvedException

Either way I think as long as the documentation mentions if pattern matching is based on == or ===, it's fine.

[thautwarm]

support anything that is isequal to a literal?
Misdefining isequal breaks common language constructs (like Sets and Dicts) anyway.
So if it also breaks MLStyle i don't see the issue.

Re: #62 (comment)

What should the output be?

Why would the output not be false ?

Hi, some of the Julia 1.1+ versions broke the String equality by ===(although get fixed since v1.2.0-rc2), and I think it a bit difficult for us to choose == or === according to Julia versions.

I'm now planning to use isequal to compare abstractstrings, while the speed will get slow down in some cases of using string patterns. e.g, in v1.1.1,

julia> using BenchmarkTools
julia> a = "123"
"123"
julia> b = "123"
"123"
julia> c = "234"
"234"
julia> @btime a == b
  12.796 ns (0 allocations: 0 bytes)
true
julia> @btime a === b
  6.091 ns (0 allocations: 0 bytes)
true
julia> @btime a == c
  12.992 ns (0 allocations: 0 bytes)
false
julia> @btime a === c
  6.088 ns (0 allocations: 0 bytes)

Is performance loss affordable for you?
Appreciations to any suggestions of this issue.