First-Class Pattern Matching

I was reading through the Tour of Scala , interested in Scala’s fusion of functional programming and Java-style object-oriented programming, when I came across the concept of extractor objects .

Essentially, a Scala object is a singleton class, and it comes with two methods you can define that - weirdly enough - can be used used for custom pattern matching:

object CustomerID:

  def apply(name: String) = s"$name--23098234908"

  def unapply(customerID: String): Option[String] =
    val stringArray: Array[String] = customerID.split("--")
    if stringArray.tail.nonEmpty then Some(stringArray.head) else None

val customer1ID = CustomerID("Sukyoung")  // Sukyoung--23098234908
customer1ID match
  case CustomerID(name) => println(name)  // prints Sukyoung
  case _ => println("Could not extract a CustomerID")

This caught me by major surprise as I was not aware any language yet had a way to support first-class pattern matching to any extent.

I was even more surprised to then learn that something similar is also supported in Haskell:

{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE ViewPatterns #-}

-- A space is used instead of `--` because Haskell's
-- standard library has no `splitOn` function :(
applyCustomerId :: String -> String
applyCustomerId name = name ++ " 23098234908"

unapplyCustomerId :: String -> Maybe String
unapplyCustomerId str = case words str of
  (name:_) -> Just name
  _ -> Nothing

pattern CustomerId :: String -> String
pattern CustomerId name <- (unapplyCustomerId -> Just name)

main = case applyCustomerId "Sukyoung" of
  CustomerId name -> putStrLn name
  _ -> putStrLn "Could not extract a CustomerID"

I do like the Haskell approach much more than Scala’s since it makes the “pattern” more obvious via the pattern keyword and specific <- (f -> x) syntax.

But it still isn’t quite satisfactory.

The is operator

Suppose Haskell had an operator that could pattern match on a value as a boolean expression:

isCustomerId :: String -> Bool
isCustomerId str = safeHead (words str) `is` (Just _)

Right now, the CustomerId pattern is checked like unapplyCustomerId -> Just name, but if the function before the -> were to always return a boolean anyway, then we could simplify this syntax:

pattern CustomerId :: String -> String
pattern CustomerId name <- isCustomerId

And the compiler would know what to bind name to as it could check where pattern matching occurs within isCustomerId, which in this case is via the is operator.

Well, I’ve been designing a language that happens to already have such an is operator, and so I was able to come across this solution naturally. Here’s how you’d define it:

def CustomerId #= subtype[String]

impl From[String, U64] for CustomerId:
	static def from #= fn(name # String, id # U64) -> Self:
		"${name}--${id}"

impl Match[String, U64] for CustomerId:
	def is #= fn(&self, name # String, id # U64) -> Bool:
		self.splitAt("--") |> @.length is 2
			and @.at(0) is name
			and U64::from(@.at(1)) is id

First off, this language is in its very early stages of design, and so a lot of the syntax is subject to change. Those who have used Rust before, though, should be familiar with the impl definition where we implement the From and Match traits for our CustomerId subtype.

A subtype differs from a type in that it does not wrap the underlying data. Instead, the data can be accessed directly and all of its properties and functions are still available to access - i.e., "Foo-1801" is CustomerId("Foo-1801"). It is also possible to impose restrictions on the input values, but that’s a topic for a different article.

The From trait works very much like it does in Rust where it allows you to call CustomerId::from() on data that isn’t implicitly convertible to a String. The Match trait, however, is something new. It allows you to overload the is operator for a particular type and set of parameters.

In pratice, it is used like this:

if CustomerId::from("Jeff", 19970823) is
	| CustomerId("Kojo", 20060717):
		echo("You must be Kojo Bailey!")
	| CustomerId("Jeff", _):
		echo("Woah! Jeffs are banned from this company!")
	| CustomerId(_, def id):
		echo("Welcome patient ${id}!")
	| _:
		echo("Your ID appears to be invalid...")

Not particularly complicated, really. There are some rules to keep in mind though:

-- Compile Error: Left side must be a value.
CustomerId(name = "Kojo", id = 20060717) is "Kojo--20060717"

-- Compares value to value.
CustomerId::from(name = "Kojo", id = 20060717) is "Kojo--20060717"

-- Compares value to pattern.
"Kojo--20060717" is CustomerId(name = "Kojo", id = 20060717)

-- Compares value to value.
"Kojo--20060717" is CustomerId::from(name = "Kojo", id = 20060717)

And that’s it! The is operator helps to keep things very simple.

You might be wondering though, how exactly does the compiler know what values to bind to from the is overload? To help answer that question, first have a look at this comparison with if the language did not have an is operator and instead had to rely on a classic match expression:

def is #= fn(&self, name # String, id # U64) -> Bool:
    self.splitAt("--") |> @.length is 2
        and @.at(0) is name
        and U64::from(@.at(1)) is id

def match #= fn(&self, name # String, id # U64) -> Bool:
    def strArray #= self.splitAt("--")
    if str.length != 2: return False
    match (strArray.at(0), U64::from(strArray.at(1))):
        (name, id) -> True
        _ -> False

The compiler should be able to deduce what both name and id bind to based on what they pattern matched against. To write it in a way that is even clearer:

def is #= fn(&self, name # String, id # U64) -> Bool:
    self.splitAt("--") |> @.length is 2
        and (@.at(0), U64::from(@.at(1)))
            is (name, id)

However, the compiler also needs to enforce that each argument that could bind is used exactly once an only in an is expression. Any other case would either cause other issues or just not be very useful anyway. I do admit that having these implicit compiler restrictions isn’t ideal and I will continue to look for possible alternatives that may feel more intuitive, but at the very least, it wouldn’t be hard for the programmer to learn given the compiler should give useful error messages.

What Haskell does with its (f -> x) syntax is very robust since it restricts you from misusing the binding arguments; the syntax is just quite confusing in my opinion. This is largely how Haskell quite frankly “cheats” via its type signature grammar:

pattern CustomerId :: String -> String
pattern CustomerId name <- (unapplyCustomerId -> Just name)

This pattern’s type is written as String -> String, but that is not accurate considering it does not take a string and then return a string. Haskell having its type signatures separate from its definitions means it can get away with this, whereas you would struggle to make the type annotations inline:

pattern CustomerId (name :: String) (input :: String) =
  (unapplyCustomerId input -> Just name)

This is already dodgy, and what exactly would its return type even be? A boolean? Because that would just get us to where I am currently.

Conclusion

Regardless, I think this is very interesting (to put it lightly) and I hope I or someone else can think of an elegant solution in the not-so-distant future.

This has been by first blog post on this new language I’m designing, and I look forward to sharing more of it. My dissatisfaction with existing programming languages has pushed me to a point where I want to focus solely on developing this language until I have it implemented so that I can use it! Whether or not it will finally satisfy my needs remains to be seen… but I am optimistic.