TryJoinads (IV.) - Concurrency using join calculus

Join calculus provides a declarative way of expressing asynchronous synchronization patterns. It has been use as a basis for programming languages (JoCaml and COmega), but also as a basis for libraries (embedded in C# and Scala). Using joinads, it is possible to embed join calculus in F# with a nice syntax using the match! construct. Formally, join calculus does not form a monad, but it can be viewed as a version of joinad as described in the first paper on joinads.

The programming model is based on channels and join patterns. A channel can be viewed as a thread-safe mailbox into which we can put values without blocking the caller. In some sense, this is quite similar to F# agents. A join pattern is then a rule saying that a certain combination of values in channels should trigger a specific reaction (and remove values from the channels). The ability to match on multiple channels distinguishes join calculus from F# agents.

Note: This blog post is a re-publication of a tutorial from the TryJoinads.org web page. If you read the article there, you can run the examples interactively and experiment with them: view the article on TryJoinads.

TryJoinads (III.): Agent-based programming

Another area where the match! syntax can be used is when programming with F# agents, implemented by the MailboxProcessor type. Formally, agents do not form the monad structure in a useful way - when programming with agents, we do not compose a new agents, but instead we write code that (imperatively) receives messages from the agent's mailbox and handles them.

This article demonstrates an agent { ... } computation builder that can be used for implementing the body of an agent. Normally, the body of an agent is an asynchronous workflow. The code in the body uses let! to perform asynchronous operations, most importantly to call inbox.Receive to get the next message from the inbox. When the agent intends to handle only certain kinds of messages, it can use inbox.Scan. When using the agent builder, pattern matching on messages can be written using match! and it is possible to write code that ignores certain types of messages simply by writing an incomplete pattern matching.

Note: This blog post is a re-publication of a tutorial from the TryJoinads.org web page. If you read the article there, you can run the examples interactively and experiment with them: view the article on TryJoinads.

TryJoinads (II.): Task-based parallelism

The implementation of joinad operations for the Task<'T> type is quite similar to the implementation of Async<'T>, because the two types have similar properties. They both produce at most one value (or an exception) and they both take some time to complete.

Just like for asynchronous workflows, pattern matching on multiple computations using match! gives us a parallel composition (with the two tasks running in parallel) and choice between clauses is non-deterministic, depending on which clause completes first.

Unlike asynchronous workflows, the Task<'T> type does not require any support for aliasing. A value of type Task<'T> represents a running computation that can be accessed from multiple parts of program. In this sense, the type Async<'T> is more similar to a function unit -> Task<'T> than to the type Task<'T> itself.

The key difference between tasks and asynchronous workflows is that the latter provides better support for writing non-blocking computations that involve asynchronous long-running operations such as I/O or waiting for a certain event. Tasks are more suitable for high-performance CPU-intensive computations.

Note: This blog post is a re-publication of a tutorial from the TryJoinads.org web page. If you read the article there, you can run the examples interactively and experiment with them: view the article on TryJoinads.

Introducing TryJoinads.org

(Click for a larger version)

If you have been following my blog, you've probably already heard of joinads. It is a research extension of F# computation expressions (or monads in Haskell). The extension makes computation expressions more useful in domains like parallel, concurrent and reactive programming. However, it can be used for any type of computation including, for example, parsers. If you're interested in detailed description, you can find it in two academic papers that I blogged about previously: PADL 2011 and Haskell 2011.

The extension adds a keyword match! - as the syntax suggests, it is akin to pattern matching using match, but instead of pattern matching on values, you can pattern match on computations like Async<'T> (or on other monadic values). Just like other features of computation expressions, the match! syntax is translated to applications of several methods defined by the computation builder.

I won't say more about joinads in this post, because you can now easily try joinads yourself...

Real-World F# Articles on MSDN

More than a year ago, Mike Stephens from Manning (who was also behind my Real-World Functional Programming book) asked me if I'd be interested in collaborating on a project for MSDN. The idea was to collaborate with Microsoft on creating some additional content for the official F# Documentation.

A few days ago, the new content appeared on MSDN, so I finally have an excuse for the recent lack of blogging! Although the content contains a large number of new articles that are not based on my book, you can find it in the MSDN section named after my book, right under Visual F#. If you can't wait to check it out, here are all the links:

• The Real-World Functional Programming section on MSDN.
• The source code for individual chapters is available on MSDN Code Gallery.
• I also published annotated TOC with source code links on my functional programming web site.

While working on the articles, I also wrote about a few topics that we didn't use in the final version. You'll see them on my blog in the next few days, as soon as I edit them into a blog post form. Continue reading for more information about individual chapters.

Extending Monads with Pattern Matching (Haskell 2011)

Some time ago, I wrote a paper about joinads and the match! extension of the F# language. The paper was quite practically oriented and didn't go into much details about the theory behind joinads. Many of the examples from the F# version relied on some imperative features of F#. I believe that this is useful for parctical programming, but I also wanted to show that the same idea can work in the purely functional context.

To show that joinads work in the pure setting, I created a Haskell version of the idea. The implementation (available below) is quite simple and consists of a pre-processor for Haskell source files and numerous examples. However, more important part of the recent work of joinads is a more detailed theoretical background.

The theory of joinads, together with the language design of Haskell extension that implements it is discussed in a paper Extending Monads with Pattern Matching, which was accepted for publication at the Haskell Symposium 2011. Here is the abstract of the paper:

Sequencing of effectful computations can be neatly captured using monads and elegantly written using do notation. In practice such monads often allow additional ways of composing computations, which have to be written explicitly using combinators.

We identify joinads, an abstract notion of computation that is stronger than monads and captures many such ad-hoc extensions. In particular, joinads are monads with three additional operations: one of type m a -> m b -> m (a, b) captures various forms of parallel composition, one of type m a -> m a -> m a that is inspired by choice and one of type m a -> m (m a) that captures aliasing of computations. Algebraically, the first two operations form a near-semiring with commutative multiplication.

We introduce docase notation that can be viewed as a monadic version of case. Joinad laws make it possible to prove various syntactic equivalences of programs written using docase that are analogous to equivalences about case. Examples of joinads that benefit from the notation include speculative parallelism, waiting for a combination of user interface events, but also encoding of validation rules using the intersection of parsers.

Links to the full paper, source code and additional materials are available below.

Fun with parallel monad comprehensions (The Monad.Reader)

This article is a re-publication of an article that I wrote some time ago for The Monad.Reader magazine, which is an online magazine about functional programming and Haskell. You can also read the article in the original PDF format as part of the Issue 18 (together with two other interesting articles). The samples from the article can be found on Github.

Monad comprehensions have an interesting history. They were the first syntactic extension for programming with monads. They were implemented in Haskell, but later replaced with plain list comprehensions and monadic do notation. Now, monad comprehensions are back in Haskell, more powerful than ever before!

Redesigned monad comprehensions generalize the syntax for working with lists. Quite interestingly, they also generalize syntax for zipping, grouping and ordering of lists. This article shows how to use some of the new expressive power when working with well-known monads. You'll learn what "parallel composition" means for parsers, a poor man's concurrency monad and an evaluation order monad.

• Continue reading on the web...
• Get The Monad.Reader Issue 18 (PDF)

Explicit speculative parallelism for Haskell's Par monad

Haskell provides quite a few ways for writing parallel programs, but none of them is fully automatic. The programmer has to use some annotations or library to run computations in parallel explicitly. The most recent paper (and library) for writing parallel programs follows the latter approach. You can find more information about the library in a paper by Simon Marlow et al. A monad for deterministic parallelism and it is also available on Hackage. However, I'll explain all the important bits that I'll use in this article.

The library provides an explicit way for writing parallel programs using a Par monad. The library contains constructs for spawning computations and sharing state using blocking variables. However, the whole programming model is fully deterministic. I believe that it is sometimes useful to lift the determinacy requirement. Some programs are deterministic, but the fact cannot be (easily) automatically verified. For example, say you have two functions fib1 and fib2. They both give the same result, but each of them is more efficient than the other one on certain inputs. To calculate a Fibonacci number, the program could speculatively try to evaluate both functions in parallel and return the result of the one that finishes first.

Unfortunately, this cannot be safely implemented using a fully deterministic library. In this article, I'll show some examples where speculative parallelism can be useful and I'll talk about an extension to the Par monad that I implemented (available on GitHub). The extension allows programmers to write speculative computations, provided that they manually verify that their code is deterministic.

F# Parallel Extras (III.): Financial dashboard with cancellation

In this article we'll look at several improvements that can be done to the Financial dashboard example (originally from the Parallel Programming with Microsoft .NET book). When I was translating samples in the book from C# to F#, the sample struck me, because it looks like a perfect fit for F# asynchronous workflows (instead of the Task<T> type used in the C# version). I already talked about an alternative implementation based on asynchronous workflows. However that version was still following some of the programming patterns, from the original C# version, which are not idiomatic in F#. In this article, I'll talk about a few other improvements that we can make to the sample...

In the original version of the sample (in both C# and F#), we explicitly checked whether a cancellation token has been cancelled in every single operation. This was needed in C#, because tasks do not support cancellation automatically. However, F# asynchronous workflows make cancellation easier. They automatically check if the computation should be cancelled at the beginning and the end of every asynchronous call. Our first change will be to use this feature. Also, the original version propagates a null value when the computation is cancelling. In F# we don't need that and we'll only change the type of the overall result to option<T>, so that we can notify the user interface (but we don't need to propagate cancellation explicitly). Finally, the original version contained sequential implementation, but didn't provide any way of actually running it, so we'll do a bit of refactoring to make that sample actually useable.

F# Parallel Extras (II.): Agent-based blocking queue

In the previous article, we briefly introduced the BlockingQueueAgent<T> type and we used it to implement the pipeline pattern (from Chapter 7 of Parallel Programming with Microsoft .NET) using asynchronous workflows. The type was used to represent intermediate buffers with a limited size. In this article we'll take a look at the implementation of the type. The type implements a very useful pattern in agent-based parallel programming, so you can use it in your work, but it could be also interesting as a demonstration of the F# Agent<T> type (an recommended alias for the MailboxProcessor<T> type).

The BlockingQueueAgent<T> type is similar to BlockingCollection<T> from .NET 4.0. It has methods for adding and removing elements that block when the operation cannot be done (e.g. adding when the queue is full or removing when the queue is empty). The most important difference is that it can be used asynchronously. This means that when we call its operations form F# asynchronous workflow (using let! and do!), the operation will block the calling workflow, but it will not block any physical thread. We start by looking at the overall structure of the agent and then look at the body of the agent which implements its behavior (using a state machine)...

F# Parallel Extras (I.): Image pipeline using agents

In a recent blog post series, I wrote about parallel programming samples that accompany the Parallel Programming with Microsoft .NET book by patterns & practices group at Microsoft. The F# translation of the samples that I wrote about mostly followed the style used in the book, so it used patterns that are typical for C#. However, some of the samples can be written in F# in a more interesting way...

In this article, we'll take a look at agent-based implementation of the Image pipeline example (from chapter 7). A pipeline is a useful pattern if you need to process large number of inputs in parallel and the processing consists of multiple phases or steps. In the original implementation, the pipeline was implemented using BlockingCollection<T> and Task<T> types from .NET 4.0.

In this article, I'll show a version that uses F# agents and asynchronous workflows. We'll use a BlockingQueueAgent<T> type, which is discussed in another article. It represents a queue with limited capacity that asynchronously blocks the process that is adding values if there is no space in the buffer and blocks the process that reads values when there are no values. This type can be elegantly used to implement the pipeline pattern. In this article, we'll demonstrate it by writing a four-phase pipeline that processes images. As you'll see, the agent-based version of the code is very much easier to write and has similar performance as the original version.

Parallel Programming in F# (IV.): Financial dashboard example

In the fourth part of the Parallel Programming in F# series, we'll take a look at the Adatum Financial Dashboard sample. The sample is a part of Parallel Programming with Microsoft .NET, which is a guide that introduces common parallel programming patterns on .NET 4.0. The C# version of the sample is in details discussed in the guide, but the F# translation contains several additional interesting aspects that I'll introduce in this article.

The sample simulates a financial modelling application that performs processing of market data in several steps that can be partly executed in parallel. In this article we'll compare two implementations. The first one (similar to the C# version) uses the Task<'T> type from .NET 4.0 and chains steps using the ContinueWith method. The second version is F# specific and it implements step as a sequential computation wrapped in asynchronous workflows. Partial results are reported to the user interface using events.

Parallel Programming in F# (III.): Aggregating data

In this part of the Parallel Programming in F# series, we'll explore examples of parallel aggregation from Chapter 4 of Parallel Programming with Microsoft .NET, which is a guide that introduces common parallel programming patterns on .NET 4.0. The C# version of the sample is in details discussed in the guide. In this article, we'll look at the F# translation and in particular at several functions from the PSeq module. Some of the functionality is currently available only in the "PSeq.fs" distributed with the samples, but will eventually appear in F# PowerPack as well.

Aggregation of data in parallel is an interesting problem. As we've seen in the previous article, PLINQ and tasks make it easy to parallelize independent blocks of code that don't share any state. Unfortunatelly, not all programs are like that. In particular, we often need to aggregate all elements of a sequence - when writing sequential code in F#, you would use the Seq.fold function. In this article, we'll look at functions that implement fold parallel.

Parallel Programming in F# (II.): Using PLINQ and Tasks

In this part of the Parallel Programming in F# series, we'll look at some basic examples of parallel programming in F# that are available in Parallel Programming with Microsoft .NET. This is a guide that introduces common parallel programming patterns on .NET 4.0. The guide discusses the samples in C#, but it also contains an F# translation of the source code. Since the languages are different, the F# version deserves a brief explanation.

In this article, we'll discuss some of the F# examples and we'll look at a couple of aspects that are specific for F#. In particular, we'll look at working with Parallel LINQ (both directly and using PSeq module from F# PowerPack) and working with tasks. We'll also look at an interesting example (using closures) where C# version doesn't behave as expected, but a literal translation in F# corrects the problem.

Parallel Programming in F# (I.): Introducing the samples

Parallel Programming with Microsoft .NET is a guide written by the patterns & practices group at Microsoft. It introduces .NET programmers to patterns for including parallelism in their applications (using support for parallel programming in .NET 4.0). It introduces techniques such as parallel loops, parallel tasks, data aggregation and so on. The book includes numerous samples in C# and Visual Basic that can be easily copied and adapted to match your needs.

As part of a contracting work for the F# team, I developed an F# version of the samples, which is now available on the book web site. You can get it by downloading F# code samples (ZIP) from the 1.0 release, or you can download the latest version of the source code directly. The F# version of the code is mostly a direct translation of the C# versions, but there are a few interesting places that are worth discussing. In particular, some of the samples use the PSeq module from F# PowerPack and I also added a version of one example that uses F# asynchronous workflows.

In this article series, I'll look at several interesting examples from the F# version of the source code. We'll look how to use PLINQ and Tasks (which are available in .NET 4.0) from F# (Part II.) including some advanced topics such as the Map-Reduce algorithm (Part III.). We'll also look at a larger example built using tasks and an alternative implementation using asynchronous workflows (Part IV.) Here are links to the individual articles:

• Parallel Programming in F# (I.): Introducing the samples
• Parallel Programming in F# (II.): Using PLINQ and Tasks
• Parallel Programming in F# (III.): Aggregating data
• Parallel Programming in F# (IV.): Financial dashboard example

Using custom grouping operators in LINQ

You can use LINQ to write queries that perform grouping of data using group by or ordering of data using orderby clause. LINQ provides the default (and the most common) implementation of both of the operations, but sometimes you may need a slightly different behavior when grouping or ordering data (this article is motivated by a question on StackOverflow which needs to do exactly that for grouping).

Let's look at a simple example, which shows when we may need a different behavior when grouping data. For example, we may have the following list of stock trades containing a name of a stock and the price of the trade (stored for example as a list of TradeInfo classes with properties Name and Price):

{ { Name = "MSFT", Price = 80.00 },
  { Name = "MSFT", Price = 70.00 },
  { Name = "GOOG", Price = 100.00 },
  { Name = "GOOG", Price = 200.00 },
  { Name = "GOOG", Price = 300.00 },
  { Name = "MSFT", Price = 30.00 },
  { Name = "MSFT", Price = 20.00 } }

Now, we may want to group adjacent trades into a single summary record which will contain the name of the stock (which is same for all trades in each group), the number of trades in the group and an average price in the group. The desired results are:

{ { Name = "MSFT", Count = 2, AvgPrice = 75.00 },
  { Name = "GOOG", Count = 3, AvgPrice = 200.00 },
  { Name = "MSFT", Count = 2, AvgPrice = 25.00 } }

The operation that we want to do is very similar to group by in LINQ, but it doesn't do quite the same thing! If we used group by, we would get only two groups as the result. However, as I wrote earlier, we want to group only adjacent trades. You could write your own extension method to do this, but then you need to leave the elegant LINQ query syntax. In this article, I'll show you how to get the desired results using a simple LINQ query with a group by clause...

Functional Programming: Available Chapter Excerpts & Discount

The work on my book Functional Programming for the Real World is slowly getting to the end. I'm currently creating index for the last couple of chapters and doing final updates based on the feedback from reviews and also from the forum at manning.com (this means that if you have some suggestions, it's the best time to post them - I haven't yet replied to all of them, but I'll certainly do that before the manuscript will go to the production).

Internship project: Reactive pattern matching

I already mentioned that I was doing my second internship with Don Syme at Microsoft Research in Cambridge. This time, I was in Cambridge for 6 months from October until April, so it has been more than a month since I left, but as you can guess I didn't have time to write anything about the internship until now... There isn't much to say though, because the internship was simply fantastic. Cambridge is a beautiful place (here are some autumn and winter photos), the Microsoft Research lab in Cambridge is full of smart people, so it is a perferct working environment (except that you realize that you're not as clever as you think :-)). Also, it is just a few meters away from the Computer Laboratory of the Cambridge University, so there are always many interesting talks and seminars. So, big thanks to Don Syme, James Margetson and everyone else who I had a chance to work with during the internship.

One of the reasons why I didn't have much time to write about the internship earlier is that I was invited to the Lang.NET Symposium shortly after the end of the internship. I had a chance to talk about my project there as well and there is even a video recording from the talk (the link is below), so you can watch it to find out more about my recent F# work.

Functional Programming in .NET using C# and F# (Manning Greenpaper)

Functional programming languages have been around for a while and were always astonishing for their ability to express the ideas in a succinct, declarative way allowing the developer to focus on the essence of problem rather than on technical details of the solution. Recently, functional paradigm is gaining new prominence as an efficient way to handle development of multi-processor, parallel and asynchronous applications.

Functional ideas are arising in C# as well as in other main-stream languages and functional languages are becoming an alternative for real-world projects. Also, Microsoft recently introduced a new language called F#, which has a strong background in traditional functional languages, but as a .NET language also benefits from the rich .NET and Visual Studio ecosystem.

Available via MEAP | 500 pages
Softbound print: March 2009 (est.)

This article is partially an excerpt from my book Real-world Functional Programming in .NET [1]. Thanks to my editors at Manning I have the permission to publish it on my blog. We’ll look at several aspects of functional programming and how the same concepts, which are essential for the functional paradigm, look in the F# and in C# 3.0 with LINQ. We will shortly look at the basic programming language features like lambda functions and type inference that are now available in both F# and C#. Functional programming isn’t only about language features, but also about using different programming style, so we’ll look at some high level concepts as well. These include using immutable data structures for developing code that can be executed in parallel and writing code in a more declarative style.

Thanks to the combination of C# 3.0 and F#, this article shows the ideas in a way that should be familiar to you in C#, but also shows a further step that you can take with a primarilly functional language F#. If you're a .NET developer and you want to understand what functional programming is and how it can help you to become better and more productive then continue reading. If you'll find this article interesting, then don't forget to check out the book, which explains everything in larger detail and discusses many other interesting ideas.

Announcing: Real-world Functional Programming in .NET

If you’ve been reading my blog or seen some my articles, you know that I’m a big fan of the F# language and functional programming style. I’m also often trying to present a bit different view of C# and LINQ – for me it is interesting mainly because it brings many functional features to a main-stream language and allows using of many of the functional patterns in a real-world. Elegant way for working with data, which is the most commonly used feature of C# 3.0, is just one example of this functional approach. Talking about real-world applications of functional programming, there is also fantastic news about F#. It was announced last year that F# will become fully supported Visual Studio language and the first CTP version of F# was released this week!

I always thought that the topics mentioned in the previous paragraph are really interesting and that functional programming will continue to become more and more important. That’s why I’m really excited by the news that I’d like to announce today – I’m writing a book about functional programming in F# and C#....

Infinite Cheese Fractal using WPF 3D and F#

I always liked fractals, because they look like objects from another world, but on the other side if you look at some things in our world you can see many similarities with fractals (but not quite as ideal with the infinite level of precision). One of my favorite fractals is 3D version of Sierpinski carpet [1], which itself is based on very famous Cantor set. Quite long time ago I thought that it would be nice to implement animation of flying through this fractal, but I was never good in 3D graphics and it looked like a lot of work, so I never get to doing it. Luckily, now with F#, which makes it very easy to write the code to generate the fractal and with WPF 3D, which can be easily used to animate the fractal, I finally had everything I needed to do it, so here it is!

Asynchronous Programming in C# using Iterators

In this article we will look how to write programs that perform asynchronous operations without the typical inversion of control. To briefly introduce what I mean by 'asynchronous' and 'inversion of control' - asynchronous refers to programs that perform some long running operations that don't necessary block a calling thread, for example accessing the network, calling web services or performing any other I/O operation in general. The inversion of control refers to the code structure that you have to use when writing a code that explicitly passes a C# delegate as a callback to the asynchronous method (typically called BeginSomething in .NET). The asynchronous method calls the delegate when the operation completes, which reverses the way you write the code - instead of encoding the control flow using typical language constructs (e.g. while loop) you have to use global variables and write your own control mechanism.

The funny thing about this article is that it could have been written at least 3 years ago when a beta version of Visual Studio 2005 and C# 2.0 became first available, but it is using iterators in a slightly bizarre way, so it is not easy to realize that this is possible. Actually, I will use some C# 3.0 methods in the article as well, but only extension methods and mainly just to keep the code nicer. As with my earlier article about building LINQ queries at runtime, I realized that it can be done in C# when I was playing with the F# solution (called F# Asynchronous Workflows), where this approach is very natural, so I will shortly mention the F# implementation as well.

Keep your multi-core CPU busy with F#

The growth of computer CPU speed is slowly being replaced by the growth of number of CPUs (or cores) in the computer at least for the close future. This causes a revolution in the way software is written, because traditional and most widely used way of writing concurrent applications using threads is difficult and brings several serious issues. Some predictions say that within a few years, almost every computer will have about 16 cores, so there is a huge need for programming paradigms or idioms that help developers write concurrent software easily (see also The Free Lunch Is Over [^] written by Herb Sutter).

Functional programming languages (especially pure functional languages) are interesting from this point of view, because the program doesn't have side-effects which makes it very easy to parallelize it (programs in pure functional languages can't have any side-effects by design, in other functional languages like F# the side-effects can be eliminated by following functional programming style).

This article describes the code that makes it possible to parallelize some common F# constructs like the List.map and List.filter...

All blog posts by tag