Vagif Abilov's blog on .NET : functional programming

Symbolic calculation in F#. Part 3: parsing and formatting expressions

Vagif Abilov — Fri, 11 Jun 2010 08:24:00 GMT

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#!

Symbolic calculation in F#. Part 2: simplifying algebraic expressions

Vagif Abilov — Tue, 08 Jun 2010 19:54:55 GMT

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.

Symbolic calculation in F#. Part 1: derivatives

Vagif Abilov — Tue, 08 Jun 2010 18:59:51 GMT

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.

Time to buy ReSharper?

Vagif Abilov — Tue, 19 Jan 2010 14:32:20 GMT

Today I spent a few hours on mysterious error. One automated test failed, and since it was actually an integration test with complex setup, tracking down the failure was not easy. The problem that I’ve eventually found can be illustrated with a couple of tests:

[Test]
public void BadClosureTest()
{
    int[] numbers = new int[]
    {
        1, 2, 3
    };

    List> functions = new List>();
    foreach (int n in numbers)
    {
        functions.Add(new Func(() => n));
    }

    // Will fail on first assertion!
    Assert.That(functions[0].DynamicInvoke(), Is.EqualTo(1));
    Assert.That(functions[1].DynamicInvoke(), Is.EqualTo(2));
    Assert.That(functions[2].DynamicInvoke(), Is.EqualTo(3));
}

[Test]
public void GoodClosureTest()
{
    int[] numbers = new int[]
    {
        1, 2, 3
    };

    List> functions = new List>();
    foreach (int n in numbers)
    {
        int m = n;
        functions.Add(new Func(() => m));
    }

    Assert.That(functions[0].DynamicInvoke(), Is.EqualTo(1));
    Assert.That(functions[1].DynamicInvoke(), Is.EqualTo(2));
    Assert.That(functions[2].DynamicInvoke(), Is.EqualTo(3));
}

As you can see, the only difference between these tests is a line in the second test assigning iterator “n” to a variable “m” defined within the “foreach” scope. Why does this matter?

Well, for us, procedural languages veterans the difference may be not so obvious at first glance. But if you happen to have ReSharper, it will immediately give you a warning about the first test: “Access to modified closure”. And will suggest to copy “n” to a local variable. I didn’t have ReSharper, so I came to the same conclusion in a hard way.

A lambda-expression “() => n” is not just a delegate – it’s a closure. It uses a variable that is defined outside its scope. Such variables are always treated by reference, even though they may be of a value type. So as long as the variable “n” lives, any changes applied to it will affect every closure where it is referenced.

And apparently ReSharper can warn us about improper use of closures.

By the way, if instead of “foreach” test had a “for” loop with an index, the first test would fail with IndexOutOfRangeException. Because closures were accessed after the array elements are iterated and index would be set to 3.

Expression tree serialization

Vagif Abilov — Thu, 29 Oct 2009 20:16:30 GMT

Serializing lambda expressions using MetaLinq, by Onur Gumus.

Remoting lambda expressions, by Casey Marshall.

Expression tree serialization project.

Functional programming for C# developers

Vagif Abilov — Mon, 12 Oct 2009 21:23:35 GMT

Latest Jeremy Miller’s article in MSDN Magazine will be very helpful for C# developers who haven’t started yet exploring functional programming. What is good about this article is that it gives practical advices on how to inject some fairly small pieces of functional programming into existing C# code in order to make it better – for example by removing code duplicates.

What seems to be radical for many C# developers is how functional programming handles blocks of code with variables that are not resolved within those blocks – closures. A piece of code with variables defined somewhere else is traditionally viewed by programmers with background in procedural languages as an invalid construction that will cause a compiler error. But closures are fully supported now in C# (in form of anonymous delegates or lambda-expressions), and Jeremy’s article demonstrates advantages of using this technique to pass around code blocks as data.

I think however that the example with ConnectedSystemConsumer could be presented somewhat simpler, without focus on Interface Segregation Principle. Here’s how the original class looks before refactoring:

class ConnectedSystemConsumer
{
    private readonly IConnectedResource _resource;

    public ConnectedSystemConsumer(IConnectedResource resource)
    {
        _resource = resource;
    }

    public void ManipulateConnectedResource()
    {
        try
        {
            // First, you have to open a connection
            _resource.Open();
            // Now, manipulate the connected system
            _resource.Update(buildUpdateMessage());
        }
        finally
        {
            _resource.Close();
        }
    }

    // The rest of the class is skipped
}

The article then introduces two new interfaces and one class: IResourceInvocation, IResource and Resource, where IResourceInvocation contains the “interesting” part of IConnectedResource (methods FetchData and Update) and IResource defines and Resource implements a single method Invoke that takes care of all ceremony stuff. While this helps splitting the original ConnectedSystemConsumer class into smaller logical blocks, for developer doing his first experiments with functional programming it may leave false impression that adding additional classes are required (or at least expected) steps to take advantage of functional programming in C# code. But the same effect can be achieved without adding new interfaces or classes, just by extracting all ceremony code in a separate method:

class ConnectedSystemConsumer
{
    private readonly IConnectedResource _resource;

    public ConnectedSystemConsumer(IConnectedResource resource)
    {
        _resource = resource;
    }

    public void ManipulateConnectedResource()
    {
        InvokeResource(x =>
        {
            x.Update(buildUpdateMessage());
        });
    }

    private void InvokeResource(Action<IConnectedResource> action)
    {
        try
        {
            // First, you have to open a connection
            _resource.Open();
            // Now, manipulate the connected system
            action(_resource);
        }
        finally
        {
            _resource.Close();
        }
    }

    // The rest of the class is skipped
}

As you can see, ManipulateConnectedResource no longer contains ceremonial code that opens and closes resource and handles exceptions. This code is now moved to InvokeResource method that takes as an argument a block or a closure defined in ManipulateConnectedResource or any other method that requires the same ceremony.

After reading Jeremy Miller’s article I browsed some of my old code and found several classes that can be simplified using the same approach. Perhaps at first they will not look simpler – functional programming style adoption requires some time. But they will become more compact, with less or without code repetition, and this alone is worth it.