Codemania: How to not write a for loop

Slides and samples from my Codemania talk are up, over at Mindscape HQ.

Discriminated unions and interfaces

I wrote earlier about F# discriminated unions, and Chris in comments rightly reminded me that discriminated unions, like C# classes, can have member methods.  While I generally reckon separate functions are more idiomatic than members, there is one case where member methods are invaluable: when you want the discriminated union to implement an interface.

This isn’t as common as C# programmers might expect.  Because discriminated unions generally represent simple containers with minimal behavioural logic, the main interfaces you might think to implement are to do with things like equality and comparison – and F# implements those for you.  (Of course, sometimes you don’t want the default equality or ordering implementations, and that’s another scenario where you need to implement an interface – but in those cases there’s a bit more to it.)  Still, it does come up now and again, particularly with system interfaces or if you’re interoperating with C# code that might be more interface-oriented.

The way you implement an interface on a F# discriminated union is exactly the same as the way you implement it on a F# class: use the interface IWhatever with member… construct.  Let’s take a look.

Suppose we want a discriminated union that we can format for display in different ways, similar to the system DateTime or numeric types.  This capability is represented by the system IFormattable interface.  IFormattable has just one method, ToString, which makes it ideal for short demos.  Here’s a discriminated union that implements IFormattable:

type Booze =
   | SauvignonBlanc of string
   | MethylatedSpirit
   interface IFormattable with
     member this.ToString(format, formatProvider) =
       match this with
       | SauvignonBlanc rgn -> if format = "G" then
                                 "Sauvignon Blanc"
                               elif format = "R" then
                                 sprintf "%s Sauvignon Blanc" rgn
                               else
                                 failwith "unknown format"
       | MethylatedSpirit   -> "Amber Nectar"

There’s two bits to this definition: first, the definition of the discriminated union data type, and second, the interface implementation.  The data type definition – the first three lines – doesn’t contain any surprises.  What’s new is that after defining the various ‘cases’ of the union, we keep going with an interface implementation.  The syntax may look a bit weird if you’re a C# programmer but all this is doing is saying that the type implements IFormattable and here is the implementation of the IFormattable.ToString member.  The implementation itself is standard F# pattern matching and hopefully you can see roughly what it’s doing even if you find pipe characters daunting.

Notice that even though this is a member method we can’t define it separately on each ‘case’ the way we would with a virtual member in C#.  The individual cases of discriminated unions are dumb: everything has to be defined on the union type itself.  (A corollary of this is that interfaces can only be implemented on the union type, not on cases.  You couldn’t implement IDrinkable on the SauvignonBlanc case; you’d have to implement it on the Booze type, and live with the deadly consequences.)

When we put the interface implementation into action, there’s a surprise in store:

> let antifreeze = SauvignonBlanc "Austria";;
val antifreeze : Booze = SauvignonBlanc "Austria"
> antifreeze.ToString("R", CultureInfo.InvariantCulture);;
error FS0501: The member or object constructor 'ToString' takes 0 argument(s) but is here given 2. 
The required signature is 'Object.ToString() : string'. 

In C# terms, F# has gone for an explicit interface implementation instead of C#’s usual implicit interface implementation.  That means the interface member can be accessed only through a reference of the interface type:

> (antifreeze :> IFormattable).ToString("R", CultureInfo.InvariantCulture);;
val it : string = "Austria Sauvignon Blanc" 

You can get around this by defining the ToString() member directly on Booze as a member method, and having IFormattable.ToString() delegate to that member method – this is a common pattern for explicit interface implementation in C#, and it’s idiomatic in F# as well.

Implementing interfaces on discriminated unions isn’t all that common; but if you need to do it, now you know how!

Discriminated unions in F#

F# has lots of different ways of expressing composite data: tuples, records, classes, etc.  One way that doesn’t have a direct equivalent in C# or Visual Basic is the discriminated union.

A discriminated union is used when there are different ‘cases’ of the data type, potentially with different kinds of data depending on the case.  That probably sounds rather abstract, so let’s see a simple example:

type Variant =
       | Numeric of int
       | Text of string
       | Empty

There are three ‘cases’ of the Variant type: the Numeric case, which carries an integer value; the Text case, which carries a string value; and the Empty case, which doesn’t carry any additional data.

We can create instances of the Variant type using the ‘constructors’ corresponding to the cases:

> let one = Numeric 1;;
val one : Variant = Numeric 1
> let hello = Text "hello";;
val hello : Variant = Text "hello"
> let empty = Empty;;
val empty : Variant = Empty

If a case carries additional data, then we pass that additional data to the constructor.  If it doesn’t, then the case is effectively a singleton instance, so we’re really just doing a variable assignment.

To process the Variant type, we can use pattern matching:

let print v =
    match v with
    | Numeric n -> printfn "Num %d" n
    | Text s    -> printfn "Txt %s" s
    | Empty     -> printfn "Empty"

Now we’ve seen discriminated unions at work, let’s see how they compare to that ubiquitous C# data structure, the class.

In C#, Variant would be an abstract base class, with three subclasses, Numeric, Text and Empty.  Numeric would have an integer field, Text would have a string field, and Empty would have no fields.

This already points up one important difference between discriminated unions and class hierarchies: discriminated unions are closed.  Users of the F# Variant type can’t create a new ‘case,’ whereas users of the C# Variant type can create a new derived class.  So discriminated unions are good for scenarios where you want to control the set of permitted cases; if you want the type to be extensible, you need to go to a class.

Ignoring this detail, here’s a naive stab at implementing the Variant type in C#:

public abstract class Variant
{
}

public class Numeric : Variant
{
   public int Value { get; set; }
}

// similarly for Text and Empty subclasses

However, this implementation has quite different behaviour from the F# discriminated union.  Discriminated unions have value semantics: that is, an instance of Variant is a value just like an instance of Int32 is a value.  Two Variants that are both Numeric 99 have the same value, and so should be considered equal; furthermore, Numeric 100 is a different value from Numeric 99, and must therefore be a different instance.  The first observation means that the Variant types need to implement custom equality; the second means they have to be immutable.  (The immutability issue may seem a bit subtle, but the reasons for wanting immutability go deep; maybe a subject for a future post.)  So our naive implementation needs quite a bit of fixing:

public class Variant : IEquatable<Variant>
{
   public override Equals(object other) { … }
   public override Equals(Variant other) { /* don’t ask */ }
   public override int GetHashCode() { … }
}

public class Numeric : Variant
{
   private readonly int _value;

   public Numeric(int value)
   {
     _value = value;
   }

   public int Value
   {
     get { return _value; }
   }
}

// similarly for Text subclass

This points up a second important difference between discriminated unions and classes: discriminated unions are much easier to write!  The F# Variant type was entirely defined and implemented in four lines.  In the C# Variant class, it takes four lines just to implement a single attribute of a single subclass (one for the field, one for the constructor assignment, one for the property declaration and one for the property getter implementation)!  And good luck writing a bug-free Equals method on your first go (and maintaining it as you add new classes).  Discriminated unions give you value semantics for free; class hierarchies make you work for it.

On the other hand, the fact that C# makes you write all that code out by hand does give you more control over the behaviour of your type.  If you want to ensure that numeric variants are always positive, you can add a check in the Numeric constructor.  You can’t do that with a discriminated union.  A discriminated union is a dumb container of values; a class is a smart container of business logic.

Anyway, now we’ve got the Variant type implemented, it’s time to do some work with it.  But thinking about implementing the ‘print variant’ function above, there are two very different ways we could tackle this.  The idiomatic approach in C# is to make Print a virtual method on the Variant base class and override it in the derived classes:

public abstract class Variant
{
   public abstract void Print();
}

public class Numeric : Variant
{

   public override void Print()
   {
     Console.WriteLine("Num " + Value);
   }
}

// Similarly for Text and Empty subclasses

This works fine as long as you’re the one defining the class hierarchy.  (It’s a bit verbose, because it repeats the ‘public override void Print()’ signature in every derived class.  But it does work.)  Unfortunately, if you have to add a function to a class hierarchy that somebody else has defined, then things get very dreary:

public static void Print(Variant v)
{
   Numeric n = v as Numeric;
   if (n != null)
   {
     Console.WriteLine("Num " + n.Value);
     return;
   }

   // similarly for Text and Empty subclasses
}

With a discriminated union, you don’t get the choice: there’s no way to define a virtual method and override it on individual cases, so you always have to take the separate function approach.  But thanks to pattern matching, implementing a function across the cases of a discriminated union in F# doesn’t incur all the intrusive logic of the C# version, and it’s actually more concise than even the C# virtual method version.

To sum up, discriminated unions provide a more compact and efficient way than full-fat classes of representing simple heterogeneous data.  You can implement a discriminated union in far less code than a class, and the code to work with a discriminated union is also more concise than the class equivalent.  However, discriminated unions are suitable only when the set of possible cases is known in advance – they aren’t openly extensible the way a class hierarchy is – and they don’t provide a way to encapsulate behaviour within the type.  For example, you would never make the Control hierarchy a discriminated union, because users need to be able to define their own range of controls, and the new control types need to carry their own behaviour (e.g. rendering) within them.  On the other hand, for types like the F# Option type (used for ‘either a value of x, or no value’), the Haskell Either type (traditionally used to express ‘either a result of x, or a failure reason of y’), or even much wider unions like LINQ expression types or node types in an Abstract Syntax Tree, discriminated unions are an ideal choice.

Action, Func, void and unit

The .NET Framework defines two ‘standard’ delegate types: Action<> and Func<>.  The Func types are used for delegates that return values, and the Action types for those that don’t – in C# terms, for void methods.

This distinction can often be very annoying.  Consider a helper method such as:

public static T WithSomeResource<T>(Func<T> f) {
  AcquireSomeResource();
  try {
    return f();
  } finally {
    ReleaseSomeResource();
  }
}

This works fine when the thing you want to do returns a value:

int y = Helpers.WithSomeResource(() => x + 1);

But the compiler won’t let you pass anything that doesn’t return a value:

Helpers.WithSomeResource(() => Console.WriteLine(x));  // error

You have to create a separate overload that takes an Action instead of a Func, and has an identical implementation except for omitting the return keyword.  Granted, that’s not much work for a simple helper like the above, but what if it were more complicated?  Or what if you had a dozen of them?  Boring!  Also, maintenance nightmare!

The reason for this distinction is that although void sits in the position where you expect the return type to sit, and looks like a return type, it isn’t.  Visual Basic makes this much clearer by distinguishing between Sub and Function instead of abusing the return type identifier.  So in the WithSomeResource generic method, the type parameter T can’t be void, because void isn’t a type.  And so we end up needing the separate Action types, which do the job of Func<void>.

Contrast this with F#.  F# doesn’t have void: it has unit.  This may seem like it’s just a difference in naming, but it isn’t, because unit in F# is a real type.  A function that ‘doesn’t return a value’ in F# is considered to return type unit.

let f (s : string) = Console.WriteLine(s);; 
val f : string –> unit

So in F#, every function has a return type.  And therefore F# doesn’t need to distinguish between functions and actions.

let withSomeResource f = 
  acquireSomeResource() 
  try 
    f() 
  finally 
    releaseSomeResource();;

val withSomeResource : (unit –> 'a) –> 'a

The F# version of withSomeResource can be called interchangeably with ‘functions’ (that return real values) and ‘actions’ (that return unit) because unit is a valid type, and so the type parameter 'a can be unit just like any other type.

let y = withSomeResource (fun () –> x + 1);;  // okay 
withSomeResource(fun () –> Console.WriteLine(x));;  // also okay

Having unit instead of void makes it easier to write generic functions, because you don’t need to write separate implementations for the ‘value’ and ‘no value’ cases.

And that, my liege, is how we know the earth to be banana shaped.

Wellington .NET user group - Windows 8 for .NET developers

Thanks to everyone who came along this evening to watch me trying to get a wireless connection to work, and especially to those who stuck around for the Windows 8 talk afterwards. Here are the slides from the session, which in a rare departure for me actually contain the content of the talk instead of a series of gnomic Talking Heads references. Enjoy!

Windows 8 presentation slides

And although we didn't really have time to look at samples, you can get source code for the Metro sample apps I used here.

Dynamic interfaces in C#

The always creative Bevan Arps demonstrates a neat prototype which uses the C# dynamic keyword to provide a concise and readable way of describing validations within C# code, and asks, “Does this qualify as evil code, or merely expressive?”

Well, it’s clearly expressive.  And languages like Ruby use this kind of idiom all the time, so it’s clearly not evil.  But there is something about it (and about some related code I demoed at TechEd) which might reasonably make you feel a bit doubtful.  It’s not evil per se, but is it un-C#-ish?  C# is traditionally a statically typed language, which encourages reliance on the compiler to check correctness: are Ruby-ish idioms simply inappropriate?

Idioms evolve with the language; or, rather, what is idiomatic develops from what people do with language features.  Take C# anonymous types.  They were initially designed to simplify writing LINQ projections, with the expectation that the results would be consumed in the same method where the anonymous type arose.  Maybe you could data-bind to them if you felt adventurous.  Then somebody realised that anonymous types made a really handy syntax for a set of key-value pairs – basically a dictionary, but without all the tedious overhead of C# dictionary literals.  An idiom was born: anonymous types are now firmly established as the C# equivalent of Ruby hashes.

So it is with dynamic.  ASP.NET MVC 3 uses a dynamic ViewBag to shield developers from the rather mild horrors of dictionary access syntax.  Libraries like Dapper, which uses dynamic properties to sweeten what would otherwise be a .NET 1.0 DataTable, are entering the vocabulary of the C# community.  People like Bevan are finding cases where dynamic interfaces enable them to write shorter, cleaner and more expressive code.  It may be unsafe, sure, but typically no more unsafe than the literal strings it often replaces.

Right now, using dynamic interfaces in C# does feel a bit weird.  And there’s no doubt that most C# code and APIs will remain statically typed and compiler verified.  But dynamic interfaces are clearly becoming part of the idiom: the question is not whether dynamic interfaces belong in C#, but where they belong and how much we should use them.

But it has angle brackets!

Pro tip: describing a technique as “all XSLT, no code” makes about much sense as describing it as “all SQL, no code.”

TechEd NZ 2011 demos and videos

Thanks to everyone who came along to my sessions on F# and dynamic programming. Here's the demo code from the talks. It includes a few fragments that go beyond what I covered in the talk -- I've tried to comment these to give you a few pointers as to what they're showing, but if you're still baffled, leave a comment and I'll try to write up what's going on!

Demos for F# talk

Demos for dynamic talk

It looks like the videos are now up for those who just can't get enough rude remarks about EF -- F# here, dynamic here.

Recursive parsers in FParsec

Probably world + dog knows this already, but it didn’t jump out at me in the FParsec documentation or in Google, so I thought I’d write it down anyway.

The problem

Many languages contain recursive structures.  A list in Scheme or Lisp can contain sub-lists; a JSON object can contain sub-objects.

In FParsec, a parser for a linguistic structure is represented by a variable of parser type.  Here’s a simple example:

let number = many1 digit |>> Number

(FParsec does include built-in parsers for common number types – I just wanted a simple example.  And the Number constructor, like List in the next fragment, is just a constructor for a hypothetical AST node.)

Now consider a parser for a Scheme list of numbers – that is, a list of numbers enclosed in brackets and separated by spaces.  This is a bit more complicated:

let sepOrEnd = (spaces1 <|> (spaces >>. followedByString ")"))
let listElement = parseExpr .>> sepOrEnd
let series = spaces >>. many listElement |>> List
let list = between (pchar '(') (pchar ')') series

(I am sure there are more elegant ways to do this, but I don’t want to get hung up on that right now I’m trying to avoid line breaks.)

And we’ll say that an expression can be either a number or a list:

let expr = choice [ number; list ]

In reality, of course, a list should be able to contain any kind of expression.  So we need to redefine listElement as follows:

let listElement = expr .>> sepOrEnd

But now disaster strikes.  F# refuses to compile listElement, complaining that expr isn’t defined.  And there’s no way to move things around to avoid this.  expr depends on list, which depends on series, which depends on listElement, which depends on expr.

You might think we could get out of this with a let rec, making the relevant parsers mutually recursive, but let rec only works for recursive functions.  FParsec parsers are values.  Think of it as if you were trying to define four C# member or local variables.  C# is happy to let you define four methods in terms of each other, but not for you initialise to initialise four variables in terms of each other.

The solution

To get around this, FParsec provides you with a way to effectively forward declare a parser.  If I could ‘declare’ the expr parser before the listElement parser, so that listElement knew about it, but defer the implementation until after the list parser, then that would break the mutual dependency.  F# doesn’t have the notion of forward declaration, but FParsec simulates it using a function.

To forward declare a parser, call the createParserForwardedToRef function.  This function returns a pair.  The first element of the pair is a parser you can use without having defined it.  It’s the forward declaration, if you like.  The second element of the pair is a reference cell you can later overwrite with the implementation of the parser.  FParsec takes care of hooking up the ‘forward declaration’ parser to the eventual implementation.

This sounds more confusing than it actually is, so let’s see it in action.

let expr, exprImpl = createParserForwardedToRef()

Now expr is a parser which is hooked up to exprImpl, and exprImpl is a reference which we can overwrite later.  Because expr is a proper honest-to-goodness variable as far as F# is concerned, and is now defined before listElement, the compiler is now happy for us to use it in listElement:

let listElement = expr .>> sepOrEnd

Of course, now we can no longer write let expr = … when we want to implement expr parser, because expr is already declared.  And this is where exprImpl comes in.  Because this is a reference, we can overwrite its contents with the parser we actually need:

do exprImpl := choice [ number ; list ]

Note the use of do and := instead of let and =.  We are not rebinding exprImpl – it’s not mutable so F# wouldn’t allow that – but because it’s a reference cell, we can overwrite its contents.

Because of the way FParsec set up the expr ‘forward declaration’ – in reality, because of the implementation FParsec generated for the expr parser – all calls to expr actually end up going to exprImpl.  As a result, when exprImpl invokes expr (indirectly through listElement), it ends up invoking itself.  And we have a recursive parser, just as we needed.

Final code

let expr, exprImpl = createParserForwardedToRef()
 
let number = many1 digit |>> Number
 
let sepOrEnd = (spaces1 <|> (spaces >>. followedByString ")"))
let listElement = expr .>> sepOrEnd
let series = spaces >>. many listElement |>> List
let list = between (pchar '(') (pchar ')') series
 
do exprImpl := choice [ number; list ]

Partial function application in F#: index

This post just provides links to the various bits of the ‘partial function application’ series.

• Part 1 describes the syntax and meaning of partially applying a function.
• Part 2 shows how partial application results in code that is simpler and more readable than lambda expressions.
• Part 3 looks at another use case for partial application, precomputing partial results.
• Part 4 discusses the underlying concepts.
• Part 5 examines how the partial application idiom affects the design of your own functions.