My interest was piqued by an article by Mark Seemann from his upcoming book “DI in .NET”. This was a good introduction, but not very in-depth – I’m certainly looking forward to his book now.

After digging in more, I discovered a few more good articles (also on .NET Slackers) that explain IoC and DI using the Castle Project – “Inversion of Control and Dependency Injection with Castle Windsor Container” – check them out:

• Part I
• Part II
• Part III
• Part IV

Very cool stuff.

I don’t know a lot of details about the positions these recruiters are trying to fill, but I did find out that one is in Columbus, OH and one is in Redmond, WA. In an effort to help out the F# community I figured I’d post about these jobs.  There’s nothing in it for me.

If you are interested, shoot me an email and I’ll send you the contact information for the folks who called/emailed/talked to me.

Here’s my info:

let email = 
    [(5,"gmail"); (2,"."); (3,"valerio"); (6,"."); (1,"matt");
     (7,"com"); (4,"@")]
    |> List.sortBy fst
    |> List.map snd
    |> List.reduce (^)

The first thing we need is a pair of mutually-recursive functions.  The easiest (laziest? ) way to do this is to write one function (e.g. f1) and duplicate its implementation as another name (e.g. f2):

// Hunting for tail calls

// 6.17.09

open

let

and

let

let

After compiling this, I popped open the resulting executable in Reflector. Of course I wasn’t going to find the ‘tail’ opcode by looking at the C# – I needed to disassemble the IL. I hunted and hunted for the ‘tail’ opcode, but couldn’t find it!  Every call to f1 from f2 (and f2 from f1) used the stack to pass around n and acc. Even stranger – this is the first F# program I’d written using Visual Studio 2010, and I could have sworn that I’d done the same thing with F# in Visual Studio 2008 a couple months ago.

After building the project again, I noticed the command-line arguments passed to fsc:

“—tailcalls-“? Somehow tailcalls are being turned off. Maybe there’s something in the project settings that are disabling the tailcalls? Ah-ha! The checkbox was unchecked

After poking around a bit more, I discovered that by default the “Generate tail calls” box is unchecked fo Debug mode, and checked by default for Release mode.  Hmmm, interesting.

After switching to Release mode, I rebuild the project and opened the .exe in Reflector.  Here we go! There’s the elusive ‘tail’ opcode:

.method

}

(The IL code for sum2 looks identical.) Interestingly enough, the C# code from Reflector looks exactly the same between Debug and Release modes (with and without tail calls) – C# doesn’t have the capability to make tail calls.

Well, there you have it! We finally found the elusive ‘tail’ opcode.

That being said, be sure to keep this in mind – the default settings of Visual Studio 2010 for F# development are drastically different between Debug and Release mode.  Bugs might crop up in Debug mode (e.g. StackOverflowExceptions) that don’t rear their heads in Release mode.

I think the motivation for this is that using tail calls severely limit the usefulness of the Visual Studio debugger since it relies on traversing the stack frame (that the tail opcode destroys) to display debugging information.

For example, without tailcall optimizations setting a breakpoint on sum1 looks like this:

The callstack shows some useful debugging information, specifically the values of n and the accumulator.

However, if we enable tailcall optimization, this breaks down after running through the breakpoint 10 times, each time it shows one line with different information:

… You get the idea.

Hope that sheds some light on tailcall optimization, as well as some of the new features of F# in Visual Studio 2010!

Enter Live Mesh. It lets you add multiple devices to your mesh network and automatically synchronize your files between devices.  Pretty cool stuff.

At first I thought it would be a great place to put all of my source code — then I could have the code on every computer.  However, what if you have working code on your desktop, then open up the code on your laptop and introduce a few bugs.  When you go to open up the project on the desktop again, those bugs are there automatically.  The synchronization is great, but there’s no way to keep version information in case you want to revert to a previous snapshot of the files.

Anyone familiar with Subversion will remember that there are two main parts to an installation — the Subversion repository (could be local or remote) and another folder with the checked-out files. A not-uncommon setup for personal development work is to have a local Subversion repository as a directory on the local file system.  I wonder what would happen if I used slapped a local repository installation into a Live Mesh folder? Well, it would get automatically synchronized between machines. All devices in the network would have an SVN client installed (e.g. TortoiseSVN) and pointed to the Mesh-synchronized folder.  I think this just might work

For anyone interested, here are the steps that I followed to set this up.

Open up your Live Mesh Folders from My Computer:

Set up a new folder named “Subversion”. Make sure that all of the devices in your Live Mesh network are set to “When files are added or modified” in the synchronization options.

Browse over to the location (Subversion folder on my desktop), open it up, and create another folder inside called “Repository”.

Then, right-click on the Repository folder -> TortoiseSVN -> Create repository here. It’s important to note here that the extra “Repository” directory is important since you can’t directly create the repository in the “Subversion” folder one level up.  There is some interaction between TortoiseSVN and Live Mesh that keeps it from working.

Then, go back to the desktop (or any other place) and make a folder called “Checkout”.  Right-click on the Checkout folder and select “SVN Checkout…”

Make sure that the “URL of repository” field is pointed towards the “Subversion/Repository” directory and the “Checkout directory” field is pointed towards the “Checkout\Repository” directory and click OK.

There you go — use the checked-out subversion repository as you wish and just point your SVN client on each device to the Mesh-synchronized folder.

Hope someone finds this useful!

UPDATE: Looks like I’m not the first to think of doing this

Why so busy?  Well, since the end of November I applied for, interviewed for, was offered, and accepted a job at Microsoft   As a consequence, I’ve been extremely busy getting ready for and making the cross-country move from Columbus, OH to Redmond, WA.  Needless to say, it was a very exciting and nerve-wracking last few weeks.

I started as a SDE (software development engineer) in the Health Solutions Group last Monday. I’m still learning the ropes and certainly relate to the feeling of “drinking from the fire hose“. Today was a “momentous” occasion as I submitted my first bugfix, only to quickly discover the need to submit a bugfix for my bugfix. It’s quite humbling being completely surrounded by veritable developer rockstars.

Despite all of the stress, I am absolutely and totally pumped to be here — my project is awesome and the people I work with are awesome — there are very exciting times ahead

Hopefully as things start to settle down I’ll get some time to braindump about all of the cool things going on.

Recursion pops up quite a bit in functional programming so it’s a good idea to understand the risks/tradeoffs/benefits. A gross simplification of an analogy would be:

For loops : C# :: Recursion : F#

Sure, you can do for-loops and imperative-style coding in F#, but it doesn’t showcase the beauty of the functional style programming that F# offers.

Recursive functions (in both C# and F#) are just functions that call themselves.  They do so by pushing the current state of the function onto the stack, popping them off when calls start completing. Because the stack is a limited resource, it can be exhausted (StackOverflowException) if the function is called recursively too many times. 

These kinds of runtime exceptions can be difficult to find unless explicitly tested for, leading to hard-to-find bugs.  Oftentimes tests will only exercise simple cases of algorithms and then fail at runtime when large (real-world) inputs are used. After all, “everything works for small N”.

F#, however, has a very interesting feature where (under certain conditions), it can recognize recursive functions and perform a “tail call optimization”, turning the recursive function into a while-loop that uses no stack space whatsoever. This is called tail recursion.

The rule for tail-recursion is simple:

If the recursive call to the function is the very last thing that happens in the algorithm, then the function can be made tail-recursive.

In most cases a recursive algorithm can be expressed in both recursive and tail-recursive forms. Other times, it may not even be possible to implement a specific algorithm tail-recursively.

Let’s look at some examples.

Tail Recursive or Not?

One way to implement the “map” function that applies a specific function, f, to every element in a list would be:

While this implementation easily expresses the algorithm (splitting a list into its head and tail, applying the function f to the head, and consing it to the list obtained from applying the function to the tail), it is NOT tail recursive! The recursive call to “map” must happen, then f is applied to h, and then the results are cons’d (:: operator).  The recursive call to “map” is not last in this instance, so it’s not tail-recursive.

How can we make this map operation tail-recursive? Typically this involves 2 things — factoring out an inner loop that is recursive and threading an accumulator through that inner loop:

In the 2nd-to-last line, f2 is applied to the head, then cons’d with the accumulator, and that result (along with f2 and the tail) are passed to the recursive call to “loop”.  In this case, “loop” is the very last thing that happens, so the F# compiler can implement this tail-recursively.

Double-Check with Reflector

We can double-check that the F# compiler created a recursive function for the “map” case by using Reflector.  While F#-compiled-to-IL-decompiled-to-C# can be a bit verbose thanks to all of the generics and partial function application (FastFunc), it can still be seen that the map function recursively calls itself.

If the Tail Recursion Police were out, we’d be totally busted.

For the “mapTR” case, the implementation is a bit hidden behind some closures, but can be found with a little work.  The meat of the tail-recursive function is implemented with a while(true) loop! This is fantastic since it uses no stack space. The Tail Recursion Police would let us off clean on this one.

Sidenote: The List<T> type here is not the standard System.Collections.Generic.List<T>.  It is a singly-linked list that is part of the F# core libraries. In F# the Generic.List<T> is known as ResizeArray<T> since it more resembles a resizable array than a singly-linked list.

Sidenote 2: I’ve heard some things about the “.tail” IL opcode, but don’t see it popping up anywhere in this code. The while loop seems more efficient to me than a recursive call that drops the current stack frame, though. I’m not entirely sure what the relationship is between the .tail opcode is and tail recursion in F#.

Let’s walk through another example and dig into a little more detail.

Kaboom! StackOverflowException Strikes

When working on some code over the weekend, I ran into the need for a slightly different version of List.map. The “map” function has the signature “(’a -> ‘b) -> ‘a list -> ‘b list” — that is, it takes a function that takes a ‘a and returns a ‘b as well as a ‘a list to operate on, producing a ‘b list. It simply applies the given function to each item in the list and returns a new list with the result of each function application.

What I needed, however, was a method that took a list of one type and returned a list of another type, but applied a function that accepted a list of values and produces a resulting value.  That is, I needed a function with a signature “(’a list -> ‘b) -> ‘a list -> ‘b list”. When you think about this, I needed an algorithm that would operate on the initial list by calling a method by “snapping off” successive portions of the list, producing another list.  So, if we had a list [1;2;3;4], the mapping function would be called in succession with input lists [1;2;3;4], [2;3;4], [3;4], [4], and []. Since it’s still doing a mapping, though making the entire list (instead of just the head of the list) available to the mapping function, I decided to call it “mapl” for “map list”.

My first stab at an implementation was straightforward:

Good so far. However, it’s not tail-recursive, so let’s see if we can break it:

Kaboom! The Tail Recursion Police are already on the scene, cleaning up the remains of fsi.exe…

Tail-Recursion Tweaks and Performance

Ok, so let’s make this “mapl” function tail-recursive. I wanted to investigate 3 different approaches and compare the performance based on slight nuances between the implementations.

Here’s my code for mapl_tr1, mapl_tr2, and mapl_tr3:

You can see that we factored out an inner loop that is recursive, added an accumulator list, and made sure that the loop function call was the last operation before recursing.

• mapl_tr1: This function captures the function “f” (a closure) from within the inner loop.
• mapl_tr2: This function explicitly passes the function “f” to the inner loop to test if a closure slows things down
• mapl_tr3: This function creates tuples when passing values to the inner loop and recursing to test if tuples are faster than partial function applications

To test these functions out, I used a simple test harness:

This takes a list of the three methods (isn’t it great to pass around code as data in functional languages?), run a test by timing it and taking the average of 10 executions, then print out the results.

Wow, that’s really interesting. mapl_tr1 and mapl_tr2 are almost the same running time, but mapl_tr2 is slightly faster.  So we can conclude that the closure adds a very small amount of overhead, which isn’t surprising.  What caught me off guard is that mapl_tr3 takes more than 50% longer than mapl_tr2, owing to the constant creation of tuple objects under the hood. Looks like we have a winner, mapl_tr2!

For completeness, the implementations of time_iter and press_enter are given below:

(time_iter can be optimized so it doesn’t create a 0..n list and uses sequence expressions…)

Conclusions

F# makes it really easy to write recursive functions that succinctly express our algorithms, but care must be taken to address tail recursion so that StackOverflowExceptions aren’t encountered in production code. Also, tail-recursive functions can be further optimized by ensuring that tuple objects aren’t created at each iteration, and by explicitly passing functions to inner loops and not relying on closures.

Whenever you write “let rec”, don’t give the Tail Recursion Police reason to take you downtown…

Hope that helps someone and eliminates some of the smoke/mirrors surrounding tail recursion! 

The default F# console application contains a single Program.fs source file. By default, this puts everything in that file into a module named “Program”.

The entry point of an F# console application is typically the top-most code in the last .fs file of the project.  This leads to the standard F# programming pattern of the last file in the project (typically Program.fs) containing something along the lines of:

Now, to add all of the assembly metadata to the project, we need to attribute the “main ()” function call with all of the attributes.  We can’t use the “unit” operator “()” like we did in the F# Library case, since our console application actually does have an entry point that we care about.

We can accomplish this by moving the “main ()” line to the AssemblyInfo.fs file, requiring us to fully-qualify it to “Program.main ()” since it resides in the Program module.

If we add the AssemblyInfo.fs file from the previous post, it must go last, for example:

Now, in Program.fs we only have:

And at the end of AssemblyInfo.fs we have:

Just like in the library case, it would be nice if the default F# console application template included both Program.fs and AssemblyInfo.fs and included a definition for “main” to avoid any confusion as to the entry point of the application.

Hope that helps!

However, F# libraries (by default) don’t have this assembly metadata, so you don’t know what version of a DLL you are looking at.  For example, without assembly information, MyLibrary looks like this in the Explorer window:

That’s not very helpful.

Thankfully, it’s very easy to add an AssemblyInfo.fs file to our F# library and achieve the same thing as a C# library.

Here’s the AssemblyInfo.fs file that you can copy/paste into your project.

To use it, make AssemblyInfo.fs the last file in your F# Library (DLL) project (remember – file order is important for F# projects).  If necessary, right click on the file and use the “Move Up” and “Move Down” commands.

After compiling the F# Library, it will then have all of the usual CLR metadata compiled into the assembly and show up in the Explorer window correctly:

It is very important to note that the last line of AssemblyInfo.fs is “()”.  The file won’t compile without this, since attributes (even though they are assembly-level attributes) must be applied to something.  In this case, we’re applying all of the attributes to the “nothing” placeholder in F#, called “unit”, or “()”.

It would be nice if the F# templates that ship with the F# CTP included this file by default. I guess I could always make my own template

Hope that helps!

To restate the problem:

In the 20×20 grid below, four numbers along a diagonal line have been bolded.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26×63x78×14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

We started down the path of how to extract all of the possible sequences of 4 numbers from the 20×20 grid using sequence expressions.  However, it occurred to me that pattern matching might be a good fit for this, so I decided to try out an alternative approach using pattern matching.

The first step is to create a pattern-matchable structure containing our 20×20 grid of numbers. I decided to use an “int list list” — a list of a list of integers.  This is easy enough to do if we split the text into lines, then split each line into number strings, and then convert each number string into an integer:

In F#-ese, we take the text, and “pipe” (using the |> operator) it into the String.split operation that splits the string on newlines.  This gives us a list of strings (string list) that we can then “pipe” into a List.map operation that applies the given function to each string in the list (each row).  This mapping function splits each row string on spaces and then converts each number string to an integer.  I’m using function composition here (the >> operator), since the string split happens, and then the integer conversion happens.

As we’re hunting through all of the possible 4-number combinations (left-right, up-down, diagonal-left, and diagonal-right), we need to store some information.  We need 1) the product of the 4 numbers and 2) the 4 numbers themselves.  This seems like a good place to use a tuple, where we can store two things — the product and the 4-number list.  We can write a function that takes 4 numbers and creates this tuple for us:

The signature of this method is “val makeTuple : int -> int -> int -> int -> int * int list”, which says that we take 4 integers and create an (int * int list), i.e. a 2-element tuple with an integer and an integer list.

Now we come to the pattern matching aspect of the problem.  We need to apply a 4×4 filter to the 20×20 cell array, look for 4 patterns, and then repeat the process for the remaining cells.

Pattern matching in F# can easily dissect a list into its head (first element) and its tail (whatever’s left). This is denoted as “head::tail”.  You can also match with more than one element out of the front of the list, using “h1::h2::h3::tail”. In addition, you can ignore things if you don’t want to explicitly give them a name by using the “I don’t care” symbol, _, e.g. “h1::h2::_”.  And, you can group elements together and give them a new name, for example “h1::(h2::h3::_ as tail)”.

So, here’s the code for our pattern finding algorithm:

The findPatterns function takes our cells (a list of list of integers) and performs a pattern match over them.  The syntax is a little odd at first, so I made a picture to show what is matched with what:

If the cells match the pattern (that is, a 4×4 square has been found), then the 4-length sequences are stored as a tuple, and the method is recursively called again, twice. 

The first recursive invocation is called with a new 2-d list containing the 4 tails from the previous match. In this loop, [t1; t2; t3; t4] keep getting their leftmost elements stripped out until there isn’t a 4×4 square left, in which case the pattern match fails, _ is matched, an empty “list list” ([[]]) is returned, and the recursion stops.  So basically we are walking left-to-right matching patterns and storing the results.

The second recursive invocation is called with the tail t5.  This is the input cells without the first row.  With this invocation we’re recursively walking the cells from top to bottom.

So, once we are able to find all of the patterns, then to solve the problem we just need to find the maximum value of the tuples returned:

Here we invoke findPatterns with the cells (returning a list list), concatenate that down to a list (of int * int list), and then find the maximum using the first value of the tuple (the product of the 4 numbers).

The result is:

> result;;
val it : int * int list = (70600674, [87; 97; 94; 89])

Cool!  It doesn’t take any time at all to execute on my machine — well below the “1 minute rule” for Project Euler.

I’m sure there are ways to improve this algorithm.  It uses the stack quite heavily, and the list concatenation (@ operator) is expensive. Also, storing all of the results for all combinations wastes memory — a fold would be more efficient, allowing you to compare as you move along.

Despite these potential problems, I really like this solution because it is so concise.

After some discussion on the Google Groups list, we decided to use Git instead of Subversion for the source control.  Sure, why not? Might as well try out something new.  We found GitHub.com which offers free hosting for public projects.

Installing the Git Client

I hunted around for a TortoiseSVN-esque Windows client for git, but there isn’t one (yet?).  Ah well, back to the command line with Cygwin.  I usually have Cygwin installed, but my installation on this machine is broken for whatever reason.  Thankfully I stumbled onto msysgit, an all-in-one installer.

I ran the installer, using all of the default options:

Git uses SSH under the covers to connect to the remote git repository, so we need to spend a second setting up our public/private key pairs.

Double-clicking on the “Git Bash” shortcut on my desktop brings me up to a MINGW32 command prompt.  I need to generate new SSH keys, so I did:

$ ssh-keygen.exe

This generated a few files:
~/.ssh/id_rsa = Private key
~/.ssh/id_rsa.pub = Public key

You’ll need to cat the id_rsa.pub file and copy/paste that public key (starting with the “ssh-rsa” line) into your GitHub account next.

Creating a GitHub account

Just sign up for a free Github account (pretty self-explanatory).

You’ll need to provide the SSH public key (not the private key!) to github so that you’ll have permission to commit. You can enter the key on the first screen (it’s optional), or add one once you’ve created the account.

Using Git

I just followed the directions on the fsharpbooksamples project page.

$ cd /d/OpenSource/
$ mkdir fsharpbooksamples
$ cd fsharpbooksamples/
$ git init

Here I created and edited a README.txt file

$ git add README.txt
$ git config –global user.email matt.valerio@gmail.com
$ git commit -m ‘Initial commit’
$ git remote add origin git@github.com:mattvalerio/fsharpbooksamples.git
$ git push origin master

And, that’s about it.  Note that on the last push command, it will fail if you don’t have your SSH keys set up correctly. It will complain with an error message that says “Permission denied (publickey)”.  If you set up a passphrase while generating your SSH keys, you’ll need to enter that here.

Hope that helps!