Saturday, 17 February 2007

Symbolic manipulation

The F# programming language excels at the manipulation of symbolic expressions. This includes compiler and interpreter writing (the manipulation of programs) but perhaps the most obvious application is computer algebra.

The language features that make F# ideal for symbolic processing are variant types and pattern matching. The following snippet of F# code defines a variant type and overloads the + and * functions, allowing symbolic mathematical expressions to be constructed using ordinary arithmetic operators:

type t =
| Q of int
| Var of string
| Add of t * t
| Mul of t * t with

static member ( + ) (f, g) = match f, g with
| Q n, Q m -> Q (n + m)
| Q 0, e e, Q 0 -> e
| f, Add(g, h) -> f + g + h
| f, g -> Add(f, g)

static member ( * ) (f, g) = match f, g with
| Q n, Q m -> Q (n * m)
| Q 0, e e, Q 0 -> Q 0
| Q 1, e e, Q 1 -> e
| f, Mul(g, h) -> f * g * h
| f, g -> Mul(f, g)
end

Composing symbolic expressions using these operators has the added benefit of performing some simplifying rearrangements. For example, adding 0 or multiplying by 1 has no effect.

> Q 2 + Q 1 * Var "x" + Q 0;;
val it : t = Add (Q 2,Var "x")

As well as being expressive, F#'s pattern matching is also very efficient. This implementation can simplify randomly generated expressions with 10^6 atoms in 0.386s on my 2.2GHz AMD64.

Cheers,
Jon.

7 comments:

Jonathan said...

I think a tutorial on using pattern matching in F# would be really helpful. Those of us who haven't used either are pretty much at a loss for understanding the code.

Jon Harrop said...

Pattern matching really is an awesome tool, so I agree entirely that tutorials would be most welcome.

I wrote a series of freely-available articles on the benefits of the OCaml programming language. You may be interested in the article on pattern matching there.

The first chapter of my book OCaml for Scientists also has a big section on pattern matching.

I'll be posting the first chapter of F# for Scientists soon, which will contain similar information specific to the F# programming language.

Pål-Kristian said...

I think you shouldn't use a short constructor name such as "Q". Instead, perhaps use "Value" or even "Num"?

If you do, then your example is:

> Num 2 + (Num 1) * (Var "x") + Num 0;;

gmoudry said...

In F#, can you match by type of a .NET object?

e.g. with C# Linq expressions, could you match an unknown Expression with LambdaExpression containing a MemberInitExpression - and do so in one line of F# code?

Thanks,
George

Tomas Petricek said...

Yes, you can use patten matching to test type of .NET object:

match o with
| :? Button as b -> ...
| :? TextBox as t -> ...

etc...

Jon Harrop said...

As Tomas says, you certainly can pattern match by run-time type in F#.

However, F# is designed to be statically typed so a cleaner way to do that is to first abstract the unnecessary run-time tests (that can cause unwanted run-time errors) into a set of active patterns and then pattern match over the LINQ expressions.

Provided you must use LINQ expressions, this is a good idea. However, you're usually much better off using a native-F# implementation of expressions as this can be customized, will be more expressive and offers better static checking.

Cheers,
Jon.

Anonymous said...

Very nicce!