by ·1 Comment

If you recall a while back when I was demonstrating some Functional Data Structures, I mentioned the fact that some of the functions were not tail recursive, and that this is something that we would probably want to do something about. Which raises the question: How exactly do we go about making a function tail-recursive? I am going to attempt to address that question here.

One of the first problems with creating a tail recursive function is figuring out whether a function is tail recursive in the first place. Sadly this isn’t something that is always obvious. There has been some discussion about generating a compiler warning if a function is not tail recursive, which sounds like a dandy idea since the compiler knows enough to know how to optimize tail recursive functions for us. But we don’t have that yet, so we’re going to have to try and figure it out on our own. So here are some things to look for:

  1. When is the recursive call made? And more importantly, is there anything that happens after it? Even something simple like adding a number to the result of the function can cause a function to not be tail-recursive
  2. Are there multiple recursive calls? This sort of thing happens when processing tree-like data structures quite a bit. If you need to apply a function recursively to 2 sub-sets of elements and then combine them, chances are they are not tail-recursive
  3. Is there any exception handling in the body of the function? This includes use and using declarations. Since there are multiple possible return paths then the compiler can’t optimize things to make the call recursive.

Now that we have a chance of identifying non-tail-recursive functions lets take a look at how to make a function tail-recursive. There may be cases where its not possible for various reasons to make a function tail-recursive, but it is worthwhile trying to make sure recursive functions are tail-recursive because a StackOverflowException cannot be caught, and will cause the process to exit, regardless (yes, I know this from previous experience Smile)

Accumulators

One of the primary ways of making a function tail-recursive is to provide some kind of accumulator as one of the function parameters so that you an build the final result and pass it on using the accumulator, so when the recursion is complete you return the accumulator. A very simple example of this would be creating a sum function on a list of ints. A simple non-tail-recursive version of this function might look like:

let rec sum (items:int list) =
    match items with
    | [] –> 0
    | i::rest –> i + (sum rest)

And making it tail-recursive by using an accumulator would look like this:

let rec sum (items:int list) acc =
    match items with
    | [] –> acc
    | i::rest –> sum rest (i+acc)

 

Continuations

If you can’t use an accumulator as part of your function another (reasonably) simple approach is to use a continuation function. Basically the approach here is to take the work you would be doing after the recursive call and put it into a function that gets passed along and executed when the recursive call is complete. For an example where we’re going to use the insert function from my Functional Data Structures post. Here is the original function:

let rec insert value tree =
    match (value,tree) with
    | (_,Empty) –> Tree(Empty,value,Empty)
    | (v,Tree(a,y,b)) as s –>
        if v < y then
            Tree(insert v a,y,b)
        elif v > y then
            Tree(a,y,insert v b)
        else snd s

This is slightly more tricky since we need to build a new tree with the result, and the position of the result will also vary. So lets add a continuation function to this and see what changes:

let rec insert value tree cont =
    match (value,tree) with
    | (_,Empty) –> Tree(Empty,value,Empty) |> cont
    | (v,Tree(a,y,b)) as s –>
        if v < y then
            insert v a (fun t –> Tree(t,y,b)) |> cont
        elif v > y then
            insert v b (fun t –> Tree(a,y,t)) |> cont
        else snd s |> cont

For the initial call of this function you’ll want to pass in the built-in id function, which just returns whatever you pass to it. As you can see the function is a little more involved, but still reasonably easy to follow. The key is to make sure you apply the continuation function to the result of the function call, otherwise things will fall apart pretty quickly

These two techniques are the primary means of converting a non-tail-recursive function to a tail-recursive function. There is also a more generalized technique known as a “trampoline” which can also be used to eliminate the accumulation of stack frames (among other things). I’ll leave that as a topic for another day, though.

Another thing worth pointing out, is that the built-in fold functions available in the F# standard library are already tail-recursive. So if you make use of fold you don’t have to worry about how to make your function tail recursive. Yet another reason to make fold your go-to function.

by ·4 Comments

Let’s say that you’ve been working hard on this really awesome data structure. Its fast, its space efficient, its immutable, its everything anyone could dream of in a data structure. But you only have time to implement one function for processing the data in your new miracle structure, so what would it be?

Ok, not a terribly realistic scenario, but bare with me here, there is a point to this. The answer to this question, of course, is that you would implement fold. Why you might ask? Because if you have a fold implementation then it is possible to implement just about any other function you want in terms of fold. Don’t believe me? Well, I’ll show you, and in showing you I’ll also demonstrate how finding the right abstraction in a functional language can reduce the size and complexity of your codebase in amazing ways.

Now, to get started, let’s take a look at what exactly the fold function is:

val fold:folder('State -> 'T -> 'State) -> state:'State -> list:'T list -> 'State

In simple terms it iterates over the items in the structure, and applies a function to each element which in some way processes the element and returns some kind of accumulator. Ok, maybe that didn’t come through quite as simply as I would have hoped. So how about start with a pretty straight-forward example: sum.

 
let sum (list:int list)= List.fold (fun s i -> s + i) 0 list

Here we are folding over a list of integers, but in theory the data structure could be just about anything. Each item in the list gets added to the previous total. The first item is added with the value passed in to the fold, so for items [1;2;3] we start by adding 1 to 0, then 2 to 1, then 3 to 3, the result is 6. We could even get kinda crazy with the point-free style and use the fact that the + operator is a function which takes two arguments, and returns a third…which happens to exactly match our folding function.

let sum (list:int list) = List.fold (+) 0 list

So that’s pretty cool right? Now it seem like you could also very easily create a Max function for your structure by using the built in max operator, or a Min function using the min operator.

let max (list:int list) = List.fold (max) (Int32.MinValue) list 
let min (list:int list) = List.fold (min) (Int32.MaxValue) list

But I did say that you could create any other processing function right? So how about something a little trickier, like Map? It may not be quite as obvious, but the implementation is actually equally simplistic. First let’s take a quick look at the signature of the map function to refresh our memories:

val map: mapping ('T –> 'U) –> list:'T list –> 'U list

So how do we implement that in terms of fold? Again, we’ll use List because its simple enough to see what goes on internally:

let map (mapping:'a -> 'b) (list:'a list) = List.fold (fun l i –> mapping i::l) [] list

Pretty cool right? Use the Cons operator (::) and a mapping function with an initial value of an empty list. So that’s pretty fun, how about another classic like filter? Also, pretty similar

let filter (pred:'a -> bool) (list:'a list) = List.fold (fun l i –> if pred I then i::l else l) [] list

Now we’re on a roll, so how about the choose function (like map, only returns an Option and any None value gets left out)? No problem.

let choose (chooser:'a –> 'b option) (list:'a list) = List.fold (fun l i –> match chooser i with | Some i –> i::l | _ –> l) [] list

Ok, so now how about toMap?

let toMap (list:'a*'b list) = List.fold (fun m (k,v) –> Map.add k v) Map.empty list

And collect (collapsing a list of lists into a single list)?

list collect (list:'a list list) = List.fold (fun l li –> List.fold (fun l' i' –> i'::l') l li) [] list

In this case we’re nesting a fold inside a fold, but it still works. And now, just for fun, list exists, tryFind, findIndex, etc

let exists (pred:'a -> bool) (list:'a list) = List.fold (fun b i -> pred i || b) false list
let tryFind (pred:'a -> bool) (list:'a list) = List.fold (fun o i -> if pred i then Some i else o) None list
let findIndex (pred:'a -> bool) (list:'a list) = List.fold (fun (idx,o) i -> if pred i then (idx + i,Some idx) else (idx + 1,o)) (-1,None) list |> snd |> Option.get
let forall (pred:'a -> bool) (list:'a list) = List.fold (fun b i -> pred i && b) true list
let iter (f:'a -> unit) (list:'a list) = List.fold (fun _ i -> f i) () list
let length (list:'a list) = List.fold (fun c _ -> c + 1) 0 list
let partition (pred:'a -> bool) (list:'a list) = List.fold (fun (t,f) i -> if pred i then i::t,f else t,i::f) ([],[]) list

Its worth pointing out that some of these aren’t the most efficient implementations. For example, exists, tryFind and findIndex ideally would have some short-circuit behavior so that when the item is found the list isn’t traversed any more. And then there are things like rev, sort, etc which could be built in terms of fold, I guess, but the simpler and more efficient implementations would be done using simpler recursive processing. I can’t help but find the simplicity of the fold abstraction very appealing, it makes me ever so slightly giddy (strange, I know).

by ·0 Comments

So, to take a slightly different turn from my usual meta discussions of process, theory, and architecture, there have been several people who have offered up some examples of extension methods that they have found useful, now that .Net 3.5 is roaring along nicely.  There are some collections of such utilities, like the Umbrella project, and some folks like Bill Wagner who have written books on the subject (okay, there are other things in there too), so I thought I might as well throw my hat into the ring as well.  Specifically, there was this tweet from @elijahmanor a few days ago.  It points to a positing which includes some extensions on string to convert from strings to value types (int, long, short, etc).  I pointed out that in our current project we have distilled this down to a single extension method: To().

He suggested I blog about it, so here it is:

So we actually have two classes of conversions, one converts from a string to a value type, and they other converts from a string to a Nullable value type.  In the case of our project, the nullable version came first, and so it became very easy to create the version that returned a non-nullable value.  Here are the methods of interest:

public static T To(this string input) where T : struct
{
    return input.To(default(T));
}

public static T To(this string input, T defaultValue) where T: struct
{
    return input.ToNullable() ?? defaultValue;
}

public static T? ToNullable(this string input) where T : struct
{
    if (string.IsNullOrEmpty(input))
        return null;
    var tryParse = GetTryParse();
    return (T?)tryParse(input);
}

Okay, so this is pretty straight forward.  The non-nullable version calls through to the nullable version, and if it is null, it returns default(T).  But, as I’m sure you are an astute reader, you will see that there is some magic going on; namely the GetTryParse() method.  This little guy goes off and looks for a TryParse method on whatever T happens to be, and then returns a Func<> delegate that will run the string input through the try parse and return either a null (in case the TryParse fails), or a boxed version of the result.  So, lets see what it looks like before we discuss pros and cons

private static Func<string,object> GetTryParse()
{
    var tryParseEx = GetTryParseExpression();
    return (s) =&gt; tryParseEx.Compile()(s,default(T));
}

private static Expression&lt;Func&lt;string,object&gt;&gt; GetTryParseExpression()
{   
    if (_tryParseCache.ContainsKey(typeof(T)))
	return _tryParseCache[typeof(T)] as Expression&lt;Func&lt;string, T, object&gt;&gt;;

    MethodInfo tryParse = typeof(T).GetMethod("TryParse", new Type[] { typeof(string), typeof(T).MakeByRefType() });
    Ensure.IsNotNull(tryParse, string.Format("Cannot convert from type string to type {0} because {0} does not have a TryParse method", typeof(T).FullName));

    var stringArg = Expression.Parameter(typeof(string), "input");
    var tempArg = Expression.Parameter(typeof(T), "tmp");

    var tryParseEx = Expression.Lambda&lt;Func&lt;string,object&gt;&gt;(
        Expression.Condition(
            Expression.Call(tryParse, stringArg, tempArg)
                , Expression.Convert(tempArg, typeof(object))
                , Expression.Constant(null))
        , stringArg, tempArg);
    _tryParseCache.Add(typeof(T), tryParseEx);
    return tryParseEx;
}

So here we have some code looking for a TryParse method, and building an expression (using Linq Expression Trees) to execute it.  Now, I’ll be honest, this is not the code I’m using in the project where this originally came from…mostly because I didn’t think of it then.  In that case I’m actually doing a big case statement, checking the type of T and running the appropriate method.  This is much shorter, but potentially much slower at runtime.  So that is where the _tryParseCache comes in.  This is a simple static dictionary which contains the expressions created for each of the types, which means you only get the runtime performance hit once when you first ask to parse a specific type.  The declaration for this object looks like this:

private static Dictionary _tryParseCache = new Dictionary();

There you have it, my first (and possibly last??) contribution into the world of extension methods. Please commence criticisms

by ·0 Comments

So previously I posed a question, which in it’s simplest form is: Should you write code for the rest of your group (or at their proficency level), or should you write code as advanced as you need. and let it serve as an example for those on your team who are less advanced in their abilities.  The practical answer I have come up with is, like most answers of this type, “It depends”.

I have decided to handle things this way: 
First, don’t compromise.  If I feel something is a bad practice, or ultimately going to restrain future development, then do what needs to be done.
But Also: Try to avoid introducing advanced concepts and idioms until there is a compelling example of what their benefit is.  This is probably something that applies more to working with existing apps, then greenfield development, but it certainly has bearing in both cases.  The big example for this that I ran into was IoC.  I am a big fan of IoC, but it is hard to come up with a good, concise explanation of why you need this additional tool.  I’ve been wanting to introduce IoC since I started working at Envisage, but the explanation “This will make things much easier later on” is not good enough…particularly when you are trying to embrace YAGNI.  So the key is to wait until you can actually demonstrate the advantage, and provide a before and after example of how things are done.

Lead by example, but make sure you have the examples.  To bring the food analogy back into play, it isn’t good enough to create a gourmet meal, and tell the people who say they don’t like it that, no, it really is better, and their just not sophisticated enough to know it.  It is better to start smaller, and build their appreciation up in increments.

by ·0 Comments

At Envisage, we have a 1 week iteration.  This means that we typically don’t want a single story to go longer than one week.  We also change up the pair rotation once per week.  The estimation process is not perfect, though, and we have a lot of support from management to choose doing things right, rather than doing things now, which leads to stories going beyond a single iteration.  So when this happens, there is usually a small rock/paper/scissors session with the developers involved to determine who will be taking the story.  More often then not, the story goes with the machine (and the developer) that was used to do the work, since it is usually not practical to check in changes at the end of the week (also, our QA builds on Fri for a demo, so a green build is needed on Fri).

One approach to this, which occurred to myself, and one of our other developers at close to the same time, was to utilize the concept of a personal branch.  This is something that I believe is supported transparently in TFS, though I’m not 100% sure.  We are using Subversion, so the process is somewhat manual, but overall pretty easy to get started.  Once a branch was created, I found it extremely liberating.  I have apparently been making decisions about how much to change while I’m refactoring code at least partly based on how much work it will be to integrate directly back into the trunk.  Having a private, protected area for me to work made it much easier to change things in the way they needed to be changed.  It also meant that I could check in more often, including checking in changes which would leave the app in a non-functional state.  Having those commit points meant that I could more easily undo changes, and gave me a nice warm and fuzzy feeling about the changes I was making.  There was also another interesting advantage, and that was when another developer was asking me about how the API would look on some of the objects I was working on, and I was able to point him directly to my branch to see the changes.

There were a few issues, however.  The biggest was that, though we are running the Subversion 1.5 server, our repository has not been updated, so the automatic merge tracking was not working.  This meant that I had to keep track of the revision numbers myself whenever I needed to merge updates to the trunk into my branch.  And this also made the “Reintegrate Branch” merge function impossible when I was ready to check my changes in.  Despite these issues, I think in this particular case (the story lasted about 3 weeks) I was worth the extra effort, and made the overall process much easier.  We will be updating our repository this week, which may make having a personal branch a viable solution for normal day-to-day work, but as it is the effort involved was a bit more than what I would want to deal with on a regular basis.  I will certainly not hesitate to break out this tool whenever I’ve got either a long running, or a large scope (meaning either large numbers of files effected, or a large change to parts of the API) story.  I certainly recommend giving it a try.

by ·0 Comments

We had a friend visiting from out of town last night, and she is apparently fond of “Top Chef”.  This was the first time I had encountered this particular “reality” based show, and I found in a lot of ways it was like the majority of the rest of the shows out there; trying hard to create drama where there really isn’t any.  In this particular episode there was a challenge to cook food for a neighborhood block party.  The group that did the worst in this particular case cited the fact that they were preparing food for everyone including kids, as a reason for not getting jiggy with the menu (in a culinary sense).  The response from the judges was that good food would speak for itself, and they should have considered it their responsibility to raise the collective bar of quality for the neighborhood.

I find this quite interesting because it mirrors an internal dilemma I am facing with the code I am currently putting together.  The dilemma is this:  Should I create things which are more “advanced” and more difficult for those who are not familiar with the concepts, or should I take the audience into consideration, and forego some of the more advanced concepts in favor of simplicity and discoverability?

My gut tells me that I should do the latter.  I’m a big believer in the power of writing code that is easy to understand and maintain.  This is particularly true whenever you are writing code which will potentially be consumed by other developers working within the application.  If someone cannot figure out how to utilize the work you’ve done, then chances are they are going to go off and duplicate it.  The eventual result of this being half a dozen ways to accomplish what is basically the same thing.

The idea brought up on the show seems to go against this philosophy by suggesting that you have the ability to expand the pallets of those who are consuming your work (the food metaphor is staring to get pretty rich here), and so you would be doing them a disservice not to.  In my case, I’ve found places where my choice to keep things more like what everyone is used to has added complexity and ugliness elsewhere. 

So does this mean I should forge ahead and present concepts which are going to be new to others on the team, and potentially create code that will not be re-used as it should because it does not make sense to those needing to re-use it?  If I don’t introduce these concepts am I missing an opportunity to bring up the overall quality of the code being by everyone?  Am I just struggling to fid answers to questions that I really shouldn’t be asking, since the YAGNI police are keeping their eyes on things?

by ·0 Comments

About two weeks ago I crafted my first Fluent Interface.  Since then I’m finding myself seeing more and more places where I think such an approach would be useful.  The part that I’m finding odd is that it is something that just recently became a possibility for me.  The big motivating factor behind that I believe was reading the post that Martin Fowler did on the subject, in which he basically describes it as a super-great idea (okay, I’m paraphrasing, but you get the idea).  The concept is fairly simple; write an API that reads like a sentence. 

This isn’t a new concept, in fact I seem to recall reading quite a bit in the world of agile and TDD in which the authors encourage you to make method/property/variable names verbose and more like natural language in order to improve readability of code, and make the items more self-documenting.  I think the big difference, though, is that fluent interfaces tend to be more granular.  Instead of a single method that reads like a sentence, you are building a sentence using method and property names, with Intellisense there to help you determine what is possible at the end.

The big shift, I think, is in the realization that within this context method names like With, For, and And are perfectly okay, and as a matter of fact make things better in the end.  Its like a taboo has been lifted, and suddenly I have a whole new landscape of possibilities opened up.

Since the original implementation of a small fluent interface I created for a small part of my project (I’m using it to describe discrete elements of a document to be parsed), I’ve found myself creating a new fluent interface to play with .Net 3.5 extension methods (replicating the Ruby 10.Minutes.Ago semantics), and also adding a new interface to the same production project as the first which is being used to grab component services from my IoC container.

I’m not sure if this is a new paradigm, or just a new hammer looking for nails, but it is interesting none-the-less. It has also opened up new challenges around testing and intellisense documentation, which I’ve not quite figured out yet.