ICFP Programming Contest

As far as elite programming contests go, I thought the only one around was the ACM-ICP. (The ACM International Collegiate Programming Contest.) However there is a less well known but arguably more hard core contest called the ICFP.

Each year as part of The International Conference on Functional Programming there is a programming contest in which the first prize is an official declaration that:

“The first place team's language is the programming language of choice for discriminating hackers”

Of course we all know the language of choice for discriminating hackers is F#, but if that could be proven by winning this completion then great! So Brian McNamara, Luke Hoban, Dustin Campbell, and Myself formed team Cup<’t>.

You can get the full ICFP 2008 problem description here, but generally it was write an AI for a Mars rover which avoids obstacles and blood thirsty Martians. I’ve never written a ‘real time’ app before and found the whole robotics domain pretty enjoyable. (Maybe you’ll start seeing blog posts using Robotics Developer Studio.)

Anyways, if you missed out on the competition I definitely encourage you to participate next year. We had a total blast.

 

Pictured from left: Brian McNamara, Luke Hoban, Anson Horton, Alex Turner

Mastering F# Lists

Lists represent the backbone of functional programming and in order to be an effective F# programmer you must truly master list processing. Fortunately lists are simple and straight forward, so let’s begin.

Mastering F# Lists

There are several things which distinguish the F# list type from the .NET Arrays and generic List<T> type in the System.Collections.Generic namespace.

	F# List	Arrays	Generic List
Modify Elements	No	Yes	Yes
Add New Elements	No	No	Yes
Element Lookup	O(n) slow	O(1) fast	O(1) fast

After looking at that chart, you might be wondering why even use F# lists at all? Element lookup is slow and you can’t even modify the thing once it has been created, so why bother. The reason why is that F# lists are immutable. Unlike arrays and generic lists, F# lists are guaranteed never to change once they have been created. If you have a type that returns an array or List<T> you don’t know what the outside world will do to it, check out Jomo’s Barrel of Bugs blog post for details.

But seriously, is this safety worth it? Yes. If used correctly in the right situations, F# lists can be more efficient than .NET Arrays or generic Lists. So let’s dig into looking at how F# lists work.

Linked Lists

F# lists are represented as linked lists, which are a foundational Computer Science data structure abstracted by links in a chain. Each individual link has a piece of data associated with it and may be connected to another link. The last link isn’t connected to anything, so it ‘points to null’ or the empty list []. (Ed. Sorry the empty list looks like a square block in my images.)

There are two main operations on a list: Cons (adding a single element) and Concat (joining two lists).

Cons

Cons is where you add an element to the beginning of a list. In F# the type of the cons function’s type is:

‘a –> ‘a list –> ‘a list

The important thing to understand is that cons executes in constant, O(1), time. To join an element to an immutable linked list all you need to do is put that value in a list node and set its ‘next list node’ to be the first element in the existing list. Everything ‘after’ the new node is none the wiser.

> 1 :: [2 .. 4];;

val it : int list = [1; 2; 3; 4]

Concat

Concat joins two lists together. The function type for concat is:

‘a list –> ‘a list' –> ‘a list

In order to join two lists all you need to do is set the ‘next node’ value in the last element of the first list equal to the first node in the second list. This sounds like a great solution, but remember you cannot modify list elements. So to join to lists you actually need to make a copy of the first list just so you can change what the last element points to. For this reason, execution of concat is on order O(n) where n is the number of elements in the first list. Visually you can see this by:

To summarize: Cons is fast and easy and Concat is slowish.

List Module Functions

Now that we understand lists, let’s look at some built-in functions for manipulating them.

List.hd

List.hd returns the first element or head of a list.

List.tl

List.tl returns the ‘tail’ of the first element, of the list of items after the first element.

> let l = [1; 2; 3];;

val l : int list

> List.hd l;;

val it : int = 1

> List.tl l;;

val it : int list = [2; 3]

List.length

List.length returns the length of the list, nothing special to see here.

> List.length [1; 2; 3; 4; 5];;

val it : int = 5

List.rev

List.rev reverses a list. This makes a copy of the entire list so be careful when calling it, as it if you use List.rev in an inner loop your performance is hosed.

> List.rev [1 .. 10];;

val it : int list = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]

List.find

List.find takes a boolean function and returns the first element where that function returns true. However, if List.find doesn’t ‘find’ the element you are searching for it throws an exception. Since generally throwing exceptions is bad for everyone involved, I recommend List.tryfind instead, which returns an Option value. In this example we look through a list of numbers for one which is equal to the square root of 144.

> List.find (fun i -> i * i = 144) [1 .. 10];;

System.Collections.Generic.KeyNotFoundException: The item was not found in the collection

at Microsoft.FSharp.Core.Operators.not_found[T]()

at <StartupCode$FSI_0014>.$FSI_0014._main()

stopped due to error

> List.tryfind (fun i -> i * i = 144) [1 .. 10];;

val it : int option = None

List.filter

List.filter takes a function and produces a new list with only the items on which the function returned true. This filters down the list to just what you want. In the example we filter down a list of numbers to only those which are even.

> List.filter (fun i -> i % 2 = 0) [1 .. 20];;

val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

Aggregate Operators

The List module also supports a trio of aggregate operators: iter, map, and fold. These three functions provide all the power you need to do heavy lifting with any collection type. (In fact you will find a subset of iter, map, and fold in the Set, Seq, Option, and Array modules.)

List.Iter

The iter function is perhaps the simplest aggregate operator. All it does is iterates through each element in a list taking calling a function for each element. Note that the iter function doesn’t produce a value. Iterating through a list is predominately used for evaluating the side effects of the provided function, such as printing to the console.

> List.iter (fun i -> printfn "List contains %d" i) [1 .. 5];;

List contains 1

List contains 2

List contains 3

List contains 4

List contains 5

val it : unit = ()

List.Map

List.map is used to transform a list of items using a given function. The type of List.map is

(‘a –> ‘b) –> ‘a list –> ‘b list

Visually we can see the effects of a map using function f by:

Inverting a list of numbers

Imagine we wanted to invert a list of numbers. All we need to do is map the invert function to each element in our list.

// Invert a list of numbers
let invertNumber x = x * -1

// Inverts numbers 1 through 10
let x = List.map invertNumber [1 .. 10]

// Prints: [-1; -2; -3; -4; -5; -6; ...]
printfn "%A" x

List.Fold

Folds are the most powerful aggregate operator and not surprisingly the most complicated. When you have a list of values and you want to distill it down to a single piece of data you use List.fold. List folds come in two flavors: fold_left and fold_right. The one you use determines the order in which elements are visited. (fold_left going left-to-right and fold_right going right-to-left.)

List.fold iterates through each element of the list and builds up an accumulator value. Once every element has been processed, List.fold returns the final value of the accumulator. The type of List.fold_left is:

(('a -> 'b -> 'a) -> 'a -> 'b list -> 'a)

To name the parameters fold_left takes:

List.fold_left :  ([function] accumulator listElement -> accumulator) initialAccumulatorValue theListToFold

List.Fold_left

Sum a list of numbers

The simplest example of a fold is summing a list of numbers. Our accumulator function will simply add the list element, x, to our accumulator value.

// Sum a list
let accumulate acc x = acc + x

let sumList = List.fold_left accumulate 0 [1 .. 10]

// Notice our accumulator function is identical to the (+) operator,
// so we can rewrite our fold as:
let conciseSum = List.fold_left (+) 0 [1 .. 10]

The accumulator value doesn’t need to be a primitive value though, perhaps you want to reduce a list to different pieces of data. You can have that accumulator be a tuple to store multiple values or even a record to store structured data.

Counting vowels

Before I go into the next example, let me quickly review an elegant syntax for cloning records:

// Cloning Records
type Car = { Make : string; Model : string; Year : int }

let eclipse   = { Make = "Mitsubishi"; Model = "Eclipse"; Year = 2005 }

// You could make a copy like this ...
let nextYears1 = { Make = eclipse.Make; Model = eclipse.Model; Year = 2006 }
// .. but an easier way would be this.
let nextYears2 = { eclipse with Year = 2006 }

Here’s another example of List.fold_left, totaling the number of vowels in a sentence. For our accumulator we will use a record.

// Counting vowels
type VowelCount = { A : int; E : int; I : int; O : int; U : int }

let countVowels acc c =
    match c with
    | 'a' -> { acc with A = acc.A + 1 }
    | 'e' -> { acc with E = acc.E + 1 }
    | 'i' -> { acc with I = acc.I + 1 }
    | 'o' -> { acc with O = acc.O + 1 }
    | 'u' -> { acc with U = acc.U + 1 }
    | _   -> acc
    
let listOfChars = Seq.to_list "The quick brown fox jumps over the lazy dog."

let accInitVal = { A = 0; E = 0; I = 0; O = 0; U = 0 }

// Evaluates to: {A = 1; E = 3; I = 1; O = 4; U = 2;} 

List.fold_left countVowels accInitVal listOfChars

Fold_right

Choosing between List.fold_left and List.fold_right may seem like a cosmetic difference, but folding order can have a substantial impact on performance. Consider the problem of splitting a string. Given a list of characters, return a list of lists of characters representing words separated by spaces.

// List.fold_left (bad)
let listOfChars2 = Seq.to_list "The quick brown fox jumps over the lazy dog"

let breakIntoWords (acc : char list list) c =
    // If the letter isn't a space, add it to our accumulator
    if c <> ' ' then
        // Words are stored in order, so the last word is at the end of the list...
        let revAcc = List.rev acc
        // Now get the first item in the reversed list
        let word = List.hd revAcc
        // And add this character at the end
        let updatedWord = word @ [ c ]
        // Finally put this updated word at the end of our accumulator
        let updatedRevAcc = updatedWord :: (List.tl revAcc)
        List.rev updatedRevAcc
    // If the letter is a space then add a new list of chars
    else 
        acc @ [ [] ]
        
let words = List.fold_left breakIntoWords [ [] ] listOfChars2

(* Prints:
[['T'; 'h'; 'e']; ['q'; 'u'; 'i'; 'c'; 'k']; ['b'; 'r'; 'o'; 'w'; 'n'];
 ['f'; 'o'; 'x']; ['j'; 'u'; 'm'; 'p'; 's']; ['o'; 'v'; 'e'; 'r'];
 ['t'; 'h'; 'e']; ['l'; 'a'; 'z'; 'y']; ['d'; 'o'; 'g']] *)
printfn "%A" words

The solution doesn’t seem terribly bad, we just need to deal with the inconvenience of reversing the lists and adding elements to the ‘back’. But remember that everything you call List.rev it takes O(n) time. And every type you call (@) that takes another O(n). In short, that fold was a steaming pile of slow. However, because of the nature of that problem if we go ‘backwards’ or fold in right-to-left order we can add characters and words to the front of the list, allowing us to use the much faster Cons function.

Solving this problem using List.fold_right allows us to remove all calls to List.rev and Concat. The resulting fold operation is much more performant.

// List.fold_right (good)
let listOfChars3 = Seq.to_list "The quick brown fox jumps over the lazy dog"

let breakIntoWordsGood c (acc : char list list) =
    // If the letter isn't a space, add it to our accumulator
    if c <> ' ' then
        // Words are stored in reverse order, so get the first word
        let word = List.hd acc
        // And add this character at the beginning
        let updatedWord = c :: word
        // Finally put this updated word at the beginning of our accumulator
        updatedWord :: (List.tl acc)
    // If the letter is a space then add a new list of chars
    else 
        [ [] ] @ acc
        
let words2 = List.fold_right breakIntoWordsGood listOfChars3 [ [] ] 

(* Prints:
[['T'; 'h'; 'e']; ['q'; 'u'; 'i'; 'c'; 'k']; ['b'; 'r'; 'o'; 'w'; 'n'];
 ['f'; 'o'; 'x']; ['j'; 'u'; 'm'; 'p'; 's']; ['o'; 'v'; 'e'; 'r'];
 ['t'; 'h'; 'e']; ['l'; 'a'; 'z'; 'y']; ['d'; 'o'; 'g']] *)
printfn "%A" words2

While there is still plenty more to know about lists, now you should be armed with enough knowledge to tackle Project Euler problems with ease.

In closing, I hope you enjoyed this post and if there is any F# topic you would like me to cover in the future blog post please use the Contact link and let me know. Thanks!

Some guidelines for readable F# code

When learning a new programming language it isn’t enough to know the syntax, you must also take the time to learn the idioms and styles for the language. Unfortunately those idioms and styles develop over years and F# still hasn’t had its ‘official v1'.0’ release. So where do we start?

We can begin by looking at F#'s roots - C# and OCaml - for guidance:

• OCaml programming guidelines
• .NET naming guidelines
• C# Coding Style guide
• Design Guidelines for Developing Class Libraries

Once you start looking at those docs however, you'll begin to notice some conflicting advice. The problem isn't just that F# is both functional and object-oriented.  Good design guidelines are hard to pin down because F# can be used to write applications ranging from simple scripts to line-of-buisiness apps to physics simulations.

So I won't set out to write the ultimate set of coding guidelines for F#, but I will at the very least try to start the dialog.

For this post I would like to focus on readability. (Caveat Emptor, I completely reserve the right to flip-flop on any of these style issues; you have been warned.)

 

F# Don'ts

Let's start with the things you shouldn't do. If you want to write obfuscated F# code, here's the way to start.

Don't open Namespaces without a fully-qualified path

The semantics of open are that once you open a namespace, you can then open any nested namespaces without fully-qualifying them. If you do this however, you lose any ability to determine what 'open X' is actually referring too. Worse yet, you can run into namespace collisions. Recommendation: don't do this.

open System
open Collections
open Generic

// System.Collections.Generic.List<T>
let x = new List<string>()

Don't outscope values

In F# it is possible to introduce new values outscoping existing ones but since everything is immutable this doesn't modify the value, it simply creates a new one with the same name. To the novice F# developer, the following code would print both "Hello" and "Goodbye" however it does not.

let greet() =
    
    let message = "Hello"
    
    let printGreeting() = printfn "%s Bob" message
    
    // prints "Hello Bob"
    printGreeting()
    
    let message = "Goodbye"
    
    // prints "Hello Bob"
    printGreeting()

F# Code to Avoid

These aren't necessarily bad things, but you need to be careful when using these concepts.

Avoid mutable function values

Passing around a mutable function value enables some interesting functional programming patterns, but also enables new classes of bugs. You should avoid mutable function values unless they have a very limited scope.

let mutable mutableFunc = fun x y -> x + y

mutableFunc <- (fun x y -> x * y * -1)
mutableFunc <- (fun x y -> List.length [x .. y])
mutableFunc <- (fun x y -> (box x).ToString().Length + y)

mutableFunc 4 5

Avoid abusing type abbreviations

Type abbreviations simplify code and increase readability, but if you do it too much you are just introducing new types that need to be remembered by the person maintaining your code.

type string_string_dictionary = Dictionary<string, string>

Avoid abusing partial function application (currying)

Just like the previous bullet, currying is a great feature when used judiciously. Just be aware that at some point it is possible to go overboard and make your code impossible to debug.

let moveFunc x y = System.IO.File.Move(x, y)

let moveFileX = moveFunc @"D:\Documents\FileX.fs"

moveFileX "E:\NewFileLocation\FileX.fs"

F# Code to Consider

These are guidelines which may not always be applicable, but you should consider using them when the situation arises.

Prefer Sequence Expressions to Seq.unfold

There certainly is a place for Seq.unfold, but Sequence Expressions are much easier to read.

// Fibonacci numbers - 1, 1, 2, 3, 5, 8, 13, ...
let seq_unfold = 
    Seq.unfold 
        (fun (idx, last1, last2) -> 
            if idx >= 20 then 
                None 
            else 
                Some(last1 + last2, (idx + 1, last1 + last2, last1))) 
        (0, 0, 1)

// vs.

let sequence_expression =
    seq {
        let lastStep = ref (0, 1)
        for i in 1 .. 20 do
            let x, y = !lastStep
            yield x + y
            do lastStep := (x + y, x) }

 

F# Dos

These are things you should always do to aid readability of your F# programs.

Use the Pipe-Forward operator wherever possible

If you find yourself stringing together a lot of operations, don't write in the lame-imperative way. Use the pipe-forward operator to simplify the code. (Do this only within reason, since you can't store intermediate results long chains of piped functions are actually very hard to debug.)

let folderSize baseFolder =
    baseFolder
    |> filesUnderFolder
    |> Seq.map getFileInfo
    |> Seq.map getFileSize
    |> Seq.fold (+) 0L 
    |> convertBytesToMB

Add comments to Union Type data tags if necessary

Currently in F# you cannot name data associated with Union Type data tags, be sure to add a comment around the declaration site so that other programs know what the tag is expected to carry AND the order that data is expected to come in.

type MotorizedTransport =
    // Model, Year
    | SUV   of string * int
    // Model, Year, Carrying capacity
    | Truck of string * int * int 

Shameless plug - FsTest

Matthew Podwysocki finished putting together a DSL for unit testing. I imagine this only scratches the surface of what you can do with DSLs in F#.

 

The same approach also works for scripting too, check out this piece of Zen:

#light

open System.IO

// Returns all the files under a given folder
let rec filesUnder rootPath =
    seq {
        for file in Directory.GetFiles(rootPath) do
            yield file
        for dir in Directory.GetDirectories(rootPath) do
            yield! filesUnder dir }
            
            
// Deletes all files
let deleteAll files = Seq.iter File.Delete files

// Notice just how flippin sweet type inference is...
// File.Delete : string -> unit
// Seq.iter    : ('a -> unit) -> #seq<'a> -> unit
// deleteAll   : #seq<string> -> unit

// The pipe-backwards operator allows you to get this to
// execute in the right order without parens around 'filesUnder'
deleteAll <| filesUnder @"C:\Logs"

Function Composition

During a lunchtime conversation with Dustin Cambell, of Did it with .NET fame, the topic of Function Composition came up. I am a huge fan of the pipe-forward operator (|>) but have never found a use for the function composition operator (>>). Dustin pointed me to his latest blog post and after reading it, realized the error of my ways. Function Composition is one of those those foundational skills that you should definitely try to master in F#.

So what is Function Composition? Function Composition is composing new, more powerful functions based on smaller ones. Let’s say your task is to compute the size on disk of all the files under a certain path and you have the following helper routines:

Basic Functions

#light

open System
open System.IO

// Gets all files under a given folder
let rec filesUnderFolder rootFolder = 
    seq {
        for file in Directory.GetFiles(rootFolder) do
            yield file
        for dir in Directory.GetDirectories(rootFolder) do
            yield! filesUnderFolder dir }

// Gets the information about a file
let fileInfo filename = new FileInfo(filename)

// Gets the file size from a FileInfo object
let fileSize (fileinfo : FileInfo) = fileinfo.Length

// Converts a byte count to MB
let bytesToMB (bytes : Int64) = bytes / (1024L * 1024L)

The old-fashioned, imperative programming way of calculating the result would be to call each function in sequence, store the result, and pass it into the next function.

Lame, Imperative Code

// Doing things the lame way
let photosInMB_lame =
    let folder = @"C:\Users\chrsmith\Pictures\"
    let filesInFolder = filesUnderFolder folder
    let fileInfos     = Seq.map fileInfo filesInFolder
    let fileSizes     = Seq.map fileSize fileInfos
    let totalSize     = Seq.fold (+) 0L fileSizes
    let fileSizeInMB  = bytesToMB totalSize
    fileSizeInMB

We can improve upon this by using the pipe-forward operator (|>) which is defined as:

let inline (|>) x f = f x

The pipe-forward operator allows you to rearrange the ordering of a function so that the argument comes before the function. Using this then, you can ‘pipe’ multiple functions together and avoid the need for temporary variables. So here we take the file path and pipe it to the ‘filesUnderFolder’ function, then pipe the sequence of files to ‘Seq.map fileInfo’, then pipe that result to ‘Seq.map fileSize’, and so on.

Better, Using Pipe-Forward Operator

// Using the Pipe-Forward operator (|>)
let photosInMB_pipeforward =
    @"C:\Users\chrsmith\Pictures\"
    |> filesUnderFolder
    |> Seq.map fileInfo
    |> Seq.map fileSize
    |> Seq.fold (+) 0L 
    |> bytesToMB

The solution using the pipe-forward operator is pretty elegant. But it contains a subtle problem in that you need to provide the initial argument to begin the piping process. So in order to reuse this code you need something like:

// A reusable function using Piping
let photosInMB_reusable baseFolder =
    baseFolder
    |> filesUnderFolder
    |> Seq.map fileInfo
    |> Seq.map fileSize
    |> Seq.fold (+) 0L 
    |> bytesToMB

And to be honest, that’s the way I’ve been writing a lot of code lately. Create a function that takes an argument and then pass that argument into a series of piped-functions back to back. But alas, there is a better way!

Introducing the Function Composition operator (>>):

let inline (>>) f g x = g(f x)

Which reads as: given two functions, f and g, and a value, x, compute the result of f of x and pass that result to g. The interesting thing here is that you can curry the (>>) function and only pass in parameters f and g, the result is a function which takes a single parameter and produces the result g ( f ( x ) ).

Here's a quick example of composing a function out of smaller ones:

let negate x = x * -1
let square x = x * x
let print  x = printfn "The number is: %d" x

let square_negate_then_print = square >> negate >> print
asserdo square_negate_then_print 2

Which when executed prints ‘-4’. We have successfully joined several functions together, like we did using (|>) but we didn’t need to declare a parameter and pass that to our function chain. Instead we rely on a partial application of (>>). We can now rewrite our original directory crawler using function composition:

// Using the Function-Composition operator (>>)
let getFolderSize = 
    filesUnderFolder 
    >> Seq.map fileInfo 
    >> Seq.map fileSize 
    >> Seq.fold (+) 0L 
    >> bytesToMB

let photosInMB_funccomp = getFolderSize @"C:\Users\chrsmith\Pictures\"

Think of function composition (>>) just like using pipe-forward (|>) except you don’t need to specify the first parameter up front. Using (>>) will allow for slightly more concise code and provide a new way to think about applying your functions.

Language Oriented Programming in F#

Last Tuesday I gave a talk to the .NET Developers Association entitled Language Oriented Programming in F#. You can find a video of the presentation here*. This essay is the written version of that presentation, which unfortunately doesn’t translate to the web so well. In fact, I’m going to go ahead and apologize now for this crazy-long post.

 

What is Language Oriented Programming

Let me start by saying that Language Oriented Programing (LOP) is a nebulous term, like meta-programming. Rather than trying to pin it down concretely, I’ll define it in broad terms and then provide many examples.

To understand what LOP is first you must understand the concept of a Domain Specific Language or DSL. A DSL is a programming language designed to solve problems within a narrowly-defined problem domain. (Opposed to a General Purpose programming language, like C# or F#, which can solve problems in any domain.) An example of a DSL would be Excel. To write a formula that adds the contents of two cells you write “= A1 + B1”, no need for defining data types, functions, conversion routines, etc. The Excel language has the concept of a spreadsheet cell baked into the language, so you don’t need to describe what ‘A1’ means in terms of anything else. In C# on the other hand, you can’t write ‘A1’ you need to write something like “MasterSheet.GetCell(new CellObject(Row = “A”, Column = 1));”.

The main advantage of a DSL is that the code is always much simpler than its general purpose programming language counterpart. With a DSL you don’t need to write the ‘scaffolding’ you normally would in order to express your ideas, since all the key concepts of the problem domain are baked into the language.

DSLs have two major drawbacks however. First, DSLs force you to learn a new language. Second, somebody needs to define that language and build the compiler for it.  For simple problem domains these drawbacks aren’t much of a problem. But if you wanted your DSL do describe the business rules for your entire company however, then you can see how DSLs fail to scale. If you are interested in building DSLs however Toolkits do exist.

So what is LOP then? To provide a great example, let me introduce a project called FsUnit over on Google code. It is a simple library for writing Unit Tests in F#, but rather than the standard ‘Assert.IsTrue(x)’ you can write:

// Equality
1 |> should (equal 1)

// Checking existence in a collection
[| "item1" |] |> should (contain "item1")
[| "item1" |] |> should (notContain "item2")

// Size of a collection
personList |> should (have 4 "people")Some text matches a regular expression: 

// RegEx patterns
"test infected" |> should (matchThePattern "inf")

// Other primitives
true |> should (be True)
false |> should (notBe True)
"" |> should (be Empty)
"a string" |> should (notBe Empty)
null |> should (be Null)
anObj |> should (notBe Null)

 

FsUnit allows you to write F# code, but using words and concepts in a different language. (In this case, English.) Armed with this example I will define what LOP is: Language Oriented Programming is a style of programming that tries to produce code that looks like it came from a Domain Specific Language but is still valid in a general purpose programming language.

The rest of this essay will provide examples of LOP in F# and how using LOP results in simpler code that better expresses the problem at hand. I’ll my examples along three major themes:

• Abstract Representation.  Features in F# that allow you to represent domain-specific concepts in your F# code without needing to introduce a new layer of abstraction.
• Concrete Representation. Features in F# that allow you to describe your problem in another language and load that into F#.
• Computational Representation. Finally I’ll go into features in F# that enable you to write code to process concepts in some other language without resorting to a third, more specialized language.

 

Part I – Abstract Representation

One problem facing programmers using modern Object Oriented languages is how to represent concepts in their language. C# only has facilities to express concepts in terms of objects and their behaviors, which makes it difficult to accurately express abstract ideas. Having a class for ‘Cat’ with methods Meow() and Purr() makes sense. But how would you write the concept of ‘Happiness’ in C#? Would there be methods ‘CheerSomethingUp(object thing)’?

By Abstract Representation I’m talking about the ability to represent concepts in your F# code as naturally as possible.

Type Abbreviations

The first feature I'll go into is Type Abbreviations. In F# you have the ability to create an alias for another type, which at compile time will be replaced with the underlying core type. Meaning that type abbreviations only exist at design-time. Using Type Abbreviations you can write code in terms of problem-domain concepts without needing to introduce custom types. For example I'll create a type alias for 'int' called CustomerID. Now if I write a function that takes type CustomerID I know exactly what it expects, rather than a function taking type 'int’ and me needing to guess at what that integer represents.

type CustomerID = int

let alice = 98123
let bob   = 78435 : CustomerID

// With the type annotation the value 'customer' appears as to
// have type 'CustomerID' but at compile time that is replaced
// with 'int'. You can pass both alice and bob to function
// getCustomerOrders.
let getCustomerOrders (customer : CustomerID) =
    printfn "%d has ordered 5 items."customer

Type abbreviations are especially helpful when you are dealing with more complex generic types. Consider Dictionary<string, string>. It has some use, but from just the type signature you have no idea what the key, value pairs correspond to. But with type abbreviations you can call it something more meaningful.

open System.Collections.Generic
type TeamCityLookup = Dictionary<string, string>

// A TeamCityLoop is a better description for the type than Dictionary<string, string>
let teamLookup = new TeamCityLookup()
teamLookup.Add("Mariners", "Seattle")
teamLookup.Add("Reds",     "Cincinati")
teamLookup.Add("Dodgers",  "Los Angeles")

teamLookup.["Mariners"]

 

Discriminated Unions

Consider the following C# code used to express the concept of a card suit.

enum CardSuit
{
    Club,
    Spade,
    Diamond,
    Heart
}

While the code looks simple and clear, it actually introduces many problems because enumerations alone aren't sufficient for expressing the idea of a mutually-exclusive set of values. It is easy to write C# code that violates the principle that a card can only have one possible suit.

CardSuit invalid1 = CardSuit.Club | CardSuit.Heart;
CardSuit invalid2 = (CardSuit) (-1);

In order to write the concept of a card suit in C# you need to write some slightly more complex code. You can see how in chapter 21 of Effective Java. In F# though, you can express this concept without any fuss.

type Suit = 
    | Diamonds 
    | Hearts
    | Spades 
    | Clubs

// An instance of 'Suit' can only have one of four possible values
let printSuitName suit =
    match suit with
    | Diamonds -> printfn "Suit is a Diamond"
    | Hearts   -> printfn "Suit is a Heart"
    | Spades   -> printfn "Suit is a Spade"
    | Clubs    -> printfn "Suit is a Club"

Moreover, in F# Discriminated Unions can also attach data making them much more powerful than enumerations without sacrificing any of their ease of definition.

// Discriminated Unions can hold data too!
type Card =
    | ValueCard of int * Suit  // Value 2 - 10 and Suit
    | Jack      of Suit
    | Queen     of Suit
    | King      of Suit
    | Ace       of Suit
    | Joker
    
// Simple syntax for defining instances of Disc Unions
let myPokerHand = 
    [ 
        ValueCard(2, Hearts) 
        ValueCard(5, Spades) 
        Joker                
        ValueCard(4, Clubs)  
        Ace(Clubs)
     ]

 

Option Type

Sorry to rag on C# some more, but here’s another instance where .NET adds confusion where there shouldn’t be. Consider the following code where I get an instance of your pet and print its name if you have one.

Pet yourPet = you.GetPet();

if (yourPet != null)
    Console.WriteLine("You have pet named " + yourPet.Name);

The code looks simple enough. But where in the real world does null exist? Is that in the problem domain? If I asked you if you had a pet wombat would you say ‘null’? No, null is an artifact of the programming language used to represent the absence of something or an uninitialized value. But in LOP we are trying to represent ideas without any overhead. F# has the option type that will represent the concept of nothing in a more natural way.

type Pet =
    | GoldFish
    | Dog
    | Cat
    
// Takes a 'Person' type and returns an option, of their pet type
let getPetType person =
    match person with
    | Me           -> Some(Dog)
    | SomebodyElse -> Some(GoldFish)
    | You          -> None

If you have a pet Some(…) is returned, meaning there is something. If you don’t have a pet you return None. Another big advantage to the option type is that it communicates intent. If you call the ‘GetPet’ method in C#, it is unclear what the result will be if you don’t have a pet. Will the method throw an exception or simply return null? In F# using the option type means that it will return None should you not have a pet.

 

Pattern Matching

Pattern matching is another way we can express what we mean clearly in code. In C# you can use a switch statement, but that only works on constant values. In F# however, Pattern Matching can do much more than compare a value against a constant. It can, for example, compare against the structure of the data. Here we match against the length of a list:

// Structure of data
let shortList = ['a'; 'b'; 'c']

let printListLength list =
    match list with
    | []      -> printfn "List is empty"
    | [_]     -> printfn "List has 1 element"
    | [_;_]   -> printfn "List has 2 elements"
    | [_;_;_] -> printfn "List has 3 elements"
    | _       -> printfn "List too long"

In addition, Pattern Matching can also capture variables as part of the match.

// Match contants and capture variables
let sayHello (first, last) =
    match (first, last) with
    // Match constants
    | "Bill", "Gates"
    | "Steve", "Balmer"
        -> printfn "Steve and Bill, wazzzup!"
    
    // Match first against constant, capture second
    | "Chris", last
        -> printfn "Hello Chris. Your last name is %s" last
    
    // Capture both values
    | first, last
        -> printfn "Hello %s %s" first last

 

Demo

Now that we have the building blocks to represent ideas in F#, we have all the power we need to represent a real world problem in the language of mathematics.

// This Discriminated Union is sufficient to express any four-function
// mathematical expression.
type Expr =
    | Num      of int
    | Add      of Expr * Expr
    | Subtract of Expr * Expr
    | Multiply of Expr * Expr
    | Divide   of Expr * Expr
    
// This simple pattern match is all we need to evaluate those
// expressions. 
let rec evaluate expr =
    match expr with
    | Num(x)             -> x
    | Add(lhs, rhs)      -> (evaluate lhs) + (evaluate rhs)
    | Subtract(lhs, rhs) -> (evaluate lhs) - (evaluate rhs)
    | Multiply(lhs, rhs) -> (evaluate lhs) * (evaluate rhs)
    | Divide(lhs, rhs)   -> (evaluate lhs) / (evaluate rhs)

// 10 * 10 - 25 / 5
let sampleExpr = 
    Subtract(
        Multiply(
            Num(10), 
            Num(10)),
        Divide(
            Num(25), 
            Num(5)))
        
let result = evaluate sampleExpr

In this simple example we were able to represent and evaluate a four-function mathematical expression using only a discriminated union and a pattern match. You would be hard pressed to write the equivalent C# in as few lines of code because you would need to add additional scaffolding to represent these concepts.

 

Part II – Concrete Representation

Concrete Representation means expressing your problem conceretely in another language and loading that into your F# program. By allowing you to work in both your Domain Specific Language and F#, you can express your problem in specific terms and then do any processing required in F#.

 

fslex and fsyacc

The simplest way to deal with a concrete representation of another language is to build a parser and ‘load it’ just like a compiler. Lex and Yacc have been standard tools for generating parsers for thirty years. FsLex and FsYacc are implementations of Lex and Yacc that generate F# parsers. I won’t go into too much deal here, but if you are interested in learning more refer to my previous blog post.

Lex and Yacc are DSLs for describing compiler parsers and lexers, or tools which break down ‘source’ into a series of tokens and then convert that token stream into an Abstract Syntax Tree. For example, here is the Lex code for converting a string like “10 * 8 + 5.0” into tokens [INT32(10); ASTER; INT32(8); PLUS; FLOAT(5.0)]

rule tokenize = parse
| whitespace    { tokenize lexbuf }
| newline       { tokenize lexbuf }
// Operators
| "+"            { PLUS }
| "-"            { MINUS }
| "*"            { ASTER }
| "/"            { SLASH }
// Numberic constants
| ['-']?digit+  { INT32 (Int32.Parse(lexeme lexbuf)) }
| ['-']?digit+('.'digit+)?(['e''E']digit+)?   { FLOAT (Double.Parse(lexeme lexbuf)) }
| eof   { EOF }

The corresponding Yacc parser file would look something like this, which would match tokens against grammar productions and create AST nodes.

Prog:
    | Expr EOF                  { $1 }

Expr: 
    | Expr PLUS Term            { Plus($1, $3) }
    | Expr MINUS Term           { Minus($1, $3) }
    | Term                      { Term($1) }

Term:
    | Term ASTER Factor         { Times($1, $3) }
    | Term SLASH Factor         { Divide($1, $3) }
    | Factor                    { Factor($1) }

Factor:
    | FLOAT                     { Float($1) }
    | INT32                     { Integer($1) }

If none of this Lex and Yacc jazz made sense to you don’t worry. The point is that if you wanted to, there are tools available that will allow you to write F# programs that can parse any other language you want. So if you wanted to write a parser for all mathematical equations (“1^5 + cos(PI)”) you could. If you wanted to parse structured log files, you could. If you wanted to write a parser for F# code so  you could manipulate it in an F# program, you could. With fslex and fsyacc you can write a parser for any domain specific language you want, and load its abstract representation into your F# program.

 

Active Patterns

The next feature I’ll talk about which allows you to convert a concrete representation of a language into F# is Active Patterns. (WhichI’ve blogged about this before.) The easiest way to think about Active Patterns is that they are a way to convert data from one representation to another, typically via a pattern matching.

Active Patterns come in three main flavors: single-case, multi-case, and partial.

 Single-case Active Patterns

Single-case Active Patterns take an input of one type of data and convert it into something else. In the following example we convert strings to integers. Notice the result of the Active Pattern is at the end of the 'match clause’.

// SingleCase Active Patterns

// Covnert a string to an int
let (|IntValue|) input = Int32.Parse(input)

// Given a string print its integer representation.
let printValue (str : string) =
    match str with
    | IntValue 0 -> printfn "str is zero"
    | IntValue 1 -> printfn "str is one"
    | IntValue 2 -> printfn "str is two"
    
    // Variable capture of AP output
    | IntValue x -> printfn "str is %d" x

Multi-case active Patterns

Multi-case Active Patterns convert the input into one of several types of output, dividing the input space into several regions. For example, we can convert an integer into one of three categories: Odd, Even, or Zero.

// Multi-Case Active Patterns
let (|Even|Odd|Zero|) x =
    if x = 0       then Zero
    elif x % 2 = 0 then Even
    else                Odd

// Takes an int and prints its status
let printStatus x =
    match x with
    | Zero -> printfn "%d is zero" x
    | Even -> printfn "%d is even" x
    | Odd  -> printfn "%d is odd " x

Partial Active Patterns

Partial Active Patterns are just like Single-case Active Patterns, but they don’t always succeede. In our previous example we converted strings to integers, but a string cannot always be converted into an integer. For example “foo”. Partial Active Patterns use Option types to represent whether or not the data was convertered. Here we will convert strings into either Integers or Floating point numbers.

// Partial Active Pattern
let (|ToInt|_|) str = 
    let (parsed, result) = Int32.TryParse(str)
    if parsed then Some(result)
    else           None

let (|ToFloat|_|) str = 
    let (parsed, result) = Single.TryParse(str)
    if parsed then Some(result)
    else           None

// Takes a string and prints whether it is an int or float
let parseValue str =
    match str with
    | ToInt   x -> printfn "str is an int with value %d" x
    | ToFloat x -> printfn "str is a float with value %f" x
    | _         -> printfn "str is neither an int nor a float"

Demo

Here is an example of how you can leverage Active Patterns to convert a concrete representation of a language into F#. The example is from a demo from a research paper by Don Syme, Margetson and Gregory Neverov which introduced the concept of Active Patterns. Since code is really complicated, but I’ll just point out the black magic. Given this XML doc we can extract all meaningful information from it, that is attributes and nested elements, in just one line of code.

// Concrete language
let xmlDoc = 
    let temp = new System.Xml.XmlDocument()  
    let superHerosXmlDoc = 
        "<?xml version=\"1.0\" encoding=\"utf-8\"?>
        <Scene>
            <Sphere r='3' x='4' y='3' z='0' />
            <Intersect>
                <Sphere r='2' x='1' y='0' z='0'/>
                <Intersect>
                    <Sphere r='2' x='4' y='0' z='0'/>
                    <Cube d='1' x='6' y='7' z='8' />
                    <Sphere r='2' x='-3' y='0' z='0'/>
                </Intersect>
                <Cube d='2' x='-2' y='1' z='0'/>
            </Intersect>
        </Scene>
        "
    temp.LoadXml(superHerosXmlDoc)
    temp

// Abstract representation
type GeometricScene =
| Cube      of float * float * float * float
| Sphere    of float * float * float * float
| Intersect of GeometricScene list

// Mach an XML element
let (|Elem|_|) name (inp: #XmlNode) =
    if inp.Name = name then Some(inp)
    else                    None

// Get the attributes of an element
let (|Attributes|) (inp: #XmlNode) = inp.Attributes

// Match a specific attribute
let (|Attr|) attrName (inp: XmlAttributeCollection) =
    match inp.GetNamedItem(attrName) with
    | null -> failwith (attrName + " not found")
    | attr -> attr.Value

// Convert a string to a float
let (|Float|) s = Float.of_string s

// Parses a vector out of an attribute collection
let (|Vector|) inp =
    match inp with
    | (Attr "x" (Float x) & 
       Attr "y" (Float y) & 
       Attr "z" (Float z)) 
        -> (x,y,z)

// Parses a GeometricScene from an XML node
let rec (|ShapeElem|_|) inp =
    match inp with
    // By using nested Active Patterns we can parse all attributes on one line!
    // (Attributes (Attr "r" (Float r))) gets the Attributes of the node, then gets
    // the attribute "r", then finally converts its string value into a float.
    | Elem "Sphere" (Attributes (Attr "r" (Float r) & Vector (x,y,z)))
        -> Some (Sphere (r,x,y,z))
    
    | Elem "Intersect" (ShapeElems(objs))
        -> Some (Intersect objs)
    
    // This is what the cde would look like without nested Active Patterns
    | Elem "Cube" xmlElement
        -> match xmlElement with
           | Attributes xmlElementsAttributes 
               -> match xmlElementsAttributes with
                  | Attr "d" dAttrib & Vector (x, y, z)
                      -> match dAttrib with
                         | Float d -> Some(Cube(d, x, y, z))

    // Did not recognize XmlNode as Shape element
    | _ -> None 

While the use of Active Patterns aren’t the easiest thing to read, they certainly allow you to easily convert data.

 

Part III – Computation Representation

This is the last part of Language Oriented Programming and definitely the most complicated. The theme of this essay has been that two languages are better than one; that using a domain-specific description the your problem makes the coding easier. The only thing better than two languages to represent your problem is not having to use three.

Consider the common Forms-Over-Data application. You have a database, CustomerInfo, and you have your application written in C#. With any luck you’re using LOP in your programming and so you can represent your customer entities naturally, but you run into a problem as soon as you try to interface with your database. Namely, having your app talk to the database requires you using another language – SQL.

With Visual Studio 2008 this problem was solved for a few specific scenarios with Linq, but in F# you can solve this problem even more generally.

This final aspect of LOP I’ll talk about is where you write F# code and manipulate the computation which that code represents. In other words, you write some F# code that does something interesting and then manipulate the computation representation of that code to either execute that code in a unique way or convert that code into a different language.

The F# language features Quotations and Workflows will undoubtedly be the subject of numerous articles, blog posts, and maybe even books in the future. So if I do a terrible job explaining what these features do, don’t fret.

Quotations

Writing .NET code is great and all, but the implicit restriction is that your code is executing on computer running the .NET framework. That doesn’t sound like a big requirement, but think for a moment on how limiting that is. If you wanted to write code that executed on your GPU you would have to resort to some other language. Or let’s say you were multiplying two sparce matricies and wanted to optimize out all the zero-multiplications, leading to a more efficent code. You can’t. Because all the code you write in .NET must execute on the .NET platform… or at least it had to before F# came along.

In F# the Quotations feature allows you to get access to the compiler’s representation of a block of code, enabling you to process that code as you wish. For example, you could write a Quotation-to-GPU converter and write programs in F# which could execute on your graphics card. Or, given a function that operates on a sequence of data, convert those operation into SQL code and automatically query the server. (A la DLinq.)

 

I won’t go into details about how the code all works, but I’ll point out the key concepts. First, the funky “<@@ … @@>” code starts a quotation. Anything inbetween the <@@ and @@> is what is ‘quoted’. So the result of <@@ x @@> is the compiler’s representation of x. Second, once you have some quoted data you will can use Active Patterns to convert the compiler’s representation into something more useful. In the simplest example, we will take the quotation of a constant value and use an Active Pattern to convert the compiler’s representation of that into the value itself.

#light

open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Typed
open Microsoft.FSharp.Quotations.Raw

// The compiler represents the code “1” as an Int32 literal.
let quot1 = <@@ 1 @@>

let printQuotation x =
    match x with
    | Int32 v  -> printfn "The quoted code is an int with value %d" v
    | String v -> printfn "The quoted code is a string with value %s" v
    | _        -> printfn "I don't know what x is..."

You can then move onto bigger, more complicated expressions by matching more types of expressions using Active Patterns. Here we break down an entire function.  (The [<ReflectedDefinition>] attribute is required for the function to be used inside of a quotation.)

// Functions
[<ReflectedDefinition>]
let checkTemp temp =
    if   temp < 60 then printfn "Too cold"
    elif temp > 80 then printfn "Too hot"
    else                printfn "Just right"

let rec printQuotation2 expr =
    match expr with
    | ResolvedTopDefnUse(_,body) 
        -> printfn "The expr is a Top Definition Use..."
           printQuotation2 body

    | Lambda(_, body) 
        -> printfn "The expr is a Lambda..."
           printQuotation2 body
           
    | Cond(_, body, nextCond)
        -> printfn "The expr is a Conditional..."
           printQuotation2 nextCond
           
    | App(info, body) 
        -> printfn "The expr is a function application..."
   
    | _ -> printfn "I don't know what the expr is"

printQuotation2 <@@ checkTemp @@>

Here is an example from Expert F# (Apress, 2007) which uses Quotations to compute the error range for floating point calculations. Given an inexact number such as p = 3.141 +/- 0.001, repeated operations on p will result in a compounded error. Such as p + p = 6.282 +/- 0.002. Given the quotation of a function, the code will walk the compiler’s interpretation of the code and calculate an error estimate.

// Example from Expert F# by Don Syme, Adam Granicz, and Antonio Cisternino
// Pg. 251

open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Typed
open Microsoft.FSharp.Quotations.Raw

type Error = Err of float

// Estimate the error for a given expression, t.
// env is a map of identifiers to their values. E.g., "pi" -> 3.14159
let rec errorEstimateAux t (env : Map<_,_>) =

    match t with
    // If the quoted expression matches the function application of
    // +, -, *, or / calculate the left and right hand sides and
    // compute the resulting error.
    | GenericTopDefnApp <@@ (+) @@> (tyargs,[xt;yt]) ->
        let x, Err(xerr) = errorEstimateAux xt env
        let y, Err(yerr) = errorEstimateAux yt env
        (x + y, Err(xerr + yerr))

    | GenericTopDefnApp <@@ (-) @@> (tyargs,[xt;yt]) ->
        let x, Err(xerr) = errorEstimateAux xt env
        let y, Err(yerr) = errorEstimateAux yt env
        (x - y, Err(xerr + yerr))

    | GenericTopDefnApp <@@ ( * ) @@> (tyargs,[xt;yt]) ->
        let x, Err(xerr) = errorEstimateAux xt env
        let y, Err(yerr) = errorEstimateAux yt env
        (x * y, Err(xerr * abs(x) + yerr * abs(y) + xerr * yerr))

    | GenericTopDefnApp <@@ ( / ) @@> (tyargs,[xt;yt]) ->
        let x, Err(xerr) = errorEstimateAux xt env
        let y, Err(yerr) = errorEstimateAux yt env
        (x / y, Err(xerr * abs(x) + abs(1.0 / y) / yerr + xerr / yerr))

    | GenericTopDefnApp <@@ abs @@> (tyargs,[xt]) ->
        let x,Err(xerr) = errorEstimateAux xt env
        (abs(x), Err(xerr))

    // If the quoted expression introduced a new value. E.g.,
    // let e = 2.71828
    | Let((var,vet), bodyt) ->
        let varv, verr = errorEstimateAux vet env
        errorEstimateAux bodyt (env.Add(var.Name, (varv, verr)))

    | App(ResolvedTopDefnUse(info,Lambda(v,body)),arg) ->
        errorEstimateAux  (MkLet((v,arg),body)) env

    | Var(x) -> env.[x]
    | Double(n) -> (n,Err(0.0))

    | _ -> failwithf "unrecognized term: %A" t

let rec errorEstimateRaw (t : Expr) =
    match t with
    | Lambda(x,t) ->
        (fun xv -> errorEstimateAux t (Map.of_seq [(x.Name,xv)]))
    | ResolvedTopDefnUse(info,body) ->
        errorEstimateRaw body
    | _ -> failwithf "unrecognized term: %A - expected a lambda" t

let rec errorEstimate (t : Expr<float -> float>) = errorEstimateRaw t.Raw

// ----------------------------

[<ReflectedDefinition>]
let poly x = x+2.0*x+3.0/(x*x)

errorEstimate <@ poly @> (3.0, Err(0.1))
// Evaluates to: (9.333333333, Err 0.5821493625)

errorEstimate <@ poly @> (30271.3, Err(0.0001))
// Evaluates to: (90813.9, Err 3.02723)

 

Work flows

Workflows are the most exciting language feature in F#, and represent perhaps the most powerful way to apply LOP in your code. But rather than telling you what they are I’ll build up to it.

Consider this code, which is called a Sequence Expression. It produces a seq of the first 10 integers. The second example is a more complex sequence expression, which uses recursion to walk every file under a given directory. Note the use of recursion requires the ‘yield!’ keyword.

// Sequence Expressions

// Numbers one through ten
let numbers = seq { for i in 1 .. 10 do
                        yield i }

// All files under a given directory (notice the use of recursion)
open System.IO

let rec allFiles dir = 
    seq {   for file in Directory.GetFiles(dir) do
                yield file
            for subdir in Directory.GetDirectories dir do
                yield! (allFiles subdir) }
            
allFiles @"C:\Windows\System32\"

Just to show that you can do powerful things with Sequence Expressions, here is some code to compute all prime numbers under 1,000. (The Sieve of Eratosthenes in F#.)

// Complex Sequence Expression
let primesUnder1K = 
    seq { 
        // First prime 
        yield 2 

        let knownComposites = ref (Set.empty)
        
        // Loop through all odd numbers; evens can't be prime 
        for i in 3 .. 2 .. int 1000 do 
            
            // Check if its in our list, if not, its prime 
            let found = (!knownComposites).Contains(i) 
            if not found then 
                yield i 

            // Add all multiples of i to our sieve, starting 
            // at i and irecementing by i. 
            do for j in i .. i .. int 1000 do 
                knownComposites := (!knownComposites).Add(j)
    } 

Seq.take 20 primesUnder1K

So to review, Sequence Expression produce seq objects and are use a seemingly limited subset of the F# language. Simple enough.

Sequence Expressions however are just a specialization of a concept known as Computation Expression or Workflow. The Computation Expression was everything between the curly braces { and }. The ‘seq’ in front was the workflow builder which I’ll come back to in a moment.

So why are Computation Expressions important? Because in F# you can you define how the Computation Expression gets executed by using a builder object. In the previous examples the ‘seq’ builder takes the Computation Expression and produces a sequence of values. But you can implement far more interesting builders. You could for example write a builder that logged every action that was taken, in order to better diagnose a failure in the code. Or even transfer the computation to a different machine and execute the code in the cloud. Computation Expressions / Workflows are a powerful new concept that open up a lot of possibilities for powerful language oriented concepts.

The most practical application of workflows is in asynchronous programming. Normally if you want concurrent code you need to write it with a bunch of callbacks, manage thread states, deal with synclocks, and other unpleasantries. But using F# Asynchronous Workflows, all you need to do is write your code in a Computation Express and pass that computational representation of your code to the Async Workflow object. It will then execute that code doing all the async goo for you. That’s right, in F# you can write async code without even trying.

Here’s an example of an async workflow in F# from Expert F#. (Which for the record is a much better resource for teaching F# than my blog :)

// Example from Expert F# by Don Syme, Adam Granicz, and Antonio Cisternino
// Pg. 366

open System.Net
open System.IO
open Microsoft.FSharp.Control.CommonExtensions

let museums = ["MOMA",           "http://moma.org/";
               "British Museum", "http://www.thebritishmuseum.ac.uk/";
               "Prado",          "http://museoprado.mcu.es";
               "SAM",            "http://www.seattleartmuseum.org/"]

// Fetch the museum website and print info to the console asynchronously
let fetchAsync (name, url:string) =
    async { do printfn "Creating request for %s..." name
            let req  = WebRequest.Create(url)

            let! resp  = req.GetResponseAsync()

            do printfn "Getting response stream for %s..." name
            let stream = resp.GetResponseStream()

            do printfn "Reading response for %s..." name
            let reader = new StreamReader(stream)
            let! html = reader.ReadToEndAsync()

            do printfn "Read %d characters for %s..." html.Length name }

for (name, url) in museums do
    Async.Spawn (fetchAsync(name,url))

That’s it. Seriously. The code will loop through all the museums specified, and asynchronously download the HTML of their homepages. All the work you needed to was write it inside of a Computation Expression and pass it to an ‘async’ builder. Async.Spawn will take the result and execute it asynchronously.

 

Conclusion

I’ve shown that language features in F# enable Language Oriented Programming and provide all the power you need write succinct code that maps directly to your problem domain. No unnecessary code required. I fully expect that Language Oriented Programming becomes the driving force for F# adoption as developers discover the true expressiveness of the language and leverage these facilities.

 

*Actually, in a poor attempt at humor you’ve been Rick Rolled.

F# in 20 Minutes – Part II

Now that we have covered the basics, in minutes 8 - 14 we will cover the foundational concepts and types in F#. By the end of Part II you should be able to read F# code reasonably well.

Immutability

You may have noticed that I’ve been using the term ‘value’ to refer to identifiers rather than ‘variable’. The reason for this is that types in F# are immutable by default, meaning that once they are created they cannot be changed. This may seem like a severe limitation, but immutability actually prevents some classes of bugs. In addition, immutable data is inherently thread safe meaning you don’t need to worry about sync locks in order to make your code parallelizeable. I’ll go into asynchronous programming in Part III.

If you do need to mutate some data however, F# has the mutable keyword. This creates a variable who’s value can be changed by using the left arrow operator (<-).

> let mutable x = "the original value.";;
val mutable x : string
> printfn "x's value is '%s'" x;;
x's value is 'the original value.'
val it : unit = ()

> x <- "the new one.";;
val it : unit = ()
> printfn "x's value is now '%s'" x;;
x's value is now 'the new one.'
val it : unit = ()

Reference values (Microsoft.FSharp.Core.Ref<_>)

Reference values are another way of being able to mutate data. But rather than having a mutable variable on the stack, a reference cell is a pointer to variable which you modify on the heap. In F# there are some restrictions on where you can use mutable values. (Such as not being able to use them in inner lambdas.) But ref objects can be safely passed around, since they are immutable record values. (Which have a mutable field which can be modified.)

To use reference cells you use (:=) to assign a new value and (!) to dereference.

> let refCell = ref 42;;
val refCell : int ref

> refCell := -1;;
val it : unit = ()

> !refCell;;
val it : int = –1

Modules

In Part I we just declared values and functions arbitrarily. You might have wondered ‘where did they go’, since in C# everything must belong to a class. Though F# can declare the standard .NET classes you are familiar with, it also has the notion of a module; which is a collection of values, functions, and types. (Contrast this with a namespace, which can only contain types.)

This is how we were able to access ‘List.map’. In the F# library (FSharp.Core.dll) there is a module named ‘List’ and on that is a function named ‘map’.

Modules serve as a way of encapsulating code when you are rapid prototyping without needing to spend the time to design a strict object-oriented type hierarchy.  To declare your own module, you can use the module keyword. In the example we will associate a mutable variable with the module, which will serve as a global variable.

module ProgramSettings =
    let version = "1.0.0.0"
    let debugMode = ref false
    
module MyProgram =
    
    do printfn "Version %s" ProgramSettings.version
    
    // You can also open modules like you can a namespace, which
    // brings all their functions and values into scope.
    open ProgramSettings
    debugMode := true

 

Tuples

A tuple (pronounced 'two-pull') is an ordered collection of values treated like an atomic unit. Traditionally if you wanted to pass around a group of semi-related values you would need to create a struct or class, or perhaps rely on ‘out’ parameters. A tuple allows you to keep things organized by grouping related values together without introducing a new type.

To define a tuple, simply enclose the group of values in parentheses separate the individual components by commas.

> let tuple = (1, false, "text");;
val tuple : int * bool * string

> let getNumberInfo (x : int) = (x, x.ToString(), x * x);;
val getNumberInfo : int -> int * string * int

> getNumberInfo 42;;
val it : int * string * int = (42, "42", 1764)

 

Functions can even take tuples as arguments.

> let printBlogInfo (owner, title, url) = printfn "%s's blog [%s] is online at '%s'" owner title url;; 
val printBlogInfo : string * string * string -> unit 

> let myBlog = ("Chris", "Completely Unique View", "http://blogs.msdn.com/chrsmith");;
val myBlog : string * string * string

> printBlogInfo myBlog;;
Chris's blog [Completely Unique View] is online at 'http://blogs.msdn.com/chrsmith'
val it : unit = ()
 

Function Currying

A novel feature F# provides is the ability to provide a subset of a function’s parameters, and bind a new value to the partial application. This is known as function currying. For example, consider a function which takes three integers and returns their sum. We can curry that function, by fixing the first parameter to be 10, resulting in a function that only takes two integers and returns their sum plus 10.

> let addThree x y z = x + y + z;;
val addThree : int -> int -> int -> int

> let addTwo x y = addThree 10 x y;;
val addTwo : int -> int -> int

> addTwo 1 1;;
val it : int = 12

 

Discriminated Unions

Consider the following enumeration:

enum CardSuit { Spade = 1, Club = 2, Heart = 3, Diamond = 4};

Logically there can only be one possible suit for a card, but since an enum is just an integer behind the scenes you don’t actually know if the value is valid or not. For example, in C# you can write:

CardSuit invalid1 = (CardSuit) 9000;
CardSuit invalid2 = CardSuit.Club | CardSuit.Diamond;

This will break any code that expects the enum to only have one of the four card values. Also, Consider the case where you need to extend an enum. (Example borrowed from Jomo’s blog.)

enum Title { Mr, Mrs }

The Title enum works great, but imagine that later you add a ‘Ms’ value. Now every single switch statement you had is a potential bug. You can try to fix up all your code, but you are bound to miss something.

Enums provide a way to easily express some concepts but don’t provide enough compiler checks to prevent errors. Enter the Discriminated Union. A Discriminated Union in F# is a type which can only have one of a set of values, known as data tags. For example, consider a discriminated union for all Microsoft employees.

type MicrosoftEmployee =
    | BillGates
    | SteveBalmer
    | Worker of string
    | Lead   of string * MicrosoftEmployee list

If you have an instance of type MicrosoftEmployee, you know that it can only be one of {BillGates, SteveBalmer, Worker, or Lead}. Moreover, if it is a Worker then you know that there is an string associated with that data tag, probably corresponding to a name. We can create discriminated unions easily and use pattern matching - described later - to match their values.

let myBoss = Lead("Yasir", [Worker("Chris"); Worker("Matteo"); Worker("Santosh")])

let printGreeting (emp : MicrosoftEmployee) =
    match emp with
    | BillGates   -> printfn "Hello, Bill"
    | SteveBalmer -> printfn "Hello, Steve"
    | Worker(name) | Lead(name, _) 
                  -> printfn "Hello, %s" name

Now what if we extend that Discriminated Union…

type MicrosoftEmployee =
    | BillGates
    | SteveBalmer
    | Worker of string
    | Lead   of string * MicrosoftEmployee list
    | ChrisSmith

… now we get a compiler warning in our match.

The compiler detected that you didn’t match every tag of the discriminated union and issued a warning.  Checks like this go a long way towards preventing bugs.  To see a few examples of just how powerful discriminated unions are, check out this post.

 

Pattern Matching

Pattern matching is like a powerful switch statement, allowing you to branch control flow. You can do more than just comparing a value against a constant however, pattern matching allows you to also capture new values. Such as in our previous example, we bound the identifier ‘name’ when matching against discriminated union tags.

let printGreeting (emp : MicrosoftEmployee) =
    match emp with
    | BillGates   -> printfn "Hello, Bill"
    | SteveBalmer -> printfn "Hello, Steve"
    | Worker(name) | Lead(name, _) 
                  -> printfn "Hello, %s" name

Pattern matching can also match against the ‘structure’ of the data. So we can match against list elements joined together. (Remember that x :: y means that x is an single element of the list, and y is list of items after it. Also ‘[]’ represents the empty list.)

let listLength alist =
    match alist with
    | [] -> 0
    | a :: [] -> 1
    | a :: b :: [] -> 2
    | a :: b :: c :: [] -> 3
    | _ -> failwith "List is too big!"