Archives
-
Reminder- DC ALT.NET Meeting - 6/24/2008 - Applied Functional Programming with F#
Just a reminder about tonight's DC ALT.NET meeting. I hope some from the FringeDC and the NoVA Language Group can make it out tonight as it's quite on topic.
The June meeting for DC ALT.NET has been set up for June 24th from 7-9PM. Check out our site and our mailing list as more information becomes available. Once again, I'd like to thank the Motley Fool for hosting the event as they did back in May. This month, I'll be covering Applied Functional Programming with F# as a continuation of the talks I've been giving lately. The beauty of this group like last month's topic of Lisp and this month's topic of F# is to step outside of the comfort zone, look to the outside for better approaches to doing things instead of the "What's new on MSDN" sessions that I hear about time and time again.
The information is as follows:
Location:
Motley Fool
2000 Duke Street
Alexandria, VA, 22314
Map Link
Applied Functional Programming with F#
Recently, I've been doing quite a few talks on the introduction to functional programming and F#. In this session, I hope to cover the basics in short order once again, but also to show the applicability of where this language really hits the right areas. Are we going to immediately flock towards F# and abandon C# and other languages for all of your coding needs? No, but we have definite areas where F# and functional programming excels.
With this talk, I plan to focus on the following:
- Functional Programming Basics
- Custom Workflows
- Async and Parallel Workflows
- Mailbox Processing
- Language Oriented Programming
- Quotations and Expression Trees
- Pattern Matching and Active Patterns
- F# with MPI and High Performance Computing
Going a Step Further
Since I've been covering concurrency with .NET lately, it has me thinking a bit about creating workshops to teach this on weekends. Instead the way we see Code Camps, Day of .NET events and so on, it's an aggregate of all sorts of topics, and not going as deep as I wish. So, instead, I'd like to rectify that situation to hold day long sessions to go deep in any given subject, much like they do with the Philly.NET group. More on this as I flush out the details, but I'd like to hear feedback if people are interested in this sort of thing.
Hope to see a great turnout tonight!
-
Announcing FsTest - A Testing DSL for F#
Over the past couple of months, I've been working on some language oriented programming concepts in F# to prove how Domain Specific Languages could work. This coincided with my lofty goals of working towards more Behavior Driven Development (BDD) frameworks and expressiveness that I think is needed to make them work. So, this led me down a road of looking first at assertion syntax. With that, it made me create FsTest which is now available on CodePlex. This is meant to be a beginning of a conversation on doing better assertions through functional programming and language oriented programming and by no means an end to it.
The Starting Point
During some of my research, I came across a now defunct project on Google Code called FsUnit. The idea behind this project was to put a syntactic wrapper around NUnit to make assertions a bit more readable and to use unique features to F# to make this happen. To be able to write such things as this for my assertions seemed powerful:
1 |> should (equal 1)
true |> should (be True)
And so on... Ultimately, I thought it could be improved and expanded, so I talked to the project owner, Ray Vernagus, and took some of the ideas and ran with them.
Looking at FsTest
I had a couple of issues with the code as it was. But, overall the ideas were quite sound. I also wanted to use xUnit.net as the back end testing framework as I'm pretty comfortable with it. The support for tests on static classes, and the ability to assert on throwing exceptions were some of the pluses that made me move in this direction. Listed below are some of the assertions that are supported:
Testing equality:
"foo" |> should equal "foo"
"foo" |> should not_equal "bar"
null |> should be Null
"foo" |> should be NonNull
"foobar" |> should contain "foo"
"foobar" |> should contain "hello"
Testing True/False:
true |> should be True
false |> should be False
Testing collections:
[1..10] |> should be NonEmpty
[] |> should be Empty
[1..10] |> should have 3
[1..10] |> should not_have 25
Exception Management:
throwsExceptionFunc |> should (throw_exception<ArgumentException>)
doesntThrowException |> should not_throw_exception
And some full examples might look like this:
#light
open System
open Xunit
open FsxUnit.Syntax
let throwsException() : unit =
raise(ArgumentException "Bad things!")
[<Fact>]
let throwsException_should_throw_exception() =
throwsException |> should (throw_exception<ArgumentException>)
[<Fact>]
let value_in_range_should_be_in_range() =
2 |> should be_in_range 0 100
It's a work in progress, but I feel that I have most of the assertion cases covered in this DSL. The ability through partially applied functions really shone when creating this library.
The Concepts Behind It
What makes this work syntactically is the use of the forward operator. I've covered this briefly in previous posts, but I'll elaborate on this again. This is one of the most important operators available to us in the F# language. This is the ability to invert the arguments in such a manner as the first argument is declared first and then the function statement is last.
This is how it's declared in F#:
let (|>) x f = f x
Which allows me to better express my intent and gives me the two advantages:
- Clarity of intent - allows you to perform various operations on the data in a forward chaining way such as:
let length = [1..10] |> List.map(fun x -> x * x * x) |> List.filter(fun x -> x % 3= 0) |> List.length
- Type inference - allows type information to flow from the left to the right and allows me to express my data first as part of my method. Shows better intention this way.
And similarly, something in C# would use extension methods to add a forward method, or maybe in this case a Should method which will then take a function as the second parameter, and then overload it as need be.
Using Actions might look something like this:
public static void Should<TArg1, TArg2>(this TArg1 arg1, Action<TArg1, TArg2> action, TArg2 arg2)
{
action(arg1, arg2);
}
And conversely to use the Func delegate might look like this:
public static TResult Should<TArg1, TArg2, TResult>(this TArg1 arg1, Func<TArg1, TArg2, TResult> func, TArg2 arg2)
{
return func(arg1, arg2);
}
public static void Contain<T>(IEnumerable<T> items, T item)
{
Assert.Contains(item, items);
}
And to use it would look something like this:
Enumerable.Range(1, 10).Should(Contain, 3);
But, I'm not necessarily a fan of that style of syntax. C# isn't quite a functional language which allows me to do such clever things with operators. I don't think it will ever gain that level of expresiveness required.
Instead, I created two functions that could be chained together such as the should function and the be function. This allows me to create some of the examples above. Let's take a look at each function:
let should f actual =
f actual
let be (f : 'a -> unit) actual =
f actual
So, that will allow me to express such things as:
true |> should be True
And the true function might look something like this:
let True condition =
Assert.True(condition)
As you can see, there isn't much to this, and covers most of the assertion scenarios that I've encountered.
Where To Go From Here?
So, where am I headed with this? For right now, I'm happy with the assertion syntax I've been able to achieve with the language. For the future, I'm looking at creating a more expressive way for doing BDD and the expresiveness of F# I think can handle such things. I've been following the Specs project for a little bit and I think they have a few good things going for them, although Scala isn't a functional language in the way that F# is, so I'm not sure how many lessons can be applied. Specter is another interesting one as well as Machine Specifications (MSpec) from the one and only Aaron Jensen.
I'd like to thank the F# team, Dustin Campbell and Harry Pierson (DevHawk) for their help on this as well. The team around F# is a wonderful team and I can't wait for the CTP of F# to ship. Makes me excited sometimes when working for Microsoft like I do.
But, in the mean time, feedback is appreciated. Tell me what works and what doesn't.
- Clarity of intent - allows you to perform various operations on the data in a forward chaining way such as:
-
Concurrency in .NET - Learning from Erlang
I'm finally getting back to my concurrency in .NET posts after a brief hiatus after I got sidetracked on various other functional programming issues such as some language oriented programming and functional C#. In the previous post, I talked about MPI in .NET and I need to get back to that one and address some of the issues raised in the next post in this series. But, in the mean time, let's focus on another area of concurrency through message passing. This time, let's bring Erlang into the picture.
Learning Erlang
For some of the upcoming talks about F# and functional programming I have planned, I will be putting a lot of the focus on concurrency programming through asynchronous and parallel mechanisms. F# is not only a well established functional programming language, but its libraries also lend well to concurrency oriented programming.
But, with these adventures, I've always wanted to reach outside my comfort zone and learn from a language that had concurrency in mind from the start. That made me turn my attention to Erlang. Some of my motivations came from not only learning a new language, which is always nice, but also to learn some of the concurrency and messaging patterns so that I can apply that to F#.
In my learnings, I've compiled a list of resources that can help you learn Erlang. This includes books, podcasts and screencasts that you might find helpful for a good deep dive into the language.
Podcasts
- Joe Armstrong - Software Engineering Radio Episode 89
Joe discusses the history of Erlang, the architecture, and why it is relevant today
- Programming Erlang: Software for a Concurrent World - Joe Armstrong
A book from the Pragmatic Programmer Series which is a comprehensive overview of the Erlang language which covers sequential, concurrent and distributed programming.
- Erlang by Example - Pragmatic Programmer Series
Kevin Smith leads a series of screencasts which cover creating a chat server using Erlang. So far there are some episodes posted on the following topics:- Sending and Receiving Chat Messages
- Messaging Clients by Nickname
- Distributing Clients in a Multi-node Environment
- Adding Store and Forward Capabilities
- Venkat Subramaniam on Functional Programming in Erlang - DNRTV
Venkat introduces the concepts of functional programming through the use of Erlang
Erlang Style Message Passing in F#
To bring this back to F# for just a moment, we can apply some of the lessons learned from Erlang to F#. Today we'll look at a simple kind of message processing called mailbox processing. This pattern is popular in the Erlang language and has been applied to F#. The mailbox is a message queue that you can scan for relevant messages to your message processing agents. The MailboxProcessor class controls this action and is defined in the Microsoft.FSharp.Control.Mailboxes namespace.
This will be a simple example of how to send and receive messages using a single mailbox processor. We can define a message type that will encompass our data. This usually comprises of a receive, a send, and a stop. But, the great thing is that it's not limited to that. We'll use async workflows (yet another post I need to do) to process the message itself, hence why you see the return! statements in there.
#light
open Microsoft.FSharp.Control.CommonExtensions
open Microsoft.FSharp.Control.Mailboxes
type Message = Phrase of string | Fetch of IChannel<string> | Stop
type MessageAgent() =
let agent = MailboxProcessor.Start(fun inbox ->
let rec loop (phrase : string) =
async {
let! msg = inbox.Receive()
match msg with
| Phrase item ->
return! loop(item)
| Stop ->
return ()
| Fetch replyChannel ->
do replyChannel.Post(phrase)
return! loop(phrase)
}
loop(string.Empty)
)
member x.Send(s) = agent.Post(Phrase(s))
member x.Stop() = agent.Post(Stop)
member x.Fetch() = agent.PostAndReply(fun replyChannel -> Fetch(replyChannel))
What I'm also doing is defining handling logic for each message type, the stop, the fetch and the receiving of a phrase. If it's a stop message, we return immediately, else if it's a phrase, we'll go ahead and loop on the given item, and once we're ready to fetch it, then we'll go ahead and post it. After that, I'll go ahead and expose three methods which will allow external access to sending and receiving messages, as well as stopping.
Now, that I have done the basic plumbing for handling messaging like this, then we can go ahead and start sending messages to it and receiving.
let agent = new MessageAgent()
agent.Send("Hello world!")
let result1 = agent.Fetch()
printfn "Message result1: %s" result1
agent.Send("Hello world again!")
let result2 = agent.Fetch()
printfn "Message result2: %s" result2
This is a pretty naive example and just to show the basics of how it could be used. I'm not going to pretend it's anywhere near as powerful as the Erlang message passing libraries, but it's a pretty good start.
Robert Pickering has a pretty good example of Erlang style message passing here. F# also comes with a sample using the MailboxProcessor for a program called ConcurrentLife which is located in the Samples directory of your F# installation.
Retlang
But, what about those in the C# world? Is there a solution? An interesting piece that came up during the look into concurrency in .NET led me back to Retlang, which is a takeoff on Erlang by the author Mike Rettig. I had looked at this previously when Ayende did a brief look back in November here. The framework itself borrows a few ideas from Scala in terms of the event-based actors. Let's take a look at a quick example of sending and receiving messages on it.
static void Main(string[] args)
{
IProcessContextFactory factory = new ProcessContextFactory();
factory.Start();
IProcessContext publisher = factory.CreateAndStart();
IProcessContext consumer = factory.Create();
consumer.Subscribe<int>(new TopicEquals("retlang"), (header, id) => Console.WriteLine(id));
consumer.Start();
for (int i = 0; i < 25; i++)
publisher.Publish("retlang", i);
publisher.Stop();
publisher.Join();
consumer.Stop();
consumer.Join();
factory.Stop();
}
Looks to be a well designed architecture and I'll continue to look at this a bit further. In the mean time, check out Mike's blog for more information.
Wrapping It Up
I hope this brief introduction will get you excited about looking at other functional programming languages and what they can do for you. If not to learn them and apply them in your daily work, but to understand the concepts behind them is rather powerful and should be part of your learning plan anyhow. These above examples of implementations in other languages should help you along.
But, what do I think of Erlang overall? It's too early to tell. Even though the language has been around for a while, it has seen a recent resurgance. With the Pragmatic Programmers throwing their weight behind the language, who's to say? But I think it'd take a bit to push this as yet another language with a virtual machine into the mix over say the JVM, CLR, and so on. Instead, maybe we'll see an implementation on top of .NET, or just applying the lessons learned from it such as we've seen in F#. It was funny to listen to Joe Armstrong think pretty much the same thing as maybe the language won't take off, but the ideas can and ultimately will.
- Joe Armstrong - Software Engineering Radio Episode 89
-
Functional C# - Learn from F# and LINQ
In the last installment of Functional C#, I covered a bit about creating delayed evaluation lists based upon unfolding constructs and generating lists from external resources. Those are some of the higher level high order functions you can do in C#, but let's look at a few more, plus those that are already available to us in .NET 3.5. We'll take samples from F# and show that some of them already exist in the base class libraries and you can use them today without having to reinvent any wheels.
Iterators
One of the most simple operations in functional programming is just the simple iterator. In F#, we have two ways of iterating through any given list or sequence, by index or through the enumerator. Below are simple examples in F# doing just that:
[1..10] |> List.iteri(fun i j -> printfn "%d - %d" i j) // By index
[1..10] |> List.iter(fun i -> printfn "%d" i) // By enumerator
If we inspect the List<T> class and the Array class, we'd find that we have methods that does the enumerating by using the enumerator that looks like this:
List<T>:
void ForEach<T>(Action<T> action);
Array:
static void ForEach<T>(T[] array, Action<T> action);
So, that I could iterate a list much like this:
Enumerable.Range(1, 10).ToList().ForEach(Console.WriteLine);
One thing I thought was critically missing from the IEnumerable<T> class was the ForEach or Iterate as the F#'er in me would say. Implementing one is pretty simple using the C# 3.0 techniques:
public static void ForEach<T>(this IEnumerable<T> items, Action<T> action)
{
if (items == null)
throw new ArgumentNullException("items");
if (action == null)
throw new ArgumentNullException("action");
foreach (var item in items)
action(item);
}
But, what about by index? IEnumerable<T> has no such concept of this, so it doesn't really do us any good to try. But, it works very nicely with IList<T> or System.Array. Let's do both just for grins.
public static void IterateIndex<T>(this T[] items, Action<int, T> action)
{
if (items == null)
throw new ArgumentNullException("items");
if (action == null)
throw new ArgumentNullException("action");
int lower = items.GetLowerBound(0);
int upper = items.GetUpperBound(0);
for (int idx = lower; idx < upper; idx++)
action(idx, items[idx]);
}
public static void IterateIndex<T>(this IList<T> items, Action<int, T> action)
{
if (items == null)
throw new ArgumentNullException("items");
if (action == null)
throw new ArgumentNullException("action");
for (int idx = 0; idx < items.Count; idx++)
action(idx, items[idx]);
}
And then we can do a simple iteration this way:
Enumerable.Range(1, 10).ToArray().IterateIndex((i, j) => Console.WriteLine("{0}-{1}", i, j));
Like I said, nothing too complex here. But, let's get more advanced, shall we?
Folding
In the functional programming world, the fold, also known as reduce and accumulate, is a family of high order functions that process a data structure in a given order and build up a return value. The data structure processed in this type of function is usually a list of some sort. They are pretty powerful which help you avoid a lot of looping and recursion in your code. These functions are in direct contrast to the unfold function that I talked about last time which took a function to generate a list.
In the F# world, we have a couple of ways about thinking about folds, we have support for both left and right folds. The Seq.fold function is applied from a left to right fashion as is the List.fold_left function. The List.fold_right function is the inverse which applies from the right to left. The Seq does not have this as it is a forward only evaluated collection much like IEnumerable<T>.
Some basic examples in F# would look like this:
[1..10] |> Seq.fold(fun acc x -> acc + x) 1
[1..10] |> List.fold_left (fun acc x -> acc + x) 1
Or using simple operator function such as sum would look like this:
[1..10] |> Seq.fold (+) 1
Where the basic structure is:
val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a list -> 'b
The fold right example would look something like this:
List.fold_right max [3; 5; 7; 9; 1; 2;] System.Int32.MinValue
Where we'd want to get the maximum value from our given list, and the Int32.MinValue is our accumulator.
Where the basic structure is:
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
So, how would we implement this in C#? Let's do a simple implementation of fold (or fold_left) in C#. It's a rather easy implementation. Let's first do one for IEnumerable<T> and then for IList<T>:
public static T Fold<T, U>(this IEnumerable<U> list, Func<T, U, T> func, T acc)
{
foreach(var item in list)
acc = func(acc, item);
return acc;
}
Enumerable.Range(1, 10).Fold((acc, x) => acc + x, 1);
And now for the IList<T> would look something like this:
public static T FoldLeft<T, U>(this IList<U> list, Func<T, U, T> func, T acc)
{
for (int index = 0; index < list.Count; index++)
acc = func(acc, list[index]);
return acc;
}
new List<int> { 1, 2, 3, 4, 5 }.FoldLeft((acc, x) => acc + x, 1);
Seems simple enough where we keep executing the function with the accumulator and the current item in the collection until we are complete. The same implementation can also be said for the FoldRight function which does the reverse of
public static T FoldRight<T, U>(this IList<U> list, Func<T, U, T> func, T acc)
{
for (int index = list.Count - 1; index >= 0; index--)
acc = func(acc, list[index]);
return acc;
}
int foldRight = new List<int> { 5,9,1,3,4,3 }.FoldRight((acc, x) => Math.Max(acc, x), int.MinValue);
Where the answer would be 9 as the maximum number.
But, wait! Don't we already have these things in .NET 3.5? With LINQ, the answer is yes, well, partly. Let's look at the Enumerable.Aggregate function:
public static TAccumulate Aggregate<TSource, TAccumulate>(
this IEnumerable<TSource> source,
TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> func)
And an implementation might look like this:
Enumerable.Range(1, 10).Aggregate(1, (acc, x) => acc + x);
So, as you can see, it solves the Fold and FoldLeft operations, but does not cover the case of FoldRight, unless I were to somehow use the Reverse extension method also available on Enumerable class. But of course that could be bad if my collection were infinite...
Filtering
Another idea from F# is the filter function. This gives us the ability to filter a given collection by the criteria given. The function looks like this:
val filter : ('a -> bool) -> 'a list -> 'a list
And a simple implementation would look like this:
let mod3List = [1..100] |> List.filter(fun x -> x % 3 = 0)
But, how would we do something similar. Let's mock something up in C# using extension methods.
public static IEnumerable<T> Filter<T>(this IEnumerable<T> source, Predicate<T> func)
{
foreach (var item in source)
{
if(func(item))
yield return item;
}
}
Enumerable.Range(1, 100).Filter(x => x % 3 == 0);
That's great, but... we already have that in .NET 3.5 once again through LINQ, so no need to reinvent the wheel here either. Instead, let's look at the Enumerable.Where method:
public static IEnumerable<TSource> Where<TSource>(
this IEnumerable<TSource> source,
Func<TSource, bool> predicate)
And then I can write my function as follows:
Enumerable.Range(1, 100).Where(x => x % 3 == 0);
So, once again, the core libraries have a lot of the functional programming things in mind already that we can take advantage of. Let's look at one final one for this installment.
Mapping
The map function in functional programming is to take a function and apply it to each item in the collection. The function will look like this:
val map : ('a -> 'b) -> 'a list -> 'b list
let cubeList = [1..100] |> List.map(fun x -> x * x * x)
Now, let's prototype how this might look in the C# world to implement something like this:
public static IEnumerable<TResult> Map<T, TResult>(this IEnumerable<T> source, Func<T, TResult> func)
{
foreach (var item in source)
yield return func(item);
}
var cubes = Enumerable.Range(1, 100).Map(x => x * x * x);
But once again, .NET 3.5 and LINQ already solved this problem as well. The Enumerable.Select method already implements this very logic:
public static IEnumerable<TResult> Select<TSource, TResult>(
this IEnumerable<TSource> source,
Func<TSource, TResult> selector)
This allows me to rewrite my function so that it looks like this:
var cubes = Enumerable.Range(1, 100).Select(x => x * x * x);
Wrapping It Up
As I gave examples above, many of the functional programming functions that are a given in the FP world have already been implemented in .NET 3.5, albeit under different names. Once again, I'll emphasize that C# is an "ok" language to understand functional programming aspects and let's you get over one hop of the programming style without having to learn the new language. But, to get the full breadth of what functional programming can do for you in terms of pattern matching, type inference, generic functions, immutability and so on, F# is the real option in the .NET world.
-
Functional C# - Unfolding Lists
In a previous post, I talked about how I thought C# has some significant drawbacks from being considered a more functional language. But, that wasn't to exclude it as a language altogether, as it has some pretty useful features. Lately, when I have been talking about F# in my sessions, many people wonder why use F# and not just use the functional aspects of C#. They figure that sooner rather than later, C# will have most of those features anyways. That may be true to some extent, but C# will never be as expressive, nor flexible as F# as a functional language or for doing language oriented programming. My thinking is that C# should remain the mainstream OOP and slightly FP language that it is without trying to do too much at once such as becoming fully dynamic or fully functional.
But, that's not to stop us from having fun with trying to implement some of the features of the F# libraries in C#. In fact, that helps you gain the understanding of what it may be doing underneath the covers. I find it's easier sometimes to teach the fundamentals of functional programming through the use of C# for those in the imperative and OO mindset. Today, let's walk through a few samples of creating lists through functional programming techniques. But first, a correction.
Corrected on Currying
As I mentioned before, currying is the simple act of reducing a function with multiple arguments into a single argument high order function. I posted the typical example using the Func, but wasn't quite right on the Action one. My thanks to Alexey Romanov for pointing this out.
public static Func<TArg1, Action<TArg2>> Curry<TArg1, TArg2>(this Action<TArg1, TArg2> action)
{
return x1 => x2 => action(x1, x2);
}
Now with both of these currying becomes a bit more natural so that now I can do the following:
Action<IEnumerable<int>, int> contains = (x, y) => x.ShouldContain(y);
var curriedContains = contains.Curry();
var containedBy30 = curriedContains(Enumerable.Range(1, 30));
containedBy30(3);
Still, it's not as natural as I'd like it to be in terms of having to specifically mark is as a curried function instead of it being more natural.
Generating Lists Through Unfolding
This is probably one of the more difficult functions to understand. The goal of the unfold function is to create a delayed evaluation list. What we want is the ability to have a function evaluated repeatedly so that we can generate the items in our list. This evaluation function must return an option type (Option<A>) that can be either Some(x) or None as well as the need for tuples (Tuple<TArg1, TArg2>). But, in C#, we don't have those features. After consulting Dustin Campbell, I noticed that he already has done a bit of legwork in post his post "Apples and Oranges" to compare the performance of a C# and F# solution to a Project Euler problem. Let's look at a sample F# unfolding sample of creating an infinite Fibonacci sequence and then we'll look at how to implement in C#.
let fibs = Seq.unfold (fun (i,j) -> Some(i,(j,i+j))) (1,1)
What we obviously need are the Option<T> and Tuple<TArg1, TArg2> type which Dustin has provided in the download link for the post. I modified mine slightly to follow F# naming conventions for the Tuple to have Item1, Item2 and so on. Now, let's look at the actual implementation of the Unfold function. This function will start with the start value and then calculate the next value from the generator, yield the first item and reset the next item. This will keep on evaluating until the option type returns None which is equivalent to null in the imperative world.
public static IEnumerable<TResult> Unfold<T, TResult>(Func<T, Option<Tuple<TResult, T>>> generator, T start)
{
var next = start;
while (true)
{
var res = generator(next);
if (res.IsNone)
yield break;
yield return res.Value.Item1;
next = res.Value.Item2;
}
}
Now we can define the actual implementation. Let's go ahead and create that implementation using the Unfold function. As you can see, we're pretty much mirroring the F# code snippet word for word. As you may notice, the C# is a bit more verbose because it requires us to physically declare tuples.
var fibs= Unfold(x => Option.Some(Tuple.New(x.Item1, Tuple.New(x.Item2, x.Item1 + x.Item2))), Tuple.New(1, 1));
var first20 = results.Take(20);
Of course I could have done this without the Unfold function and just had a property with an infinite sequence, but I like this solution because it's quite nice and generic. Something like this though could have sufficed:
public static IEnumerable<long> Fibonacci
{
get
{
long i = 1;
long j = 1;
while (true)
{
yield return i;
long temp = i;
i = j;
j = j + temp;
}
}
}
But, then that leaves off the implementing the following section in a nice generic fashion.
Initializing Lists
Now that we understand the unfolding function, we can apply it to any number of operations. How about if we want to initialize a delayed infinite or finite list? We can reuse the logic from the Unfold to make this happen. First, let's look at some F# samples of how we might want to do this:
let allCubes = Seq.init_infinite (fun x -> x * x)
let tenCubes = Seq.init_finite 10 (fun x -> x * x)
The first example, I created a list of all cubes possible, and the second, I created a list of just the first 10. You must create a function which passes in the current iteration, and then you can use it to calculate your return value. Ok, so, how would we do this in C#? Well, let's just first put up the infinite list because it's easier to implement.
public static IEnumerable<T> InitializeInfinite<T>(Func<int, T> f)
{
return Unfold<int, T>(s => Option.Some(Tuple.New(f(s), s + 1)), 0);
}
What I'm doing is return an option type with a tuple of the current value and the next value. Then I seed the function with the starting value of 0. My function that I create is passing in the current index, so that I can increment it. That's pretty easy, but how about limiting it to an exact number of items to take?
public static IEnumerable<T> InitializeFinite<T>(int count, Func<int, T> f)
{
return Unfold<int, T>(s =>
{
if(s < count)
return Option.Some(Tuple.New(f(s), s + 1));
else
return Option<Tuple<T, int>>.None;
}, 0);
}
Now, what I've done is made sure that my index is less than the count specified and then return the next value, or else I return none. With this in place, I can then create the exact duplicates from F# from above:
var allCubes = InitializeInfinite(x => x * x);
var tenCubes = InitializeFinite(10, x => x * x);
Generating Lists
So, in the previous example, we have a way to create a nice list through an initialize function. But what if we want to create a list from some sort of cursor? This cursor could be anything from a stream, to a reader, etc. In F#, we have the generate and generate_using functions which allow us to specify the opening cursor function, the actual computation and then a closing cursor function. Let's look at a quick sample:
let htmlList = Seq.generate (fun () ->
File.OpenText(@"D:\Tools\Reflector\ReadMe.htm")) (fun x ->
if x.EndOfStream then None else Some(x.ReadLine())) (fun x ->
x.Close())
Here I am generating a list of text from a text file, while specifying the opening, calculating of the list, and then the closing. But, since my reader that I'm using supports IDisposable, let's go ahead and use the generate_using, which was created for just that.
let htmlList = Seq.generate_using (fun () ->
File.OpenText(@"D:\Tools\Reflector\ReadMe.htm")) (fun x ->
if x.EndOfStream then None else Some(x.ReadLine()))
There! A bit better. But, how do we do this in C#? Well, let's go ahead and use the Option type that we took from above. From there, we can pretty much go line for line with the F# version. What we want to do is continue executing until we get a None return value and at that point, clean up and then exit.
public static IEnumerable<TResult> Generate<T, TResult>(Func<T> opener, Func<T, Option<TResult>> generator, Action<T> closer)
{
T openerResult = opener();
while (true)
{
var res = generator(openerResult);
if (res.IsNone)
{
closer(openerResult);
yield break;
}
yield return res.Value;
}
}
Now that we have that defined, we can create the GenerateUsing function in much the same way by calling Generate and passing in a function that disposes of the resource.
public static IEnumerable<TResult> GenerateUsing<T, TResult>(Func<T> opener, Func<T, Option<TResult>> generator) where T : IDisposable
{
return Generate(opener, generator, x => x.Dispose());
}
Now, I have the ability to read in files nicely into my lists just by doing this with both the regular generate and generate_using:
var generatedResults = Generate(() => File.OpenText(@"D:\Tools\Reflector\ReadMe.htm"), x =>
{
if (x.EndOfStream)
return Option<string>.None;
else
return Option.Some(x.ReadLine());
}, x => x.Dispose());
generatedResults.ForEach(Console.WriteLine);
var generatedUsingResults = GenerateUsing(() => File.OpenText(@"D:\Tools\Reflector\ReadMe.htm"), x =>
{
if (x.EndOfStream)
return Option<string>.None;
else
return Option.Some(x.ReadLine());
});
generatedUsingResults.ForEach(Console.WriteLine);
The GenerateUsing function is a bit cleaner if we can help it, so that we don't have to worry about a function that closes the resource and instead, we could make a better assumption about the type and close it ourselves generically.
Wrapping It Up
As you can see, you can implement plenty using C# and its current constructs, especially in regards to creating lists. Is it the better approach over F#? No, but it will get you most of the way there as I have shown here with the addition of some more types which include the Tuple<TArg1, TArg2> and the Option<T> type.
The more important thing for you to remember is the bare concepts that this post covered. There are plenty more to learn in terms of recursion (tail, mutual, etc), folding and so on. But, ultimately, I need to get back and focused on my concurrency in F# posts, unless there is a big demand for more of these functional C# samples.
-
ICFP Programming Contest
With great excitement, Portland State University and the University of Chicago has announced the 11th annual International Conference on Functional Programming (ICFP) Programming Contest to be held from July 11th to July 14th, 2008. If you're not familiar with the contest, it is one of the most advanced and prestigious programming contests. It is a good chance to show off your programming skills, your favorite languages and tools, and your ability to work as a team as you tackle these hard problems. What's great about this is that you can have a team consisting of one or more people, from any part of the world, and with any programming language you so choose. The contest will begin at noon (PDT) on July 11th and all entries must be received by the organizers by July 14th at noon (PDT).
To me, this is a much more interesting than the International Obfuscated C Contest because we're actually trying to solve a problem, let alone in any language we so choose.
Years Past
In years past, there have been some pretty interesting contests. Last year's contest was an interesting one to help find a DNA prefix to help an alien, who was dropped onto Earth from an interstellar garbage collector, survive with the new climate. And the year before that was to analyze an ancient codex and universal machine. The list of previous contests can be found at the contest site.
This time around, it'd be great to see a few teams submit with F#!
-
DC ALT.NET Meeting - 6/24/2008 - Applied Functional Programming with F#
The June meeting for DC ALT.NET has been set up for June 24th from 7-9PM. Check out our site and our mailing list as more information becomes available. Once again, I'd like to thank the Motley Fool for hosting the event as they did back in May. This month, I'll be covering Applied Functional Programming with F# as a continuation of the talks I've been giving lately. The beauty of this group like last month's topic of Lisp and this month's topic of F# is to step outside of the comfort zone, look to the outside for better approaches to doing things instead of the "What's new on MSDN" sessions.
The information is as follows:
Location:
Motley Fool
2000 Duke Street
Alexandria, VA, 22314
Map Link
Applied Functional Programming with F#
Recently, I've been doing quite a few talks on the introduction to functional programming and F#. In this session, I hope to cover the basics in short order once again, but also to show the applicability of where this language really hits the right areas. Are we going to immediately flock towards F# and abandon C# and other languages for all of your coding needs? No, but we have definite areas where F# and functional programming excels. Some of these include asynchronous programming, parallel programming, metaprogramming, language oriented programming, messaging systems and so on. The list could go on and on. We'll explore some of the functional programming basics and some of these scenarios as we try to wrap our heads around this emerging, yet not new paradigm.
Be there and hope to see a great crowd!
-
Functional C# Revisited - Into the Great Void
Lately, I've been doing some functional C# in both user groups and on this blog. As the C# language has evolved it has definitely taken some functional programming aspects, such as high order functions, extension methods, LINQ and so on. But with that, there is a cost. Functional programming with C# tends to be verbose due to a number of things which include the lack of type inference on methods, void as not a first class citizen and so on. I'm going to explore a couple of those today in this post.
Into the Great Void
I conversed with Jimmy Bogard last week regarding some limitations I saw in the C# language and how F# is better suited to handling this issue. One thing that has frustrated me is the fact that the System.Void structure is not treated as a first class citizen, in that I cannot do the following:
Func<int, int, Void> equals = (x, y) => Assert.Equal(x, y);
I get the following error if I even try to do this:
System.Void cannot be used from C# -- use typeof(void) to get the void type object
And why is that exactly? The ECMA Standard 335, Partition II, Section 9.4 "Instantiating generic types" states:
The following kinds of type cannot be used as arguments in instantiations (of generic types or methods):
- Byref types (e.g., System.Generic.Collection.List`1<string&> is invalid)
- Value types that contain fields that can point into the CIL evaluation stack (e.g.,List<System.RuntimeArgumentHandle>)
- void (e.g., List<System.Void> is invalid)
let should f actual = f actual
let not_throw_exception actual =
Assert.DoesNotThrow(Assert.ThrowsDelegate(actual))
which compiles down to:
public static U should<T, U>(FastFunc<T, U> f, T actual)
public static void not_throw_exception(FastFunc<Unit, Unit> actual)
What this allows me to do is pass in a function that will return nothing, and yet, if I passed in a FastFunc<int, int> that would work too with the should function. Both of them are treated the same, yet not in C#. Instead, we are forced to differentiate
Func versus Action?
As we're forced to differentiate our functions, it makes it hard to generalize functional programming in C#. I feel at this point, C# can't be a first class functional language because we need to make this distinction. If we don't return a value, we must use the Action<T> whereas if we do return a value, we must use Func<TArg, TResult>. Let's look at some samples where we have to differentiate.
Let's first look at the forward operator function in C#. This is one we looked at last time:
F# example
let (|>) x f = f x
[1..10] |> List.map(fun x -> x * x)
C# version
public static TResult ForwardFunc<TArg1, TResult>(this TArg1 arg1, Func<TArg1, TResult> func)
{
return func(arg1);
}
- And -
public static TResult ForwardFunc<TArg1, TArg2, TResult>(this TArg1 arg1, Func<TArg1, TArg2, TResult> func, TArg2 arg2)
{
return func(arg1, arg2);
}
This allows me to do the following code:
var mapResult = Enumerable.Range(1, 10).ForwardFunc(x => x.Map(i => i * i));
var mulResult = 3.ForwardFunc((x, y) => x * y, 3);
Whereas if my methods returned void, I'd also have to create functions to match that as well, such as:
public static void ForwardAction<TArg1>(this TArg1 arg1, Action<TArg1> func)
{
func(arg1);
}
- And -
public static void ForwardAction<TArg1, TArg2>(this TArg1 arg1, Action<TArg1, TArg2> func, TArg2 arg2)
{
func(arg1, arg2);
}
And then I can accomplish this code:
true.ForwardAction(x => x.ShouldBeTrue());
Enumerable.Range(1, 10).ForwardAction((x, y) => x.ShouldNotContain(y), 3);
These of course are simplistic examples, and it just shows that you have to think a little bit about whether you return something or not. Not something you have to necessarily think about in F# or other functional languages. Currying is also pretty difficult using the Action delegate as well. It's not really a usable thing at this point. Feel free to correct me, however...
How could you curry an Action given that you curry any normal function such as this?
public static Func<TArg1, Func<TArg2, TResult>> Curry<TArg1, TArg2, TResult>(this Func<TArg1, TArg2, TResult> f)
{
return a1 => a2 => f(a1, a2);
}
Maybe something like this?
public static Action<TArg2> Curry<TArg1, TArg2>(this Action<TArg1, TArg2> func, TArg1 arg1)
{
return a2 => func(arg1, a2);
}
But of course this function can't scale as you add more parameters to this. So, this isn't really an ideal situation. Unless I'm missing something blindingly obvious.
Wrapping It Up
With these given limitations of the void type, lack of type inference on method signatures, etc, it's hard to take C# seriously as a full citizen in the functional programming sense. I think it's a rather large weakness to me. Instead, I think we should focus on languages which already make these semantics easy, such as Haskell, F# and so on for when you need functional programming. Sure, C# can support a lot of functional programming paradigms, but it doesn't quite feel natural.
-
RubyNation - August 1st-2nd
One of the interesting things happening in the Ruby community is the budding of regional Ruby conferences. The Washington DC area is a pretty strong area for Ruby and Ruby on Rails as we have two Ruby user groups, Northern Virginia Ruby Users Group (NovaRUG) and the DC Ruby User Group (DCRUG). With that, it was due time that DC got its own conference called RubyNation which will be held August 1st-2nd, 2008 in Herndon, Virginia. What's great about this conference is that they are just trying to cover expenses and doing it for the love of the technology.
They have a fantastic lineup of speakers which include:
- Neal Ford - Keynote
The debate between static and dynamic languages is a red herring, that the debate should be about Essence vs. Ceremony. Neal's keynote will illustrate the origins of these concepts, what they mean to modern software development, and why everyone is suddenly interested in dynamic languages like Ruby.
- Stuart Halloway - Closing Keynote
- David Bock - Tools for your Ruby Toolbox
Rails may be the framework that turned many of us on to Ruby, but if you are using it for all of your server-related Ruby projects, you probably have a hammer and are seeing every problem as a nail. There are a number of smaller, tighter solutions to problem in this space, including GServer (built into the Ruby libraries), StaticMatic (a tool for generating a static site, but with all the templating goodness), and Sinatra, a small server with an awesome DSL for restful web services. We will spend a little bit of time of each of these, seeing how you can use each for a project where you might have previously considered Rails.
- Giles Bowkett - Archaeopteryx: A Ruby MIDI Generator
Archaeopteryx generates MIDI via Ruby to drive prosumer studio music software. It can generate hyperkinetic DJ mixes, infinite streams of ambient music for meditation, and original drum and bass rhythms.
- Yehuda Katz - Living on the Edge
Yehuda will walk you through some of the most exciting advances on the frontiers of Ruby, and provide a tour guide to those who want to walk the dangerous path. By the time the talk is over, you should feel comfortable downloading a bleeding-edge git-repository and installing it.
- Glenn Vanderburg - The Culture of Innovation in Ruby
The Ruby community is a wellspring of innovation at the moment; many people are doing fascinating new things with tools, libraries, and exploring new ways to use the language. This talk will explore some of the reasons for that innovative culture, and discuss ways we can benefit from it and keep it healthy.
The event will be held at the Center for Innovative Technology (CIT) in Herndon, VA. If you're familiar with the area, you'll notice it is the upside down oddly shaped building. As you travel along Rt 28 or the Dulles Toll Road, you can't miss this building.
The address for the conference is:
CIT Complex
2214 Rock Hill Road
Herndon, Virginia 20170
Register today here! Looking forward to this event.
- Neal Ford - Keynote
-
Language Oriented Programming and Functional Unit Testing in F#
As I've covered earlier, I'm very interested in the unit testing and behavior testing story in F# and functional programming. And as I've indicated earlier, I'm pretty fascinated by Domain Specific Languages (DSLs) as well in this regard. In the past, I've posted about some of the interesting things that are coming from the DSL community, especially from the .NET community itself. I wanted to challenge myself to prove that F# can also produce very readable and powerful DSLs as well. I think with the language flexibility that F# offers, I should be able to get quite expressive
Starting with DSLs
In part of what has me fascinated by DSLs lately is the recent book activity from both Martin Fowler and Ayende. Martin has been posting his Domain Specific Languages Work In Progress and keeping us somewhat up to date on its progress. So far I've been rather impressed with the book and I hope it continues. Although I think fluent builders are nice, I don't think they sometimes have the expressiveness of DSLs that I'm looking for. Many of the samples are written in both Java and C#, and it gives you a pretty good idea where he's going. However, I don't find the intent to be as clear though as DSLs written in Ruby, Boo or F#.
Ayende on the other hand has been working on his books "DSLs in Boo" that is partially available online right now. It's been interesting to see how flexible the language is in regards to DSLs and seeing it twist in new ways is pretty interesting. The first chaper is available for free, so you can check it out for yourself.
But with this, I was seeing such opportunities when I've been experimenting with language oriented programmiing and F#. Where are there opportunities?
Language Oriented Programming and FsUnit
I recently came across a dormant project on Google Code called FsUnit, which was a syntactic extension to NUnit using the F# language semantics. This to me looked like a great example of language oriented programming with F# and some of its uses. There isn't much to this library, yet very powerful. Let's take a look at a few samples:
1 |> should (equal 1)
"two" |> should (notEqual "three")
[| 1 .. 10 |] |> should (contain 5)
What makes this possible and pretty easy to understand? That would be the use of the forward operator. I've covered this operator in the past, but I can't emphasize its importance in this regard. If you're not familiar with that post, let's go over the basics. The basic definition of this operator is that it's just function application in reverse.
The forward operator has a basic definition that looks like this:
let (|>) x f = f x
What this allows us to do is put the first argument last. Let's take a quick example of just a simple forward operator:
let newList = [1..10] |> List.map(fun x -> x + x)
What it essentially becomes is the following code:
let newList = List.map(fun x -> x + x ) [1..10]
This gives us a couple of advantages doing this which includes:
- Intent Clarity - Allows you to perform data transformations, iterations, filtering, etc in a forward chaining fashion
- Type Inference - Since we're chaining together methods, we can better type infer when we specify the data first to the functions that will flow across all of them.
Just as an aside, Chris Smith, of the F# team, follows up from his recent presentation on Language Oriented Programming with F#. It's well worth the time invested to look at the possibilities that F# as a language offers. I am also hoping to do some presentations on this in the future as there is a lot of ground to cover with this language.
Replicating with C#?
During some of my recent talks on functional programming and F#, I have come across some resistance to the language itself because many saw that they can replicate a lot of the behaviors in C# 3.0. Indeed that is the case with many things, but not so much with where I'm going. One of my many gripes with C# and in turn the BCL is the fact that they don't treat Void (or Unit to those F#'ers) as a first class citizen. Therefore, I'm stuck with either using a Func<TArg, TResult> delegate or the Action<T> delegate for many operations and never the two shall combine. Whereas in F#, I'm free to create FastFunc<TArg, TResult> delegates with a Unit return type which returns nothing. It's a thing of beauty and I didn't have to mangle my code to get there.
So, with that in mind, let's see if we can replicate the forward operator in C# to the extent that I did in F#. The concept isn't really hard at all when you think about it. We're just calling a function with the arguments reversed. Let's create one with an actual return type, because remember, we're forced into the paradigm of either returning something or not with C# and we must use different delegates for it.
public static TResult ForwardFunc<TArg1, TArg2, TResult>(this TArg1 arg1, Func<TArg1, TArg2, TResult> func, TArg2 arg2)
{
return func(arg1, arg2);
}
var result = 4.ForwardFunc((x, y) => x * y, 3);
What I've been able to do is not as clean as F#, but a little interesting. What I'm doing is taking the first argument, then a function to process it, and then finally pass in my second argument. Below that function is a quick and dirty example of how to use it. But what about those times I don't want to return a value? Well, we have an answer for that as well:
public static void ForwardAction<TArg1, TArg2>(this TArg1 arg1, Action<TArg1, TArg2> func, TArg2 arg2)
{
func(arg1, arg2);
}
Enumerable.Range(1, 10).ForwardAction((x, y) => x.ShouldContain(y), 3);
What I did is change the Func<TArg1, TArg2, TResult> to a simple Action<TArg1, TArg2> which has the same effect. From there, I was able to use the xUnit.net 3.5 extensions to show that the IEnumerable<T> contained the number 3. If you mix in currying to this equation things get interesting quickly. I hope those who attended my functional C# class got some inkling, but since then I've been exploring more aspects of it as well as lessons learned. But the overall story is that it's just not as expressive as F# and kind of clumsy.
Extending the Syntax
As you may see, there really isn't much to FsUnit. Instead, I would like to apply some of those lessons to xUnit.net instead because of allowing static tests and it better fits my needs at the moment. Instead of relying on the underlying unit testing framework to take care of a lot of the details, instead, I'm going to use functional programming aspects of currying to make my DSL look more readable.
The first piece of the puzzle that we need is the basis of getting started. Let's put down the should and a few housekeeping items:
#light
namespace FsXUnit
#R @"D:\Tools\xunit-1.0.1\xunit.dll"
module Extensions =
open Xunit
let should f actual =
f actual
What I have created is a module under the FsXUnit namespace called Extensions which will hold my methods. Then I can reference using a standard open statement such as open FsXUnit.Extensions. Then the should will be a partially applied function that will tie the functions together. Now we can start throwing our first functions at it. I'll mark each by section giving you a quick sample of each.
Equality
let equal expected actual =
Assert.Equal(expected, actual)
let not_equal expected actual =
Assert.NotEqual(expected, actual)
[<Fact>]
let equal_with_equal_values_should_be_equal() =
"foo" |> should equal "foo"
[<Fact>]
let not_equal_with_inequal_values_should_not_be_equal() =
"foo" |> should not_equal "bar"
Contains
let have expected actual =
Assert.Contains(expected, (actual :> seq<_>))
[<Fact>]
let sequence_should_have_2() =
[1..10] |> should have 2
Exception Handling
let throw_exception<'a when 'a :> exn> actual =
Assert.Throws<'a>(Assert.ThrowsDelegate(actual))
let throws_exception() : unit =
raise(System.ArgumentException "Bad things")
[<Fact>]
let function_should_throw_exception () =
throws_exception |> should (throw_exception<System.ArgumentException>)
This by no means is a complete list of things that you can do with this, but you get the idea.
Where To Go?
As I stated before, I think Scala Specs is an interesting framework for Behavior Driven Development (BDD), and with some of these techniques discussed, it could be rather possible to make a rather expressive framework. It's all about the time for tinkering at this point I suppose. But with all this tinkering I've been doing, I have to wonder to myself, whether we need another testing DSL, or should we more focus on a general purpose language that is best suited for testing, call it Test#, or Fact#, just to humor Brad Wilson... Is that where we should be headed?
