Symbolic calculation in F#. Part 1: derivatives
I am learning F#, and one of the best areas to use a functional language is to apply it to symbolic calculations. Like evaluating function derivatives. I remember how I was impressed many years ago when I looked at a program in Prolog that occupied not more than one computer screen but could tell me that derivative of sin(x) was cos(x). So I wanted to do the same in F#.
If you ask a developer who is only using procedural languages to write a program that calculates derivatives in a symbolic form, chances are pretty good that he will start with parsing input strings. That’s the nature of procedural languages: you solve a task by building a sequence of steps that it takes to convert input to output. A developer focusing on a higher level abstraction migh start with building classes for expression trees, so he can implement derivative calculation on the top of them. But what derivative calculation has with creating classes to store tree nodes? Why should we care?
In procedural languages we need to care. As Niklaus Wirth stated in his book title, "Algorithms + Data Structures = Programs". So we express our imperative programs in algorithms and apply them to data structures.
With F# it’s completely different. You simply describe your domain, your rules. And things just happens…
So we’ll do derivatives. First we need to define the scope of our calculations, our symbols. Note that Expression type doesn’t define a data structure – it’s just a collection of symbols that we will be using to form functional expressions.
type Expression =
| X
| Const of float
| Neg of Expression
| Add of Expression * Expression
| Sub of Expression * Expression
| Mul of Expression * Expression
| Div of Expression * Expression
| Pow of Expression * Expression
| Exp of Expression
| Log of Expression
| Sin of Expression
| Cos of Expression
What we just declared is called in F# discriminated union. I won’t be spending time on F# syntax details, I am learning F# from two great books: "Programming F#" and "Real World Functional Programming: With Examples in F# and C#" (I started with the second one but had to switch to the first one that in my opinion provides a better transition to a functional programming and F# style).
As you can see, we made some restrictions to expression syntax: we assume that numeric constants are of type float, and we only support four functions: exponent, natural logarithm, sine and cosine. But this should be sufficient for a purpose of language demo. In addition, there is only one variable symbol (X).
Before we proceed with derivative definition, there is a couple of helper construction I’d like to define. We may need to have a common match for binary operators (Add, Sub, Mul, Div) and supported functions (Exp, Log, Sin, Cos). So we’ll define so called active patterns that can be used to match such constructs:
let (|Op|_|) (x : Expression) =
match x with
| Add(e1, e2) -> Some(Add, e1, e2)
| Sub(e1, e2) -> Some(Sub, e1, e2)
| Mul(e1, e2) -> Some(Mul, e1, e2)
| Div(e1, e2) -> Some(Div, e1, e2)
| Pow(e1, e2) -> Some(Pow, e1, e2)
| _ -> None
let (|Func|_|) (x : Expression) =
match x with
| Exp(e) -> Some(Exp, e)
| Log(e) -> Some(Log, e)
| Sin(e) -> Some(Sin, e)
| Cos(e) -> Some(Cos, e)
| _ -> None
Again, I am afraid I can’t use this post to define the meaning of active patterns, banana clips (“(|” and “|)”), and options syntax (“Some” and “None”), there is a lot of information online, but you can think about the definitions above as something similar to regular expression matching: an expression “Add(e1, e2)” will be matched as “Op” (Add, e1, e2), and an expression “Exp(e)” is matched as “Func (Exp, e)”. We will see in a moment how this can become useful.
Now what’s left is just a definition of a derivative. Here it is:
let rec Derivative x : Expression =
match x with
| X -> Const(1.)
| Const(n) -> Const(0.)
| Neg(e) -> Neg(Derivative(e))
| Add(e1, e2) -> Add(Derivative(e1), Derivative(e2))
| Sub(e1, e2) -> Sub(Derivative(e1), Derivative(e2))
| Mul(e1, e2) -> Add(Mul(Derivative(e1), e2), Mul(e1, Derivative(e2)))
| Pow(e, Const(n)) -> Mul(Const(n), Pow(e, Const(n-1.)))
| Exp(X) -> Exp(X)
| Log(X) -> Div(Const(1.), X)
| Sin(X) -> Cos(X)
| Cos(X) -> Neg(Sin(X))
| Func(g, f) ->
let dg = Derivative(g(X))
let df = Derivative(f)
match dg with
| Func(dgf, dge) -> Mul(dgf(f), df)
| Op (op, e1, e2) -> Mul(op(e1, e2), df)
| _ -> failwith(sprintf "Unable to match compound function [%A]" dg)
| _ -> failwith(sprintf "Unable to match expression [%A]" x)
As you can see, it’s not an algorithm – it’s a description of what derivative is. You can also why we needed to introduce “Op” and “Func” active patterns: they are used in declaration of complex function derivative evaluation. Without these patterns we would need to list all supported operators and functions.
To test how this works, we can open a F# interactive window (FSI) and type a function to test:
> let d = Derivative(Sin(X));;
val d : Expression = Cos X
> let d = Derivative(Exp(Pow(X,Const(2.))));;
val d : Expression = Mul (Exp (Pow (X,Const 2.0)),Mul (Const 2.0,X))
That’s it! But while we are on symbolic calculations, we can improve the presentation part of it. Right now, if there is no attempt to simplify resulting expressions, so if we calculate a derivative of an expression corresponding to “5 * x + 3”, we will get a correct but silly looking answer:
> let d = Derivative(Add(Mul(Const(5.), X), Const(3.)));;
val d : Expression =
Add (Add (Mul (Const 0.0,X),Mul (Const 5.0,Const 1.0)),Const 0.0)
But if it was so simple to calculate derivatives in F#, it should not be difficult to write a function to simplify algebraic expressions. That will be in the next part.