The syntax of pattern matching

[kyouko-taiga]

Our implementation of pattern matching has significantly drifted from our specification so I think it may be good to have a look at the current state of things. Today, pattern matching looks like Swift but with a couple of notable syntactic differences.

First, don't use the is, as and as? operators; instead we use : to match over types. For example:

// In Swift
let x: Any = ...
switch x {
  case let y as T:
    print("a T equal to \(y)")
  case is U:
    print("an arbitrary U") }
  default:
    print("something else")
}

// In Hylo
let x: Any = ...
match x {
  case let y : T
    { print("a T equal to \(y)") } 
  case _: U
    { print(y) } 
  case _
    { print("something else") }
}

The reason for having match instead of switch is kind of cosmetic but my sense is that Swift picked the latter to make simple switch statements (e.g., over integers) look familiar to a C-family audience. IMO, this construction is going much farther than C's switch and relates more to pattern matching as popularized by other languages like Scala or Ocaml.

I find the use of as and as? confusing in Swift. The latter must be used in if statements and the former in all other forms of matching. This rule seems questionably (pun intended) motivated to me. In contrast, I find : more concise and using it consistently feels less confusing.

A second difference is that we don't use case to introduce patterns in if statement/expression or a for loop:

// In Swift
let x: [Any] = ...
for case let y as T in x { print(y) }

// In Hylo
let x: Array<Any> = ...
for let y: T in x { print(y) }

The absence of case makes our statements/expressions more concise without removing clarity. The same couldn't be said in match, however, because patterns may become difficult to identify in that expression if you (as a human) quickly parse it. To understand what I mean, let's examine the following expression:

match x { _: T { a } _ { b } }

The structure of our AST currently makes it impossible to introduce names at arbitrary depths in structural pattern. For example, this program is syntactically illegal:

let x = (a: 1, b: 2)
if (a: 1, b: let y) = x { print(y) }

I am not sure it is something we actually want, though, so when I discovered the limitation I left it there. We can often rewrite this kind of code using a side condition on the match, or even write another match in the success clause. However, these workarounds are more verbose and so it is quite possible that we may want to lift the limitation.

A last notable change is that optional binding in Hylo must use an optional pattern rather than Swift's more concise syntax. This difference makes optionals behave more consistently w.r.t. to other union types because let y = x is irrefutable and doesn't narrow x's type in Hylo.

// In Swift
let x = Optional(1)
if let y = x { print(y) }

// In Hylo
let x = Optional(1)
if let y? = x { print(y) }

Note: a variant of the Hylo syntax does exist in Swift.

Ideas for extensions

It would be nice if we could pattern match on non-structural types. Swift has some support of custom patterns but I find it lacking. AFAIK, there's no way to "bind" values with a custom pattern; we can only match existing values.

Custom patterns

One way to support more powerful custom patterns would be to define a trait that requires a projection:

public trait Inspectable {
  type Scrutinee
  property scrutinee: Scrutinee { let }
}

type Point: Regular, Inspectable {
  public var x: Int
  public var y: Int
  public memberwise init

  public typealias Scrutinee = { x: Int, y: Int }
  public property Scrutinee: { (x: x, y: y) }
}

public fun main() {
  let p = Point(x: 4, y: 2)
  match p {
    case (x: _, y: 2) { ... }
    case _ { ... }
  }
}

Of course, we could have different effect requirements on scrutinee to support inout patterns and sink patterns too.

List patterns

I wrote this extension in the utilities of hc, which I use all the time.

extension Collection {
  /// The first element of `self` and its suffix after its first index or `nil` if `self` is empty.
  public var headAndTail: (head: Element, tail: SubSequence)? {
    if isEmpty { return nil }
    return (head: self[startIndex], tail: self[index(after: startIndex)...])
  }
}

You'll notice that this method relates to a non-empty list pattern in Haskell. It would be nice if we could use it in pattern matching.

I think we could with the following trait:

public trait InspectableAsCollection {
  type Element
  type SubCollection
  property collection_scrutinee: Optional<remote let {head: Element, tail: SubCollection}> { let }
}

// Or perhaps Collection : InspectableAsCollection ?
public conformance Array: InspectableAsCollection { ... }

public fun main() {
  let a = Array([1, 2, 3])
  match a {
    case let (h +... t) where t.is_empty()
      { /* matches a collection of one element */ }
    case let (h +... t)
      { /* matches the head and tail of a non-empty collection */ }
    case _
      { /* collection is empty if we're here */ }
  }
}

[dabrahams]

I'm just noticing in two of your Hylo examples:

for let y: T in x { print(y) }

and

if (a: 1, b: let y) = x { print(y) }

The inconsistency of the placement of let is surprising and the apparent use of y as a type name in the 2nd example is confusing. Or maybe I'm not reading the 2nd example correctly? Oh, I see, I'm not. Fact remains that the possiblity of these two syntaxes being legal is potentially confusing, so I'm leaving that part there as a marker.

OK, you say the 2nd example is “introducing names at arbitrary depths in structural pattern.” The introduced name is y here, right? y is at depth 1, where at depth 0 you have the entire pattern. So it sounds like you're saying you can't do a destructuring bind as part of a pattern match and instead must separately match and bind, e.g.:

if (a: 1, b: _) = x { let y = ??; print(y) }

Actually I don't know what I'd even write for ??. I can't write x.b in the general case because x could have union type, so .b is not necessarily statically knowable (and I hope we're not silently changing the type of x inside the if body based on the pattern match—that was proposed several times for Swift but I think it's confusing).

Anyway, I'm surely not interpreting your words correctly because not being able to pattern match and bind to a part in one expression seems awfully and needlessly inconvenient.

[dabrahams]

Suggestion:

extension Collection {
  /// The first element of `self` and the rest of its elements, or `nil` if `self` is empty.
  public var headAndTail: (head: Element, tail: SubSequence)? {
    first.map { (head: $0, tail: dropFirst()) }
  }
}

[kyouko-taiga]

Is this really how you want to spell computed properties, or am I mis-guessing the meaning of this construct?

It should have been property, sorry. It's clearly a computed property and it should have the same syntax and semantics.

[dabrahams]

But I can easily be convinced otherwise.

I'm glad you have no strong position and don't feel the need to convince you until real use-cases present contrary evidence.

[dabrahams]

@kyouko-taiga https://github.com/orgs/hylo-lang/discussions/1195#discussioncomment-8822064 ?
I didn't see an associated type declaration in your code but I assume you need one, unless I'm misunderstanding the whole idea.

[kyouko-taiga]

Yes, another mistake ...
I'm updating the original post.

[kyouko-taiga]

See also: https://docs.scala-lang.org/scala3/reference/changed-features/pattern-matching.html

[tothambrus11]

// In Swift
let x: [Any] = ...
for case let y as T in x { print(y) }

// In Hylo
let x: Array<Any> = ...
for let y: T in x { print(y) }

I find the second syntax a bit confusing. Usually, we are allowed to write the type of the binding after its declaration like let myVar: Int = getMyNumber() to constrain its type and make sure that the right hand side matches it. The problem with this syntax is that it might actually work for some time, but when the e.g. library writer changes x to be a collection of CaillerChocolates, the above code would silently turn into a filter.

@kyouko-taiga earlier mentioned a special where syntax for for loops, I think that would be a better alternative:

for let e in x where e : T { 
  .... 
}

...Or some generic algorithm that can utilize pattern matching as predicates. For this, I think the is keyword is actually useful from Swift, as it would look too ambiguous to write without a keyword:

let filtered = x.filter({ $0 is T })

// or

for let t in x.filter({ $0 is T }) {
  print(x)
}