Rash thoughts about .NET, C#, F# and Dynamics NAV.


"Every solution will only lead to new problems."

Category Informatik

Wednesday, 15. January 2014


FSharp.Configuration 0.1 released

Filed under: C#,F#,Informatik — Steffen Forkmann at 13:40 Uhr

As part of a longer process of making FSharpx better maintainable I created a new project called FSharp.Configuration. It contains type providers for the configuration of .NET projects:

Yaml type provider

Additonal information:

Please tell me what you think.

Tuesday, 14. January 2014


FSharpx.Collections 1.9 released

Filed under: .NET,C#,F#,FAKE - F# Make,Informatik — Steffen Forkmann at 11:29 Uhr

I’m happy to annouce the new release of the FSharpx.Collections package on nuget.

Most important changes:

Please tell me if it works for you.

Wednesday, 3. April 2013


A tale of nulls – part I

Filed under: F#,Informatik — Steffen Forkmann at 17:43 Uhr

Triggered by a short tweet by Tomas Petricek and a blog post by Don Syme I had a couple of conservations about null as a value, Null as a type (Nothing in Scala), the null object pattern and the Maybe monad (or Option type in F#). I decided to share my opinion on this topic in order to help others to make their own opinion.

Part I – Null as a value

Unfortunately most programming languages have some kind of null pointer. We are now even at a point where some people claim that Tony Hoare’s famous billion dollar mistake costs actually a billion dollar per year.

But before we start to think about solutions to the null pointer problem let us first see where null values might come in handy.

Uninitialized values

In a statement oriented language like C# it is sometimes not that easy to represent uninitialized state.

As you can see we forgot to initialize peter in the missing "else-branch" which might lead to a NullReferenceException. There are a couple of things we can do to prevent this from happening. First of all we should omit the explicit initialization with null:

In this case the C# compiler throws an error telling us "Use of unassigned local variable ‘peter’".

In expression oriented languages like F# the problem doesn’t exist. We usually write initializations like this:

image

There is no way to forget the else branch since the types don’t match.

Unknown values

Consider a search function which tries to find a Person in a list:

Unknown values are probably the most common cause for the introduction of nulls and in contrast to uninitialized values they have much more global effects.

Solutions to unknown values

1. Using explicit exceptions

One easy solution to get rid of the nulls is to make the exception explicit:

One benefit here is that we have a concrete exception which is telling us what went wrong. Unfortunately nothing forces us to handle this exception in the calling method. This means the program can still crash. Another problem is that if we use try/catch as a control flow statement (i.e. use it very very often) then we might slow down our program.

And there is still a philosophical question: is it really an exception if we don’t have a person in our repository?

2. Using out parameters and returning bools

If we want to make the result of our search a little more explicit we can also introduce a boolean return value:

This is a pattern which is actually used everywhere in the .NET framework, so it must be good right?!

Just a simple question here: What did we gain exactly? If we forget to check for nulls why would we remember to check the bool?

There is another interesting observation here. Due to the introduction of out parameters we also introduce the uninitialized value problem in every calling method, which is bizarre.

3. Null object pattern

“In object-oriented computer programming, a Null Object is an object with defined neutral ("null") behavior. The Null Object design pattern describes the uses of such objects and their behavior (or lack thereof).”

Wikipedia

So obviously this makes only sense in a context where objects have observable behavior. So let’s add some behavior to our Person class:

Let’s look at this solution for a moment.

  • Pro: Implementation of missing behavior is trivial
  • Pro: We don’t introduce null values –> we won’t get NullReferenceExceptions
  • Pro: The name of the class carries information about the reason for the null value
  • Cons: In order to to get rid of the Person(string name, int age) constructor in the null-object we had to introduce an interface
  • Cons: In order to use the interface we had to modify the Person class. This might be a real problem if we don’t have access to the source. We would need some kind of ad-hoc polymorphism like Haskell’s type classes, Scala’s Traits or Clojure’s Protocols (read more about the expression problem)
  • Cons: Everything we want to do with Persons has to be part of the IPerson interface or we have to fall back to explicit runtime type tests, because there is no way to get to the data:

    image

  • Cons: Without ad-hoc polymorphism the Person class is getting more and more complex over time since we are adding all the behavior to it. Compare it with our starting point where it was a simple data representation. We totally lost that.
  • Cons: Errors/bugs might appear as normal program execution. [see Fowler, Martin (1999). Refactoring pp. 261]

Don’t use this approach it’s really not a good solution.

4. The Option type (a.k.a. Maybe monad)

The option type is a way to push the idea from 2. “returning bools” into the type system. There are lots of tutorials about the option type on the web, but for now it’s enough to know that it is something which is based on the following idea:

In order to allow pattern matching in C# we introduce a small helper:

With this idea we can get rid of all null values in the program, we don’t have to introduce an IPerson interface, the null case is type checked and the best thing is it’s really easy to create functions like IsOlderThan12:

Please don’t implement the option type yourself. Even in C# it’s much easier to just reference FSharp.Core.dll and use FSharpx (read 10 reasons to use the F# runtime in your C# app).

Of course this is only the tip of the iceberg. If you read more about the option type you will see that its monadic behavior allows all kinds of awesome applications (e.g. LINQ, folds, map, …).

5. The Either type

One of the benefits of the null object pattern above was that it allows to encode the reason for the missing value. In some cases we need the same thing for the maybe monad. So let’s try to capture the reason in the None case:

Now we can use this in the TryFindPerson method:

As with the option type please don’t rewrite this stuff yourself. There is a Choice type in F# which helps to capture this idea and Mauricio has a couple of blog posts which explain how to use it from C# (of course FSharpx is helping here again).

6. The (singleton) list monad

The option type captures the idea that we can either have one value or nothing. We can do the same thing with List<T>:

Of course this uses only a small subset of the power of IEnumerable<T> but I wanted to show the similarity to the maybe monad. You can read more about the “poor man’s option type” on Mauricio’s blog.

Conclusion

We saw a couple of very different solutions to get rid of null values. Normally I’d only use the option type or the either type (if I need to carry the reason). In some very rare situations (e.g. C# only projects) I would also use singleton lists.

I wouldn’t use the other solutions. They are potentially dangerous, especially if your project gets bigger.

I would be happy to read your opinions.

Tags: , ,

Tuesday, 11. December 2012


Testing, proving, checking – How to verify code properties

Filed under: F#,Informatik — Steffen Forkmann at 13:12 Uhr

As programmers we often want to express that a special property holds for a method, e.g. we want to say that the associativity law holds for list concatenation. In F# we could define a concat method like this:

As programmers we could write a couple of unit tests which try to check the associativity law. With NUnit enabled we could write this:

But the question is: did we cover all interesting cases? In computer science we have a method to prove that the property holds for all lists. This methods is called structural induction (see also this video lecture by Martin Odersky) and would look like this:

1) Rewrite the code as equations
concat ([],ys)    = ys                  [CON1]
concat (x::xs,ys) = x :: concat(xs,ys)  [CON2]
2) Rewrite the property as an equation
concat(concat(xs,ys),zs) = concat(xs,concat(ys,zs))
3) Check the base case
concat(concat([],ys),zs) 
= concat ([],zs) // using CON1 = [] // using CON1
concat([],concat(ys,zs))

= concat (ys,zs) // using CON1
= [] // using CON1
3) Show the inductive step
concat(concat(x::xs,ys),zs) 

= concat (x::concat(xs,ys),zs)) // using CON2
= x :: concat(concat(xs,ys),zs) // using CON2
= x :: concat(xs,concat(ys,zs)) // induction hypothesis
= concat(x::xs,concat(ys,zs)) // using CON2

This math is very clean and shows that the associativity law holds for all lists. Unfortunately even with a slightly more complicated sample this gets at least tricky. Try to prove that reverse(reverse(xs)) = xs with reversed defined as:

As you will see the naïve approach with structural induction will fail (for a nice solution see this video lecture).

There is even a bigger problem with the proof: one assumption of induction is referential transparency of the given functions. We can’t always assume this.

So we can’t always (easily) proof code properties and we don’t want to write too many unit tests – then what can we do?

One compromise solution is to use a tool which systematically generates instances for our tests. There are a couple of tools out there, e.g. there is QuickCheck for Haskell or PEX for .NET. In F# we can use a tool called FsCheck:

Of course a test like this doesn’t prove that the property holds for all lists, but at least it verifies all bases cases and probably a lot more cases than one would manually do.

If you introduce a bug you get a nice report, which even shows a counterexample:

fscheck

It’s even possible to add these tests to your test suite and to run them during the CI build. So don’t stop at classical unit test – check code properties!

Tags:

Tuesday, 18. September 2012


Dev Open Space 2012 – 19.-21.10.2012 in Leipzig

Filed under: Coding Dojo,F#,NaturalSpec,Veranstaltungen — Steffen Forkmann at 7:08 Uhr

Open Source. Open Space. Developer Open Space Nachdem es sich die letzten beiden Jahre mehr und mehr angekündigt hat, wurde der .NET Open Space in Leipzig nun in Dev Open Space 2012 umgetauft. Dies trägt dem Punkt Rechnung, dass die Themenwünsche der Teilnehmer immer breiter geworden sind und wir uns vor allem auch über git, Ruby, JavaScript, HTML5, node.js, CQRS und vieles mehr unterhalten haben. Weiterhin wird es natürlich trotzdem noch reine .NET-Themen geben.

Neu sind außerdem die kostenlosen Workshops die bereits einen Tag vor dem OpenSpace angeboten werden. Ich selbst werde einen zu F# und Test Driven Development halten:

“Test Driven Development (TDD) bringt viele Vorteile für den Code aber erfordert auch eine Menge Übung. Dieser Workshop zeigt, wie man TDD mit F# mittels NaturalSpec and NCrunch erfolgreich einsetzt. NaturalSpec ist ein F#-TDD- Framework, mit dem Unit Tests auf sehr intuitive Weise ausgedrückt werden können. NCrunch hilft, diese Tests ständig (bei jedem Tastendruck) auszuführen. Das zusammen ergibt einen sehr schnellen Feedbackzyklus und TDD wird deutlich schneller. Nach einer kurzen Einführung in die Tools werden im Workshop gemeinsam kleine Programmieraufgaben gelöst.”

Die Anmeldung ist bereits möglich.

Tags: ,

Thursday, 13. September 2012


Skillsmatter “Progressive F# Tutorials 2012” session in London

Filed under: F#,NaturalSpec,Veranstaltungen — Steffen Forkmann at 15:54 Uhr

I’m happy to announce that I’m giving one of the “Progressive F# Tutorials 2012” in London this year. This event is going to be legendary. Abstract:

Test-Driven Development can give you a lot of benefits for your code but also needs a lot of practice. Come to this session and learn how to master TDD with F#, NaturalSpec and NCrunch.

NaturalSpec is a F# TDD framework which allows to express tests in a very intuitive way and NCrunch helps to execute these tests continuously on very key stroke. This gives a very fast feedback loop and helps to speed up your TDD coding.

After a short introduction of the tools we’ll try to solve a small coding problem together in a coding dojo. All skill levels are welcome and the session will give a lot of room to try out new ideas.

Book your tickets for this awesome event.

Tags: ,

Graph type providers in FSharpx

Filed under: C#,F#,Informatik,Mathematik — Steffen Forkmann at 9:24 Uhr

After the official Visual Studio 2012 launch yesterday I think it’s a good idea to announce two new type providers which are based on the DGMLTypeProvider from the F# 3.0 Sample Pack.

Synchronous and asynchronous state machine

The first one is only a small extension to the DGMLTypeProvider by Tao. which allows to generate state machines from DGML files. The extension is simply that you can choose between the original async state machine and a synchronous version, which allows easier testing.

image

If you want the async version, which performs all state transitions asynchronously, you only have to write AsyncStateMachine instead of StateMachine.

State machine as a network of types

The generated state machine performs only valid state transitions, but we can go one step further and model the state transitions as compile time restrictions:

image

As you can see the compiler knows that we are in State2 and allows only the transitions to State3 and State4.

If you write labels on the edges of the graph the type provider will generate the method names based on the edge label. In the following sample I’ve created a small finite-state machine which allows to check a binary number if it has an even or odd number of zeros:

image

As you can see in this case the compiler has already calculated that 10100 has an odd number of zeros – no need to run the test Zwinkerndes Smiley.

This stuff is already part of the FSharpx.TypeProviders.Graph package on nuget so please check it out and give feedback.

Tags: , ,

Wednesday, 17. August 2011


Some special monads in F# – Part 5 of n – Application: Poker – Your chance to get rich!

Filed under: F#,Informatik — Steffen Forkmann at 8:52 Uhr

In the last part of this blog series I showed how we can utilize the DistributionMonad in order to solve the famous Monty Hall problem. This time I want to show you how we can use it to solve some basic Texas hold’em poker questions.

We start by defining a model for poker in F#:

As you can see we model cards as tuples of a rank and a suit. The complete deck is just a combination of all ranks with all suits.

Now we need some additional helpers for the DistributionMonad, which will allow us to draw cards from the deck. You can find further explanations about these helpers in the excellent paper by Martin Erwig and Steve Kollmansberger called "Functional Pearls: Probabilistic functional programming in Haskell". Like the DistributionMonad itself, these helpers are already in the FSharp.Monad project and you get the bits from nuget.org.

Now we are ready to perform our first query. Let’s see how we can compute the probability of drawing the Ace of Clubs and the Ace of Spades:

But we can easily go a step further:

If you keep this model in mind you might come up with a poker odds calculator on a smart phone. This might be your chance to get rich. ;-)

Tags: ,

Tuesday, 16. August 2011


Some special monads in F# – Part 4 of n – Application: The Monty Hall problem

Filed under: F#,Informatik — Steffen Forkmann at 10:34 Uhr

In the last part of this blog series I showed a DistributionMonad, which allows to perform queries to probability scenarios. Today we will use this monad in order to solve the famous Monty Hall problem. This article is based on the excellent paper by Martin Erwig and Steve Kollmansberger called "Functional Pearls: Probabilistic functional programming in Haskell".

“Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?”

[problem definition from Wikipedia]

Let’s start by modeling the first choice using the DistributionMonad:

As we can see the solution is 1/3 as we expected and if we don’t switch, we stay with these odds. But if we switch we might improve the probability for a car. Remember the host will always remove a Goat after your first pick. Let’s analyze the second pick if we switch:

Car behind First choice Temp. Outcome Host removes Switching to Outcome
Door 1 Door 1 Car Door 2 Door 3 Goat
Door 1 Door 1 Car Door 3 Door 2 Goat
Door 1 Door 2 Goat Door 3 Door 1 Car
Door 1 Door 3 Goat Door 2 Door 1 Car

If the Car is behind door 2 or door 3 the situation is symmetrical and therefor we can conclude, the following:

And if we run this, we get this nice solution:

Next time I will show how we can use the DistributionMonad to solve some basic poker scenarios.

Tags: ,

Monday, 15. August 2011


Some special monads in F# – Part 3 of n – DistributionMonad

Filed under: F#,Informatik — Steffen Forkmann at 18:41 Uhr

In part I of this blog series I showed a simple InfinityMonad, which allows to treat special calculations as infinity and in the second part I showed the UndoMonad, which defines an environment which allows to undo and redo state changes.

This and the following posts are based on a famous paper by Martin Erwig and Steve Kollmansberger called "Functional Pearls: Probabilistic functional programming in Haskell".

Let’s start by looking at a small scenario:

This simple query calculates the probability of the event, that an dice roll gives a value greater than 3 and an independent coin flip gives “Heads”. In order to do this the DistributionMonad enumerates all possibilities and calculates the joint probability using the following formula:

Probability

If we want the nice syntactic sugar we can easily define a computation expression builder:

In order to allow easier access to our monad, we define some helper functions and basic distributions for fair coins and dices:

In the next part of this blog series I will show how we can utilize the DistributionMonad in order to solve the famous Monty Hall problem.

Tags: ,