F# Hawkeye : Pattern Matching

(Harry is @ DevTeach in Vancounver with his family this week. He was hoping to still do Morning Coffee posts, but that’s turned out to be infeasible. So instead, you get a series of pre-written posts about F#.)

Most FP languages include some type of pattern matching, and F# is no exception. At first blush, pattern matching looks a little like a switch statement, but it’s much more powerful. Where switch statements typically only do simple matches such as “does this variable equal this constant?”. In F#, you can break apart types, use wildcards even pass the potential match data into a custom function to determines if there’s a match. Of course, you can also do your more run-of-the-mill “does value equal constant” comparisons as well.

The problem with most functional language is that while pattern matching is powerful, it’s not particularly extensible. As Don pointed out in a recent paper, this becomes a real problem when trying to integrate FP with OO. OO is designed to hide details behind abstractions. Yet those abstractions can’t be used in pattern matching. Luckily, Don and the F# Guys (sounds like a band) have invented an extensible pattern matching syntax called Active Patterns to deal with this problem. Basically, in more recent versions of F#, you can adorn functions with special syntax so that you can use them in your pattern matching clauses.

This turns out to be wicked cool for writing parsers. I’m building recursive descent parsers, so each grammar production is implemented as a function. Yet, since I’m using the active pattern syntax, I can use them in pattern matching clauses. This allows me to chain together functions in a single match clause rather than having multiple match statements. And it’s very readable. For example, the function to recognize the grammar production Additive  <- Multitive ‘+’ Additive | Multitive is translated into the following F#:

and (|Additive|_|) input =
    match input with
    | Multitive(v1,Token '+' (Additive(v2, input))) -> Some(v1+v2,input)
    | Multitive(v,input) -> Some(v,input)
    | _ -> None

The weird “bananas” around Additive on the first line indicate this is an active pattern. Multitive and Token are also an active patterns. This syntax is a little parens heavy, but otherwise, that translation from grammar to F# is nearly declarative. It almost defeats the need for having a parser generator when building a parser is this straightforward. Almost.


Out of curiosity, are you able to post any of your parser code? I'm only just getting into F# as and when I have spare time - but I'm interested in if/how you tokenize your input string using F# code before parsing the stream of tokens via pattern matching - I've been attempting to use regex Active Patterns so far, and the results aren't pretty (possibly because I haven't quite "grokked" how best to use Active Patterns to their full potential). Keep up the good posts on F#! Chez, - Alex
Will do - just let me get caught up at work first!
Does your weaponly also comprise such elements as "nice red uniforms"? I'd love to see the parser, too, as I'll soon be embarking on one of my own, though I'll be using fslex and fsyacc for practice. I'll post about it. The Active Pattern thing is mind-blowing.
I didn't expect a kind of Spanish Inquisition! :)
I'm interested in generating various classes of pictures using grammars. I've worked through the included intro fslex fsyacc examples from Microsoft, Foundations of F#, and F# Journal; each has its'differences. Just ordered F# Expert, and considering geting OCaml book. I'm always interested in more intelligible code examples. Glad to find you're a resource.