Forty Six and Two

API design: Record types and backwards compatibility

2012-01-04T01:46:00.000Z

If you’re designing an API in F#, be very careful when exposing any of the public types as record types. Record types, as they stand in F# 2.0, by default are impossible to change while keeping backwards binary compatibility.

Let’s look at a couple of changes that you might want to make to a record type:

Adding a new field.
Changing the type of a field.
Changing the order of the fields.

None of these changes are backwards compatible. A record type is compiled by F# to a normal .NET class, with a constructor that takes the fields as arguments. This means order of the fields matters, and also the number and types of fields of course. Accessing the record fields is accomplished through a getter for each of the fields. So if your clients are using a very limited usage pattern – basically only accessing an existing record type using a getter – you may be alright with 1 and 3, and even 2 if they don’t happen to access the particular field whose type you’re changing. Anything else, including with syntax, is a no-no.

To make this abundantly clear – a record type definition and usage:

type MyRecord =
    { Field : int
      SecondField : string }

let instance = { Field = 3; SecondField = "3" }

Is translated by the F# compiler to:

type MyRecordTranslated(field:int,secondfield:string) =
    member this.Field = field
    member this.SecondField = secondfield

let instanceTranslated = new MyRecordTranslated(3,"3")

Now in the translated case, it’s intuitively clear that changing the order of the arguments in the constructor is not backwards compatible. With the record syntax however, the F# syntax makes the record type look like a bag of fields. However, the compiler looks up the one and only constructor for the type, and explicitly calls that. So, if you change the constructor in any way, clients are going to fail at runtime if they are not recompiled first.

Two solutions (sort of)

The first solution is not to use record types as part of a public API that needs to be backwards compatible – use class types instead.

If record types are still handy, say because they have automatic value-based comparison and equality, then with some planning you can still use them – but to your clients they won’t look much like record types anymore, because we’re going to prevent clients from accessing the constructor and getters (unfortunately there’s no way to set accessibility on those two separately). And there is a lot of tedious code involved. Here’s an example – here’s the first version of a “record type” that can be kept backwards compatible:

module A_v0 =
    type MyRecord =
        internal { _Field : int } with
        static member Create(field:int) = { _Field = field }
        member this.Field = this._Field
        member this.With(?Field:int) = { this with _Field = defaultArg Field this.Field }

Note that the most important change is that we made the constructor internal (private does not make much sense, as everything in the assembly of the record type itself should be trivial to update in concert with any change to the record type). To create the record type from outside of the assembly there is the factory method ‘Create’. Note that using F# method call syntax, we can still make this look much like a record type: ‘MyRecord.Create(field=3)’ for example.

Then we need to provide a getter for each field ourselves (because we’ve made them internal...). I’ve chosen to start the actual field names with an underscore above, just to allow the explicit getters.

Finally, using optional fields, we can regain some sort of with syntax. Here’s an example of usage:

let a = A_v0.MyRecord.Create(2).With(Field = 3).Field

Now, suppose we want to add a new field. We can do that as follows, without breaking any clients:

module A_v1 =
    type MyRecord =
        internal { _Field : int 
                   _Foo   : string } with
        static member Create(field:int) = { _Field = field; _Foo = "default" }
        static member Create(field:int,foo:string) = { _Field = field; _Foo = foo }
        member this.Field = this._Field
        member this.Foo = this._Foo
        member this.With(?Field:int) = { this with _Field = defaultArg Field this.Field }                                   
        member this.With(?Field:int,?Foo:string) = { this with _Field = defaultArg Field this.Field
                                                               _Foo = defaultArg Foo this.Foo }

Note how we can now use overloading of both Create and With to our advantage.

In this way, we prevent clients from using the record constructor directly, but pay the cost of re-implementing most of the useful functionality for record types ourselves. It’s not much less work than basically doing the same with a class type.

Can F# v_next solve this?

The problem is that the syntax is deceiving: it looks like the order of arguments does not matter – both in the definition syntax, and in construction syntax. Also, if you use ‘with’ it looks like the call is resilient to adding a new field. And in fact, it is as long as you recompile – which makes the problem worse in some sense as a programmer will see her intuitions confirmed with every compilation.

Given that the syntax is pretty much set in stone at this point, I don’t see a good way around it. If you want to keep the illusion of order-independence of the fields, one thing to do is make the compiler generate some kind of discovery phase at runtime, which would incur an unreasonable performance cost. Another approach would be to have Set method per field that returns a new record instance, and make the constructor private – but then setting many fields would involve as many object creations – again unreasonable for performance reasons.

In fact, I don’t think this is such a big problem at all, as 95% of users will probably not encounter it, and for them the abstraction is valid. What v next could address though, is a way for the other 5% to control backwards compatibility of record types better.

A first idea would be to allow the declaration of “optional fields”, and compile those as overloaded constructors – say you could write:

type MyRecord =
    { Field : int
      SecondField : string
      ?OptionalField = 5 }

which would be compiled to:

type MyRecordTranslated(field:int,secondfield:string, optionalField:int) =
        new(field:int,secondfield:string) = MyRecordTranslated(field,secondfield, 5)
        member this.Field = field
        member this.SecondField = secondfield
        member this.OptionalField = optionalField

I.e. make an overloaded constructor per optional field, and the F# compiler can enforce that optional fields should always be last in the definition. This shouldn’t be too much of a surprise, as the same restriction holds for optional arguments, and also helps somewhat to counter the wrong intuition that order of record fields does not matter. This would at least allow people to add new optional fields without breaking backwards compatibility.

Another option is to explicitly allow overloaded constructors – similar to the implicit class definition syntax, it could be enforced that all the overloads call into the same constructor. Syntax may be a bit of a pain, but I’m sure something can be worked out.

Finally, it would be good to be able to control the visibility of the constructor and the getters separately. In fact it would be nice for other reasons too to control accessibility of the getter for each field separately anyway. internal/private could be allowed in front of the field definitions to control visibility of the getter, while the visibility in front of the curly brace, as now, would only influence visibility of the constructor.

In retrospect, I think there’s something to be said for having the compiler emit a warning or even error when constructing a record type with the fields in a different order from the record type definition, if only to counter the wrong intuition.

I believe the best option here is the second one, allowing overloaded constructors. 3 and 4 are not backwards compatible as far as the F# compiler is concerned, and although the optional fields are nice, this is probably best left as some syntactic sugar over real overloaded constructors as the latter are more flexible.

Conclusion

Binary compatibility may not be a big issue for you. It’s certainly not an issue if you don’t expose any programmatic API as part of your F# projects. In that case, live happily ever after.

On the other hand, you may want to think about giving yourself some flexibility in keeping your API backwards compatible. In that case, hopefully this post has given you some tools to come up with an appropriate strategy. Note that if you can reasonably expect that your clients will recompile whenever you release a new version, the whole problem is moot too.

Overall many F# programmers don’t need to consider this at all. However it deserves a bit more attention than it’s getting, and might catch some people unaware (it certainly caught me out at some point...).

Share this post :

FsCheck 0.7.1: NuGet packaging

2011-05-29T21:32:00.000+01:00

I’ve released a minor update to FsCheck, mostly so it can now be downloaded as a NuGet package. It also comes with source server support, courtesy of SymbolSource.org.

Furthermore, there are a couple of bug fixes.

Enjoy.

Technorati Tags: fscheck,random testing

Share this post :

F# projects someone should start

2011-01-02T21:57:00.000Z

Some ideas for projects that would scratch a few itches I have. However it’s unlikely that I’ll ever have to time to actually get round to doing them myself, so by blogging about them I hope someone who is looking for ideas can pick one of these up and make them real. Hope there is some room after New Year’s resolutions! The difficulty and work involved varies widely. Look at it this way – if you pick one of these up, you can be assured you’ll have at least one user.

A usable documentation system

I’m not talking about xml doc comments here (although that is a part of it). It should be possible to come up with a good domain specific language to write documentation of any kind – be it straightforward API documentation, a tutorial or a cookbook, that is easy to keep up to date with the current API you’re documenting, and that can export to a variety of different formats.

My main inspiration here is Scribble, for Racket (formerly PLT Scheme). From the scribble paper’s abstract:

Scribble is a system for writing library documentation, user guides, and tutorials. It builds on PLT Scheme’s technology for language extension, and at its heart is a new approach to connecting prose references with library bindings. Besides the base system, we have built Scribble libraries for JavaDoc-style API documentation, literate programming, and conference papers. We have used Scribble to produce thousands of pages of documentation for PLT Scheme; the new documentation is more complete, more accessible, and better organized, thanks in large part to Scribble’s ﬂexibility and the ease with which we cross-reference information across levels. This paper reports on the use of Scribble and on its design as both an extension and an extensible part of PLT Scheme.

The cool thing here is that you write your documentation in Scheme itself – you write a function or member in your text, and it uses the default name resolution rules to look up what you’re referring to, and if you say export to HTML, adds a hyperlink to the actual API documentation for that particular function. Also you can write a short program, have it typeset in place, along with the results of running the program. That would be hugely useful for cookbook style documentation.

I realize it is probably not possible to do this in F# in the same way due to the lack of macros. Maybe ClojureCLR would be a better choice. On the other hand, now that the F# compiler is open source – how about a compiler extension? For some inspiration closer to home, have a look at BumbleBee. Bonus points for Visual Studio integration.

Difficulty: Medium. The hard part is figuring out how to do this cleanly – but maybe a fairly straightforward pre-processor is enough to make people happy.

Work: Lots. Getting all this stuff to work together reliably and preferably inside Visual Studio...that’ll take some time.

Mirror-based reflection library

Let’s face it. The reflection APIs in .NET suck. First of all, because I have to write APIs, and not API – I mean there’s System.Reflection, System.Reflection.Emit, CodeDOM, the Debugger API (what else is debugging if not reflecting over your code?), a separate API for F# reflection (and probably for any language that’s not C# or VB), Cecil, ReflectionOnlyLoad, Metadata reading in the F# PowerPack, and so on.

This indicates insufficient abstraction of System.Reflection: if I’m playing with F# types, I cannot use GetType() – this exposes internal implementation details! The reflection API by itself cannot cope with other languages, or other types of reflection – hence the need for e.g. a separate debugging API, as it needs to cope with distributed debugging. Or for things like Cecil, to cope with situations where you don’t want to load an assembly and all its dependencies when you’re reflecting over it. Sadly, this sometimes makes it look like I'm learning the same old reflection API over and over again, except someone’s changed all the names. And don’t get me started on how many times Type is overloaded. High cohesion, anyone?

Enter mirror-based reflection, which is an idea that might solve these problems. Except of course, .NET does not have a library that uses this type of reflection. This is where you come in...for inspiration, Newspeak has the beginnings of such an API. It should be possible to have a specific API that is clear in the limits of what it can do, while still sharing much of the concepts with very similar systems – imagine being able to use Cecil and System.Reflection but with the same names for everything possible. And if you ever need to reflect over a running program, you can use the debugging API, except you can leverage your existing knowledge. Obviously, the library should be pluggable so that people can plug their own reflection libraries in there.

Difficulty: This may be a research problem. On the other hand, there are things to build on, and a motivated person or team could build, say, an introspection only API in a reasonable amount of time.

Work: lots and lots, obviously. However, a proof of concept API that just does introspection of structure (not behaviour) would be enough to get more people on board and would already be useful.

Contribute to NuGet so it knows about F#

NuGet is a package manager for .NET . The current release does not work with F# – boo! However looks like David Fowler actually already went ahead and contributed some code to make this work! Excellent. However, keep voting the issue up so the NuGet team adds it to the next release :)

Difficulty: shouldn’t be all too hard – I gleaned at the source code and it looks like they’re using the Visual Studio Automation API. I know the F# project system’s implementation here is kind of shaky, so probably a bunch of workarounds is needed.

Work: Not too much – mostly finding your way around the NuGet codebase and finding what works and what doesn’t in the F# language service..

Add snippets and organize usings support to the F# project system

I miss snippets. Sure, everything in F# is nice and short so the official story is that this isn’t needed as much as in C#, but still...oh, and while you’re at it, and now the compiler is open source (I love saying that – it makes everything look so easy) can we have organize usings too please? Bonus points for adding Refactor –> Rename.

Difficulty: Straightforward. Only roadblock could be that the current F# language service is just not easily extensible for these kinds of things.

Work: Reasonable. Finding your way around the Visual Studio language service extensibility model, and the F# compiler. Knowledge about this seems very useful to have, but I can’t deny it would take some time, obviously.

That should give you enough to pass the time in 2011, I hope!

Share this post :

F#, xUnit theories and InlineData

2010-12-16T22:03:00.000Z

How do you know you haven’t blogged much lately? When you want to write a blog post and you forgot the name of the thing you’re actually writing it with. “Wait, it’s called Window Live something something…what did that icon look like again?”. Also, Windows Live Writer now has a ribbon! Good stuff.

Anyway, just a short heads up to save people some time: in the xUnit extensions, there is a Theory attribute which in combination with the InlineData attribute lets you specify a parameterized xUnit test. The InlineData attribute lets you specify the values the test should run with (you can’t test everything randomly with FsCheck, you know). That and other xUnit extension goodies are explained here.

My point is – this attribute does not work in F# (or managed C++), because the AttributeUsage attribute on the InlineData attribute is defined on its parent class, DataAttribute. It is correctly defined as Inherited = true; but only the C# compiler seems to honour this. More detailed explanation in this stackoverflow post. If you care about this, please vote for the bug on the xUnit site!

Luckily, the workaround is not too bad – just use the PropertyData attribute instead:

let symbolTestData = 
    [ "an1 rest",           "an1"
      "?test bla",          "?test"
      "?+_est bla",         "?+_est"
      "+_123 bla",          "?+_123"
      "+._1.2.3 bla",       "+._1.2.3"
      "+_q1r-2g3! bla",     "+_q1r-2g3!"
      "abc.def.feg/q bla",  "abc.def.feg/q"
      "ab/cd? bla",         "ab/cd?"
    ]
    |> Seq.map (fun (a,b) -> [|a; b|])

[<Theory>]
[<PropertyData("symbolTestData")>]
let ``should parse symbol``(toParse:string, result:string) =
    Assert.Equal(result, run symbol result)

Note that xUnit actually expects a sequence of arrays, but I think the list of tuples looks better, at the small cost of an extra conversion step.

Technorati Tags: xUnit,F#,xUnit Theory

Share this post :

F# and Code Contracts: not quite there yet

2010-07-10T17:26:00.000+01:00

In this post I’ll show how you can get Code Contracts sort of working for F#. From my very initial explorations, I would conclude that they seem basically usable for F# programming – but you’ll need some glue and tape, and not everything works as you’d expect.

Code Contracts: the short story

Code contracts are a way to express pre- and postconditions and invariants for (theoretically) any CLR based programming language. This is a Very Good Thing, as such contracts are a great way to specify the expected behaviour of your program (i.e. your intent).

Pragmatically, contracts are usually compiled into a debug build of a program, and checked at runtime. That’s how Eiffel does it, where this whole contract thing got started. So every time your program runs, it’s actually being tested in a very deep way. That’s why a tool like Eiffel’s ARTOO, which basically randomly constructs objects and calls method sequences on them, works well: you can find bugs by just executing your program randomly! Of course contracts are also good for documentation: no more looking in the code to find out what happens when you pass in 0 for a particular argument – the pre- and postcondition should tell you.

In the .NET world Code Contracts delivers this kind of functionality by means of a rewriter. That is, you write your actual contracts in a contract language using the System.Diagnostics.Contracts namespace in .NET 4.0, but the methods you’re calling do not actually do much: instead the rewriter runs after the compilation phase on the resulting assembly, recognizes the calls and writes the actual contract checking code in the assembly. This is necessary for example because it’s very useful in a contract to be able to refer to the old value of a parameter, or to the result of the method. Without a rewriter, you’d basically just have something like Debug.Assert, which is not very expressive.

MS research also has made a static checker for contracts, which tries to statically determine whether your contracts hold, and if so, is able to feed that information back to the rewriter so that statically checked contracts do not need to be checked at runtime. Personally I don’t think that is useful because it seems very imprecise. Time will tell – happy to be proven wrong.

Since the rewriter works on the assemblies, you can just use the Contracts API from any .NET language, at least in theory. In practice, different compilers tend to output different representations of types or whatever construct they offer, so it’s not unthinkable that the rewriter gets confused. In fact, in the case of F# it gets confused when you try to write contracts in constructors, as we’ll see.

So while nice in theory, this turns out to be another case of “It works for all .NET languages, as long as they’re exactly like C# or VB.” At least until the contracts folks get round to actually supporting F#, I guess.

The nuts and bolts

‘Nuff complaining. Let’s see how we get code contracts to work with F#.When you install the code contracts add-on, in C# you get a nice extra tab in your project properties. Not so in F# – but that’s the easy part. The whole rewriter thing is actually nicely abstracted away in some custom target file that the Code Contract folks have kindly provided, so we’ll just need some manual editing of the F# project file to get it to work. Here’s an example:

<?xml version="1.0" encoding="utf-8"?>
<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
  <PropertyGroup>
    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
    <ProductVersion>8.0.30703</ProductVersion>
    <SchemaVersion>2.0</SchemaVersion>
    <ProjectGuid>{dd086c3a-9cbd-4dc9-89d2-4386df7ee986}</ProjectGuid>
    <OutputType>Exe</OutputType>
    <RootNamespace>CodeContractsFs</RootNamespace>
    <AssemblyName>CodeContractsFs</AssemblyName>
    <TargetFrameworkVersion>v4.0</TargetFrameworkVersion>
    <Name>CodeContractsFs</Name>
    <CodeContractsAssemblyMode>1</CodeContractsAssemblyMode>
  </PropertyGroup>
  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
    <DebugSymbols>true</DebugSymbols>
    <DebugType>full</DebugType>
    <Optimize>false</Optimize>
    <Tailcalls>false</Tailcalls>
    <OutputPath>bin\Debug\</OutputPath>
    <DefineConstants>TRACE;DEBUG;CONTRACTS_FULL</DefineConstants>
    <WarningLevel>3</WarningLevel>
    <DocumentationFile>bin\Debug\CodeContractsFs.XML</DocumentationFile>
    <CodeContractsEnableRuntimeChecking>True</CodeContractsEnableRuntimeChecking>
    <CodeContractsRuntimeOnlyPublicSurface>False</CodeContractsRuntimeOnlyPublicSurface>
    <CodeContractsRuntimeThrowOnFailure>True</CodeContractsRuntimeThrowOnFailure>
    <CodeContractsRuntimeCallSiteRequires>False</CodeContractsRuntimeCallSiteRequires>
    <CodeContractsRunCodeAnalysis>False</CodeContractsRunCodeAnalysis>
    <CodeContractsNonNullObligations>False</CodeContractsNonNullObligations>
    <CodeContractsBoundsObligations>False</CodeContractsBoundsObligations>
    <CodeContractsArithmeticObligations>False</CodeContractsArithmeticObligations>
    <CodeContractsRedundantAssumptions>False</CodeContractsRedundantAssumptions>
    <CodeContractsRunInBackground>True</CodeContractsRunInBackground>
    <CodeContractsShowSquigglies>False</CodeContractsShowSquigglies>
    <CodeContractsUseBaseLine>False</CodeContractsUseBaseLine>
    <CodeContractsEmitXMLDocs>False</CodeContractsEmitXMLDocs>
    <CodeContractsCustomRewriterAssembly />
    <CodeContractsCustomRewriterClass />
    <CodeContractsLibPaths />
    <CodeContractsExtraRewriteOptions />
    <CodeContractsExtraAnalysisOptions />
    <CodeContractsBaseLineFile />
    <CodeContractsRuntimeCheckingLevel>Full</CodeContractsRuntimeCheckingLevel>
    <CodeContractsReferenceAssembly>%28none%29</CodeContractsReferenceAssembly>
  </PropertyGroup>
  <ItemGroup>
    <Reference Include="mscorlib" />
    <Reference Include="FSharp.Core" />
    <Reference Include="System" />
    <Reference Include="System.Core" />
    <Reference Include="System.Numerics" />
  </ItemGroup>
  <ItemGroup>
    <Compile Include="Module1.fs" />
    <None Include="Script.fsx" />
  </ItemGroup>
  <Import Project="$(MSBuildExtensionsPath32)\FSharp\1.0\Microsoft.FSharp.Targets" Condition="!Exists('$(MSBuildBinPath)\Microsoft.Build.Tasks.v4.0.dll')" />
  <Import Project="$(MSBuildExtensionsPath32)\..\Microsoft F#\v4.0\Microsoft.FSharp.Targets" Condition=" Exists('$(MSBuildBinPath)\Microsoft.Build.Tasks.v4.0.dll')" />
</Project>

I’ve put the things to change from a vanilla F# project file in bold. I won’t go over all of them – you can experiment for yourself by playing with the UI in a C# project and checking what the effect is. The three important bits are:

CodeContractsAssemblyMode: per assembly, code contracts allows you to set it in either a compatibility mode (0) or the standard mode (1). For new assemblies, 1 is what you want.
CODECONTRACTS_FULL compile constant: if you don’t define this, the rewriter won’t write the contract checking methods in your assembly. So define this in you Debug configuration (or in a special Contracts configuration)
CodeContractsEnableRuntimeChecking: Otherwise the rewriter doesn’t kick in. Not sure why you’d need this and the constant, but there you go.

Add this to your F# project and you should see the rewriter kick in after the build – it’s called ccrewrite.exe.

Let’s write some contracts

That was the easy part. Now, let’s try to convert the program given in the Code Contracts documentation to F#:

type Rational(numerator,denominator) =
    do Contract.Requires( denominator <> 0 )
    [<ContractInvariantMethod>]
    let ObjectInvariant() = 
        Contract.Invariant ( denominator <> 0 )
    member x.Denominator =
        Contract.Ensures( Contract.Result<int>() <> 0 )
        denominator

So this is a simple rational type. It shows you basically how contracts work – you call methods on the Contract static class:

Contract.Requires to impose a precondition on arguments – in this case an argument of the constructor.
Contract.Ensures to express a postcondition – in this case a postcondition on the result of a getter, which is nicely accessible using Contract.Result.
ObjectInvariantMethodAttribute and Contract.Invariant to impose an invariant on a class – something that should hold after every execution of a method.

So far so good. Alas, when we try to build this, we get:

warning CC1041: Invariant method must be private
error CC1011: This/Me cannot be used in Requires of a constructor
error CC1011: This/Me cannot be used in Requires of a constructor
error CC1011: This/Me cannot be used in Requires of a constructor
error CC1011: This/Me cannot be used in Requires of a constructor
error CC1038: Member 'Module1+Rational.denominator' has less visibility than the enclosing method 'Module1+Rational.#ctor(System.Object,System.Int32)'.: error CC1069: Detected expression statement evaluated for potential side-effect in contracts of method 'Module1+Rational.#ctor(System.Object,System.Int32)'. (Did you mean to put the expression into a Requires, Ensures, or Invariant call?) error CC1004: Malformed contract. Found Requires after assignment in method 'Module1+Rational.#ctor(System.Object,System.Int32)'.

And it turns out that the rewriter is confused by F#’s representation of constructors. When we comment out the Contract.Requires in the constructor, everything works fine.

The warning about the invariant method is because F# actually compiles private members as internal. The rewriter flags this using this warning, but it’s otherwise not much to worry about, I guess, though slightly annoying if you’re – like me – fairly obsessive about getting your code to compile without warnings.

Conclusion

I’ve also checked code contracts with various pre-and postconditions to functions, and that seems to work fine. So overall it’s not a bad story, but it would be nice to see some better integration and to fix the bug(s).

I haven’t checked other features of code contracts, like contract inheritance or expressing code contracts on interfaces, which needs a few tricks as well, so there is a chance that you’ll run into problems there.

Finally, a tip: if you don’t like the C#-ish feel of the Contracts API, you can define your own inline functions that call into the actual API – given that they’re inlined, the rewriter will not see the difference.

So close, but not quite there yet. I’ve asked a year ago if the situation was going to improve, and again a few weeks back, but it’s basically unchanged since then. So F#-ers: head over to the Code Contracts forum and ask for F# support! I’m feeling a bit alone in the desert there at the moment…

Technorati Tags: F#,code contracts

Share this post :

Thinking outside the Visual Studio box

2010-06-09T18:38:00.000+01:00

Visual Studio and .NET development go hand in hand. As far as I know, every .NET developer uses it. Compared to the Java IDE landscape, there isn’t even competition. And what little competition there is, is pretty much a carbon copy of the approach Visual Studio takes to development. Visual Studio is incontournable, and there is little on the horizon that will change this situation.

What toothpicks and Visual Studio have in common

I did some Java development in Eclipse over 3 years ago, and as I remember it, it worked better than Visual Studio 2010. Let me repeat that:

Eclipse 2007 (for Java) is a better IDE than Visual Studio 2010 (for C#).

I don’t want to go into a feature by feature comparison. No doubt Visual Studio would win. I’m saying that for actual development, you know the thing you’re doing 95% of the time in an IDE, it’s just better. I believe these activities are compiling, testing, refactoring, browsing code and source control.

Compiling. The most important feature of compilation is that you don’t see it. The incremental compilation in Eclipse is just way better. Even for medium sized projects, press Ctrl+S and your code is ready to run. Instantly. This is different from the incremental “compilation” Visual Studio does – while this updates intellisense info on the fly, it does not actually build your code. So if you want to test or run, you’ll have to wait.

Testing. Eclipse comes with excellent JUnit integration out of the box. I guess there’s MSTest for Visual Studio, which is ok, but it doesn’t have that Red-Green-Refactor feel. Open source testing frameworks as far as I know don’t reach the same level of integration. If you want code coverage, be prepared pay some money for at least the Premium edition.

Refactoring. The refactorings in Visual Studio pale in comparison to those in Eclipse. Hands down.

Browsing Code. I think Visual Studio actually has many features in this area, but the UI doesn’t make them particularly discoverable. I’ve found that following references, finding overrides and such in Eclipse is faster and easier than in Visual Studio.

Source control. If you fork out some money, you get integration with Team Foundation with Visual Studio. My feeling is that integration with other source control systems like mercurial and subversion is just not as good as the integration in Eclipse.

Products like Resharper and Testdriven.NET mitigate the refactoring, browsing and testing issues for Visual Studio. But Eclipse comes with these things out of the box. It’s just there when you download it, which is first of all free and second, convenient.

Then, Visual Studio just doesn’t have a good UI. I’m not excited that I can finally make code windows free floating. The solution explorer naturally makes you focus on the files and the file system – while this actually matters little for your day to day development activities. You want to focus on modules, classes, namespace instead (yes, I know about the class browser, but somehow I keep getting pulled back to the solution explorer by Visual Studio.) And then that annoyance among annoyances – the much hated Add Reference dialog. In 2010 they made it asynchronous, so we can now pretend that it is not as slow and painful as amputating your arm with a toothpick, except that it’s worse! At least before you knew when you could start searching for a reference. Now you’re left to wonder – is my reference not there or is it still loading in the background?

What rocks and Visual Studio have in common

Both SharpDevelop and MonoDevelop seem to focus on conforming with Visual Studio. I guess the argument is that this makes it easier for people to migrate from Visual Studio. Wake up people: if it looks like Visual Studio, nobody is going to bother anyway.

I don’t want to talk down to the developers of these projects. I’m sure they’re passionate about what they’re doing. But let’s face it – they’re not going to be able to compete on features, as long as Microsoft is throwing money at Visual Studio. On marketing alone, they’re overwhelmed. As far as I can see there is no buzz surrounding these projects at all. Nobody particularly likes or hates them. They’re boring. Because Visual Studio is. It’s just there. Like a rock. A boring, grey rock.

A call to arms

So, dear SharpDevelop or MonoDevelop developer, or whoever is looking to develop a new software project: here’s my call to arms for you.

Dare to innovate! Forget about Visual Studio. It’s there, and it’s going to stay – but give use a ray of hope. Give us something to look forward to. Give us something that we can love, or hate – something that at least provokes some feelings.

Need some ideas?

Stop bothering with trying to be compatible with Visual Studio. Sure, the assemblies need to be compatible with .NET, but who really cares about MSBuild, and project files, and why even duplicate the solution-project-file based organization of Visual Studio - is there a better way? Can you finally free us from the tyranny of the file system and let us focus on the abstractions provided by the language – it’s called software development, not file shuffling.

Can we make better compilers for C# or VB or F# that are incremental? Note I am talking about the compiler here, not the build system. The Eclipse Java compiler proves that incremental compilation can be pretty much as fast as no-compilation (as in dynamic languages).

Source control – can we go beyond superficial integration with popular SCMs and really integrate change tracking in the language and IDE? With the disk space currently available, is there even a use for the distinction between in memory undo/redo, saving a file to disk and committing a change in source control? Can’t I just type in my code and expect it to be saved, and undoable, and in source control? In addition, can we make “diff” tools language aware please – it’s silly that conflict resolution is line-based, while pretty much every coherent change to code spans multiple files and multiple lines. I’ve never heard of a line-based programming language. Let’s talk about modules and functions and objects and interfaces all the way through please.

Have a look at a Smalltalk IDEs. They have a browser oriented perspective on development, and have had another view on code organization and source control for ages now. There are lots of good ideas there, and it’s about time they are finally acknowledged and brought to the mainstream. The Hopscotch browser for Newspeak looks interesting too.

As far as UI goes, Code Bubbles (built on Eclipse for Java) seems to have some very well thought out UI ideas on browsing, cooperating and debugging.

I believe that any project that does just some of the above has the potential to become huge in the .NET space. Even with respect to mainstream Java IDEs which are nowhere near revolutionary, the .NET community seems to be behind the curve IDE-wise. Developers can see how computing devices all around them are becoming smarter, better integrated and user-oriented. Mainstream IDEs are lagging way behind.

Time for a revolution?

Technorati: IDE,.NET,Visual Studio,Eclipse

Share this post :

FsCheck 0.7: Pleasure and Pain

2010-06-04T21:40:00.000+01:00

I just released FsCheck 0.7 on the codeplex page. Whereas previous releases have been mostly incremental, this one is quite different. With the official release of F# 2.0 and all that it entails, I’ve refactored the FsCheck API from a usability perspective.

The previous API was inherited from Haskell QuickCheck, which means that it wasn’t very .NET like. For example, once you opened the FsCheck namespace, all the relevant functions just came into scope. So you, dear user, had to rely mostly on your memory to find the function you need, and also you were not empowered to discover new functions. The new API is a much needed improvement on that situation: it is consistent with .NET idioms, works well with intellisense and the documentation should tell you all you need to know.

I’ve also tried to improve FsCheck’s output, tried to improve the story with registering generators by type (which was a real pain before, and I hope it has now got at least a bit better), removed concepts that nobody seemed to understand (Hi, coarbitrary!) and generally improved the documentation and names of functions.

That’s the good news – the bad news is that this release is not backwards compatible. I’m afraid that was not possible given the breadth and depth of the refactoring that I wanted to do. I really believe that FsCheck is in a much better place now, also as far as plans for the future are concerned.

Short attention span?

Get a visually appealing (but much less detailed) overview in this prezi.

The whole truth

Well, at least as far as I can remember.

Factored API into three type and module pairs – cfr e.g. the collection types in FSharp.Core. So there is now:

Gen<’a> type and the Gen module that contains utility functions to define your own random generators. This is essentially the same as before, except there have been many renames to make everything consistent both internally and with .NET, and understandable (e.g. vectorOf has been renamed to listOfLength, and fmapGen has been renamed to Gen.map). Also, where functions used to take a list as argument, they now take a more general and .NET-like seq instead.
Arbitrary<’a> type and Arb module. Arbitrary, as before, packages up a generator and a shrinker. Coarbitrary was removed (without removing FsCheck’s functionality to generate functions). The Arb module is new, and plays a fairly central role in FsCheck now – a few useful functions that operate on a generator and a shrinker at the same time were added.

Arb.Default type contains the default generators and shrinkers that ship with FsCheck. I’ve cleaned up most of the mess, but am not completely finished yet. Anyway, you should find many useful Arbitrary instances here, and they are now easily accessible (I believe in the previous version you had to type something like Arbitrary.Arbitrary.String().Arbitrary – now it is Arb.Default.String)

Property type and Prop module. Here is where all the functions to build the actual properties live. Not much changes here, except that Prop.forAll now takes an Arbitrary instance instead of a generator – I believe this is a first step in making FsCheck more easily extendable to other kinds of generators (e.g. file based or exhaustive generators) by abstracting away the Gen type from Property. (This is currently only skin-deep though)

Similar refactoring with running tests.

Instead of quickCheck, verboseCheck, and all the other functions, there is now a Check type with relevant static methods that do the same thing. This made it possible to overload method names, which was annoying about the functions – I felt like I had to make up meaningless names. Also, the various checking types that you can do are now discoverable using intellisense by typing Check.<intellisense>.
Similarly, the default configurations have now been added as static members on the Config record type, which is were you would expect them to be.
The Runner module has had some cleanup as well, with some new names for old friends, and the IRunner interface has been extended a bit. Like the other modules, it should only expose what is useful to you, so it should be fairly easy to figure out what you need from intellisense alone.

Output has been improved in various places.

When registering generators, FsCheck now automatically overrides the previous generators, and also produces to some output where you can see what the new types that have been registered are, as well as what types were overridden. Hopefully this will help you fix those frustrating issues where types are not registered properly more easily.
When checking all the members on a type or module, and an exception is thrown, the TargetInvocationExcception is now removed and you just get to see the actual exception, which reduces much of the noise.
Various small output improvements.

Size control has been changed in the Config. Instead of a function, you can now give a begin and end size and FsCheck will increase the size linearly between those two values. I did this to make the size independent of the number of test runs that you choose – the final size is always guaranteed to be the end size you ask for. So it is easy to change the number of tests while keeping the same size. I believe this is the least surprising result, as changing the number of tests should not directly influence the test size.
Added many more tests, especially for the generators. I’m still not happy with the coverage, but we’re getting there.
Wrote a simple documentation generator. I’m not very happy with it, but at least I reviewed all the documentation and at least the output shown in the documentation is now consistent with the actual output, and it is easy to keep that way.
Cleaned up the examples a bit. The examples used in the documentation are now moved to the FsCheck.Documentation project (which also generated the codeplex formatted output).
Typeclass simulation has had a pretty much bottom up rewrite. Hopefully this cleans up some nasty issues with static state I’ve seen, and also the API is I think much improved. Various bug fixes.

That’s pretty much it. I’ve got more in store still, but not sure when it will materialize into something that I can release. My spare time is getting scarce…but do post a comment on the forum or on my blog if you get stuck in moving your old FsCheck code to the new API, or any other feedback you may have.

Happy FsChecking!

Technorati: fscheck,f#,random testing

Share this post :

Accessing Visual Studio’s Automation API from F# Interactive

2010-05-15T22:24:00.000+01:00

Because why anyone would want to write VBA in the Visual Studio macro editor is beyond me. All the bits and pieces below are pretty much known, but I think the overall result is new. For the bewildered (I don’t blame you), what you’ll be able to do is, from F# Interactive, for example enumerating the current projects in the open solution:

> myDTE.Solution.Projects |> Seq.cast<Project> |> Seq.map (fun p -> p.FullName);;

val it : seq<string> =
  seq
    ["C:\Users\Kurt\Projects\FsCheck\doc\FsCheck\FsCheck.fsproj";
     "C:\Users\Kurt\Projects\FsCheck\doc\FsCheck.Examples\FsCheck.Examples.fsproj";     "";
     "C:\Users\Kurt\Projects\FsCheck\doc\FsCheck.Checker\FsCheck.Checker.fsproj";     ...]

You get access to the DTE top level automation object of the Visual Studio instance the current FSI is running under. This DTE is a COM interface that basically allows you to do programmatically what you can do using the Visual Studio UI interface – it’s the thing you get access to in the Macro IDE as well. So you can do pretty cool things – like add files, generate code, listen to build events, find dependencies of projects and such.

But…how?

The Macro IDE gives access to the DTE object automagically. But fsi is actually a separate process, that just happens to input and output through Visual Studio. So basically we need to get access to a Visual Studio instance’s DTE object from outside of Visual Studio. Luckily, each instance of Visual Studio registers its DTE object in the Running Object Table (hereafter called ROT) with two keys:

As a string of the form “!VisualStudio.<VS version>.0:<processid>”. E.g. for VS2008 with process id 1234: !VisualStudio.9.0:1234
As the path to an open solution file, if any.

We’ll use the first option. That means we need to find out the process id of the Visual Studio instance the current FSI instance is running under. FSI is started as a child process of Visual Studio – each Visual Studio has its own FSI.

Let’s tackle each of these in turn – first finding the process id of the current Visual Studio instance, then its DTE object via the ROT.

Step 1: Finding the Visual Studio process id

Not as straightforward as it sounds. System.Diagnostics.Process does not give you direct access to a process’ parent. There are at least two ways to go about it – using the Windows API or, maybe surprisingly, through performance counters. I used the latter because that didn’t require me to do interop.

The code is pretty straightforward – remember the point is that this is being executed in F# interactive:

open System
open System.Diagnostics

let getParentProcess (processId:int) =
    let proc = Process.GetProcessById processId
    let myProcID = new PerformanceCounter("Process", "ID Process", proc.ProcessName)
    let myParentID = new PerformanceCounter("Process", "Creating Process ID", proc.ProcessName)
    myParentID.NextValue() |> int
    
let currentProcess = Process.GetCurrentProcess().Id

let myVS = getParentProcess currentProcess

You should just be able to paste that into an F# Interactive window and myVS will contain the process id of the Visual Studio instance it’s running under. (No doubt this will crash spectacularly when you’re running FSI standalone or something.)

Step 2: Getting the DTE object

This was a bit harder, as we’re now going to have to do some interop with OLE32. Code for this is floating around on the internet if you know where to look – I just translated it to F#. Here’s what we need:

#r "EnvDTE"
#r "EnvDTE80.dll" 
#r "EnvDTE90.dll" 

open EnvDTE
open EnvDTE80
open EnvDTE90

open System.Runtime.InteropServices
open System.Runtime.InteropServices.ComTypes

module Msdev =
    
    [<DllImport("ole32.dll")>]  
    extern int GetRunningObjectTable([<In>]int reserved, [<Out>] IRunningObjectTable& prot)
 
    [<DllImport("ole32.dll")>]  
    extern int CreateBindCtx([<In>]int reserved,  [<Out>]IBindCtx& ppbc)

These two interop functions allow us to enumerate the ROT and get the registered object with the key we want:

let tryFindInRunningObjectTable (name:string) =
    //let result = new Dictionary<_,_>()
    let mutable rot = null
    if Msdev.GetRunningObjectTable(0,&rot) <> 0 then failwith "GetRunningObjectTable failed."
    let mutable monikerEnumerator = null
    rot.EnumRunning(&monikerEnumerator)
    monikerEnumerator.Reset()
    let mutable numFetched = IntPtr.Zero
    let monikers = Array.init<ComTypes.IMoniker> 1 (fun _ -> null)
    let mutable result = None
    while result.IsNone && (monikerEnumerator.Next(1, monikers, numFetched) = 0) do
        let mutable ctx = null
        if Msdev.CreateBindCtx(0, &ctx) <> 0 then failwith "CreateBindCtx failed"
            
        let mutable runningObjectName = null
        monikers.[0].GetDisplayName(ctx, null, &runningObjectName)
        
        if runningObjectName = name then
            let mutable runningObjectVal = null
            if rot.GetObject( monikers.[0], &runningObjectVal) <> 0 then failwith "GetObject failed"
            result <- Some runningObjectVal
        
        //result.[runningObjectName] <- runningObjectVal
    result

I won’t go into the virtues of this particular piece of code. Suffice to say it’s an acquired taste. (Bonus points for anyone who can write a function that returns the ROT as a nice, lazy seq<string*obj>. Yes I know it seems easy – but please try and prepare to be frustrated.). So we now have a function that returns the COM object in the ROT based on the name. If you put in the code in comments and change a few bits and pieces, it should be easy to get a function that outputs the ROT completely.

Putting two and two together

Armed with these functions, here’s the DTE object that you can use to call the Automation API:

let getVS2008ROTName id = 
    sprintf "!VisualStudio.DTE.9.0:%i" id
    
let myDTE = (tryFindInRunningObjectTable (getVS2008ROTName myVS) |> Option.get) :?> DTE2

This is for Visual Studio 2008. For 2010, it should be as easy as changing the 9 to 10 in the ROT key string. It’s possible to make this more general if you can come up with a way to check whether the current process is .NET 4 or .NET 3.5 – the former would indicate an FSI running in VS2010, the latter in VS2008.

And that’s it. Have a look around using Intellisense to see what is possible. Also check out the Macro IDE – it has some code examples in VBA that involve the DTE. Some ideas:

myDTE.ExecuteCommand lets you execute any command – the things you can bind keyboard shortcuts to in the Options. For example, use ProjectandSolutionContextMenus.Item.MoveDown to move the currently selected item one place down.
myDTE.Events to register event handlers for all sort of Visual Studio events. For example, myDTE.Events.BuildEvents.add_OnBuildDone notifies you when a build is done. Nice for post-build steps that need to run after a solution is built (as opposed to after a particular project is built).
myDTE.Quit(). The l33t hax0r way to exit Visual Studio. You’ll be the envy of your less tech-savvy colleagues.

If you find an imaginative use for this, please let me know.

Technorati: F# Interactive,Visual Studio Automation,DTE,F#,FSI

Share this post :

Moving FsCheck to Mercurial

2010-04-09T22:20:00.000+01:00

I’ve been using Mercurial as my source control system of choice for a few years now, and I’ve been very happy with it. The only problem I had was that codeplex, where FsCheck is hosted, only supported SVN. I used Mercurial for daily development, and when a release was imminent I just copied the final snapshot to my local SVN checkout and updated codeplex from there. Needless to say, the SVN repository was out of date and didn’t represent the actual history.

Well, no more! Codeplex now supports Mercurial as well. One email to the kind folks at codeplex support, and they wiped my SVN repository from codeplex and provided me with a shiny new hg repository. Great.

That left me with a problem: since I was used to the hg repository being private, I also dumped some, well, private stuff in it. Before you start imagining things, there is nothing special there – just a few pdfs of papers and such, but nonetheless things I didn’t want to put in a public repository. If only because some authors prefer that they alone control dissemination of their work.

And obviously Mercurial isn’t keen on letting you delete history.

Luckily it has the excellent convert extension. This is usually used to convert SVN, CVS or other repositories to a Mercurial repository. But you can also convert a Mercurial repository to a new one, and rewrite and update history along the way. One of the things the convert extension lets you do is to specify files and folders that should not be migrated. It also lets you remove branches, and even splice a certain set of changesets on a parent in the new repository.

I used the first two features to remove some superfluous history and files. I used the last because I’m used to clone my main repository to a bunch of feature repositories to work on specific features in relative isolation. I have a few of those in progress, but of course since I was converting my main repository to a new one the feature repositories couldn’t be used to push changes back to the new main. This makes them pretty much useless, unless they are converted as well.

So here’s what I did:

Convert the old main repository to the new main, stripping out files and branches along the way.
Clone the new repository for each feature I’m currently working on. Now I have a mirror image of my old folder where the old main and the old feature repositories are – except the changesets in the old feature repositories need to be migrated to the new feature repositories.
Using hg convert’s splice feature, and the excellent TortoiseHg repository explorer to find out the changeset numbers, I then additionally converted only the extra changesets from each old feature repository to its corresponding new feature repository. One thing to keep in mind is that hg convert uses the .hg/shamap file in the new repository to keep track of which changesets from the old repository it has already converted. This file is however not automatically copied when cloning – so I had to manually copy that over from the new main to the new feature repositories – otherwise convert would try to convert all of the changesets again.

Confused yet? Well, here’s my first Prezi to explain it all…

You can check out the result in FsCheck’s source tab – although the main result is that there is now much less friction in my development process.

Technorati: mercurial,hg convert,fscheck,codeplex

Share this post :

FsCheck 0.6.3 for Visual Studio 2010 RC and F# February 2010 CTP

2010-02-15T20:08:00.000Z

A new release of F# means a new release of FsCheck.

Removed the dependency on the F# PowerPack. This makes FsCheck easier to use, especially since the PowerPack is now separately distributed. Besides, it was only used to pretty print functions.
Cleaned up reflective generators a bit.
All projects are upgraded to build with Visual Studio 2010 now. For backwards compatibility, I’ve added an FsCheck2008.sln solution which allows you to build in Visual Studio 2008 with the February 2010 CTP. You’ll get a warning from MSBuild saying that ToolsVersion 4.0 is not supported and that it is treating the build as a 3.5 build. Good – that’s exactly what you want. FsCheck is still targeting .NET3.5 until .NET4 is out.

Enjoy.

Technorati: FsCheck,random testing,F#

Visug presentation in Leuven, Belgium on 8 Feb 2010

2010-02-11T20:54:00.001Z

Thanks to everyone who attended – hope you got something out of it (besides the free food and drinks…).

Here are the slides I used, as well as the (completed) demo project. There are some extra slides and some extra parts to the demo which I didn’t present. Apparently the whole thing will also appear on MSDN chopsticks, at which point I’ll update this post with the link.

On Understanding Data Abstraction, Revisited

2009-12-22T16:57:00.000Z

I’m not in the habit of posting links, but this essay by Willam R. Cook on the difference between ADTs and objects made such an excellent and humbling read... Humbling because in my arrogance I had assumed that I knew the difference – after all this is basic stuff. Excellent because despite the humbling experience, it’s a very enjoyable read.

Enjoy.

Technorati: ADT,objects,data abstraction

Share this post :

How to get hg-git working with Mercurial without installing Python on Windows

2009-12-08T19:51:00.000Z

Sorry for the horrendous search keyword-driven title, but I’ve been trying to get this to work for ages.

Here’s a step by step guide, along with some potential pitfalls.

1) Download TortoiseHg. I used 0.9.1.1. with Mercurial 1.4.1. Do not use the windows Mercurial command line only distribution – we’ll need to modify a zip file later and for some reason the zip file with the command line distribution cannot be modified with either WinRar, Winzip or 7-zip.

2) Install TortoiseHg as usual.

3) Download dulwich 0.4.0.

4) Add the directory called ‘dulwich’ inside the dulwich download (the one with the file __init__.py in it) to the library.zip file in the TortoiseHg folder (normally just C: \Program Files\TortoiseHg) using your favorite zip utility.

5) Download the tip of an up to date hg-git fork. I used http://bitbucket.org/gwik/hg-git/.

6) Put the hg-git directory in the TortoiseHg directory.

7) Add the following lines to your Mercurial.ini file:

bookmarks =

hggit = C:\Program Files\TortoiseHg\hg-git\hggit

That’s it. I finally managed to clone the ClojureClr repository with the above install:

> hg clone git://github.com/richhickey/clojure-clr.git
destination directory: clojure-clr.git
importing Hg objects into Git
Counting objects: 4001, done.
Compressing objects: 100% (1816/1816), done.
Total 4001 (delta 3153), reused 2774 (delta 2148)
importing Git objects into Hg
at:   0/307
at: 100/307
at: 200/307
at: 300/307
updating to branch default
313 files updated, 0 files merged, 0 files removed, 0 files unresolved

And with this we’re back to functional programming languages ;)

I didn’t test this any further.

Good luck!

Technorati: mercurial, hg, hg-git, git

Share this post :

FsCheck 0.6.2: F# October 2009 CTP/2010 Beta 2

2009-10-26T10:10:00.000Z

FsCheck is updated for the new F# release! Conversion was fairly straightforward, some name changes and indentation changes mostly. Furthermore, the following smaller changes:

A nice set of new default generators contributed by Howard Mansell. FsCheck can now generate any Enum instance, as well as generators for DateTime, arrays, positive and negative ints and so on. Check out the Arbitrary.fs file for a complete overview.
Some more examples
registerInstances and overwriteInstances now throws an exception if it cannot find any instances in the given type.

Happy FsChecking!

Simple and Fair Backtracking Computations

2009-09-19T14:53:00.000+01:00

Translated to F# from the fair and terminating backtracking monad and monad transformer by Oleg Kiselyov.

Sequence expressions in F# can be seen as backtracking computations. For example,

let backtrack =
    seq {   for i in 1..10 do
            for j in 1..10 do
            if i*j > 10 then yield (i,j) }

will yield one by one (i.e. lazily) all the tuples i,j that satisfy the guard i*j>10. In Haskell, you would use list comprehensions to much the same effect. Once the values of j are exhausted for a given i, the computation backtracks, takes the next value for i and retries all values for j. Don’t mistake the syntactic sugar for nested loops – there is really a computation builder behind this that translates to something like

1..10 >>= (fun i –> 1..10 >>= (fun j –> …))

where (>>=) represents monadic bind. This translations shows more clearly that the binds are really doing backtracking. It’s just F#’s syntactic sugar for computation expressions that makes the computation look like a nested loop.

Unfortunately, this simplicity has some drawbacks.

let infinite =
    seq {   for i in 1..10 do
            for j in Seq.initInfinite id do
            if i > 5 then yield (i,j) }

will never return any results, although there is an infinite number of solutions. The reason is that generation gets stuck on j – an infinite stream that will never yield a solution as long as the computation does not backtrack and tries new values for i. The computation is unfair in its choice of values to try – it always chooses the last stream until that is exhausted.

The thing to realize is that, if viewed as a backtracking computation, there are basically two operations that are important: choice and bind.

Choice gives the computation a range of elements to choose from. In the example above, we have an element i that can be chosen from the interval [1,10] and an element j that can be chosen from the interval [0,Infinity]. It can be viewed as logical disjunction: for i, choose 1 or 2 or 3 or 4 or…

Bind gives the computation a number of sub-computations that all need to return a value if the complete computation is to return a value. It can be understood as logical conjunction: in the example above, i should be chosen from [1,10] and j should be chosen from [0,Infinity] and i should be > 5.

Theoretically, it does not matter in which order these kinds of generate-and-test computations are executed. However, for performance and once you start using infinite streams, it becomes important that the computation is fair – in the sense that the choices it makes give every option consideration, even if once choice has not been exhausted yet. The results of all backtracking computations should be equivalent modulo the order in which the results are returned.

So, can we make an alternative computation builder for which this kind of computation returns results?

Fair streams

Let’s start by making a new datatype of streams, that we can use to make fairer choices, and that also can be suspended so that infinite streams can be supported:

type Stream<'a> = 
    | Nil                               //empty
    | One of 'a                         //one element
    | Choice of 'a * Stream<'a>         //one element, and maybe more
    | Incomplete of Lazy<Stream<'a>>    //suspended stream

Using this stream, we can code a fair choice function:

let rec choice r r' = 
    match r with
    | Nil -> r' //first empty-> try the second
    | One a -> Choice (a,r') //Put in front of the new stream
    | Choice (a,rs) -> Choice (a,choice r' rs) //interleave r and r' here
    | Incomplete i ->
        match r' with
        | Nil -> r
        | One b -> Choice (b,r)
        | Choice (b,rs') -> Choice (b,choice r rs') 
        | Incomplete j -> Incomplete (lazy (choice i.Value j.Value))

The important thing here is the switch of argument order in the recursive call to choice in the third case. This ensures that, in contrary to normal sequences, a choice will choose alternatively from the first and second stream (and so on, recursively, for more streams). Choice is actually somewhat equivalent to concatenate on sequences, only it interleaves the elements so that the choice is fair.

Bind is more straightforward:

let rec bind m f =
    match m with
        | Nil -> Nil
        | One a -> (f a)
        | Choice (a,r) -> choice (f a) (Incomplete (lazy bind r f))
        | Incomplete i -> Incomplete (lazy bind i.Value f)

This is what you would expect from a normal monadic bind on a list like type: a variant of map – concat on each element of the first stream. Note in the third case that we take care to encode the resulting stream as a number of choices that we can choose from fairly.

We now have the important elements to make a computation builder:

type FairStream() =
    member x.Return a = One a
    member x.Yield a = One a
    member x.Bind (m, f) = bind m f
    member x.Zero() = Nil
    member x.Combine (r,r') = choice r r'
    member x.Delay (f:unit->Stream<_>) = Incomplete (Lazy.Create f)

   
let bt = FairStream()

I called it bt, short for backtracking. Now we need a function to run our computation:

let rec run d st =
    match (d,st) with
    | _,Nil -> Seq.empty
    | _,One a -> seq { yield a }
    | _,Choice (a,r) -> seq { yield a; yield! run d r }
    | Some 0,Incomplete i -> Seq.empty //exhausted depth
    | d,Incomplete (Lazy r) -> let d' = Option.map ((-) 1) d in run d' r

The run function takes an optional parameter to bound the number of backtracking steps, which may be useful to help with termination.

A few examples

First, let’s define a stream of numbers [0,Infinity]:

let rec number() = bt { yield 0
                        let! n = number() in yield n+1 }

Nothing really amazing here – you could do something similar with sequences as well. However, if we use the choice constructor explicitly, we can define number as a left-recursive function:

let rec number() = choice (bt { let! n = number() in return n+1 }) (bt {return 0})

Both number functions yield the same results.

Now for something a bit more spectacular.

let guard assertion = 
    bt { if assertion then return () }

let pythagoreanTriples =
    bt{ let! i = number()
        do! guard (i > 0)
        let! j = number()
        do! guard (j > 0) 
        let! k = number()
        do! guard (k > 0)
        do! guard (i*i + j*j = k*k)
        return (i,j,k) }

This computation will never yield any results in a standard sequence expression, but with the fair streams it works, even if you leave off the guards.

The discerning reader might wonder why we can’t write:

let rec number() = 
    bt { let! n = number() in return n+1
         return 0 }

which is a left recursive version in a computation expression style. I don’t know the answer myself – some details are lost in the translation to the methods on the computation builder, but I’m guessing it has something to do with the bind not being lazy enough, and/or the choice function not getting inserted in the appropriate place. I’ve tried various approaches, but couldn’t get it to work. So I guess there’s some homework for you :) In the mean time, I think I’m going to work through Backtracking, Interleaving, and Terminating Monad Transformers by Kiselyov et al…

Technorati: F#,computation builder,backtracking,monads

Share this post :

More fun with data structures, continuations and call/cc

2009-06-27T12:32:00.000+01:00

Last time I showed a few ways of implementing insert into an unbalanced binary tree, as an implementation of a set data structure. This post adds an implementation that is similar in functionality to the example that uses call/cc, but using the more familiar exceptions to avoid allocating elements needlessly:

let insertExc x t =
    try
        let rec insertRec x t =
            match t with
            | Empty ->  cont { return Elem(empty,x,empty) }
            | Elem (left,e,right) when x < e -> 
                cont {  let! t' = insertRec x left
                        return Elem(t',e,right) }
            | Elem (left,e,right) when x > e -> 
                cont {  let! t' = insertRec x right
                        return Elem(left,e,t') }
            | Elem _ -> failwith "alreadyExists"
        insertRec x t id
    with e –> t

Performance shootout

A comment on the last post indicated that exceptions should be much slower (on .NET, at least) than the callCC approach. Furthermore, I said that callCC was necessary to avoid re-allocating elements needlessly on the search path to an already existing element. Let’s put these claims to the test with a simple benchmark:

let longList = 
    let r = new System.Random()
    let l = 100000
    [ for i in 1..l -> r.Next(0,l) ]

let insertALot f nbRuns =
    for i in 1..nbRuns do
        longList |> List.fold (fun t elem -> f elem t) empty

How many duplicates are in the long list (i.e. how much can we expect to gain by using callCC/exceptions):

> longList |> Seq.distinct |> Seq.length;;
val it : int = 63362

So about 35% duplicates. The results:

> insertALot insert 100;;
Real: 00:01:38.717, CPU: 00:01:37.516, GC gen0: 2247, gen1: 520, gen2: 8
val it : unit = ()
> insertALot insert' 100;;
Real: 00:01:44.583, CPU: 00:01:37.251, GC gen0: 4050, gen1: 1444, gen2: 18
val it : unit = ()
> insertALot insertM 100;;
Real: 00:02:35.101, CPU: 00:02:29.792, GC gen0: 12698, gen1: 1875, gen2: 24
val it : unit = ()
> insertALot insertCallCC 100;;
Real: 00:01:09.410, CPU: 00:01:02.540, GC gen0: 12149, gen1: 7, gen2: 0
val it : unit = ()
> insertALot insertExc 100;;

- Interrupt

Observe that:

the readability of computation expressions comes with a cost;
even with that cost, the callCC code is still significantly faster;
Exceptions are indeed horribly slow – I interrupted after about an hour.

Share this post :

Fun with data structures, continuations and call/cc

2009-06-24T21:00:00.000+01:00

Prompted by exercise 2.3 in Purely Functional Data Structures, by Chris Okasaki.

type Tree<'a> = Empty | Elem of 'a Tree * 'a * 'a Tree

let empty = Empty

Recursive

let rec insert x t =
    match t with
    | Empty ->  Elem(empty,x,empty)
    | Elem (left,e,right) when x < e -> Elem (insert x left,e,right)
    | Elem (left,e,right) when x > e -> Elem (left,e, insert x right)
    | Elem _ –> t

Tail Recursive

let insert' x t =
    let rec cont x t k =
        match t with
        | Empty -> k (Elem(empty,x,empty))
        | Elem (left,e,right) when x < e -> cont x left (fun t' -> k <| Elem (t',e,right))
        | Elem (left,e,right) when x > e -> cont x right (fun t' -> k <| Elem (left,e,t'))
        | Elem _ -> k t
    cont x t id

Using a continuation monad

type Cont<'a,'r> = ('a -> 'r) -> 'r

type ContBuilder() =
    member x.Return (a):Cont<'a,'r> = fun k -> k a
    member x.Bind (c:Cont<'a,'r>, f:'a -> Cont<'b,_>) =
        (fun k -> c (fun a -> f a k))
    member this.Delay(f) = f()

let cont = ContBuilder()

let insertM x t =
    let rec insertRecM x t =
        match t with
        | Empty ->  cont { return Elem(empty,x,empty) }
        | Elem (left,e,right) when x < e -> 
            cont {  let! t' = insertRecM x left
                    return Elem(t',e,right) }
        | Elem (left,e,right) when x > e -> 
            cont {  let! t' = insertRecM x right
                    return Elem(left,e,t') }
        | Elem _ -> cont { return t }
    insertRecM x t id

Using call with current continuation

let callCC (f:('a -> Cont<'b,'r>) -> Cont<'a,'r>) : Cont<'a,'r> = fun k -> f (fun a _ -> k a) k

let insertCallCC x t =
    callCC (fun alreadyExists ->
        let rec insertRecCallCC x t =
            match t with
            | Empty ->  cont { return Elem(empty,x,empty) }
            | Elem (left,e,right) when x < e -> 
                cont {  let! t' = insertRecCallCC x left
                        return Elem(t',e,right) }
            | Elem (left,e,right) when x > e -> 
                cont {  let! t' = insertRecCallCC x right
                        return Elem(left,e,t') }
            | Elem _ -> alreadyExists t
        insertRecCallCC x t
    ) id

Please note that the complexity of the last implementation is not obfuscation – it avoids recreating nodes on the path to an already existing element (exercise 2.3 actually asks to do it using exceptions, which works just as well).

Share this post :

Traversing and transforming F# quotations: A guided tour

2009-06-13T15:25:00.000+01:00

There seems to be some lack of information about quotations – most is either short, a specific example, or is a bit outdated. The most comprehensive example is probably Tomáš Petříček’s Quotations Visualizer in the F# samples. His site is also one of the better resources about quotations that I’ve found. Another one with some recent activity is Alex Pedenko’s blog. Furthermore, even the otherwise excellent Expert F# book has little to say about it, and predates the major changes that were made in the September CTP.

Here I’ll focus on the important general patterns of using quotations. That is, I’m going to show how to traverse and transform quotations, independent of any specific example. I’m going to focus more on the API and programming aspects, than on introductory concepts, so this assumes some intermediate-level knowledge of F#. Basic knowledge about quotations doesn’t hurt either, as I‘ll make explanations terse.

Either way, this post represents some knowledge that took me a while to figure out on my own, piecing together scattered sources.

I would like to point out that once you get over the learning curve, working with quotations is actually enjoyable. I’ve been refraining from using them because I was put off by some bad experiences with System.Reflection (I think System.Reflection truly sucks as an API) and because I felt that to do anything useful, you’d almost be forced to support (i.e. at the very least provide default implementations of) every single construct in F#. It turns out that the quotations API is very enjoyable to work with and that there are built-in means to start small and focus on the things that are interesting to you.

The basics

In short, a quotation is metadata that represents the code of a particular function or code snippet, that gets compiled into the dll (along with the actual executable code, in some cases) by the F# compiler. To those of you who are familiar with LINQ Expression trees, it’s the same concept only F#’s quotations cover the entire reach of the F# language.

There are three ways to obtain a quotation:

1) Use the <@ @> operation around a code snippet to get a typed quotation of type Expr<’a>, where ‘a is the type of the actual value you put into the snippet. The Expr “wrapper” essentially indicates that we’re not dealing with an actual value of type ‘a, but instead with a reified representation of that value – the quotation:

let typedExpr = <@ 1 + 5 @>

let typedExpr2 = <@ fun i -> i + 5 @>

Sending these to FSI gives:

val typedExpr : Quotations.Expr<int> =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Value (1), Value (5)])
val typedExpr2 : Quotations.Expr<(int -> int)> =
  Lambda (i,
        Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
              [i, Value (5)]))

First notice the types: the first is Expr<int> because 1 + 5 of course is an int value. The second example illustrates a function value, of type Expr<int->int>.

FSI has printed the values of the quotations: a representation of the code! In fact, as we’ll soon see, the Expr type is nothing more than a discriminated union with one case for each possible language construct in F# (it’s not actually a discriminated union under the covers, but that’s how it’s abstracted, and the abstraction is very clean. It doesn’t hurt to think about it that way.)

2) Use the <@@ @@> operator around a code snippet to get an untyped quotation, of type Expr. Expr<’a> is a subtype of Expr, and every Expr<’a> can be converted to an Expr by calling .Raw:

let untypedExpr = <@@ 1 + 5 @@>

let untypedExpr2 = <@@ fun i -> i + 5 @@>

Sending to FSI gives:

val untypedExpr : Quotations.Expr =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Value (1), Value (5)])
val untypedExpr2 : Quotations.Expr =
  Lambda (i,
        Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
              [i, Value (5)]))

Pretty much exactly the same information, except for the type. For library writers, the Expr type does all the heavy lifting of inspecting and transforming quotations: since in a library you almost always want to write some code for any quotation, you cannot write this code in a generic way with typed quotations.

3) Using the ReflectedDefinition attribute on a top level function gives you the best of both worlds: the function can be called and executed as normal, but it can also be inspected as a quotation:

[<ReflectedDefinitionAttribute>]
let quotation i = i + 5

Based on a MethodInfo, the Expression.TryGetReflectedDefinition method allows you to get to the Expr associated with the function. The necessary metadata is actually marshaled into the dll when this function is compiled.

The Microsoft.FSharp.Quotations namespace

This namespace in the FSharp core libraries contains three modules and three types. The types are Expr, Expr<’a> and Var. The first two we’ve discussed already, the third one is just the representation of a variable.

The meat of quotations processing is in the module Quotations.Patterns and the static methods on Expr. If you compare these two, you’ll notice that for every active pattern in the Patterns modules, there is a static method on Expr. For example, you have Patters.Call(…) and Expr.Call(…), with equivalent signatures. This is no coincidence: the Patterns module contains all the patterns you’ll need to deconstruct a quotation expression. Together, these patterns can traverse any F# abstract syntax tree. It contains 32 active patterns (that’s a lot, but don’t despair yet: it gets better. ).

Its dual, the static methods on the Expr type, construct quotation expressions programmatically.

If you know F#, it shouldn’t be too hard to figure out what the arguments mean. For example:

Expr.Call : obj:Expr * methodInfo:MethodInfo * arguments:Expr list –> Expr

constructs an expression that represents a method call (defined by a methodInfo) on a target object (i.e. it’s an instance method), taking the given arguments. Conversely,

( |Call|_| ) : Expr -> (Expr option * MethodInfo * Expr list) option

is an active pattern that matches a method call, with an (optional) target, methodinfo and a list of arguments.

This duality makes it fairly easy to get started with constructing and deconstructing quotations. Try to make some quotations and print them using fsi – it will give you a good idea of what code constructs the patterns represent. Alternatively, use the quotation visualizer mentioned above.

Another module, Quotations.DerivedPatterns, contains additional active patterns that are not needed in the strict sense, but that represent some common use cases for deconstructing a quotation. An example is

( |SpecificCall|_| ) : Expr -> (Expr -> (Type list * Expr list) option)

which is a variant of Call that takes an expression and matches if the quotation is the given method or function call. The beauty of this particular active pattern is that you can use quotations to match on the given quotation:

let recognizePlus quotation =
    match quotation with
    | SpecificCall <@ (+) @> (types,exprs) -> printfn "Plus! types=%A  exprs=%A" types exprs
    | _ -> printfn "something else"

> recognizePlus <@ 1 + 2 @>;;
Plus! types=[System.Int32; System.Int32; System.Int32]  exprs=[Value (1); Value (2)]

Come on, this is still a lot of work, isn’t it?

That last example has one major shortcoming, which will hit you pretty hard when you’re trying to do anything useful with quotations. Even when you’re only interested in one particular kind of node (say, you’re interested in doing something with all (+) calls), you still have to walk the whole expression tree in order to be sure that you’ve seen all the method calls. Consider:

> recognizePlus <@ 1 * (2 + 3) @>;;
something else

Why? Because the tree looks like:

Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),
      [Value (1),
       Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
             [Value (2), Value (3)])])

so we’re calling multiply first – and our function doesn’t do anything with that. In order to find all plus calls, we need to look through the whole tree recursively – including the multiply call’s children. But doesn’t that mean that we’ll have to rewrite our recognizePlus function to incorporate a match on all of the 32 active patterns in Quotations.Patterns (or at least those that return child expressions, which is pretty much all of them) just to be able to traverse the whole expression tree looking for a plus call?

Luckily, no. This is were the third module in the Quotations namespace comes in.

The secret sauce: Quotations.ExprShape

This module is really the workhorse of pretty much anything you’ll do with quotations. Now, I believe this will come as a surprise to most people – in fact, it took me a bit of luck (when I saw it being used in passing, in a post on hubfs) to really understand what this module was all about. It was one of those moments for which a beautiful German word exists: Aha-Erlebnis.

This module’s mystery is in no small part thanks to its“terse” documentation. In fact, it’s so short I’ll reproduce it completely here:

val RebuildShapeCombination : obj * Expr list -> Expr	Re-build combination expressions. The first parameter should be an object returned by the ShapeCombination case of the active pattern in this module.
val ( \|ShapeVar\|ShapeLambda\|ShapeCombination\| ) : Expr -> Choice<Var,(Var * Expr),(obj * Expr list)>	An active pattern that performs a complete decomposition viewing the expression tree as a binding structure.

First, look at the active pattern. The key thing is that this active pattern is complete: every quotation will match with one of the three cases of the active pattern: either it is a variable (ShapeVar), a lambda (ShapeLambda) or a “combination” (ShapeCombination). So, we now have a general and complete decomposition of any quotation, and it is short:

let workhorse quotation =
    match quotation with
    | ShapeVar v -> ()
    | ShapeLambda (v,expr) -> ()
    | ShapeCombination (o, exprs) -> ()

Notice if you paste this in an .fs file that the compiler does not complain about any missing match cases, reinforcing my point. So, now we can do this recursively, which gives us:

let rec traverse quotation =
    match quotation with
    | ShapeVar v -> ()
    | ShapeLambda (v,expr) -> traverse expr
    | ShapeCombination (o, exprs) -> List.map traverse exprs |> ignore

Here’s the beauty: this simple function traverses all the expressions and sub-expressions in any quotation. You don’t have to deal with all 32 cases in order to do something with one node. This function should be the basis of all your work with traversing quotations: anything you want to do, as far as inspecting the tree goes, can be built on top of this simple structure. Let’s revisit our earlier example:

let rec recognizePlus' quotation =
    match quotation with
    | SpecificCall <@ (+) @> (types,exprs) -> 
        printfn "Plus! types=%A  exprs=%A" types exprs
        List.map recognizePlus' exprs |> ignore
    | ShapeVar v -> ()
    | ShapeLambda (v,expr) -> recognizePlus' expr
    | ShapeCombination (o, exprs) -> List.map recognizePlus' exprs |> ignore

Let’s run this on our failing example of earlier:

> recognizePlus' <@ 1 * (2 + 3) @>;;
Plus! types=[System.Int32; System.Int32; System.Int32]  exprs=[Value (2); Value (3)]

It sure found the plus now.

Transforming quotations

So far, we’ve just been inspecting the quotation. Now let’s actually do something with it. Again, the ExprShape module will be a big win: the workhorse here is the ShapeCombination and RebuildShapeCombination duality.

You might have noticed the o parameter in the ShapeCombination; this is an opaque marker that stores how the sub-expressions in a shape combination can be put back together , i.e. whether it is a function call, a let binding, or anything else that has child expressions. This is were the function RebuildShapeCombination comes into play: given an o marker and the right number and type of child expressions, it can put an expression deconstructed by ShapeCombination back together . So, whereas above we wrote a general traversal function for quotations, a general transformation function looks like:

let rec transform quotation =
    match quotation with
    | ShapeVar v -> Expr.Var v
    | ShapeLambda (v,expr) -> Expr.Lambda (v,transform expr)
    | ShapeCombination (o, exprs) -> RebuildShapeCombination (o,List.map transform exprs)

This function takes any quotation and transforms it into itself, visiting, deconstructing and reconstructing every node in the expression tree along the way.

If you’re familiar with a zipper data structure, this reminds me of it: the active patterns “open the zipper” and the RebuildShapeCombination function “closes the zipper”. (Actually, I’m not sure that the sub-expressions get reused or are made anew, but it seemed familiar anyway.)

So, let’s do some transformation: let’s replace all calls to (+) with calls to (-). (Maniacal laugh and organ playing):

let rec evilTransform quotation =
    let minus l r = <@@ %%l - %%r @@>
    match quotation with
    | SpecificCall <@ (+) @> (types,l::r::[]) -> 
        minus (evilTransform l) (evilTransform r)
    | ShapeVar v -> Expr.Var v
    | ShapeLambda (v,expr) -> Expr.Lambda (v,evilTransform expr)
    | ShapeCombination (o, exprs) -> RebuildShapeCombination (o,List.map evilTransform exprs)

Ignoring the specifics of the actual transformation, which I’ll get to in a moment, notice that the structure of the transformation is exactly the same as above, except now we’ve added one pattern to deal with the case we’re interested in: a call to addition. Essentially, this is saying: do something special for addition, and just traverse the tree, leaving it unchanged, for all the rest.

Splicing

Now, I know I said earlier that the Expr.Call static method is the dual of the Call active pattern, so you’d expect that I would have used that in the result of the SpecificCall match above. I could have done that, but instead I chose to demonstrate another useful technique for constructing expressions: splicing, denoted by the % or %% operator, for typed and untyped splicing respectively. All this operator does is insert an expression in a certain place (or places) into a quotation. So the minus function constructs a quotation that represents the subtraction of two given expressions (this doesn’t always make sense – in that case we’ll get a runtime exception with untyped quotations). Splicing is a very readable and versatile way of constructing expressions, because you can actually write your expressions in F# instead of using Expr.Call and friends.

The proof of the pudding

In the F# powerpack, there are some useful (but somewhat experimental) functions to actually compile and evaluate any F# quotation. The process is somewhat convoluted: the quotation trees are first translated to .NET Expressions, and then that API is used to compile them. This comes with a significant performance hit: code compiled using that route can be a factor of 5 slower. So don’t use it for optimization. So far, I haven’t run into any limitations yet, and it’s a nice way to check whether everything works:

let before = <@ 1 + 2 * 3 + 5 @>
let after = evilTransform <@ 1 + 2 * 3 + 5 @>
printfn "%A" <| before.EvalUntyped()
printfn "%A" <| after.EvalUntyped()

Shows:

12
-10

val evilTransform : Expr -> Expr
val before : Expr<int> =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
             [Value (1),
              Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),
                    [Value (2), Value (3)])]), Value (5)])
val after : Expr =
  Call (None, Int32 op_Subtraction[Int32,Int32,Int32](Int32, Int32),
      [Call (None, Int32 op_Subtraction[Int32,Int32,Int32](Int32, Int32),
             [Value (1),
              Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),
                    [Value (2), Value (3)])]), Value (5)])

Pretty cool, and it opens up all kinds of interesting possibilities. For example, you can write a lazy transformer, which inserts lazy and force in the appropriate places to simulate call-by-need semantics in F#. You can add side-effects to print the result of each call as it is evaluated. Or you can transform the expression in something completely different – SQL, PHP, FPGA instructions, whatever you want.

Conclusions

The three main things you should know about the quotations API:

Quotations.Expr and Quotations.Patterns are each other’s dual: they are used for constructing and deconstructing Expr types respectively;
Quotations.ExprShape contains the workhorse of any quotations-using implementation: a zipper-like pattern for traversing and transforming any quotation in a straightforward way;
Splicing is used to effectively and readably construct parameterized expressions as an alternative to Expr.Whatever calls.

Like I said before, I think the API strikes an excellent balance between simplicity and abstraction. F#’s features come together nicely to provide a clean development experience. I was somewhat afraid of quotations before, because I had an image in my mind that it would be messy, lots of work, and lots of special cases. Turns out it isn’t, and I hope this post will do its part in getting some more attention to this aspect of F#.

Download the example .fs file. Don’t forget to add references to FSharp.PowerPack and FSharp.PowerPack.Linq, if you want to run the dynamic compilation examples.

Technorati: F# quotations

Share this post :

Announcing FsCheck 0.6.1

2009-05-23T17:36:00.000+01:00

No functional changes, just an update as a result of the May CTP released by the F# team.

Get it here.

Change log:

Many name changes as a result of name changes in the F# API
Used the new formatting API, which gets rid of a bunch of obsolete warnings
Tried to solve issues resulting from changed initialization order
Added a standalone version of the FsCheck binary, to accommodate C#/VB users better
Added a contributors file. Want your name in there? Then contribute ;)

Enjoy the new CTP!

Share this post :

How to test DSLs (and: FsChecking FsCheck)

2009-05-12T21:50:00.001+01:00

There are two causes for this post.

First, I’ve been watching videos from Lang.NET and DSL DevCon, so I’m in language-mode. It occurred to me that (domain specific) languages seem difficult to test using traditional unit tests: after all, the usage possibilities are far greater for a language than for, say, a typical user interface (maybe this means that typical user interfaces suck - you decide). The word “combinator library”, which are internal DSLs avant la lettre, says it all: the usage possibilities are combinatorial. Classic, example based unit testing thus becomes combinatorially expensive as well.

Second, I’ve been saying in the last release announcement of FsCheck that I wanted to write some FsChecks for FsCheck itself. So far, this effort is about 60% complete. As a sort of challenge, I want to check as much as possible from FsCheck without any traditional example-based unit testing – in other words, I want to test FsCheck using only FsCheck (and maybe some Pex and Code Contracts later on).

FsCheck itself consists of basically two internal DSLs: one for constructing random value generators for whatever value it is your tests need, and one for constructing properties: basically assertions augmented with property combinators for adding labels, classifying generated values and such. It’s the latter DSL that I’m going to test, and draw some general conclusions that may apply to testing other DSLs or even general purpose languages as well.

To see what we’re dealing with, here’s an example of using the property DSL:

let prop_InsertCombined (x:int) xs = 
    ordered xs ==> (ordered (insert x xs))
        |> classify (ordered (x::xs)) "at-head"
        |> classify (ordered (xs @ [x])) "at-tail"
        |> collect (List.length xs)
quickCheck prop_InsertCombined

This property asserts that the insert function maintains the invariant that the list is ordered. The classify and collect property combinators are used to gather some information about the generated data. So in this test, there are three property combinators at work: implies (==>), classify and collect. Also, the arguments to the property (x and xs) are implicitly universally quantified using the forAll property combinator. These and more combinators in FsCheck can be combined an arbitrary ways, so testing this using example-based testing can be quite tedious. Can FsCheck do better?

The property DSL’s syntax tree

First, we’re going to need to generate an arbitrary property, i.e. an arbitrary combination of property combinators. To do that, I made a symbolic representation of the property language – a sort of abstract syntax tree of the language. It’s no secret that discriminated unions are great for this, and this case is not different:

type SymProp =  | Unit | Bool of bool | Exception
                | ForAll of int * SymProp
                | Implies of bool * SymProp
                | Classify of bool * string * SymProp
                | Collect of int * SymProp

So, a property can consist of, respectively:

A function that returns the unit value;
A function that returns a bool value;
A function that throws an exception;
A function that uses the implies combinator, which needs two arguments: a boolean condition and another property;
A function that classifies the generated values, which needs three arguments: a boolean condition, the name to classify with if the condition is true and another property;
A function that collects values, which takes two arguments: the value to collect, and another property.

Note that I’ve made some simplifications here: in fact forAll takes a generator that generates values of an arbitrary type – but since we’re not testing generators here, I’ve assumed the forAll always generates a constant int value. Also, collect would normally collect a (function of a) generated value, but it’s here constrained to collecting a constant int value.

We can build an actual property from this symbolic representation:

let rec private toProperty prop =
        match prop with
        | Unit -> property ()
        | Bool b -> property b
        | Exception -> property (lazy (raise <| InvalidOperationException()))
        | ForAll (i,prop) -> forAll (constant i) (fun i -> toProperty prop)
        | Implies (b,prop) -> b ==> (toProperty prop)
        | Classify (b,stamp,prop) -> classify b stamp (toProperty prop)
        | Collect (i,prop) -> collect i (toProperty prop)

The simplifications are plainly visible here.

Defining the semantics of properties

Now, let’s define a specification of what a symbolic property means, in terms of what it should produce as Result. Result is an internal datatype used by FsCheck to track the result of one execution of a property. This is the gist of it:

type Outcome = 
    | Timeout of int
    | Exception of exn
    | False
    | True
    | Rejected

type Result = 
    {   Outcome     : Outcome
        Stamp       : list<string>
        Labels      : Set<string>
        Arguments   : list<obj> }

So, a result tracks the outcome of a property: timed out, raised exception, returned false or true, or value rejected. The latter means a generated value did not pass the condition of an implies combinator. Furthermore, it also tracks the generated arguments, the stamps applied using classify and collect, as well as labels which are not tested here.

And here is a formal, executable specification of a subset of the FsCheck property DSL:

let rec private determineResult prop =
        let addStamp stamp res = { res with Stamp = stamp :: res.Stamp }
        let addArgument arg res = { res with Arguments = arg :: res.Arguments }
        match prop with
        | Unit -> succeeded
        | Bool true -> succeeded
        | Bool false -> failed
        | Exception  -> exc <| InvalidOperationException()
        | ForAll (i,prop) -> determineResult prop |> addArgument i
        | Implies (true,prop) -> determineResult prop
        | Implies (false,_) -> rejected
        | Classify (true,stamp,prop) -> determineResult prop |> addStamp stamp
        | Classify (false,_,prop) -> determineResult prop
        | Collect (i,prop) -> determineResult prop |> addStamp (any_to_string i)

You can check this definition with the FsCheck documentation. For example, it shows that an assertion that returns unit or true is interpreted as succeeded, false as failed and so on. The succeeded function and friends are defined in FsCheck and just construct basic Result instances:

let private result =
  { Outcome     = Rejected
  ; Stamp       = []
  ; Labels       = Set.empty
  ; Arguments   = []
  }

let internal failed = { result with Outcome = False }

The test

Armed with these functions, we can write our test:

let SymProperty (symprop:SymProp) = 
        let expected = determineResult symprop 
        let (MkRose (Common.Lazy actual,_)) = generate 1 (Random.newSeed()) (toProperty symprop) 
        areSame expected actual
        |> label (sprintf "expected = %A - actual = %A" expected actual)
        |> collect symprop

Ignore the specifics of the “actual” symbol definition – it executes an actual property and extracts the Result from it. The gist of the property is the comparison between the actual Result of the execution of the property (that was built from the symbolic property representation), and compare that with our expected semantics. Just to see what kind of properties we’re testing, I’ve also added a collect combinator, as well as a label to see what’s wrong if the test should fail. Thanks to FsCheck’s built-in discriminated union generator, running this gives:

Property.SymProperty-Ok, passed 100 tests.
22% Exception.
12% Unit.
6% Bool true.
6% Bool false.
4% Classify (false,"",Unit).
2% Implies (false,Exception).
2% Classify (true,"",Unit).
2% Classify (true,"",Exception).
2% Classify (false,"",Exception).
1% Implies (true,Exception).
1% Implies (true,Collect (2,Bool true)).
1% Implies (true,Collect (0,Unit)).
1% Implies (true,Collect (0,Collect (0,Bool false))).
(and so on)

Generating more interesting properties

This leaves something to be desired: the depth of combinations isn’t very high, and almost half of the generated properties are the trivial bool, unit or exception cases. One way of increasing this depth is by increasing the size of the generator, but that didn’t work very well: it mostly increased the length of the generated strings, without increasing the depth too much. The reason is that three of the seven options are “leaf” nodes, where generation ends. So I wrote my own generator for the SymProp type:

let rec private symPropGen =
        let rec recGen size =
            match size with
            | 0 -> oneof [constant Unit; liftGen (Bool) arbitrary; constant Exception]
            | n when n>0 ->
                let subProp = recGen (size/2)
                oneof   [ liftGen2 (curry ForAll) arbitrary (subProp)
                        ; liftGen2 (curry Implies) arbitrary (subProp)
                        ; liftGen2 (curry Collect) arbitrary (subProp)
                        ; liftGen3 (fun b s p -> Classify (b,s,p)) arbitrary arbitrary (subProp)]
            | _ -> failwith "symPropGen: size must be positive"
        sized recGen

If you’re somewhat familiar with FsCheck’s generator combinators, this shouldn’t be hard to read. The idea is that we only generate one of the leaf nodes if the size equals zero, and halve the size if we generate a “real” property combinator to ensure the generation ends at some point. Let’s change the property to incorporate this generator:

let Property = 
        forAllShrink symPropGen shrink (fun symprop ->
            let expected = determineResult symprop 
            let (MkRose (Common.Lazy actual,_)) = generate 1 (Random.newSeed()) (toProperty symprop) 
            areSame expected actual
            |> label (sprintf "expected = %A - actual = %A" expected actual)
            |> collect (depth symprop)

I added a depth function that calculates the depth of the generated symbolic property (i.e. depth of Unit, Bool and Exception is zero, and the rest adds one to the depth of it’s subproperty). Running this gives:

Property.get_Property-Ok, passed 100 tests.
26% 5.
26% 4.
18% 3.
12% 2.
7% 6.
6% 0.
4% 1.

which shows that FsCheck is now generating more properties with greater depth (4-5), and trivial properties only 6% of the time.

Conclusion

This post showed an approach for testing DSLs, combinator libraries or “language-oriented” programs, whatever you’d like to call it:

Write a symbolic representation of the abstract syntax tree of the language you want to test. This symbolic representation is used to abstract from details you don’t want to test, to define semantics of the language later on, and it to generate output for counter-examples that FsCheck may find.
Generate the actual representation in your compiler or interpreter from the symbolic representation.
Specify the semantics of the symbolic representation.
Rely on FsCheck’s built-in generators, or make your own generator to generate the symbolic representation.
Write an FsCheck property to compare the actual with the expected semantics.

This approach may even be usable for testing compilers of general purpose programming languages. The effort involved will be much larger, but it’s easy to start small.

Want more of this? Also check out the Checks.fs file in the FsCheck distribution for a complete test of the FsCheck property language.

Share this post :

Announcing FsCheck 0.6: Dot is the new pipe

2009-05-12T21:17:00.000+01:00

It is about time to release a new version of FsCheck, and here it is.

What’s new in this release?

A fluent interface for C# and VB

This is in prototype stage at the moment, and has some limitations with respect to the F# interface, but I would say it’s about 90% functional. An example of a property in C#:

Spec.ForAny<int, int[]>((x, xs) => xs.Insert(x).IsOrdered())
                .When((x, xs) => xs.IsOrdered())
                .Classify((x, xs) => new int[] { x }.Concat(xs).IsOrdered(), "at-head")
                .Classify((x, xs) => xs.Concat(new int[] { x }).IsOrdered(), "at-tail")
                .QuickCheck("InsertClassify");

This property is the equivalent of the following in F#:

let prop_InsertClassify (x:int) xs = 
    ordered xs ==> (ordered (insert x xs))
    |> classify (ordered (x::xs)) "at-head"
    |> classify (ordered (xs @ [x])) "at-tail" 
quickCheck prop_InsertClassify

As you can see, it’s about the same amount of code, but because of the fluent interface I have to add a class for each number of type arguments - currently limited to three. Ideally, I’d like to generate some code for classes up to six or nine, but for the moment it’s all copy-paste and you can only write properties with up to three parameters this way. For the rest, almost everything should be working: you can register generators, provide configuration, add shrinkers, and write generators using some combinators and LINQ:

var gen = from x in Any.OfType<int>()
          from y in Any.IntBetween(5, 10)
          where x > 5
          select new { Fst = x, Snd = y };

Pretty neat.

Incidentally, there is no C# code in FsCheck itself, and the fluent interface is all pure F# code. This was a good test to see how interoperable F# really is. Overall, the experience has been great, with just a few minor hiccups.

I translated most of the F# examples from the documentation to C# as well, you can find those in the F# source distribution.

Possibility to replay a test run. FsCheck now displays the seed it used to start a test run when it fails. You can give this seed to a configuration parameter, so that FsCheck will repeat the run with exactly the same generated values:

check { quick with Name="Counter-replay"; Replay = Some <| Random.StdGen (395461793,1) } (asProperty spec)

Various bug fixes and updates to xml docs.
I’m making headway in testing FsCheck using FsCheck itself. It’s an interesting experience, and I have a blog post lined up about it.

The C#/VB “mainstream” support is something that I hope to continue to improve – I also plan to add reflective object generators and Gallio integration, mainly as a means to get some more attention for FsCheck. It’s also an interesting exercise to compare approaches. So far, if you know F#, I’d stick with it, but you can see that LINQ is occasionally very elegant for defining generators.

Happy FsChecking!

Share this post :

Tests are not specifications

2009-05-06T21:03:00.000+01:00

There seems to be some consensus in the TDD and BDD community that the tests (or behaviors) for a given software system constitute an (executable) specification of the system.

Wrong.

A specification is an unambiguous and complete description of a system or subsystem. Or at least it should be a heroic attempt.

A test, whether written as a traditional unit test, or as an executable scenario in BDD is neither unambiguous nor complete. Worse, it’s not even trying.

A test is almost always written as one specific example of how a subsystem should behave. An implementation that can fail on other examples will pass the test, and so still fulfill the non-specification. Furthermore, there are many implementations with wildly differing behavior that can pass the test.Doesn't sound like a specification to me, or at least not a good one.

In fact, if TDD/BDD advocates would really follow their advice to program no more than what the tests test, then given the following test:

Assert.Equal (Reverse [1,2,3] , [3,2,1])

they should implement the pseudo function:

Reverse list = [3,2,1]

Compare with what FsCheck's properties look like (again, in pseudo-code):

Reverse [x] = [x]

Reverse (x::xs) = Reverse xs @ [x]

That's what I call a specification: unambiguous, and complete. So TDD talks the talk, but does not walk the walk.

Before you start commenting, foam at the mouth, I’m not saying testing is bad – on the contrary. It’s just that you should stop kidding yourself by calling tests specifications. It’s like saying that “8” is an algorithm for adding two numbers, because it happens to work for 3 and 5.

Using frameworks and tools such as Code Contracts, Pex and FsCheck (I’m being completely unbiased here, of course), you will take a big step towards writing real specifications, not tests. That’s where their real value is.

Share this post :

FsChecking dnAnalytics – Part 3

2009-03-13T15:37:00.000Z

Thanks to Marcus Cuda, coordinator of the dnAnalytics project, I can end my little series (part 1 – part 2) with a nice result: the dnAnalytics team have decided to incorporate FsCheck in their testing. Cool! So next time, I’ll probably choose another project to “experiment” with (all in the interest of science), but this post I had lined up already.

Last time I described one kind of property based on invariants that hold over two or more related functions or methods. The example I gave was mathematically oriented (i.e. directly originating from the problem domain). Today I’ll show a property that should be familiar to many of you, and is applicable for quite a few of your types.

It happens that the Complex type in dnAnalytics can be constructed by parsing it from a string such as “1 + 3.0i”. On the other hand, calling ToString() on a Complex object produces a similar string. So, we specify that the ToString of a Complex value can be parsed, and produces the original value again:

let prop_ParseToString (c:Complex) =
    let actual = Complex.Parse(c.ToString(CultureInfo.InvariantCulture), CultureInfo.InvariantCulture)
    if Complex.IsInfinity(c) then Complex.IsInfinity(actual)
    elif Complex.IsNaN(c) then Complex.IsNaN(actual)
    else equalsUpTo 12 c actual

The only thing to watch out for is again the special values infinity and NaN. Also, since the ToString of a complex does not return a representation of Complex value up to its complete precision, we’re just checking equality up to a certain number of significant digits by using the equalsTo function.

In dnAnalytics version 0.3, running this property produces:

Parse ToString-Falsifiable, after 4 tests (0 shrinks):
0 + 1,79769313486232E+308i
with exception:
System.FormatException: One of the identified items was in a bad format

This bug was due to the fact that the string is split on the basis of the ‘+’ character – which is also used when a floating point number is printed in scientific notation – clearly visible in the counter example given by FsCheck. This is a confirmed bug that is solved by now. Apparently the same property also detected a bug when parsing NaN and Infinity values.

This again shows that writing properties, or specifications, for your code in FsCheck is easy, short, and most importantly, finds bugs!

The kind of property that is described here you can write for any pair of functions or methods that convert a representation A to a representation B and back (in this case, a Complex value to a string and back). It can be generalized as follows:

let toAndFro x transformTo transformFrom equals =
    x |> transformTo |> transformFrom |> equals x

Applied to the example:

let prop_ParseToString (c:Complex) =
    toAndFro c 
        (fun c -> c.ToString(CultureInfo.InvariantCulture)) 
        (fun s -> Complex.Parse(s, CultureInfo.InvariantCulture)) 
        (fun c actual -> 
            if Complex.IsInfinity(c) then Complex.IsInfinity(actual)
            elif Complex.IsNaN(c) then Complex.IsNaN(actual)
            else equalsUpTo 12 c actual)

This kind of property is fairly common: think about Parse/ToString, serializing/deserializing, and all kinds of conversion and formatting functions.

(I was at TechDays 2009 in Antwerp this week, and watched a presentation about Pex by Peli de Halleux. He showed a similar pattern when using Pex to write parameterized unit tests. In fact, a lot of the patterns and scenarios he described sounded very recognizable to my ears. If you like FsCheck, definitely check out Pex as well.)

Conclusion

One project converted, a gazillion to go. If you maintain an open source project and are unsure or even better, skeptical! how FsCheck can be used for testing in your project, contact me and you’ll probably get me crazy enough to write some tests for you. I choose a scientific domain because F# is targeted towards that, but the applicability goes far beyond that, as I hope to have showed in this post. On the other hand, I am also curious for what kind of projects or domains you are already using FsCheck. Did you encounter testing patterns like “toAndFro” that you’d like to share? Got any wishes? Don’t hesitate to let me know. Or even better, spread the word and blog about FsCheck yourself.

Happy FsChecking!

Technorati: fscheck,dnanalytics,random testing,F#

del.icio.us Tags: fscheck,dnanalytics,random testing,F#

Share this post :

FsCheck on Ohloh

2009-03-06T20:14:00.000Z

I found out about Ohloh recently and decided to play around with it by adding FsCheck. From FsCheck’s Ohloh page we learn that:

it’s mostly written in Make. Uhm, what?
it has a short source control history (that’s right: I do all my local development using Mercurial, and only export to codeplex on release)
it has a single active developer (I’m not single, I have a lovely wife!)
it has very few source code comments (I didn’t put any comments in the Makefile. Sorry.)

It seems that the appraisal of an open source project can not be replaced by a small shell script…

Anyway, it’s nice to see how many related projects there are (and how many projects in general). If you’re in the neighborhood, come say hi, add a rating, add a user, whatever…

Technorati: fscheck,ohloh

FsCheck 0.5.1

2009-03-01T11:54:00.001Z

Just a short note to announce v0.5.1 of FsCheck, which fixes some bugs in 0.5 and includes one improvement in the category I-can't-believe-I-didn't-see-this-earlier.

Bug fix: no more escaping exceptions when using lazy
Bug fix: no extra initialization (init.Value) necessary when registering generators 'early'
check (and quickCheck, verboseCheck) now take a simple value 'a instead of a function value 'a->'b as argument, so you can just write 'quickCheck <| forAll ...' instead of 'quickCheck (fun () -> forAll ...)'.

I don't see any reason not to update if you're using 0.5.

Technorati: F#,FsCheck

FsChecking dnAnalytics Part 2

2009-02-27T23:10:00.000Z

In part 1, I started out with defining some FsCheck properties on dnAnalytics' Complex class. The properties I showed were fairly straightforward: break the complex number in its real and imaginary part, apply the definition of the operation and compare that to the result of the actual operation under test.

A possible critique on this kind of property is that it partly duplicates the implementation of the operation under test. In my experience, it almost never does completely: there is of course some overlap, but the property is invariably simpler, takes into account less detail, and is easier to understand. The property is mostly unusable for an actual implementation, for example because it is inefficient, is not tail recursive, causes more rounding errors etc. The only important thing about such a property is that is simple, so that you are sure it is correct (in fact, FsCheck will verify that it is correct...). So this critique is not justified.

But anyway, such definition properties are not the only kind that can be written using FsCheck. Today we'll look at properties that relate different operations (functions, methods) of the same class or module together.

As an example, we'll test that the complex numbers form a field over addition and multiplication, i.e. the field C+,*.

Now, the first thing to realize here is that instances of type Complex do not form an actual field, due to the presence of NaN, Infinity, rounding errors and overflow. So, for the purpose of this property we're about to write, we need to be able to generate Complex instances where these values are not generated.

There is a nice trick to define a custom generator that filters or otherwise manipulates values from another generator but keeps the other generator's type. First define a wrapper union type and define a generator for that:

type NoSpecials = NoSpecials of Complex

type Generators =
    static member NoSpecials() =
        { new Arbitrary<NoSpecials>() with
            override x.Arbitrary = 
                arbitrary 
                |> suchThat (fun (C (r,i) as a) -> 
                    not (Complex.IsInfinity(a)) && 
                    not (Complex.IsNaN(a))      && 
                    r > 1e-16  && r < 1e16      &&
                    i > 1e-16  && i < 1e16  )  
                |> fmapGen NoSpecials
            override x.Shrink (NoSpecials c) = shrink c |> Seq.map NoSpecials
        }

Notice how special values like NaN, and very low and high values are filtered out in the generator using the suchThat generator combinator.

Now, we can write a property with a signature like:

let prop_ComplexField (NoSpecials a,NoSpecials b,NoSpecials c) =

which will generate "non-special" complex values in a, b and c. F#'s pattern matching and FsCheck's type directed value generation come together nicely here. (The alternative for this style is to use an explicit generator using forAll or forAllShrink).

Our property should check that both addition and multiplication are commutative, associative, distributive and have an an identity. So, the following functions will be useful:

let (=~=) (expected:Complex) actual = 
    try TestHelper.TestRelativeError(expected, actual, 2e-10); true with _ -> false

let commutative f (a,b) = f a b =~= f b a 
let associative f (a,b,c) = f (f a b) c =~=  f a (f b c) //e.g. (a+b)+c = a+(b+c)
let rightdistributive f g (a,b,c) =  g (f a b) c =~= f (g a c) (g b c) //e.g. (a+b)c = ac+bc
let leftdistributive f g (a,b,c) = g c (f a b) =~= f (g c a) (g c b) // e.g. c(a+b) = ca+cb
let identity f id a = f a id = a

Armed with these, our property can be written as:

let prop_ComplexField (NoSpecials a,NoSpecials b,NoSpecials c) =
    commutative (+) (a,b)               |@ "+ commutative"      .&.
    commutative (*) (a,b)               |@ "* commutative"      .&.
    associative (+) (a,b,c)             |@ "+ associative"      .&.
    associative (*) (a,b,c)             |@ "* associative"      .&.
    rightdistributive (+) (*) (a,b,c)   |@ "right distributive" .&.
    leftdistributive (+) (*) (a,b,c)    |@ "left distributive"  .&.
    identity (+) Complex.Zero a         |@ "0 is identity of +" .&.
    identity (*) Complex.One a          |@ "1 is identity of *" 
quickCheckN "Complex numbers are a field"  prop_ComplexField

Which produces:

Complex numbers are a field-Ok, passed 100 tests.

It should be clear that the possibilities for coming up with such properties are almost limitless, and that you'll never have to repeat any part of your implementation to express them.

Conclusion

FsCheck makes it easy to test whether relations between a set of related methods or functions hold. This technique is in my experience sometimes neglected when unit testing, because of the focus on the unit. Nevertheless, such properties can have great value in documentation and testing.

In this post I took a few shortcuts to avoid having to deal with the "specials", and so in that sense this specification could be called misleading because indeed, instances of Complex do not form a field. I did this for two reasons. First, I wanted to show the wrapper type/pattern match technique to define derived generators that generate a subset of the values of an original generator. Second, I wanted to show that FsCheck makes you work if you want to ignore these special values - in other words, you have to make a very conscious decision to ignore them. In contrast, using unit tests the default is that you forget about these values until it's too late.

A third point I wanted to show is that with a little refactoring and common sense, you can write elegant and very readable properties that could conceivably be part of your documentation - in other words, true executable specifications.

Download fs file

Technorati: F#,fscheck case study,fscheck,dnAnalytics

FsChecking dnAnalytics

2009-02-23T22:06:00.000Z

I've been thinking lately what I can do to make FsCheck more widely used. Whenever I write "regular" unit tests, I feel like I'm back in the stone ages. It just feels so clumsy and tedious. Why don't more people see this? Is it because there's a learning curve? Surely that's part of it, but the benefit is so huge that this can't be the whole story. I came across this question on stackoverflow, and read a lot of misunderstandings about random testing (luckily the chosen answer was well-informed, and even mentions FsCheck). I could respond to each of those, but I'll keep that to a later post; instead, I'm resolved to convert the world to FsCheck, even if I have to do it one project at a time ;)

Today's candidate: dnAnalytics. dnAnalytics makes a good candidate for FsChecking because it is in the mathematical field - finding properties for the functionality to satisfy should be straightforward: there's millennia of mathematical knowledge to choose from. Secondly, dnAnalytics already has some tests that I can trash later. Also, dnAnalytics has an F# interface which I won't be using in this post, but at least the maintainers are familiar with F#, so I have some hope of "converting" them. Finally, dnAnalytics has quite a few downloads (over a 1000), so hopefully this can raise visibility of FsCheck outside the F# community.

Without further ado, let's go find bugs! (I'll give it away now to keep you interested, as this has become a long post: I found a bug...read on.)

For my first experiment, I choose to test the Complex class, which represents a complex number a+bi, along with some operations. Fairly straightforward stuff that even a mathematically challenged person like myself can follow.

For education and amusement, I'll give an overview of how the tests I wrote revolved over time - errors and imperfections included.

The complex number generator

To test a type, typically the first step to take when using FsCheck is writing a generator for a type. In this case, we'll just be using a generator for a tuple of two floats, and map that to a complex number:

type Generators =
    static member Complex() =
        { new Arbitrary<Complex>() with
            override x.Arbitrary = two arbitrary |> fmapGen ( fun (a,b) -> new Complex(a,b))
            override x.Shrink (C (r,i)) = 
                shrink (r,i)  
                |> Seq.map (fun (r,i) -> new Complex(r,i))
        }
registerGenerators<Generators>()

Pretty easy. The shrink function also exploits the relation between a complex number and a pair of floats. In case you're wondering, I added an active pattern C to deal with the Complex class, it's just:

let (|C|) (c:Complex) = (c.Real, c.Imaginary)

The Absolute of a complex number

I started out with testing the Complex type's Absolute method. It's supposed to return the Absolute value of the Complex instance it's applied to. Here's the property I wrote:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @| (lhs = rhs)

Basically this just checks that the outcome of the Absolute method is equal to the mathematical definition of the absolute value of a complex number. The sprintf and the label operator @| are there to display the intermediate values should the property fail. And failing it does:

Absolute-Falsifiable, after 6 tests (1 shrink):
Label of failing property: lhs=NaN (Niet-een-getal), rhs=NaN (Niet-een-getal)
NaN

Classic mistake: NaN is a special case; NaN is never equal to NaN. That's easily solved:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    (if Complex.IsNaN(c) then Double.IsNaN(lhs) else lhs = rhs)

produces

Absolute-Falsifiable, after 10 tests (2 shrinks):
Label of failing property: lhs=7,00446286306095, rhs=7,00446286306095
7 + 0,25i

Hmm. Instead of looking up how I could see all of a float's significant digits, I just assumed a rounding error. I explored dnAnalytics existing tests and found just the thing to deal with that: a method to test equality taking into account a relative error. Using that method in the property results in:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    (   if Complex.IsNaN(c) then Double.IsNaN(lhs) 
        else TestHelper.TestRelativeError(lhs, rhs, 2e-16);true)

And yes:

Absolute-Ok, passed 100 tests.

Notice that FsCheck works nicely with NUnit here; suppose we introduce a "bug" by adding 1 to the right hand side:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    (   if Complex.IsNaN(c) then Double.IsNaN(lhs) 
        else TestHelper.TestRelativeError(lhs, rhs+1.0, 2e-16);true)

produces:

Absolute-Falsifiable, after 1 test (0 shrinks):
0 + 0i
with exception:
NUnit.Framework.AssertionException:   Expected: less than 2E-16.0d
But was: 1.0d

   at NUnit.Framework.Assert.That(Object actual, Constraint constraint, String message, Object[] args)
   at NUnit.Framework.Assert.Less(Double arg1, Double arg2, String message, Object[] args)
   at NUnit.Framework.Assert.Less(Double arg1, Double arg2)
   at dnAnalytics.Tests.TestHelper.TestRelativeError(Double expected, Double approx, Double acceptableError) in c:\Documents and Settings\Kurt\My Documents\dnAnalytics\0.3\src\dnAnalytics.Tests\TestHelper.cs:line 53
   at Complex.prop_Absolute(Complex _arg1) in C:\Documents and Settings\Kurt\MyDocuments\dnAnalytics\0.3\src\dnAnalytics.FsCheck\Complex.fs:line 32
   at FsCheck.Property.evaluate[T,U](FastFunc`2 body, T a) in C:\Documents and Settings\Kurt\My Documents\FsCheck\FsCheck\Property.fs:line 162

But wait! Why aren't our labels displayed? We've found a bug...in FsCheck :) Hold on, I didn't con you earlier, I really did find a bug in dnAnalytics as well.

People can get a bit nervous now because they're not actually seeing what values FsCheck is generating. Let's find out:

let prop_Absolute (C (r,i) as c) = 
    let lhs = c.Absolute
    let rhs = Math.Sqrt( r*r + i*i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    if Complex.IsNaN(c) then Double.IsNaN(lhs) 
    else TestHelper.TestRelativeError(lhs, rhs, 2e-16);true
    |> classify (Complex.IsNaN(c)) "NaN"
    |> classify (Complex.IsInfinity(c)) "Infinity"
    |> classify (c = Complex.Zero) "Zero"
    |> classify (c = Complex.One) "One"

Absolute-Ok, passed 100 tests.
17% Infinity.
8% NaN.
2% Zero.

As you can see, using the classify combinator you can make FsCheck print out the ratio of test cases that fulfill a certain criterion. Here we learn that One is never generated; and infinity quite a bit. This is due to the fact that the built in generator for floats generates these special values with preference. We can change this behavior by changing the generator. Suppose we'd like to generate the value One also:

override x.Arbitrary = 
  frequency   [ (98,two arbitrary |> fmapGen ( fun (a,b) -> new Complex(a,b)))
              ; (2, constant Complex.One) ]

Absolute-Ok, passed 100 tests.
10% Infinity.
9% NaN.
4% Zero.
2% One.
1% Infinity, NaN.

Easy enough. Our generator now indeed generates One as well.

But hold on: we see also that a Complex number can be both Infinity and NaN. That doens't make sense. Let's write a property to check this:

let prop_NaNInfinity (c:Complex) =
    not ( Complex.IsInfinity(c) &&  Complex.IsNaN(c))
checkName  "Both NaN and Infinity" { quick with MaxTest = 1000} prop_NaNInfinity

Note that I didn't use the usual quickCheckN function to run the tests, because the Absolute test indicated that only one test in a hundred exhibited the behavior. So I made FsCheck run this test a bit more, 1000 times to be exact. Running this sure enough produces:

Both NaN and Infinity-Falsifiable, after 418 tests (0 shrinks):
NaN

and this find was confirmed as a bug by the dnAnalytics team. A small victory for FsCheck.

The conjugate of a complex number

Let's do one more: finding the conjugate.

let prop_Conjugate (C (r,i) as c) =
    let lhs = c.Conjugate
    let rhs = new Complex(r,-i)
    sprintf "lhs=%O, rhs=%O" lhs rhs @|
    if Complex.IsNaN(c) then Complex.IsNaN(lhs) 
    else lhs = rhs

Since the Absolute property, I've become a bit wiser and factored in the possibility of NaN from the start. Running this gives:

Conjugate-Ok, passed 100 tests.

And all is well. Except one thing: our tests like a bit ugly, because we had to duplicate some code.

Red, green, refactor!

We're going to refactor two things.

First, all the classify's we've added to the Absolute property are actually common to every property where we use our Complex generator. These kinds of "tests" are not uncommon when writing a new FsCheck generator - for example, it ensures that our generator does not throw an exception when generating values (which can happen when certain objects are constructed). I've taken the habit of separating these kinds of tests into a single separate property:

let prop_ComplexGen c = 
    ()
    |> classify (Complex.IsNaN(c)) "NaN"
    |> classify (Complex.IsInfinity(c)) "Infinity"
    |> classify (c = Complex.Zero) "Zero"
    |> classify (c = Complex.One) "One"

And we leave these classify's out of the other properties. (Note that a property that returns unit or true is interpreted as succeeded by FsCheck. An exception or false indicates failure.)

Then, we add the following helper method to abstract out the labeling of left and right hand side; cleaning it up in the process:

let compare expected actual prop = 
      sprintf "expected=%O, actual=%O" expected actual @| (prop expected actual)

Now our two properties can be written:

let prop_Absolute (C (r,i) as c) = 
    compare (Math.Sqrt(r*r + i*i)) c.Absolute (fun expected actual ->
        if Complex.IsNaN(c) then Double.IsNaN(actual) 
        else TestHelper.TestRelativeError(expected, actual, 2e-16);true)

let prop_Conjugate (C (r,i) as c) =
    compare (Complex(r,-i)) c.Conjugate (fun expected actual ->
        if Complex.IsNaN(c) then Complex.IsNaN(actual) 
        else expected = actual)

A successful experiment

In my eyes, the FsCheck based tests are hugely superior to the original tests, for the following reasons.

First, we've replaced 2 x 100 hand-written tests with presumably manually calculated values in dnAnalytics with just a few lines of code. An excerpt from the original tests:

[Test]
public void Absolute()
{
  TestHelper.TestRelativeError(ComplexMath.Absolute(new Complex(0.0, 1.19209289550780998537e-7)), 1.19209289550780998537e-7, 2e-016);
  TestHelper.TestRelativeError(ComplexMath.Absolute(new Complex(0.0, -1.19209289550780998537e-7)), 1.19209289550780998537e-7, 2e-016);
  TestHelper.TestRelativeError(ComplexMath.Absolute(new Complex(0.0, 5.0e-1)), 5.0e-1, 2e-016);
  TestHelper.TestRelativeError(ComplexMath.Absolute(new Complex(0.0, -5.0e-1)), 5.0e-1, 2e-016);

(Note that these are actually tests for a static method on ComplexMath, but Complex.Absolute calls this method directly without further ado. In any case we could easily rewrite our properties to call this method directly as well.)

These must've been a pain to write. Probably someone generated a little script to apply the definition of Absolute in each of these cases. That should be the work of a computer! Using FsCheck, it is.

Second, the original tests do not reveal the intent of the Absolute or Conjugate methods. Basically you just see a bunch of values going in, and the expected values coming out. In a normal program, you would call these "magic numbers" and call the developer that wrote them names. In unit tests, this is commonly tolerated.

FsCheck's specification on the other hand reveals the intent of the tested methods directly - in fact, I just looked up the mathematical definition of these operators to come up with the properties, and this definition is still readily apparent.

Third, FsCheck forced us to make the specification complete, and factor in NaN values. I could not find any test using NaN in the original dnAnalytics tests. This led directly to the discovery of a previously unknown bug.

In conclusion; FsCheck's tests are shorter, clearer and more complete than the original tests.

To boot, I dare say they are faster to write: I downloaded dnAnalytics, explored the code, choose a type to test, wrote the above properties, reported the bug, and typed in the bulk of this blog post in the course of about 4 hours yesterday. I spent another hour or two today cleaning up the post itself.

Technorati: FsCheck,dnAnalytics,FsCheck case study

Announcing FsCheck 0.5

2009-02-19T21:19:00.000Z

Another month has gone by, another release of FsCheck is a fact. (No, I won't keep this up). Check out the goodies.

Major:

Shrinking, which was introduced in FsCheck 0.4, is now fully customizable per type. This concludes the integration of Neil Mitchell's shrinking code (modulo the extra bugs I introduced, obviously)
Combining properties using and, or, and giving a name to subproperties, similar to functionality in a port of QuickCheck to Scala: scalacheck
Model based testing for stateful types, another shameless scalacheck rip-off. A surprisingly small extension to FsCheck that allows you to check stateful object types.
Thanks to some excellent feedback from Ganesh (from the Crédit Suisse team, which has been generous with contributions; thanks!) property combinators have become more general, in particular any Lazy<property> can now be tested (as opposed to only Lazy<bool> in 0.4).

Minor

New property combinators: throws (expect an exception), within (expect a result within some time). The latter is from QuickCheck 2.
New generator combinators: listOf, constant, suchThat, suchThatMaybe, again from QuickCheck 2.
Pretty printing and shrinking of function values. You guessed it, ported from QuickCheck 2.
Added support to TypeClass.fs to define typeclasses of arrays (this needs to be special cased since an array is not an ordinary generic type. Hurray for the consistencies of language design). FsCheck now also knows how to generate and shrink arrays.
Added makefile for Mono users, thanks to toyvo. I've tried to keep it up to date, but have not tested it so let me know if you have any problems.
Various bug fixes and smaller improvements.Notably the generator for discriminated unions should now produce "bigger" values, and the float generator now generates NaN, Infinity and Epsilon fairly often.

With these changes, I can safely say that FsCheck 0.5 has reached near feature parity with the combination(!) of both QuickCheck 2.1.0.1 and Scalacheck 1.5. Not bad for half a release on a technology preview platform.

I plan to let this stabilize over the next few months, and finally adding those FsChecks to FsCheck itself - FsCheck is fornicating priestware at the moment (*). I have however used FsCheck fairly frequently in private projects and I must say it has helped me a lot. Hopefully I'll have time to blog more about my experiences soon.

As usual, let me know if you have any feedback, always a pleasure to hear from you!

(*) i.e. it does not practice what it preaches

Technorati: F#,FsCheck,quickcheck,scalacheck

How to deal with out parameters in F#

2009-01-24T14:28:00.000Z

This is the third installment of my modest 'how to' series, where I try to highlight some in my opinion unappreciated (or under-marketed) gems of F#: little language features that pleasantly surprised me when I first learned about them.

Don't you hate out parameters? It's such a chore to use them: you need to declare a variable, pass it in the method with the out parameter modifier, and then check the results. Out parameters suck: they're just a poor excuse for not having to add a decent tuple type to your language. Unfortunately, some methods in the .NET framework use out parameters, and you might be dealing with some legacy code that uses them (some developers, apparently, think out parameters are the greatest idea since sliced bread).

Luckily, calling methods with out parameters is very easy in F#: they are converted to a tuple type automatically. For example, the Math.DivRem method has the following signature:

public static int DivRem( int a, int b, out int result )

which calculates the quotient of two numbers and also returns the remainder in an output parameter (in F#, this is a byref parameter).

Using this method in F# is simple:

let (q,r) = Math.DivRem(n,d)

The out parameter has been automatically converted to the second element of the resulting tuple.

Technorati: F#,out parameters

Announcing FsCheck 0.4

2009-01-14T22:18:00.000Z

It's been a month and a half since the last release of FsCheck. Time for an update!

Major changes:

Rewrote the back end using typeclasses. The result: much less reflection, cleaner code, and improved flexibility in the property combinators. In particular, the 'prop' and 'propl' combinators can now be omitted. Properties can take any nunber of arguments, that do not need to be tupled. Generators can now be more easily defined, and function generators are also derived based on type.
Two major new features were contributed generously by Howard Mansell and team at Credit Suisse. Most of the implementation was done by Neil Mitchell, who has also helped me a lot in integrating the changes in the main FsCheck branch. Thank you both!
The features are:
- Automatic generation of records, discriminated unions (including recursive ones), arrays and tuples. So once you define a generator for a type, FsCheck can now automatically generate lists, arrays, record types, functions, discriminated unions and options involving that type.
- Shrinking. Especially with recursive datatypes, counter examples can become quite large. FsCheck now automatically shrinks these examples to a smaller one, making bug finding lots easier.

Minor changes:

Some performance improvements
Improvements in FsCheck's output.
Factored out the function that prints the result of a test, so you can use it in your IRunner implementation if necessary
Because FsCheck uses less reflection, stack traces of exceptions when a test case fails are shorter and clearer

Breaking changes:

quickCheck no longer checks types; instead use quickCheckAll, verboseCheckAll or checkAll. quickCheck is the preferred way to check properties: it is faster, clearer and more flexible.
You'll need to redefine some of your custom generators; the mechanism to define and register generators has changed. See the manual for details, an don't hesitate to ask questions.

This is a bit of an intermediary release - for v0.5 I'd like to integrate shrinking better, so you can define your own shrinkers for a given datatype. Should be straightforward now that I've reworked the back-end, but I wanted to get this release out first - I think shrinking and the reflective datatype generators by themselves are worth a new release. Most of the churn should be over now, I'm finally happy now with the way a user can define new properties and generators.

Enjoy!

Technorati: FsCheck,quickcheck,F#

A poor man's typeclass

2009-01-13T20:43:00.000Z

This post contains a surprisingly short library which allows you to emulate Haskell's typeclasses in F#, except the type-safety. You might think that takes a lot away from the concept, but there is still plenty usefulness left. Not in the least it allows you to use an almost one-to-one translation of Haskell code including typeclasses to F#. At runtime both behave identically. In addition, since this is a library, its functionality can be extended beyond Haskell's typeclasses. Finally, if nothing else, you might be interested in how typeclasses work: this post shows you an implementation.

What is a typeclass, really?

If you don't know what typeclasses are, I recommend reading this chapter in the excellent Real World Haskell book. Let's look at a simple example of a typeclass from that chapter:

class BasicEq a where
isEqual :: a -> a -> Bool

This defines a typeclass BasicEq. All instances (which are defined later) will need to provide a function isEqual, which compares two values of the instance a. An example of such an instance is:

instance BasicEq Bool where
    isEqual True True = True
    isEqual False False = True
    isEqual _     _     = False

This example provides an instance of BasicEq for the type Bool. A lot of people coming from an OO background compare this with an abstract class BasicEq with a subclass Bool, when in fact it is nothing like that. There is absolutely no subtyping of any kind going on. The only relevant type here is Bool; after the instance definition Haskell just knows what isEqual function to call when applied to type Bool. There is absolutely no abstract class. Even more, although Bool is an already defined type, we are adding it as an instance of BasicEq after the fact, something which is not possible in any mainstream statically typed OO language with subtyping.

Typeclasses are a form of so called ad-hoc polymorphism. It has much more in common with operator overloading as it is known in F#, than with subclassing. In fact, the type of isEqual is:

isEqual :: (BasicEq a) => a -> a -> Bool

This indicates that isEqual can be called on any instance a of the typeclass BasicEq. In fact, Haskell only knows the specific function to call when it knows the type a: then, it just looks up the functions associated with that type. So, in fact, the (BasicEq a) => in front of the arguments can (besides as a type annotation) be seen as a dictionary that maps types a to functions implementing the BasicEq typeclass functions for a. The great thing about this is that because of type inference, the actual type a is inferred without any programmer annotation. So Haskell can choose the correct function to call automatically.

So, in the end, what is a typeclass? It's just a dictionary from type to a record of functions, where on each application of a typeclass function Haskell passes along the dictionary to it's calling function implicitly (i.e. without requiring the caller to pass it in). Because of type inference, this sometimes looks like pulling a function or value out of thin air.

The idea

If a typeclass at runtime is nothing more than using type information to pass in an implicit parameter to a function, then in F# we can use respectively reflection and side effects to emulate much the same thing:

Using reflection, we can obtain the type arguments with which a function is called
Using side effects, we can build a globally accessible dictionary of types to functions, that can be accessed "transparently", without needing the caller to thread it in calls.

The rest is some syntactic sugar.

Let's first look at how we can use the library, before diving into it's internals. Usage is remarkably similar to that of typeclasses. First, we define the typeclass:

type IListOf<'a> =
    abstract ListOf : list<'a>

This looks like a traditional class or interface type definition, that represents the functions in the typeclass. This type should have exactly one type parameter, which represents the type that we'll be defining instances for.

Now, let's register this new typeclass with our library:

newTypeClass<IListOf<_>>

newTypeClass takes one generic parameter, of which only the generic type definition part is important; this registers IListOf<'a> as a typeclass with which instances for certain types 'a can be registered.

Now, let's make some instances:

type IListOfInstances() =
    static member Unit() = 
        { new IListOf<unit> with
            override x.ListOf = [()]}
    static member Bool() = 
        { new IListOf<bool> with
            override x.ListOf = [true;false] }
    static member Int() = 
        { new IListOf<int> with
            override x.ListOf = [1..20] }

That defined instances for our typeclass IListOf with three instances for types unit, bool and int. As you can see, the corresponding interface implementations should be returned as the result of static members.

These instances must now be registered with the typeclass:

registerInstances<IListOf<_>,IListOfInstances>()

A function that we need to give two type arguments: the typeclass we're registering instances for, and the the type with the static members which return the instances.

Now we can get a specific IListOf implementation for a specific type:

getInstance (typedefof<IListOf<_>>,typeof<unit>)

However, this returns an obj - not nice. We'd like a typed listOf function that can be used whenever we want a list of some typeclass instance. Let's define such a function:

let listOf<'a> = getInstance (typedefof<IListOf<_>>,typeof<'a>) |> unbox<IListOf<'a>> |> (fun l -> l.ListOf)

The function takes only a type argument - which is used to get the instance, unbox the result (if the implementation of the typeclass library is correct, the unbox should always succeed), and then call the ListOf property which should return the correct list. This function can now be used just like an overloaded function:

printfn "%A" (listOf |> List.map (fun x -> x+5))
printfn "%A" (listOf |> List.map (fun x -> if x then "pos" else "neg"))

What is going on? The first listOf returns a list of ints, while the second returns a list of bools, although it seems we're not passing it any argument or hint as to what list to produce. Magic? Of course not.

We are passing listOf information - in its type argument. The reason we don't have to explicitly mention this argument is because F# infers it for us. So this is a great way to let type inference do some work at runtime.

The implementation

The library maintains an internal dictionary of typeclass names to instances of that typeclass:

let private typeClasses = new Dictionary<_,_>()

Defining a new typeclass prepares the one value of that dictionary to hold another dictionary which will map the actual instance types to their implementation of the typeclass functions:

let newTypeClass<'typeClass> = typeClasses.Add((typeof<'typeClass>).GetGenericTypeDefinition(), new Dictionary<_,_>())

The following method then uses some reflection to find all the instances of a given typeclass, which should be defined as static members on a given class type:

let private findInstances (typeClass:Type) = 
    let addMethods l (t:Type) =
        t.GetMethods((BindingFlags.Static ||| BindingFlags.Public)) |>
        Seq.fold (fun l m ->
            match m.ReturnType with
                | GenericTypeDef typeClass args -> 
                    if (args.Length <> 1) then
                        failwithf "Typeclasses must have exactly one generic parameter. Typeclass %A has %i" typeClass args.Length
                    else
                        let instance = args.[0]
                        if instance.IsGenericType 
                            && (instance.GetGenericArguments() |> Array.for_all (fun t -> t.IsGenericParameter)) then
                            (args.[0].GetGenericTypeDefinition(), m) :: l   
                        else
                            (args.[0], m) :: l
                | _ -> l
            ) l
    addMethods []

///Register instances in a given class as instances of the given type class. 
let registerInstancesByType typeClass instance =
    findInstances typeClass instance |> Seq.iter (typeClasses.[typeClass].Add)

///Register instances in a given class as instances of the given type class.
let registerInstances<'typeClass,'instance>() = 
    registerInstancesByType (typedefof<'typeClass>) (typeof<'instance>)

The final ingredient is the lookup function, to get the implementation of a typeclass given a type:

let getInstance   =
    memoize (fun (typeClass:Type, instance:Type) ->
        let instances = typeClasses.[typeClass]
        let mi =
            match instances.TryGetValue(instance) with
            | (true, res) -> res
            | _ when instance.IsGenericType -> //exact type is not known, try the generic type
                match instances.TryGetValue(instance.GetGenericTypeDefinition()) with
                | (true, mi') -> if mi'.ContainsGenericParameters then (mi'.MakeGenericMethod(instance.GetGenericArguments())) else mi'
                | _ -> failwithf "No instances of class %A for type %A" typeClass instance 
            | _ -> failwithf "No instances of class %A for type %A" typeClass instance 
        mi.Invoke(null, Array.empty))

There is some heavy reflection going on here, which I'll let you figure out in your own time. The memoize function I took from the Expert F# book. Full implementation is downloadable below.

Conclusions

This posts shows how to get all the advantages of typeclasses in F#, except the static checking. I've found these advantages considerable:

The use of reflection is heavy, but it is very nicely encapsulated: all the un-typesafeness goes on strictly inside the library and definition. What goes in and what comes out is strongly typed, and from a user point of view, the reflection is completely behind the scenes.
Although reflection is involved, it is actually fast: there is some manipulation of Types, but this is highly optimized in .NET. There is one reflective invocation per instance that is looked up, but the result is memoized so this can be considered startup cost. Finally, there are two constant time dictionary lookups.
To give a real world example, in FsCheck 0.4 (which will be out real soon) I have been able to use this simple library to translate the Arbitrary and Testable typeclasses from QuickCheck directly into F#, making property combinators more powerful. For one, there is no longer a need for the 'prop' and 'propl' functions, a feat which I was not able to accomplish using reflection alone (and I did try!). So the typeclass abstraction is a nice way to structure your code around overloading.
It has also allowed me to reduce the amount of reflection code in FsCheck and other projects - which is a Good Thing as reflection is always a pain to use.
It's a great way to let type inference work for you, also at run time.

Finally, some things for the future:

This library is not thread safe, although it could be made thread safe at the cost of some locking.
Are multi-parameter type classes possible using this technique?
...

Anyway, I hope that this post has shown that with some imagination and a little work, you can do great things with F#, not in the least thanks to a lot of infrastructure in the form of .NET libraries, without which this would not have been possible.

Download the full implementation. It will also be distributed with FsCheck 0.4 (soon, I promise :).

Technorati: F#,typeclass,haskell

How to change the accessibility of a constructor using implicit object construction

2008-12-20T16:54:00.001Z

The recommended way to define a class in F# is by using so-called implicit object construction. The more traditional (for C# programmers, that is) but typically more tedious explicit object construction syntax feels distinctly less "functional". In short, implicit construction relieves you of writing an explicit constructor for your class, and also allows you to use let and do clauses in the body of your class that take the place of static or instance initializers. Check out Robert Pickering's F# wiki for a nice overview.

The other day I was writing a class that needs only factory methods to construct it, a not so uncommon pattern. In C#, I wouldn't think twice about how to do this: just add a private or internal constructor, and a few public factory methods. This is also straightforward to do using F#'s explicit object construction syntax, but I wondered if it is possible using implicit construction. Turns out it is!

The trick is simple:

type Foo internal()=

static member FactoryMethod = new Foo()

Notice the position of the 'internal' modifier. Modifying the accessibility of the 'Foo' class proper is done in the usual way, by putting the modifier right after the 'type' keyword. You can even mix these up:

type internal Foo private()=

This defines an internal class with a private constructor.

Thanks to Brian and Tomas for helping me out on this one!

Technorati: F#,implicit object construction,syntax,accessibility modifier

Announcing FsCheck 0.3

2008-12-03T22:28:00.000Z

I am very pleased to announce a new release of FsCheck, for the first time on codeplex! Here is a short description.

FsCheck is a port of Haskell's QuickCheck: it is a tool for testing F# programs automatically. The programmer provides a specification of the program, in the form of properties which functions, methods or objects should satisfy, and FsCheck then tests that the properties hold in a large number of randomly generated cases. While writing the properties, you are actually writing a testable specification of your program. Specifications are expressed in F#, using combinators defined in the FsCheck library. FsCheck provides combinators to define properties, observe the distribution of test data, and define test data generators.

This release brings FsCheck about up to par with QuickCheck 0.1, and adds some smaller features. An overview:

Added feature to derive a generator from the type of arguments. You can add your own generators for custom types. Radically reduces the use of forAll.
Added feature to reduce use of prop and propl. For example: "quickCheck (fun a -> a+a = 2*a)" just works.
Added feature to group related properties in a class, and check it at once. Can also be used to check all toplevel properties in a module.
FsChecks no longer dies when a property throws an exception, but reports a test failure.
Bug fixes and suggestions received through this blog, email and hubfs implemented. Thanks Neil, Chance, Mat and Anton, and everyone who emailed me!
Some extension points to use FsCheck with whateverUnit frameworks.
Updated examples, and documentation, the whole codeplex thing.

It was a lot of work, but I hope it was worth it.

I plan to devote more of my time to other projects from now on, at least for the next coming months. That said, your contributions to FsCheck are more than welcome. Besides, this release should keep you quiet for a while ;).

I will be posting some suggestions for features and improvements soon, should you run out of ideas.

[Update: check out the FsCheck issue tracker for some ideas on how to contribute]

Technorati: F#,FsCheck,random testing

Future plans for FsCheck

2008-11-15T14:18:00.000Z

Because of a recent question on HubFS, I made my future plans for FsCheck public. I'm re-iterating them here:

smaller bug fixes, some cleaning (mostly done)
adding FsCheck.fsi module declaration & comments
Feature: derive generators from types of arguments (mostly done)
Feature: ability to group properties in classes, and check the class with one command (mostly done)
Investigate using FsCheck with unit testing frameworks like MbUnit & co, or generally how to use it in practice (currently active)
putting the project on codeplex + clarifying license . I'm checking compatibility with the QuickCheck license, but I'm aiming for a permissive license, like the new BSD license.

I intend to finalize this before the end of the year.

Finally, you can help by answering the following question. How are you using FsCheck? Do you have a separate console app that you run that contains your properties, or do you use F# interactive with the properties inline, or something else?

Technorati: F#,random testing,FsCheck

How to use named arguments in F#

2008-11-10T21:58:00.001Z

Named arguments are a little-known feature of F#, that is actually very useful when calling heavily overloaded members. The DateTime constructor is one such example: it has twelve overloads, and I can never remember what (in C#) DateTime d = new DateTime(2008,11,12) means. Is it December 11th or 11 November (as we would say it in Dutch)? Fortunately, in F# there is a nice solution for this: you can always use the names of the formal arguments to specify a named argument. This not only clarifies what overload you're calling, you can also easily change the order of the arguments. For example:

let d = new DateTime(month=12, day=11, year=2008)

makes it very clear that we're talking about December 11th here. If you're from the US, it even looks 'normal'. Europeans may like:

let d' = new DateTime(day=11, month=12, year=2008)

For F#, it's all the same.

You can also mix positional with named arguments, and if the object has setters, you can use these to. For details, read Section 8.4.5 in the F# (draft) language spec.

Technorati: F#,named arguments

Fun with units of measure

2008-10-11T17:35:00.000+01:00

Since the CTP, F# has a nice feature in its type system, called units of measure. Briefly, it allows you to specify a unit with any float, and the type system checks that your uses of units are consistent. For example, you can't add a float<m> to a float<ft>, which results in, among other things, less crashes of spacecraft on Mars. I won't go into details, if you're interested but don't know what I'm talking about, read Andrew Kennedy's blog before you continue.

But anyway, using units for, well, tracking units is kind of boring - type systems are made to be abused after all. So here's my attempt to use units of measure to track the lengths of vectors, so that the compiler will for example detect that you try to add two vectors of unequal length.

How can this be achieved? The basic idea is to encode the length of the vector as an exponent to a unit, that is kept in the 'safe vector' type as a unit of measure parameter. To do this, we first need a unit of measure and a 'safe vector' type that uses it:

[<Measure>] type length

type SVec<'a,[<Measure>]'l> = 
    SVec of list<'a> * float<'l>

So, SVec is a vector containing elements of type 'a, and with a length encoded in 'l. We'll use the float to both encode the length of the string as a value and as a type; the idea is that SVec ([1,5], 2.0) has type SVec<int, length ^2>. Let's define some utility functions to make type safe vectors:

let nil = SVec ([],0.0)
let cons elem (SVec (xs,un:float<'l>)) : SVec<_,'l length> = 
        SVec (elem::xs, (un + 1.0<_>) * 1.0<length>)
let (=+=) = cons

let removeUnits f = f |> box |> unbox<float>

let length (SVec (_,c)) = removeUnits c |> int 
let from_list xs (l:float<'u>) : SVec<'a,'u> = 
    if List.length xs <> int (removeUnits l) then raise <| new ArgumentException("Actual length of list is not equal to given length")
    else SVec (xs,l)

'nil' constructs an empty vector. It has type SVec<'a>,1>, denoting a list with zero elements. 'cons' adds an element to the front of the vector. To do this, it needs to do three things:

Add the actual element to the front of the list
Update the length value by adding 1
Update the length type by multiplying with 1.0<length>

To get the length of a vector, we return the unit value, stripping of all static unit types. I tried this first by dividing by 1.0<'u>, but it appears that you can't use a type argument as a unit of measure with a constant value. I'm not exactly sure why.

'from_list' takes a list and turns it into a safe vector. You need to provide a list, with the length of the list correctly encoded in both value and type. The value is tested, the type is not: as far as I can see, this is impossible to check.

Let's make a safe vector:

let l = 3 =+= (2 =+= (1 =+= nil))

The type of l is SVec<int,length^3>. Now we can define type-safe multiplication and addition:

type SVec<'a,[<Measure>]'l> = 
    SVec of list<'a> * float<'l>
        static member (+) (SVec (xs, l1): SVec<_,'l>, SVec (ys, l2): SVec<_,'l>) = 
            SVec (zip xs ys |> map (fun (x,y) -> x + y), l1)
        static member (*) (SVec (xs, l1) : SVec<_,'l>, SVec (ys, l2): SVec<_,'l>)=
            zip xs ys |> sum_by (fun (x,y) -> x*y)

The interesting part is of course not the implementation, but the types: they statically enforce that when you add or multiply two vectors, they have the same length. So:

let sum = l + l

will typecheck fine, but

let badsum = l + nil

will give a type error!

That concludes my experiment. Some final thoughts:

This cannot be used to make a type safe head and tail operation, as far as I can see. We'd need an additional type to represent the empty list, and somehow make a head function that can transform between the two types - the kind of overloading necessary does not seem to be possible in F#.
Try to make a recursive function with SVec: it's impossible, since generic recursion is impossible.

Technorati: F#,units of measure

How to invoke a method with type parameters using reflection (in F#)

2008-10-07T10:10:00.000+01:00

Methods with type parameters arise naturally in F# code, for example:

type Example =
    static member Test l = List.rev l

'Test' has one type parameter 'a, the type of the elements of the list that is being reversed.

In F# you can call the Test method with a list of any type, and the compiler infers the type parameters for you:

let result = Example.Test [1;2;3]

The compiler infers that 'a must be an int.

Mainstream languages such as C# and VB.NET only infer the type arguments at the call site. The programmer needs to declare all the type parameters of a method explicitly. Consider the type signature of the following method:

type Example =
    static member Test2 (a,b) = (fst a = snd b)

Test2 has three type arguments: it takes two tuples a and b as its arguments, which is a total of four types. But since Test2 compares the first element of a with the second element of b, these two are inferred to have the same types. In C#, a programmer would have to infer this for herself, and write:

public static bool Test2<T, U, V>(Tuple<T, U> a, Tuple<V, T> b)
{
   return a.Fst == b.Snd;
}

(of course, assuming that a type Tuple would be defined in .NET, which is not the case if you're not using the F# core libraries)

Because it is obvious that such type annotations require much more work by the programmer, in C# and VB.NET type arguments to methods are in my experience much less common, and much less complex, than what is written without a second thought in F#.

However, recently I faced the problem of calling a number of static methods such as the above using reflection. I had the actual arguments to the method available, so for Test2 above I would have the (type-correct, of course) arguments (true,2.0) and ("whatever", false) available.

To call a method using reflection, you can use MethodInfo.Invoke, on a MethodInfo object obtained using typeof<Example>.GetMethod("Test2") or some such. Executing a non-generic method is easy - just call Invoke() with the actual arguments. However, System.Reflection refuses to call Invoke on a method with unspecified generic arguments (T,U and V for Test2) . You need to specify the actual arguments (bool, float and string for Test2 resp.) manually. So, I had to deduce these from the actual arguments given to the method. The following two functions demonstrate how to do this:

let rec resolve (a:Type) (f:Type) (acc:Dictionary<_,_>) =
    if f.IsGenericParameter then
        if not (acc.ContainsKey(f)) then acc.Add(f,a)
    else 
        Array.zip (a.GetGenericArguments()) (f.GetGenericArguments())
        |> Array.iter (fun (act,form) -> resolve act form acc)

let invokeMethod (m:MethodInfo) args =
    let m = if m.ContainsGenericParameters then
                let typeMap = new Dictionary<_,_>()
                Array.zip args (m.GetParameters()) 
                |> Array.iter (fun (a,f) -> 
                    resolve (a.GetType()) f.ParameterType typeMap)  
                let actuals = 
                    m.GetGenericArguments() 
                    |> Array.map (fun formal -> typeMap.[formal])
                m.MakeGenericMethod(actuals)
            else 
                m
    m.Invoke(null, args)

The second function, invokeMethod, can be used as a replacement for MethodInfo.Invoke that also works for methods with generic arguments. The function above only works for static methods, but taking away this restriction should be straightforward.

invokeMethod takes a MethodInfo m(which should be a static method) and the arguments you want to call the method with. First we check if m is a generic method. If not, nothing needs to be done and we can just call Invoke.

If m is a generic method, we build a a typeMap which maps the formal type arguments to their actual types, for which we can use the signature of the method on the one hand (i.e. as given by the MethodInfo), and the types of the actual arguments args. The function 'resolve' does most of the heavy lifting here, building up the typeMap by comparing actual and formal arguments in a pairwise fashion. 'resolve' needs to be called recursively, since type arguments may be nested arbitrarily deeply. For example, the formal argument list<'a*option<'b>> should resolve with the actual argument list<int*option<bool>> by mapping 'a to int and 'b to bool.

Once we've determined the actual type arguments to the generic method, System.Reflection lets us instantiate an invoke-able method using MethodInfo.MakeGenericMethod(), which takes an array of actual types that fill in the generic type arguments to the method. If we've determined the type arguments correctly, the result of MakeGenericMethod() is another MethodInfo object that can be invoked as usual.

The interested reader can figure out the details.

Some notes:

'resolve' is not tail-recursive. I just didn't bother since you would need to write some extremely convoluted method arguments to blow the stack. list<list<list<list<(repeat x 1000 000)>>>> anyone? Also for the same reason I didn't worry about performance - I don't actually expect to have very deeply nested types. (if type classes were ever added to F#, I guess I would need to start worrying about that...)
I dislike that I used a Dictionary in there, though it seemed to be the most elegant solution. I tried using a Map, but then I had to merge maps when the recursive call to resolve returned. It seemed easier with a (non-functional) Dictionary. If anyone can do better, I'd like to hear about it.

Technorati: F#,System.Reflection

Announcing FsCheck 0.2

2008-08-15T11:05:00.000+01:00

[Update: I noticed that the download comes with a preliminary version of random.fs, which contained many mistakes! I've now updated the link. Sorry! I also added the link directly to this post as well.]

[Update 2: I converted the old F# project to a shiny new .fsproj compatible with the F# September CTP which was released yesterday. Had to clean up and change some code as well, mostly due to renames and a different type signature of assert. New download link below.]

Version 0.2 introduces the following changes:

Ported the Haskell random implementation, which gives more dependable results when splitting seeds.
Introduced lazy evaluation of properties to improve checking of conditional properties. The function prop needs a lazy argument from now on; a shorthand propl can be used if you don't need or want this. (Thanks to galen for bringing this to my attention)
Tried lots of approaches to get rid of both prop and lazy when they are not needed. Also tried to get rid of the generators using reflection and quotations. Very few approaches were feasible, none were satisfactory. In the end, nothing changed. I'm hoping for type classes or some other way of overloading and/or implicit parameter passing, but I'll guess that'll be for F# 2.0 at the earliest. If anyone has any suggestions, please let me know.
Added some examples in another style, where the property is separated from the actual generator, and added some convenience functions qcheck and vcheck to support this style. This improves readability of the actual properties, and makes them somewhat more reusable.

Breaking change: if you have some properties lying around, the easiest way to get them to work is to replace prop by propl.

Read the updated complete documentation in my previous post. My plan is to keep that post as the up to date and complete documentation of the latest version, and announcing new releases with changes in separate posts like this.

Thanks for your interest, and do keep giving me feedback and suggestions!

Download FsCheck 0.2 source

Download FsCheck 0.2 for the F# September CTP

Technorati: fscheck,F#

Parsing Dot with F#: Part 4 - Conclusion

2008-05-10T22:56:00.001+01:00

In this very last part, I'll just show how to put everything together: the types, the lexer and the parser. First, we need to generate some F# files from the dotlexer.fsl and the dotparser.fsy files. This is easily accomplished by running fslex and fsyacc, respectively. This creates dotlexer.fs, dotparser.fs and dotparser.fsi. If, like me, you're working in Visual Studio, you can add these files to your project, but take care that you put everything in the right order or it won't compile (I actually lost quite a bit of time with this): first the definition of the abstract syntax type, then the parser files, then the lexer file. Finally, you can call the parser:

let parseFromString(text) =
    let lexbuf = Lexing.from_string text
    try
        DotParser.start DotLexer.token lexbuf
    with e ->
        let pos = lexbuf.EndPos
        printf "error near line %d, character %d\n%s\n" pos.Line pos.Column (e.ToString())
        Graph (new List<_>())

This is fairly straightforward: the Lexing module defines functions to create a lexing buffer from a string. Feed this buffer into the DotParser.start function generated by fsyacc. This function will return the expected type, as defined in the .fsy file.

That's really all there is to it - the rest is some exception catching and printing an error for debugging purposes. One thing I'd like to warn you about is that debugging this stuff can be quite tedious, due to the fact that first the F# files are generated by the fsyacc and the fslex tools, and afterwards compiled. Although the compiler does a fairly good job of showing where the actual errors are in the fsy and fsl files, it is sometimes hard to track down what exactly is the problem.

Finally, you can download the example project.

Technorati: parsing,fslex,fsyacc,F#

Parsing Dot with F#: Part 3 - The parser

2008-05-09T22:46:00.001+01:00

The parser is produced by fsyacc (yacc stands for Yet Another Compiler Compiler). Basically it turns the tokens produced by the lexer into a nice set of types that you can easily manipulate from within your program. Fsyacc can generate a parser based on a definition that looks pretty much the same as the simplified grammar for Dot that I discussed in part 1.

Our dotparser.fsy file starts off with some preliminaries:

%{

open Ast
open System.Collections.Generic

%}

Same as the lexer, this code will eventually be transformed into regular F# code. So here we can open some modules for use later, and potentially do other preliminaries.

Then, some parser-related startup:

%start start

%token <string> ID
%token NODE EDGE DIGRAPH GRAPH DIEDGE UNEDGE QUOTE LACC RACC LPAREN RPAREN SEMI COMMA ASSIGN EOF 

%type < Ast.Graph > start

The first and last line indicate to fsyacc where to start parsing (at which rule, to be defined later), and the type the complete parsing process will construct; if you remember our abstract syntax tree from part 1, we're trying to make a Graph type.

The lines in between are just an enumeration of all the possible terminal tokens (i.e. tokens that needn't be parsed further), along with the type of data that they carry. You should recognize these from the lexer. In our parser, only the ID token carries information of type string.

And finally, the part that makes this all tick:

start: Graph { $1 }

Graph: DIGRAPH ID LACC StmtList SEMI RACC    { ($4:List<_>).Reverse(); Graph $4 }

StmtList: Stmt            { let l = new List<Element>() in l.Add($1); l }
    | StmtList SEMI Stmt  { $1.Add($3); $1 }

Stmt: 
    | ID AttrListOpt             { Node($1,$2) } 
    | ID DIEDGE ID AttrListOpt   { Edge($1,$3,$4) }
    | GRAPH AttrListOpt          { GraphAttributeList($2) }
    | NODE AttrListOpt           { NodeAttributeList($2) }
    | EDGE AttrListOpt           { EdgeAttributeList($2) }

AttrListOpt:
    |                            { new Dictionary<string,string>() }
    | LPAREN AttrList RPAREN     { $2 }

Attr: ID ASSIGN ID               { new KeyValuePair<string,string>($1,$3) }

AttrList: Attr              { let attr = new Dictionary<string,string>() in attr.Add($1.Key,$1.Value); attr }
    | AttrList COMMA Attr   { $1.Add($3.Key, $3.Value); $1 }

Notice that this is very similar to the grammar defined earlier. I guess with some experience one can derive this fsyacc spec from the grammar in a fairly straightforward way. Expect some bumps on the road the first time around though. Notice that with each rule we can again associate the transformation that needs to occur, similar as we did in the lexer. Only this time we're not producing tokens, we're producing the actual F# types that we need. The $n variables in the right part refer to the data that is carried by the nth token on the left.

Some things to be aware of:

If you need to parse a list of things, like the StmtList above, you need to do this "backwards", i.e. the second option in StmtList is 'StmtList SEMI Stmt', not 'Stmt SEMI StmtList'. This also means I reverse the list once read in the Graph rule. This is simply a consequence of how the parser produced by fsyacc works under the hood - in this case a minor inconvenience.
I chose here to use regular .NET types as much as possible, since I intended to use this code from C#. If you use F# types like list, the code actually becomes a lot shorter. For example, 'let l = new List<Element>() in l.Add($1); l" just becomes '[$1]'.
I deliberately reversed the order of the rules Attr and AttrList, so that F# could infer the types of the arguments better. This is a result of the fact that F# parser top to bottom, left to right. If you get a lot of type inference errors, it pays off to experiment with the order of your statements, if you can reverse them. I try to avoid adding type annotations as much as possible, they make the code harder to read and to maintain. (in C# my use of the C# 'var' keyword has increased exponentially)

That's it; next time, I'll show you how to put everything together and call the parser.

Technorati: F#,fsyacc,graphviz,parsing

FsCheck: Random testing for F#

2008-05-02T19:36:00.001+01:00

[Updated for version 0.2]

[Update: this documentation is no longer kept up to date as of FsCheck 0.3. Please check out FsCheck on codeplex for up to date releases, information and what not.]

FsCheck is an as-literal-as-possible port of Haskell's QuickCheck 0.1. Using FsCheck, you define properties that should hold for all your functions. FsCheck checks that those properties hold by generating random values for the parameters of the properties. While writing the properties, you are actually writing a testable specification of your program.

This release is still a bit rough around the edges; basic things work, but there's for example no easy way to check all properties in a given file. Also parts of FsCheck itself are still untested (ah, the irony). I wrote FsCheck mainly as an exercise - learn from the best, or suck like the rest, so Haskell seems like a good place to start.

The next part of this post is a manual for using FsCheck; most of it is almost literally "adapted" from the QuickCheck manual and paper. Any errors and omissions are entirely my responsibility.

What is FsCheck?

FsCheck is a tool for testing F# programs automatically. The programmer provides a specification of the program, in the form of properties which functions should satisfy, and FsCheck then tests that the properties hold in a large number of randomly generated cases. Specifications are expressed in F#, using combinators defined in the FsCheck library. FsCheck provides combinators to define properties, observe the distribution of test data, and define test data generators.

FsCheck is currently best used to test the functions in your F# programs. I may be experimenting in the future with using it to test classes and methods, in combination with existing .NET unit testing frameworks. The generator combinators can be used already in any testing framework to easily generate a number of random values for many types. Mostly these are F# specific at this point (tuples, option values, function values), but that should be easy to remedy.

A Simple Example

A simple example of a property definition is

let prop_RevRev (xs:list<int>) = List.rev (List.rev xs) = xs  |> propl

This property asserts that the reverse of the reverse of a list of integers is the list itself. (the propl function comes with FsCheck and is explained shortly) To check the property, we load this definition in F# interactive and then invoke

> qcheck (Gen.List(Gen.Int)) prop_RevRev;;
Ok, passed 100 tests.
val it : unit = ()

As the example shows, you indicate to FsCheck the type to generate for the property (in this case, a list of ints).

When a property fails, FsCheck displays a counter-example. For example, if we define

let prop_RevId xs = List.rev xs = xs |> propl

then checking it results in

> qcheck (Gen.List(Gen.Int)) prop_RevId;;
Falsifiable, after 8 tests:
["[-2; -4; -1]"]
val it : unit = ()

Using FsCheck

To use FsCheck, you download the latest FsCheck solution at the very end of this post. Build and reference the assembly in any projects containing specifications or test data generators. You can then test properties by loading the module they are defined in into F# interactive, and calling
qcheck <generator> <property_name>;;
or by running and writing a small console application that calls the qcheck function.

What do I do if a test loops or encounters an error?

In this case we know that the property does not hold, but qcheck does not display the counter-example. There is another testing function provided for this situation. Repeat the test using

vcheck <generator> <property_name>;;

which displays each test case before running the test: the last test case displayed is thus the one in which the loop or error arises.

Properties

Properties are expressed as F# function definitions, with names beginning with prop_. Properties can be defined together with their generators, by universal quantification over their parameters using the function forAll, which takes the form

forAll <generator> (fun arg -> <property>)

The first argument of forAll is a test data generator. The second argument is a function that takes as argument one value generated by the test data generator, and returns the property that needs to be checked. The values generated by the test data generator must be of the correct type for the argument, which is checked at compile time. For example,

let prop_RevRev = 
    forAll (Gen.List(Gen.Int)) (fun xs -> 
        List.rev (List.rev xs) = xs |> propl)

will generate a number of int lists for the argument xs, and evaluate the function using the generated value.

The core of a property is an assertion function that returns a bool. Such a function should be made into a Property type by calling the function propl. This allows you to use property combinators explained below.

`Polymorphic' properties, such as the one above, are restricted to a particular type to be used for testing, which is done by specifying a generator. The anonymous function given to forAll can take only one argument: if a property needs more, they should be tupled using Gen.Tuple.

Note: thanks to Haskell's type classes, QuickCheck does not force you to use forAll or needs you to use prop. I do realize it makes the properties in F# harder to read - at the moment I see no elegant ways around this. But in FsCheck you can separate the generators from the properties using qcheck and vcheck. In the examples you can find examples of both styles. For clarity, I'll use the forAll function in the following.

Conditional Properties

Properties may take the form

<condition> ==> <property>

For example,

let rec ordered xs = match xs with
                     | [] -> true
                     | [x] -> true
                     | x::y::ys ->  (x <= y) && ordered (y::ys)
let rec insert x xs = match xs with
                      | [] -> [x]
                      | c::cs -> if x<=c then x::xs else c::(insert x cs)
let prop_Insert = forAll (Gen.Tuple(Gen.Int, Gen.List(Gen.Int))) (fun (x,xs) -> 
                    ordered xs ==> propl (ordered (insert x xs)))

Such a property holds if the property after ==> holds whenever the condition does.

Testing discards test cases which do not satisfy the condition. Test case generation continues until 100 cases which do satisfy the condition have been found, or until an overall limit on the number of test cases is reached (to avoid looping if the condition never holds). In this case a message such as
Arguments exhausted after 97 tests.
indicates that 97 test cases satisfying the condition were found, and that the property held in those 97 cases.

Since F# has eager evaluation by default, the above property does more work than necessary: it evaluates the property at the right of the condition no matter what the outcome of the condition on the left. While only a performance consideration in the above example, this may limit the expressiveness of properties as well - consider:

let prop_CheckLazy2 = forAll (Gen.Int) (fun a -> a <> 0 ==> propl (1/a = 1/a)))

Will throw an exception. However, FsCheck also provides the function prop which makes a lazy property, and so requires the F# keyword lazy to force the lazy evaluation of the condition:

let prop_CheckLazy2 = forAll (Gen.Int) (fun a -> a <> 0 ==> prop (lazy (1/a = 1/a)))

Works as expected. propl is actually a shorthand for prop (lazy ...)), but beware: the argument of propl is evaluated eagerly!

Generators

There are number of generators for some common types, but by supplying a custom generator, instead of using the default generator for that type, it is possible to control the distribution of test data. In the following example, by supplying a custom generator for ordered lists, rather than filtering out test cases which are not ordered, we guarantee that 100 test cases can be generated without reaching the overall limit on test cases:

let prop_Insert = forAll (Gen.Tuple(Gen.Int, orderedList(Gen.Int))) (fun (x,xs) -> 
                    propl (ordered (insert x xs)))

Combinators for defining generators are described below.

Observing Test Case Distribution

It is important to be aware of the distribution of test cases: if test data is not well distributed then conclusions drawn from the test results may be invalid. In particular, the ==> operator can skew the distribution of test data badly, since only test data which satisfies the given condition is used.

FsCheck provides several ways to observe the distribution of test data. Code for making observations is incorporated into the statement of properties, each time the property is actually tested the observation is made, and the collected observations are then summarized when testing is complete.

Counting Trivial Cases

A property may take the form

trivial <condition> <property>

For example,

let prop_Insert = forAll (Gen.Tuple(Gen.Int, Gen.List(Gen.Int))) 
                    (fun (x,xs) -> 
                    ordered xs ==> propl (ordered (insert x xs))
                    |> trivial (List.length xs = 0))

Test cases for which the condition is true are classified as trivial, and the proportion of trivial test cases in the total is reported. In this example, testing produces

> quickCheck prop_Insert;;
Ok, passed 100 tests (46% trivial).
val it : unit = ()

Classifying Test Cases

A property may take the form

classify <condition> <string> <property>

For example,

let prop_Insert2 = 
    forAll (Gen.Tuple(Gen.Int, Gen.List(Gen.Int))) (fun (x,xs) -> 
        ordered xs ==> propl (ordered (insert x xs))
        |> classify (ordered (x::xs)) "at-head"
        |> classify (ordered (xs @ [x])) "at-tail")

Test cases satisfying the condition are assigned the classification given, and the distribution of classifications is reported after testing. In this case the result is

> quickCheck prop_Insert2;;
Ok, passed 100 tests.
48% at-tail, at-head.
25% at-head.
21% at-tail.
val it : unit = ()

Note that a test case may fall into more than one classification.

Collecting Data Values

A property may take the form

collect <expression> <property>

For example,

let prop_Insert3 = 
    forAll (Gen.Tuple(Gen.Int, Gen.List(Gen.Int))) (fun (x,xs) -> 
        ordered xs ==> propl (ordered (insert x xs))
        |> collect (List.length xs))

The argument of collect is evaluated in each test case, and the distribution of values is reported. The type of this argument is printed using any_to_string. In the example above, the output is

> quickCheck prop_Insert3;;
Ok, passed 100 tests.
46% 0.
36% 1.
11% 2.
6% 3.
1% 4.
val it : unit = ()

Combining Observations

The observations described here may be combined in any way. All the observations of each test case are combined, and the distribution of these combinations is reported. For example, testing the property

let prop_Insert3 = 
    forAll (Gen.Tuple(Gen.Int, Gen.List(Gen.Int))) (fun (x,xs) -> 
        ordered xs ==> propl (ordered (insert x xs))
        |> classify (ordered (x::xs)) "at-head"
        |> classify (ordered (xs @ [x])) "at-tail"
        |> collect (List.length xs))

produces

> quickCheck prop_Insert3;;
Ok, passed 100 tests.
46% 0, at-tail, at-head.
18% 1, at-head.
17% 1, at-tail.
6% 2, at-head.
3% 3.
2% 2.
2% 3, at-tail.
2% 2, at-tail.
1% 4.
1% 3, at-head.
1% 2, at-tail, at-head.
1% 1, at-tail, at-head.
val it : unit = ()

from which we see that insertion at the beginning or end of a list has not been tested for lists of four elements.

Test Data Generators: The Type Gen

Test data is produced by test data generators. FsCheck defines default generators for some often used types, but you can use your own, and will need to define your own generators for any new types you introduce.

Generators have types of the form 'a Gen; this is a generator for values of type a. The type Gen is a computation expression called gen, so F#'s computation expression syntax can be used to define generators.

Generators are built up on top of the function

val choose : (int * int -> int Gen)

which makes a random choice of a value from an interval, with a uniform distribution. For example, to make a random choice between the elements of a list, use

let chooseFromList xs = gen { let! i = choose (0, List.length xs) 
                              return (List.nth xs i) }

Note that choose does not include the upper bound of the interval, so you can use List.length without deducting 1.

Choosing Between Alternatives

A generator may take the form

oneof <list of generators>

which chooses among the generators in the list with equal probability. For example,

oneof [ gen { return true }; gen { return false } ]

generates a random boolean which is true with probability one half.

We can control the distribution of results using the function

val frequency: (int * 'a Gen) list -> 'a Gen

instead. Frequency chooses a generator from the list randomly, but weights the probability of choosing each alternative by the factor given. For example,

frequency [ (2, gen { return true }); (1, gen { return false })]

generates true two thirds of the time.

The Size of Test Data

Test data generators have an implicit size parameter; FsCheck begins by generating small test cases, and gradually increases the size as testing progresses. Different test data generators interpret the size parameter in different ways: some ignore it, while the list generator, for example, interprets it as an upper bound on the length of generated lists. You are free to use it as you wish to control your own test data generators.

You can obtain the value of the size parameter using

val sized : ((int -> 'a Gen) -> 'a Gen)

sized g calls g, passing it the current size as a parameter. For example, to generate natural numbers in the range 0 to size, use

sized <| fun s -> choose (0,s)

The purpose of size control is to ensure that test cases are large enough to reveal errors, while remaining small enough to test fast. Sometimes the default size control does not achieve this. For example, towards the end of a test run arbitrary lists may have up to 50 elements, so arbitrary lists of lists may have up to 2500, which is too large for efficient testing. In such cases it can be useful to modify the size parameter explicitly. You can do so using

val resize : (int -> 'a Gen -> 'a Gen)

resize n g invokes generator g with size parameter n. The size parameter should never be negative. For example, to generate a random matrix it might be appropriate to take the square root of the original size:

let matrix gn = sized <| fun s -> resize (s|>float|>sqrt|>int) gn

Generating Recursive Data Types

Generators for recursive data types are easy to express using oneof or frequency to choose between constructors, and F#'s standard computation expression syntax to form a generator for each case. There are also liftGen functions for arity up to 4 (more are easy to add) to lift constructors and functions into the Gen type. For example, if the type of trees is defined by

type Tree = Leaf of int | Branch of Tree * Tree

then a generator for trees might be defined by

let rec unsafeTree = 
    oneof [ liftGen (Leaf) Gen.Int; 
            liftGen2 (fun x y -> Branch (x,y)) unsafeTree unsafeTree]

However, there is always a risk that a recursive generator like this may fail to terminate, or produce very large results. In any case, the F# compiler generates an error for the above function for exactly this reason: the function calls itself. To avoid this, recursive generators should always use the size control mechanism. For example,

let tree =
    let rec tree' s = 
        match s with
          | 0 -> liftGen (Leaf) Gen.Int
          | n when n>0 -> 
            let subtree = tree' (n/2) in
            oneof [ liftGen (Leaf) Gen.Int; 
                    liftGen2 (fun x y -> Branch (x,y)) subtree subtree]
    sized tree'

Note that

We guarantee termination by forcing the result to be a leaf when the size is zero.
We halve the size at each recursion, so that the size gives an upper bound on the number of nodes in the tree. We are free to interpret the size as we will.
The fact that we share the subtree generator between the two branches of a Branch does not, of course, mean that we generate the same tree in each case.

Useful Generator Combinators

If g is a generator for type t, then

two g generates a pair of t's,
three g generates a triple of t's,
four g generates a quadruple of t's,
vector n g generates a list of n t's.
If xs is a list, then elements xs generates an arbitrary element of xs.

Default Generators

FsCheck uses static members of the type Gen to define default test data generators for some types. FsCheck defines instances for the types (), bool, int, float, pairs, triples, quadruples, lists, and functions. You can define new ones by making new instances of 'a Gen.

To generate random functions of type 'a->'b, you need to provide an instance of type 'a-> 'b Gen -> 'b Gen, which we'll call the cogenerator. The implementation of ('a->'b) Gen uses a cogenerator for type a. If you only want to generate random values of a type, you need only to define a generator for that type, while if you want to generate random functions over the type also, then you should define a cogenerator as well.

A cogenerator function interprets a value of type a as a generator transformer. It should be defined so that different values are interpreted as independent generator transformers. These can be programmed using the function

val variant : (int -> 'a Gen -> 'a Gen)

For different natural numbers i and j, variant i g and variant j g are independent generator transformers. The argument of variant must be non-negative, and, for efficiency, should be small. Cogenerators can be defined by composing together generator transformers constructed with variant.

For example,for the type Tree defined above, a suitable instance of a cogenerator, allowing you to define functions Tree -> 'a, can be defined as follows

let rec cotree t = 
    match t with
       | (Leaf n) -> variant 0 << Co.Int n
       | (Branch (t1,t2)) -> variant 1 << cotree t1 << cotree t2

Properties of Functions

Since FsCheck can generate random function values, it can check properties of functions. For example, we can check associativity of function composition as follows:

let treegen = (Gen.Tuple(tree,three (Gen.Arrow(cotree,tree))))
let prop_Assoc gen = forAll gen (fun (x,(f,g,h)) -> 
    propl ( ((f >> g) >> h) x = (f >> ( g >> h)) x ))

where we use the generator and cogenerator for trees defined above; we thus generate functions Tree -> Tree. If a counter-example is found, function values will be displayed as "<func>".

FsCheck internals

FsCheck follows the Haskell implementation of QuickCheck almost literally. For some explanation, read the original QuickCheck paper.

In the implementation, there are still a few issues that I'm unhappy with:

I ported Haskell's random implementation, but I'm still not 100% satisfied with it.
decodeFloat is somewhat amateurish. Might even be wrong. I need to test the generator for floats more thoroughly.
It would be cool to have more standard generators, e.g. for strings and more .net oriented types, like Func<>, TimeSpan, DateTime and so on.

Download

Finally, download the latest Visual Studio solution from my Skydrive folder: FsCheck 0.2

Older releases:

FsCheck 0.1

Enjoy!

Technorati: fscheck,quickcheck,random testing,F#

WPF Pointers

2008-04-11T22:59:00.001+01:00

I recently went to a session at Microsoft Belgium for ISV's, where Tim Sneath gave a packed session about WPF, answering some question but mainly giving a wealth of pointers of the WPF related information out there. Enjoy!

WPF/Silverlight reference applications

Silverlight in financials

Family.Show

NBC Olympics in Silverlight (Tim showed a demo but it was local on his machine - don't think it is publicly available as the time of this writing)

Hard rock memorabilia (Tim also showed an application for actually making the deep zoom effect that you can see on the site, I guess it's included when with Silverlight 2 somehow?)

WPF Performance

WPF performance blog

WPF Performance white paper

Optimizing WPF performance on MSDN

WPF Performance suite download

WPF controls and dev tools

Kevin's bag-o-tricks

Kaxaml (XamlPad, but better)

Blendables (the only link in this list which is not free, but some nice samples in the blog, so worthwhile to visit even if you're not spending)

Snoop

Mole

Neat Trick

Did you know that an .xps file is actually just a zip file with various files in them, and that one of those files contains a xaml dialect? This is really cool to export clip art from office. Tim just took a random Office piece of clip art, printed it to xps, renamed the file extension to .zip, unpack and pasted a part of one of the files in XamlPad. One or two adjustments for fonts later, and the clip art displayed in XamlPad. Nice to keep in mind!

Technorati: WPF

Parsing Dot with F#: Part 2 - The lexer

2008-04-09T22:04:00.001+01:00

Now that the preliminaries are over, we can get on with using the first part in the fslex/fsyacc tandem: the lexer. The lexer's responsibility is to break up the long input text into tokens that are better manageable for the parser, which in turn will produce the actual abstract syntax tree. So, instead of having to deal with the string "digraph MyGraph { 0 [label="a string_{}"] }", the lexer will turn this into a list of tokens, where each token can be attributed with some information. For the example, the output of our lexer is the following list of tokens: DIGRAPH ID["MyGraph"] LACC ID["0"] LBR ID["label"] ASSIGN ID["a string_{}"] RBR RACC. As you can see, the only token with an attribute is the ID, in which all kinds of string names are parsed. Notice also that any ID string can contain "control characters" like { and }. The lexer's main job is to filter those kinds of things out so the parser's job is much easier.

You can tell fslex how to tokenize a string by providing it with a list of rules. Each rule is a series of regular expressions-action pairs, each producing an (attributed) token. These rules are specified in a special format, which is pre-processed to an actual F# code file by the fslex tool. I'm not going to explain that in detail, there are other sources for that.

Our parser.fsl file starts with some preliminaries:

{
open System
open DotParser
open Lexing
}

let digit = ['0'-'9']
let whitespace = [' ' '\t' ]
let newline = ('\n' | '\r' '\n')
let letter = [ 'a'-'z' 'A'-'Z' '_']

Notice here that, besides opening the System and Lexing namespaces, the DotParser namespace is opened. That's because the type that defines the tokens (actually a regular discriminated union type) is defined in the fsyacc file. We'll come back to that in the next post. Then, some basic regular expressions that are useful for almost any parser, are defined. If you're at all familiar with regular expressions, this stuff should be easy. Notcie that these are just regular let variable bindings in F#. Fslex just translates this file to actual F# code, so you're free to use F# constructs as you see fit.

Our actual parser consists of 2 rules. This is the first:

rule token = parse
| whitespace     { token lexbuf }
| ('\r' | '\t')  { token lexbuf }
| "digraph"      { DIGRAPH }
| "node"         { NODE }
| "edge"         { EDGE }
| "graph"        { GRAPH }
| "->"           { DIEDGE }
| "--"           { UNEDGE }
| "\""           { ID ( (string lexbuf.StartPos "" lexbuf) ) }
| '{'            { LACC }
| '}'            { RACC }
| '['            { LPAREN }
| ']'            { RPAREN }
| ';'            { SEMI }
| ','            { COMMA }
| '='            { ASSIGN }
| letter(letter|digit)*                { ID (lexeme lexbuf) }
| ['-']?('.'digit+ | digit+('.'digit*)? ) { ID (lexeme lexbuf) }
| newline        { lexbuf.EndPos <- lexbuf.EndPos.NextLine; token lexbuf }
| eof            { EOF }

On the left, written like a pattern match, are the regular expressions that will be matched against the input string. On the right, the tokens that are returned. As you can see in the line for lexing IDs, you can access the current lexeme, i.e. the currently-being-lexed part of the input string, by calling lexeme lexbuf. Just skipping the current lexeme can be achieved by calling token lexbuf. Also, it is useful if you keep track of the line number for debugging later. That's what the action in the newline pattern does.

One gotcha here is that the order of these regular expressions matter not only for lexing (a line higher up will take precedence over a lower line), but also for type inference. The above rule needed no type annotations, but try placing the newline rule at the top; after pre-processing, F# will complain during compilation that it needs some type annotations. It's not a big deal, but if the order does not matter for lexing, it is nicer and more flexible to change later if you don't need to put any type annotations.

One line in the above sample may puzzle you:

| "\""            { ID ( (string lexbuf.StartPos "" lexbuf) ) }

That's because this calls a second rule, called string, which parses a string,i.e. something between double quotes ("). We go into this second rule when we encounter an open double quotes in the input. Such multiple rules are useful when you have different contexts in the input string in which different lexing rules apply. For dot, a string can contain characters such as brackets, arrows, semicolons and such that have a particular meaning in the main dot file. But when they're between double quotes, the lexer is in another context, where these characters lose their meaning and should just be added to a string that is part of the name of some entity. So once we encounter a " in our main file, we start parsing with the second rule; once the second rule finds a ", we return the string parsed so far and continue in the main rule:

and string pos s = parse
| "\\"    { string pos s lexbuf }
| "\r"    { string pos s lexbuf }
| "\""    { s }
| "\n"    { lexbuf.EndPos <- lexbuf.EndPos.NextLine;
            string pos s lexbuf }
| eof     { failwithf "end of file in string started at or near %A" pos }
| _       { string pos (s + (Lexing.lexeme lexbuf)) lexbuf }

As you can see, the string function takes the pos of the start of the string (for debugging) and accumulates the string in its parameter s. If the third pattern matches, the rule is finished: we've encountered the second ". The last pattern matches with anything that isn't matched by the previous lines, so we add it to the s accumulator.

The other matches, 1st 2nd and 4th match, are control characters that are simply skipped, and in the case of newline we update the line number. I did this because graphviz has the annoying habit of inserting a newline after a certain number of characters on one line. Presumably this is for readability, but why anyone would want to read dot files is beyond me. Anyway, Graphviz inserts a \ followed by \r in such cases, and this is what the two first rules filter out. This solved quite some pains afterwards when interpreting IDs ("230,345" is a much easier string to interpret than "230,3\\r45", especially when you don't know if, when or where graphviz will insert a line break. Yes, it actually did this in the middle of numbers.).

By the way, another typical example where it is useful to have multiple rules is when you would like to parse comments; also there the normal lexing rule does not apply. In fact, I adapted the above string function from a similar function designed to parse comments in the excellent Expert F# book.

That's it for the lexer. Paste all the stuff from this post together, and you should have a working .fsl file. Not compilable yet I'm afraid, you need the token definitions which are produced by the parser (remember the open DotParser?).

You've made it halfway! Next post: the parser.

Technorati: F#,fslex,fsyacc,parsing

Parsing Dot with F#: Part 1

2008-04-02T17:08:00.000+01:00

A while back I decided to write a parser for dot, the language used by Graphviz. This is both my first real project in F#, and in parsing. I learned the basics from the excellent Expert F# book.

I'll try to explain my solution, using fslex and fsyacc, in the order that I tackled the problem. There are a few more basic examples out there, explaining what parsing is, what a lexer and a parser are etc., However it seems the examples given are always small, typically parsing some expressions. Graphviz' dot definitely has more of a real world flavor, and I'll present it as a real world example of using fslex and fsyacc, without explaining much about those tools per se.

This is how I see this mini-series play out:

Simplified dot grammar and abstract syntax tree
The lexer
The parser
Putting it all together

This post is part 1.

Graphviz

Graphviz is a command line tool that takes a description of a graph as input, and outputs a description (or an image) of a layout of the graph. For example, as input you can give:

digraph G {
0 [label="Type1<>", shape=box];
1 [label="Type1<Type2>", shape=box];
2 [label="T", shape=box];
3 [label="Type2", shape=box];
4 [label="Type2[], Type2*, Type2&", shape=box];
5 [label="#Type2", shape=box];
6 [label="Type2.Type3", shape=box];
0 -> 1 [ label="MakeGenericType(Type2)"];
0 -> 2 [ label="GetGenericArguments()"];
1 -> 0 [ label="GetGenericTypeDefinition()"];
1 -> 3 [ label="GetGenericArguments()"];
2 -> 0 [ label="DeclaringType"];
3 -> 4 [ label="MakeArrayType(), MakePointerType(), MakeByRefType()"];
3 -> 6 [ label="GetNestedType(Type3.Name)"];
4 -> 3 [ label="GetElementType()"];
5 -> 3 [ label="BaseType"];
6 -> 3 [ label="DeclaringType"];
}

Basically, just a sequence of nodes and edges annotated with attributes. In the above example, only label and shape are used, but dot supports many, many more. Given such a file, graphviz outputs:

digraph G {
    node [label="\N"];
    graph [bb="0,0,1028,328"];
    0 [label="Type1<>", shape=box, pos="502,302", width="1.03", height="0.50"];
    1 [label="Type1<Type2>", shape=box, pos="380,210", width="1.61", height="0.50"];
    2 [label=T, shape=box, pos="625,210", width="0.75", height="0.50"];
    3 [label=Type2, shape=box, pos="568,118", width="0.78", height="0.50"];
    4 [label="Type2[], Type2*, Type2&", shape=box, pos="249,26", width="2.61", height="0.50"];
    5 [label="#Type2", shape=box, pos="703,210", width="0.92", height="0.50"];
    6 [label="Type2.Type3", shape=box, pos="784,26", width="1.42", height="0.50"];
    0 -> 1 [label="MakeGenericType(Type2)", pos="e,322,216 465,301 381,298 181,288 161,266 156,259 156,252 161,246 170,235 252,223 312,217", lp="263,256"];
    0 -> 2 [label="GetGenericArguments()", pos="e,623,228 539,298 561,293 589,284 607,266 615,258 619,247 621,237", lp="708,256"];
    1 -> 0 [label="GetGenericTypeDefinition()", pos="s,465,293 455,290 430,284 403,275 394,266 385,256 381,240 380,228", lp="504,256"];
    1 -> 3 [label="GetGenericArguments()", pos="e,540,121 394,192 405,179 420,163 437,154 467,137 504,128 531,123", lp="528,164"];
    2 -> 0 [label=DeclaringType, pos="s,539,300 548,300 628,295 785,284 802,266 807,259 807,252 802,246 781,222 691,237 661,228 658,227 655,226 652,225", lp="863,256"];
    3 -> 4 [label="MakeArrayType(), MakePointerType(), MakeByRefType()", pos="e,155,36 540,117 432,114 50,100 32,82 26,75 27,68 32,62 40,53 93,44 145,37", lp="251,72"];
    3 -> 6 [label="GetNestedType(Type3.Name)", pos="e,733,40 596,101 616,89 645,73 671,62 688,54 707,48 725,43", lp="781,72"];
    4 -> 3 [label="GetElementType()", pos="s,540,110 532,107 515,100 495,92 480,82 470,75 472,67 461,62 441,51 390,42 343,36", lp="557,72"];
    5 -> 3 [label=BaseType, pos="e,595,136 676,192 655,178 625,157 602,141", lp="692,164"];
    6 -> 3 [label=DeclaringType, pos="s,596,117 605,117 687,113 875,103 894,82 915,58 873,43 835,34", lp="956,72"];
}

The basic structure of the file is the same: a sequence of nodes and edges, but Graphviz has added position, height, width and other layout info. This is actually the file that was used to draw the graph in my previous post.

The dot grammar

When parsing using fslex and fsyacc, the first thing you should find or make is a grammar of the thing you're trying to parse. Everything else sort of flows from there. Luckily, the complete dot grammar can be found here. I thought it was a bit complicated for my purposes, so I simplified the grammar a bit:

(in the following, terminals are shown in bold. Literal characters are given in single quotes. Parentheses ( and ) indicate grouping when needed. Square brackets [ and ] enclose optional items. Vertical bars | separate alternatives.)

graph    :    digraph [ ID ] '{' stmt_list '}'
stmt_list:    [ stmt [ ';' ] [ stmt_list ] ]
stmt     :    node_stmt
         |    edge_stmt
         |    attr_stmt /*defines a default attribute*/
attr_stmt:    (graph | node | edge) attr_list
attr_list:    '[' attr  [ ',' ] [ attr_list ] ']' 
atrtr    :    ID '=' ID  
edge_stmt:    node_id -> node_id [ attr_list ]
node_stmt:    node_id [ attr_list ]
node_id  :    INT

If you compare with the original dot grammar, I made the following simplifications:

No node ports
No sub-graphs
No short definition of multiple edges (a -> b -> c)
no HTML IDs
only digraphs

Basically this grammar says that a graph is "digraph name { bunch of node, edge or default statements }". We've already seen node and edge statements; default statements basically just set an attribute on all the nodes and edges that follow. It is overridden by an attribute of the same name on a node or edge itself, or by a new default statement.

The abstract syntax tree

Based on that grammar, I came up with the following abstract syntax tree using F# discriminated unions:

#light

open List
open System
open System.Collections.Generic

type Attributes = Dictionary<string,string>

type Element = 
    | Node of string * Attributes
    | Edge of string * string * Attributes
    | GraphAttributeList of Attributes
    | NodeAttributeList of Attributes
    | EdgeAttributeList of Attributes

type Graph = Graph of List<Element>

It's easiest to read this from bottom to top (unfortunately it needs to be defined the other way round, otherwise F# has difficulty parsing). A graph is a list of elements. An element can either be a node, an edge or a default attribute list for the graph, the subsequent nodes or the subsequent edges. Each of these elements can have a number of attributes. Attributes are simply presented as a Dictionary. The abstract syntax tree was fairly straightforward to build from the grammar; I expect the same for any well-written grammar.

The abstract syntax tree is the parser's interface to the outside, so it's important that you think about how you're going to use the parser when making decisions about the representation of the abstract syntax tree. For example, I took care not to use any F# specific types in the above AST definition, so that client assemblies in other language would not need to reference F# specific assemblies. On that topic, don't forget to compile your F# assemblies with the --standalone flag, otherwise client assemblies will still need some F# specific libraries (e.g. discriminated unions implement IStructuralHash, so clients also need to know this interface).

Another issue you should think about is how 'deep' you want to parse. For example, it would be theoretically possible to define separate cases for each of the different types of attributes that can be generated by Graphviz. This would also allow us to parse some of the arguments (e.g. the list of position coordinates could be parsed into a list of tuples). However, given the large amount and frequent changes in Graphviz dot attributes, I choose not to take this route.

Next episode: the lexer!

Technorati: F#,fslex,fsyacc,parsing,graphviz

Reflection: Type unraveled

2008-03-16T22:02:00.001Z

The Type class in .NET is not the easiest to understand, I believe because of the many different "kinds of types" that are modeled by it: generic types, generic type parameters, reference types, pointer types, array types, etc. Furthermore, sometimes you have one kind of type (e.g. a generic type) and want to make another kind (i.e. "instantiate" a generic parameter with another type). The Type class offers all the necessary methods to do the feasible conversions; however it is not always easy to find. The following graph should help.

The boxes show the different kinds of types that exist. An example of Type1<> is typeof(IList<>); Type1<Type2> is typeof(IList<string>) and so on. The arrows denote how you can obtain one kind of type from the other. For example, if you have a generic type definition (e.g. typeof(IList<>)) you can make this into an instantiatable type (typeof(IList<string>))by calling typeof(IList<>).MakeGenericType(typeof(string)). With "#Type2" I mean a subtype of Type2.

Hope this helps someone.

PS the graph was laid out by Graphviz's dot layout. It was rendered using a self-made WPF control. More on that later.

Technorati : .NET, Type, reflection
Del.icio.us : .NET, Type, reflection

A graph control for WPF

2008-03-15T22:37:00.001Z

Recently, I decided to write a WPF control that can display graphs (I mean, the kind with edges and nodes; not charts). This post describes the beginning of that little project. It does not contain many technical details, just a few hints and pointers for anyone who would like to start a similar project.

I have the time nor the inclination to write a graph layout algorithm myself. Graph algorithms are complex and fairly specific, and I couldn't really find a good overview of the algorithms involved on the net. I found many references to papers, but it seems some papers are hard to get if you don't have a subscription to the ACM portal. (When I was still a PhD candidate this stuff was much easier). So much for free science.

Maybe I can reuse a graph layout algorithm from some existing Winforms control? After some searching, it seems that .NET lacks a free graph layout control. A good graph algorithm library is QuickGraph , but as far as I can see it does not offer any algorithm for layout. Another library is GLEE from Microsoft, but that's is not available for commercial usage (something I'd like for later when my imaginary startup will take over the world).

Outside the .NET world then? After all, .NET has excellent interoperability.
Graphviz by AT&T is an excellent graph layout utility. Not only can it do beautiful hierarchical graphs (like GLEE does) it can also do spring layout and radial graphs, is fast and is highly configurable. Graphviz reads graphs in a proprietary format, called dot. It then layouts the graph, and can export to a variety of formats, of which attributed dot is one. Attributed dot is basically the same as the dot input file, but attributed with node, edge and label positions, as well as other layout info.

Another C++ based alternative is Dynagraph which is a daughter of Graphviz but is geared toward dynamical graph layout. Whereas Graphviz takes an input graph, does layout and produces an output graph, Dynagraph can add and delete nodes and edges incrementally, keeping existing positions the same as much as possible.

	Graphviz	Dynagraph
.NET interoperability	COM, using Wingraphviz dot in/any out	P/Invoke (COM) 'incrface' in and out dot
Maintained	Actively	Hardly
Incremental	No	Yes
Algorithms	Hierarchical, spring, radial, circular	Hierarchical
Speed	Fast, even for large graphs	Noticeably slower than Graphviz for large graphs

After some tinkering with Dynagraph, which I liked better at first because of its flexibility, and after some back and forth email with Gordon Woodhull, the maintainer of Dynagraph, it turned out that Dynagraph COM support is not completely implemented yet. By the time we came to that conclusion, I had already sort of given up and started on an interface for Graphviz using the Wingraphviz COM interface.

It turns out that a few people before me had thought of that. Quickgraph can actually output a dot file to be consumed by Graphviz. Furthermore, D ot2Wpf is a WPF control that parses output from Graphviz.

You'd think I'm done, right? So did I. However, there were a few more things I expected from my graph control than dot2wpf offered. For example, I'd like to change the color or line style of an edge without having to do a complete layout of the graph. So I figured I'd take the dot2wpf source and add some features. That didn't quite work out as planned.
That's because dot2wpf actually parses the 'plain' output format of Graphviz. It is supposedly easier to parse than the dot output format, but loses some information. It turns out that it contains a flaw: for cyclic graphs, the plain format does not allow you to determine whether an arrow should be at the beginning or the end of an edge. Graphviz' hierarchical layout algorithm cannot handle cycles, so it reverses one edge in a cycle automatically for layout purposes. However, in the plain output format there is no indication of this reversal, and the points of the edge are given in the reverse direction. There's no way for dot2wpf to distinguish these reversed edges from normal edges in the plain output format, so it has no way to determine where to draw the arrow.

That one took me a while to figure out.

So it turns out that to make a faithful representation of a graph layout by Graphviz, I need to parse the (fairly complicated) dot output format of Graphviz. So my idea now is that the WPF graph control takes as input a string containing a dot representation of the graph it should draw (such a dot representation is easy to get from e.g. Quickgraph), passes this string to Graphviz which passes an annotated dot file back. The control parses it, and draws the visuals on the canvas.

Since I've been wanting to learn F# for a while, and F# comes with a bunch of parsing tools (fslex and fsyacc), I thought it would be a good idea to use F# to write a dot parser - it could be useful for other things than the graph control. More on parsing with F# in a later post.

Technorati : .NET, WPF, dynagraph, graphviz
Del.icio.us : .NET, WPF, dynagraph, graphviz

Comparing presentation styles

2008-01-14T09:45:00.000Z

I recently watched a recorded presentation by Jim Hugunin and John Lam, entitled "Just Glue It! Ruby and the DLR in Silverlight".

The presentation made me wish that more performers would be like Edsger W. Dijkstra, or at least make an effort towards imitating his style. See and listen for yourself, and I hope you'll share my preference. Unfortunately the "demo-oriented" presentation style, in which contrived demonstrations that require nor provide any insight are exchanged for content, is becoming common.

PS I would like to add that, judging from their blogs, both Jim Hugunin and John Lam are intelligent, creative and well-spoken human beings. Which makes their performance all the more saddening: it may be a cultural phenomenon.

Writing WCF config files programmatically and dynamically

2007-11-21T07:45:00.000Z

OK, so I said I'd write a series of posts on WPF first, but this came up the other day.

Problem

Suppose you need to write a wizard-type application where you allow a user to expose a service over WCF (maybe allowing the input of a port number and name). At the same time, you want to allow so-called power-users to just edit the app.config file and change WCF details, such as various binding parameters. (The same mechanism applies for the client side.)

So, what you need is to write a WCF configuration, let's say exposing a service, on the fly to the app.config file, and then opening a ServiceHost that uses the configuration that was just written.

Solution

Let's start of with a very simple example. First, the service contract.

[ServiceContract] internal interface ISimpleService { [OperationContract] string AddWordToString( string input ); }

Now, a service that implements this contract:

[ServiceBehavior( InstanceContextMode=InstanceContextMode.Single )] public class SimpleService : ISimpleService { #region ISimpleService Members public string AddWordToString( string input ) { return input + " and a word"; } #endregion }

So, what we want to do now is, in code, expose a SimpleService over WCF, while updating the app.config file so that it shows the configuration of the exposed service.

So, the idea is to first write to the WCF config file, and then use a standard ServiceHost call on the service type to allow WCF to read the configuration from app.config, and expose the service. The following code snippet achieves this:

//first write the service config for the service WriteWCFConfig( typeof(SimpleService), typeof(ISimpleService) ); //now try to open the wcf service ServiceHost host = new ServiceHost( new SimpleService() ); host.Open();

For the WriteWCFConfig method (of course, the crux of the matter), I recommend reading this blog post, which gives an overview of the object model for the WCF configuration sections (which is basically an implementation of System.Configuration).

private static int portNumber = 12000; private static void WriteWCFConfig(Type serviceType, Type contractType) { //standard method from System.Configuration Configuration appConfig = ConfigurationManager.OpenExeConfiguration( ConfigurationUserLevel.None ); //the main section in the app.config file for WCF ServiceModelSectionGroup serviceModel = ServiceModelSectionGroup.GetSectionGroup( appConfig ); //the section ServiceElementCollection serviceSection = serviceModel.Services.Services; //a new configuration for a service ServiceElement newService = new ServiceElement( serviceType.FullName ); if ( !serviceSection.ContainsKey( serviceType.FullName ) ) { ServiceEndpointElement endpoint = new ServiceEndpointElement( new Uri( "net.tcp://localhost:" + portNumber ), contractType.FullName ); portNumber++; endpoint.Binding = "netTcpBinding"; newService.Endpoints.Add( endpoint ); serviceSection.Add( newService ); appConfig.Save(); } }

THe code above basically uses the System.Configuration API to get an object model for the exising app.config file, uses the API in System.ServiceModel.Configuration to build up the necessary configuration section for a new service, and then saves the config file back to disk. Once this is done, WCF can read the config file, and the code snippet above will work.

However, there is one catch: suppose that, after writing a config and opening a service using ServiceHost, you want to add a new service, like this:

//first write the service config for the service WriteWCFConfig( typeof(SimpleService), typeof(ISimpleService) ); //now try to open the wcf service ServiceHost host = new ServiceHost( new SimpleService() ); host.Open(); //do this again with another service WriteWCFConfig( typeof( AnotherSimpleService ), typeof( ISimpleService ) ); ServiceHost host2 = new ServiceHost( new AnotherSimpleService() ); host2.Open();

This won't work, because WCF (or rather, System.Configuration which is used by WCF to read the app.config file) only reads the app.config file once, and then uses its cache. However, you can force System.Configuration to re-read a certain section of the app.config file from disk, using:

ConfigurationManager.RefreshSection( serviceModel.Services.SectionInformation.SectionName );

Add this line to the obvious place in WriteWCFConfig, and all will work as planned. For the client side, an identical strategy can be used.

First post

2007-11-11T15:14:00.000Z

Hello world, A first blog post, in what I hope to be a long series. The main topic of this blog is probably going to be .NET and related technologies, since I'm working with those daily. In time, I'd also like to blog about some more research oriented topics, most notably languages like Haskell and Spec#. Finally, I'm also particularly interested in the topic of software architecture. Hope you will enjoy my blog...