An upcoming experimental feature: Active Patterns in F#

Greg Neverov (inventor of the C# dialect Metaphor and an intern at MSR Cambridge this summer) has been working on an experimental new language feature called "active patterns".  This topic has come up on The Hub, so I thought I would mention a bit about it here, though I will only be able to give a brief taste in this entry.  This will be an experimental (and in some ways quite incomplete) feature in the next release of F#. 

In their simplest incarnation active patterns essentially let you use functions that have types such as

   valPattern : int -> int option as pattern "destructors" (I prefer the term "query functions").  For example, consider the following query functions:letEven (n) = if (n% 2 = 0 ) thenSome (n/ 2 ) elseNone
letOdd (n) = if (n% 2 = 1 ) thenSome (n/ 2 ) elseNone

These can be used as:

match

n with
| Even (m) -> ...
| Odd (m) -> ...
| _ -> ...

There are a few quirks - query functions are actually values of type IPattern<'a,'b>:

typeIPattern <'a,'b> =
  interface
abstractQuery : ('b -> 'a option)
end

to allow them to support additional functionality (e.g. construction, or more efficient query interfaces).  We are also working on optional techniques to label a set of query values as forming a complete and disjoint decomposition of a type (a "view" - see also Phil Wadler's original paper and the proposed design for Haskell 98, as well as Erwig's 1996 paper, from where we get the name "active patterns").  We also want to give interfaces for faster byref-based query functions that do not need to allocate each time a particular query is run.  Greg has also been doing some work on better code generation - at the moment we generate naive code for nested active pattern matches.

The important thing about active patterns is that they allow pattern matching to work through abstraction boundaries (unlike existing pattern constructs), and can be nested (as with all patterns).  One downside is that in there is nothing to stop them having side effects. Another potential downside is that in most common and interesting usage scenarios there's no real way to prevent patterns from overlapping - a library designer can add an assertion that Even and Odd are disjoint and complete, but for most interesting patterns that can't be statically checked.  

The question always comes up "how many times do the pattern functions get run?"  (Chris Okasaki gave one potential semantics in his 1998 paper.) The F# semantics is being finalized, but we believe we will not guarantee a particular execution strategy for pattern matches involving active patterns, or at least not at this stage in our experimentation. In other words, the compiler will be free to run the pattern functions as many times as it likes, or not at all if it can detect a pattern clause will fail for other reasons. We believe this is a suitable preliminary semantics in the context of F#.

Greg is doing the compiler work on this, and has been developing lots of great examples of the use of the feature (higher order active patterns, querying abstract objects such as System.Type objects, querying lists with different underlying implementations, and using the patterns in conjunction with F# quotation templates).   We're looking forward to your feedback, and to finalizing the feature over the next few releases.

BTW I showed this feature to Martin Odersky at the Functional Programming WG2.8 meeting.  He has obviously been thinking a lot about pattern matching and defending it to the Scala community .  He was extremely interested to see the prototype design for active patterns in F#.  I have a suspicion we may also see something like active patterns it Scala one day.  I'm always glad to see tech transfer in this way - if techniques make their way into Scala and F# and are well received then we may soon see similar things in Haskell, C# and VB too.