Vagif Abilov's blog on .NET : F#

Mock framework challenges in F#

Vagif Abilov — Wed, 04 Aug 2010 16:30:43 GMT

Getting mock framework API rigth is uneasy task. Mock framework designers don’t have as much freedom as designers of other libraries: the purpose of a mock framework is not to expose an arbitraty API (unknown at the time of mock framework design) and intercept it in a transarent way, so developers can use mocked object as they were using real instances.

This is why API of modern mock frameworks is full of technique such as extension methods and lambda expressions. In addition these frameworks use so called fluent approach to API. Unfortunately such methods are not easily portable to other, especially non-imperative languages. Being fluent in one language does not mean fluent in the other one.

I decided to try various mock frameworks with F#. I realized that their C#-friendly syntax will look in F# clumsy, but I coudl overcome it by writing small wrappers. What concerned me more is incomatibility of F# functional delegates and expressions comparing to C#. For my tests I’ve chosen a Zoo example listed in an excellent series of blog posts by Richard Banks dedicated to mock framework comparison. Richard ran his comparison on free frameworks:

Rhino.Mocks
NSubstitute
Moq

I’ve extended this set with two commercial products:

Typemock Isolator
Telerick JustMock

So far I only tried very basic mocking described in the first post of Richard’s series: faking return value. As I expected, even such a simple operation became a challenge when executed from F# code. I managed to make tests work only for two and half frameworks. Below is a description of what I did and how it was possible to have half of success.

1. Rhino.Mocks: success

Rhino.Mocks is the most popular .NET mock framework. This was the test code that I wanted to port to F#:

[Test]
public void Return()
{
    var monkey = MockRepository.GenerateMock<IMonkey>();
    monkey.Stub(m => m.Name).Return("Spike");

    var actual = monkey.Name;

    Assert.AreEqual("Spike", actual);
}

As you can see, “monkey” is used both as an instance of an object that implements IMoney interface (so we can call money.Name directly) and as an object exposing mocking API (so we can call a Stub method on it). This is achieved by using extension methods, and extension methods are language specific – being defined in C# code they are not available in F# as extensions. But they can be used from a static class where they are originally defined:

[<Test>]
member this.Return() =
    let monkey = MockRepository.GenerateMock<IMonkey>()
    RhinoMocksExtensions.Stub<IMonkey, string>(monkey, fun m -> m.Name).Return("Spike");

    monkey.Name
    |> should equal "Spike"

The test works, but RhinoMocksExtensions class has not been meant to be exposed to general public, so I put it in a little wrapper:

module FsMock.RhinoMocks

open Rhino.Mocks

type mock<'T when 'T : not struct>() =

    let instance = MockRepository.GenerateMock<'T>()

    member this.Object = instance

module Mock =

    let arrange<'T, 'R when 'T : not struct> (f : ('T -> 'R)) (r : 'R) (m : mock<'T>) = 
        RhinoMocksExtensions.Stub<'T, 'R>(m.Object, Function<'T, 'R>(f)).Return(r)

Now I can rewrite the origianl test in a F# style:

[<Test>]
member this.Return() =
    let monkey = mock<IMonkey>()
    monkey
    |> Mock.arrange (fun m -> m.Name) "Spike"
    let monkey = monkey.Object

    monkey.Name
    |> should equal "Spike"

Both the original and rewritten tests passed.

2. NSubstitute: success

NSubstitute is a new kid on the block. The framework prioritizes simplicity over coverage of all possible mocking scenarios. Unlike other frameworks, NSubstitutes avoids using lambda expressions. This makes it easier to use in F#.

Here’s the C# code using NSubstitute:

[Test]
public void Return()
{
    var monkey = Substitute.For<IMonkey>();
    monkey.Name.Returns("Spike");

    var actual = monkey.Name;

    Assert.AreEqual("Spike", actual);
}

Like Rhino.Mocks, NSubstitute also uses extension methods, so porting the above test to F# results in the following code:

[<Test>]
member this.Return() =
    let monkey = Substitute.For<IMonkey>()
    SubstituteExtensions.Returns(monkey.Name, "Spike")

    monkey.Name
    |> should equal "Spike"

Again, I created a little helper to make syntax F# friendly:

module FsMock.NSubstitute

open NSubstitute

type mock<'T when 'T : not struct>() =

    let instance = Substitute.For<'T>()

    member this.Object = instance


module Mock =

    let arrange<'T, 'R when 'T : not struct> (f : ('T -> 'R)) (r : 'R) (m : mock<'T>) = 
        SubstituteExtensions.Returns<'R>(f(m.Object), r)

Now the test code looks identical to Rhino.Mocks example:

[<Test>]
member this.Return() =
    let monkey = mock<IMonkey>()
    monkey
    |> Mock.arrange (fun m -> m.Name) "Spike"
    let monkey = monkey.Object

    monkey.Name
    |> should equal "Spike"

And the test passed!

NB! I have deliberately unified mocking API when creating F# wrappers for different frameworks. Since F# API will be quite different from it’s C# counterpart, I didn’t want to multiply number of API sets. Instead I came up with a common and easy to understand set of names (“mock”, “arrange”) that is used in each wrapper.

3. Moq: half success

Now that sounds strange. A test should either succeed of fail. So what has happenned to Moq? Here’s the story.

Moq is a second most popular framework after Rhino.Mocks, and it has pioneered act-arrange-assert API based on lambda-expressions. This is how the C# test looks when using Moq:

[Test]
public void Return()
{
    var monkey = new Mock<IMonkey>();
    monkey.Setup(m => m.Name).Returns("Spike");

    var actual = monkey.Object.Name;

    Assert.AreEqual("Spike", actual);
}

Although the expression “m => m.Name” looks exactly like in Rhino.Mocks, there is a big difference behind. Rhino.Mocks uses Func<T> delegate, and Moq is based on LINQ expressions. Working with such expressions in F# requires use of so called quotation expressions that should be converted to LINQ and then downcasted to a generic LINQ expression. The corresponding code looks quite criptic:

[<Test>]
member this.Return() =
    let monkey = new Mock<IMonkey>()
    let expr = (<@@ System.Func<IMonkey, string>(fun (m : IMonkey) -> m.Name) @@>).ToLinq()
    monkey.Setup(expr :?> System.Linq.Expressions.Expression<System.Func<IMonkey, string>>).Returns("Spike");
    let monkey = monkey.Object

    monkey.Name
    |> should equal "Spike"

But this does not work. Here’s the output:

Test 'MoqTests+MoqTests.Return' failed: System.NullReferenceException : Object reference not set to an instance of an object.
	at Moq.MethodCall.SetFileInfo()
	at Moq.MethodCall..ctor(Mock mock, Expression originalExpression, MethodInfo method, Expression[] arguments)
	at Moq.MethodCallReturn..ctor(Mock mock, Expression originalExpression, MethodInfo method, Expression[] arguments)
	at Moq.MethodCallReturn`2..ctor(Mock mock, Expression originalExpression, MethodInfo method, Expression[] arguments)
	at Moq.Mock.<>c__DisplayClass15`2.b__14()
	at Moq.PexProtector.Invoke[T](Func`1 function)
	at Moq.Mock.SetupGet[T1,TProperty](Mock mock, Expression`1 expression)
	at Moq.Mock.<>c__DisplayClass12`2.b__11()
	at Moq.PexProtector.Invoke[T](Func`1 function)
	at Moq.Mock.Setup[T1,TResult](Mock mock, Expression`1 expression)
	at Moq.Mock`1.Setup[TResult](Expression`1 expression)
	C:\Projects\NET\MockComparison\TempTests\MoqTests.fs(20,0): at MoqTests.MoqTests.Return()

So why half success then? Well, if I execute the same code from F# interactive window, it works!

> let monkey = new Mock<IMonkey>()
let expr = (<@@ System.Func<IMonkey, string>(fun (m : IMonkey) -> m.Name) @@>).ToLinq()
monkey.Setup(expr :?> System.Linq.Expressions.Expression<System.Func<IMonkey, string>>).Returns("Spike");
printfn "%s" monkey.Object.Name;;
Spike

val monkey : Mock<IMonkey>
val expr : Expression = m => m.Name

Note the word “Spike” printed right after the line that begins with “printfn”. This is the output.

So I don’t really have a clue why the same code works in F# interactive session but fails being compiled in an assembly. I may need to investigate some more.

4. Typemock Isolator: failure

Ironically, both commercial frameworks failed to be used with F#. The C# code that used to test Typemock Isolator looks like this:

[Test]
public void Return()
{
    var monkey = Isolate.Fake.Instance<IMonkey>();
    Func<string> func = () => monkey.Name;
    Isolate.WhenCalled(func).WillReturn("Spike");

    var actual = monkey.Name;

    Assert.AreEqual("Spike", actual);
}

Here's the corresponding F# code:

[<Test>]
member this.Return() =
    let monkey = Isolate.Fake.Instance<IMonkey>();
    Isolate.WhenCalled(System.Func<string>(fun ignore -> monkey.Name)).WillReturn("Spike");

    monkey.Name
    |> should equal "Spike"

This test fails with the following output:

Test 'TypeMockTests+TypeMocksTests.Return' failed: TypeMock.TypeMockException : 

*** Cannot call Isolate.WhenCalled() with method group fake.Invoke. Try using Isolate.WhenCalled( () => fake.Invoke()) instead
	at ec.a()
	at dm.b(Boolean A_0)
	at im.c(Boolean A_0)
	at im.a(Object A_0, Boolean A_1, Func`1 A_2, Action A_3, Action A_4, Action A_5)
	at im.c(Object A_0)
	at TypeMock.ArrangeActAssert.ExpectationEngine`1.a(TResult A_0)
	C:\Projects\NET\MockComparison\TempTests\TypeMockTests.fs(21,0): at TypeMockTests.TypeMocksTests.Return()

I described the problem to Typemock developers and was advised to try a different approach presented by Roy Osherove in his blog post. Unfortunately the modified test still fails, although with a different exception.

5. JustMock: failure

JustMock is also a commercial product, and it’s API also lacked F# compatibility. This is the original C# code:

[Test]
public void Return()
{
    var monkey = Mock.Create<IMonkey>();
    Mock.Arrange(() => monkey.Name).Returns("Spike");

    var actual = monkey.Name;

    Assert.AreEqual("Spike", actual);
}

JustMock also uses LINQ expressions, so I had to use a similar trick to what I had to do with Moq:

[<Test>]
member this.Return() =
    let monkey = Mock.Create<IMonkey>();
    let expr = (<@@ System.Func<string>(fun ignore -> monkey.Name) @@>).ToLinq()
    Mock.Arrange<string>(expr :?> System.Linq.Expressions.Expression<System.Func<string>>).Returns("Spike");

    monkey.Name
    |> should equal "Spike"

The code compiles and does not throw any expection during the execution. But the “Name” property is not set, so “should equal” assertion fails.

Conclusion: no offence, just exploring possibilities

One thing that I want to get straigh is that these tests say absolutely nothing about general design quality of respective mock frameworks. As I mentioned in the beginning, API design requirements of such frameworks require their developers to apply language-specific tricks to make mocking simple. So the fact that some API fits another programming language is more luck rather than conscious vision. Moreover, I only tried the simplest of a large variety of functions exposed by mock frameworks. A slightly more complicated scenario would fail all frameworks, I am sure.

However, since more developers express interests in F# and start using it in their projects, I believe it’s time for mock frameworks developers to consider this new territory and extend their products to offer full suport for this exciting language.

Exploring Amazon S3 with F#

Vagif Abilov — Thu, 15 Jul 2010 20:51:54 GMT

Introduction

Traditional imperative languages teach developers that program code requires ceremony. You can’t just write a line and expect it to do something. When programming book writers explain how easy is it to display "Hello world" string in their favorite language, they actually start with an explanation that every call should be wrapped in a method, and the method typically takes some arguments etc. And of course they have to let beginners know how to compile the resulting program and how to execute it. Without all these steps the world won’t get its greeting.

All these steps have valid reasons, but as a result development environment based on major imperative languages does not really encourage exploration. It’s best suited towards large scale development, but if a developer wants to have a quick look on something new, and he can’t proceed without creating a new project, then he will often postpone this work until he has enough time or enough reasons to go ahead.

Luckily, there’ve always been alternatives to languages like C# or Java that worked better for rapid prototyping or technology exploration. One of the late additions is F#, and when I recently introduced myself to Amazon Simple Storage Service, I realized that if I need to get a quick overview of its programming facilities, using F# would be much more efficient than if write a test program in C#.

The purpose of this article is to show how fast you can dig into low level details of an unknown technology using F#, and how little code you need to write. Therefore I keep the text of the article short, focusing just on the required steps. If you need more information about F# or Amazon S3, there’s plenty of books and articles available. Just google for them. Instead of numbering steps that I’ve gone through, I’ll provide timing information: I started the exercise at about 17:00 CET on July 15th. It took me about 45 minutes to display a picture extracted from my S3 bucket. And all code was written in F#.

17:00. Getting Amazon Web Services SDK

Amazon Web Services SDK, also known as AWS SDK is available at http://aws.amazon.com/sdkfornet. Once downloaded, it’s installer copies binaries and samples, and optionally registers AWSSDK.dll in the GAC.

17:10. You can’t go wrong with Reflector

Before firing a Visual Studio F# session, I checked the content of the installed binaries and loaded into Red Gate .NET Reflector the only .NET assembly that I found: AWSSDK.dll. I could probably manage without it, but it would take longer time. After I created an S3 client session, I mostly relied on Intellisense support for F# in Visual Studio, but spending few minutes looking at namespaces and classes hinted me about entry points. For example, I assumed that I would need to create an instance of AmazonS3Client and probably use classes from Amazon.S3.Model.

17:15. Opening F# Interactive session

I started Visual Studio and immediately was able to use comparative advantage of F# environment. I didn’t have to create a project – in fact I didn’t know what kind of project I would need to create if I had to: should be a console application? Or maybe a Windows Form program? I didn’t know yet what to expect, all I wanted to get from an IDE is a notepad where I could write code lines and execute them one by one. So F# was a very good fit for my intention: I created a new F# script file and started sending individual lines to an FSI window. The first lines referenced AWSSDK and imported Amazon.S3 namespace that I expected to be useful (thanks Reflector):

#r "AWSSDK"
open Amazon.S3

Later I imported another namespace (Amazon.S3.Model), but these two lines above were enough to connect to Amazon S3 storage.

17:20. Connecting to Amazon S3 and accessing a bucket

The fun part began. My guess was that since AmazonS3Client class has a constructor with two string parameters, this is the one I should use and assign parameters to AWS key ID and secret key. F# Intellisense confirmed it. So here’s my first call to Amazon S3 in F# (I removed actual access key values).

let s3Client = new AmazonS3Client("KEY-ID", "SECRET-KEY")

After a few seconds F# Interactive came with a response:

val s3Client : AmazonS3Client

Now I had a mighty client with many interesting methods to try. The next logical step would be to list available buckets. I had only one, so I could retrieve only the first element of the list.

let response = s3Client.ListBuckets()
response.Buckets

Here’s an FSI output:

val it : System.Collections.Generic.List =
  seq
    [Amazon.S3.Model.S3Bucket {BucketName = "abilov.com";
                               CreationDate = "to, 15 jul 2010 10:17:18 GMT";}]

Great! This looked like a real thing. Encouraged with a quick success, I wanted to start retrieving the bucket contents.

17:25. Failed attempt to retrieve bucket objects

The bucket collection was wrapped in a sequence, so I only needed to get it’s head to obtain the only bucket I had at S3:

let bucket = Seq.head response.Buckets

I thought in order to retrieve bucket objects, I had to send the obtained bucket to some method, but I was wrong. Actually I didn’t need to obtain a bucket at all – since I knew the name of the bucket, I could construct a ListObjectRequest from the name and send it to a ListObjects. But I didn’t know about it 5 minutes ago. Anyway, here’re new calls, to retrieve bucket objects – data files with images from our home photo gallery.

let request = new ListObjectsRequest(BucketName = bucket.BucketName)
let objects = s3Client.ListObjects(request)

Bang!!! Exception!

System.Net.WebException: The underlying connection was closed: Could not establish trust relationship for the SSL/TLS secure channel.
---> System.Security.Authentication.AuthenticationException: The remote certificate is invalid according to the validation procedure.
   at System.Net.Security.SslState.StartSendAuthResetSignal(ProtocolToken message, AsyncProtocolRequest asyncRequest, Exception exception)
   at System.Net.Security.SslState.CheckCompletionBeforeNextReceive(ProtocolToken message, AsyncProtocolRequest asyncRequest)
   at System.Net.Security.SslState.StartSendBlob(Byte[] incoming, Int32 count, AsyncProtocolRequest asyncRequest)
   at System.Net.Security.SslState.ProcessReceivedBlob(Byte[] buffer, Int32 count, AsyncProtocolRequest asyncRequest)
   at System.Net.Security.SslState.StartReadFrame(Byte[] buffer, Int32 readBytes, AsyncProtocolRequest asyncRequest)

(The rest of the call stack is skipped)

Now when I am writing this article, I am in fact glad that I had this problem. If everything went smooth, you might look at my timing information with a grain of disbelief: the guy probably knew what he was doing. No I didn’t! So I had to check around. Since the error came after so basic steps, I hoped that I wasn’t alone who experienced it, and luckily I was not. Several people complained at Amazon forum, and they were recommended a simple workaround in case they would accept using HTTP instead of HTTPS. And for the purpose of exploration it was just fine.

17:30. Connection to Amazon S3 revisited

Here’s an updated version of connection code, taking now two lines instead of one.

let s3Config = new AmazonS3Config(CommunicationProtocol = Protocol.HTTP)
let s3Client = new AmazonS3Client("KEY-ID", "SECRET-KEY", s3Config)

Then I replayed the other two lines requesting bucket objects. And now I successfully received results:

    {AmazonId2 = "//VkK6Mb7Xe26pNPG7nt40GkYcp4GDyNV45I1E1mfZVCL67aak9/0Txmrk8X+JAE";
     CommonPrefix = seq [];
     CommonPrefixes = seq [];
     Delimiter = null;
     Headers = seq
                 ["x-amz-id-2"; "x-amz-request-id"; "Transfer-Encoding";
                  "Content-Type"; ...];
     IsTruncated = true;
     MaxKeys = "1000";
     Metadata = seq [];
     Name = "abilov.com";
     NextMarker = "private/photo/2005/2005-06-10-12 Elverum/IMG_6803.JPG";
     Prefix = "";
     RequestId = "3A27D1A4495A747A";
     ResponseStream = null;
     S3Objects = seq {…}

     (The rest of results is skipped)

17:35. Retrieving object data

I inspected the response and found the property that I needed: S3Objects. It was a collection of bucket objects representing the photo gallery files I uploaded to S3. Taking a further look at available AmazonS3Client methods I’ve found a method that I should use to retrieve an individual object: GetObject. It took an instance of GetObjectRequest. I first created a GetObjectRequest instance without assigning a Key property. But after receiving exception with error message about missing a key I corrected my mistake. Here’s a code that worked:

let objectRequest = new GetObjectRequest(BucketName=bucket.BucketName, Key="private/photo/2005/2005-01 Kolbotn/IMG_5645.JPG")
let obj = s3Client.GetObject(objectRequest)

The "Key" property is just a file path within the bucket, so it’s easy to figure it out.

I sent "obj" to an FSI window, and it printed it’s properties:

{AmazonId2 = "zUH8IaRglPSPQuC+8m5pzAR59paJTi/L5M1DnxNympp9HcU5RigrntS7NGvpxQQf";
     ContentLength = 1138630L;
     ContentType = "image/jpeg";
     ETag = ""ea02192ee842d3b1987a8de4ac879595"";
     Headers = ?;
     Metadata = seq ["x-amz-meta-cb-modifiedtime"];
     RequestId = "A93CF70A966E4A56";
     ResponseStream = System.Net.ConnectStream;
     ResponseXml = null;
     VersionId = null;}

One of the properties was called ReponseStream. This sounded very promising – perhaps I could try to create an image out of this stream and display it in a Windows Form?

17:40. Displaying an image

What should you do if you want to display an image in a Windows Form in C#? You have to start from creating a new project using Windows Forms Application template. Then you can edit form class and add an Image control to it in a Form designer. How do you do it in F#? You simply create a form with an image right from the script. Here’s the code:

#r "System.Drawing"
#r "System.Windows.Forms"
 
open System.Windows.Forms
open System.Drawing

let img = Image.FromStream(obj.ResponseStream)
let frm = new Form(ClientSize = img.Size)
frm.Paint.Add(fun e -> e.Graphics.DrawImage(img, new Point(0,0)))
frm.Show()

Note that first four lines are just to reference required DLLs and import namespaces. The rest of the code is equally short and complete the task. Look at the Image.FromStream call: I wasn’t quite sure I could do this, but the property name "ResponseStream" was too tempting not to give it a try. And suddenly I saw this window:

This is our house cat Figaro (unfortunately not with us anymore). And no, I didn’t specifically select this photo for my test. This was a random choice, perhaps hinting about what kind of pictures some families tend to take.

17:45. Done!

Yes, we are! Perhaps just to show my environmentalist attitude, I’ll make one last call:

s3Client.Dispose()

Conclusion

So it was three quarters of exploration. Completely new API, combined with my relatively poor experience with Amazon S3, but a picture from a family photo gallery retrieved from an S3 bucket and shown in a Windows form proves that we managed the full stack of operations. All done in F#. This experiment does not expose other (and far more important) language qualities, but I deliberately wanted to focus on a different topic: language efficiency for the purpose of technology exploration and rapid prototyping. Being .NET language, F# can access any .NET area or feature, and its REPL support ensures that developer’s time is spent in a most optimal way.

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.