June 2010 - Posts
It must be NDC that inspires test-driven songs. Last year it was We Can Mock It Out, this time it’s Mock Me Tender. Here we go…
Mock me tender,
Mock me sweet.
Time is to confess:
You have made my code complete -
Let us gently test.
Mock me tender,
Mock me true,
Make asserts fulfill.
For, my darling, I mock you,
And I always will.
Mock exceptions,
Mock success.
Mock me whole, my dear.
Don’t be shy, you’re always blessed -
You can TDD.
Mock me tender,
Mock me true,
Make my tests all pass.
For, my darling, I mock you,
And our mocks will last.
Habits can be
Hard to change,
And please don’t feel hurt:
You should always first arrange,
Act and then assert.
Mock me tender,
Mock me true,
Make asserts fulfill.
For, my darling, I mock you,
And I always will.
Of course the whole genre is inspired by Roy Osherove.
A couple of interesting posts for those who care about supporting multiple timezones:
Time zones, singletons, deployment options, names and source control by Jon Skeet.
iCalendar is wrong by Tony Finch.
NB! For some strange reason some sample code for this post was rejected by the server with “BLOCKED EXPRESSION” error. After several attempts to fix the problem, I converted code snippets to images. All three blog posts are combined now in an article that is published at CodeProject.
The first post about symbolic calcutaion in F# showed how to calculate derivatives, and the sequel demonstrated how the algebraic expressions can be simplified. Still, the most natural would be to write expressions in plain text, so the program could take an input like “sin(x ^ 2)” and generate an output “2 * x * cos(x ^ 2)”.
Let’s see how this can be approached with F#. We start with a formatter – formatting is usually easier than parsing. First we define a couple of helper functions to format operators and function names:
Then the rough implementation of the expression formatter does not take many lines of code:
There is only one problem with this code: it always surrounds algebraic operations with parenthesis, and this is only necessary in case the expression is contained in an outer expression. This is an example of redundant parenthesis:
It’s not complicated however to modify the original code, so it does not embrace top-level expressions with parenthesis:
Now we’re getting nice-looking output:
Satisfied with expression formatting, we can now proceed with expression parsing which appeared to be a more challenging tasks. First we need a tokenizer that would convert an input string into a list of tokens – atoms that will be building blocks of the resulting expression. Here is a simple tokenizer:
The tokenizer includes one rule that is specific for processing exponential functions (e ^ x). Unlike other functions (log, sin, cos), the exponent uses power operator notation, so adding proper support for it would devote large part of the post series just to this specific case. So I made a light constraint on use of exponent: its argument is always enclosed in parenthesis (so the input string should look like “e ^ (x)”, not “e ^ x”, and during the tokenization process the expression is converted into notation similar to other functions: e(x). So when proceeding with expression parsing, we won’t need to handle exponential functions in a special way.
Next step is to eleminate parenthesis and divide tokens into groups, each group representing a trivial expression construct. For example, an expression “(2 + x) * (5 - x) can be split into groups containing expressions “2 + x”, “5 – x” and the operator “*” binding them together. We achive this in a few steps: first by assigning each token a level (incremented with each opening parentheses and decremeneted with a closing parentheses), and then by putting contiguous tokens with the same level in a list. Here is the code that handles these operations and an example of its use:
We will also need some auxilliary functions: to test if a string represent an operator or a function, a couple of active pattern definitions to match numeric constants and variables, and methods to apply parsed operators or functions to expressions that they bind:
With supporting stuff in place, here’s the code that converts text input into expression trees:
Now it’s just to test how this all works:
So we’re done: we can now enter math expressions in plain text and obtain results of symbolic derivative calculation also in plain text. All in F#!
In the previous post we have shown an F# program that calculates derivatives. It has a room for improvement in its presentation part: resulting expressions often can be rewritten in a simpler form, and F# suits very well to solve such task.
We will be using the same set of expression primitives and active pattern helpers “Op” and “Func”:
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
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
Now we define a recursive function Simplify that converts an input of Expression type to an output of the same type attempting to rewrite an expression in a simpler form. Like with Derivative function, the definition is a list of rules rather than a sequential algorithm:
let rec Simplify x : Expression =
match x with
| Add(Const(n1), Const(n2)) -> Const(n1 + n2)
| Sub(Const(n1), Const(n2)) -> Const(n1 - n2)
| Mul(Const(n1), Const(n2)) -> Const(n1 * n2)
| Div(Const(n1), Const(n2)) -> Const(n1 / n2)
| Neg(Const(0.)) -> Const(0.)
| Neg(Neg(e)) -> e |> Simplify
| Add(e, Const(0.)) -> e |> Simplify
| Add(Const(0.), e) -> e |> Simplify
| Add(Const(n), e) -> Add(e, Const(n)) |> Simplify
| Add(e1, Neg(e2)) -> Sub(e1, e2) |> Simplify
| Add(Neg(e1), e2) -> Sub(e2, e1) |> Simplify
| Sub(e, Const(0.)) -> e |> Simplify
| Sub(Const(0.), e) -> Neg(e) |> Simplify
| Mul(e, Const(1.)) -> e |> Simplify
| Mul(Const(1.), e) -> e |> Simplify
| Mul(e, Const(0.)) -> Const(0.)
| Mul(Const(0.), e) -> Const(0.)
| Mul(e, Const(n)) -> Mul(Const(n), e) |> Simplify
| Mul(Div(Const(n), e1), e2) -> Mul(Const(n), Div(e2, e1)) |> Simplify
| Mul(e1, Div(Const(n), e2)) -> Mul(Const(n), Div(e1, e2)) |> Simplify
| Mul(Neg(e1), e2) -> Neg(Mul(e1, e2)) |> Simplify
| Mul(e1, Neg(e2)) -> Neg(Mul(e1, e2)) |> Simplify
| Div(Const(0.), e) -> Const(0.)
| Div(e, Const(1.)) -> e |> Simplify
| Div(Neg(e1), e2) -> Neg(Div(e1, e2)) |> Simplify
| Div(e1, Neg(e2)) -> Neg(Div(e1, e2)) |> Simplify
| Pow(Const(0.), e) -> Const(0.)
| Pow(Const(1.), e) -> Const(1.)
| Pow(e, Const(0.)) -> Const(1.)
| Pow(e, Const(1.)) -> e |> Simplify
| Op (op, e1, e2)
->
let e1s = Simplify e1
let e2s = Simplify e2
if e1s <> e1 || e2s <> e2 then
op(Simplify e1, Simplify e2) |> Simplify
else
op(e1, e2)
| _ -> x
The set of rules is not complete. For example, there is no rule to rewrite “2 * (3 + X)” as “6 + 2*X”, but it should be enough to eliminate most obvious redundancies, such as multiplication by one and zero addition. So if we can fire F# interactive window, we can test how it works:
> let s = Simplify(Add(Mul(Const 0., X), Mul(Const 5., Const 1.)));;
val s : Expression = Const 5.0
What we can do now is extend the Derivative function written in the previous post, so it can take advantage of our new Simplify function:
let rec Derivative x : Expression =
let y =
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)
Simplify y
Now let's test what we have by calculating derivative for various functions:
> let d1 = Derivative(Add(Mul(Const(5.), X), Const(3.)))
let d2 = Derivative(Add(Pow(X, Const(3.)), Const(3.)))
let d3 = Derivative(Sin(Mul(Const(2.), X)))
let d4 = Derivative(Log(Mul(Const(2.), X)))
let d5 = Derivative(Exp(Mul(Const(2.), X)))
let d6 = Derivative(Exp(Pow(X, Const(2.))))
let d7 = Derivative(Log(Sin(X)))
let d8 = Derivative(Log(Cos(X)));;
>
val d1 : Expression = Const 5.0
val d2 : Expression = Mul (Const 3.0,Pow (X,Const 2.0))
val d3 : Expression = Mul (Const 2.0,Cos (Mul (Const 2.0,X)))
val d4 : Expression = Div (Const 2.0,X)
val d5 : Expression = Mul (Const 2.0,Exp (Mul (Const 2.0,X)))
val d6 : Expression = Mul (Exp (Pow (X,Const 2.0)),Mul (Const 2.0,X))
val d7 : Expression = Div (Cos X,X)
val d8 : Expression = Neg (Div (Sin X,X))
Can we improve anything? Well, maybe… Since it’s getting so easy, why not set an ultimate goal: present input and output as a plain text, not as Expression items. So we can pass “log(cos(x))” and get back “-sin(x)/x”. I guess this will be slightly more work to achieve, but should be fun once we get there. In the next part.
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.