Research | Blog | TomasP.Net

Power of mathematics: Reasoning about functional types

Tomas Petricek — Tue, 14 May 2013 17:54:46 GMT

One of the most amazing aspects of mathematics is that it applies to such a wide range of areas. The same mathematical rules can be applied to completely different objects (say, forces in physics or markets in economics) and they work exactly the same way.

In this article, we'll look at one such fascinating use of mathematics - we'll use elementary school algebra to reason about functional data types.

In functional programming, the best way to start solving a problem is to think about the data types that are needed to represent the data that you will be working with. This gives you a simple starting point and a great tool to communicate and develop your ideas. I call this approach Type-First Development and I wrote about it earlier, so I won't repeat that here.

The two most elementary types in functional languages are tuples (also called pairs or product types) and discriminated unions (also called algebraic data types, case classes or sum types). It turns out that these two types are closely related to multiplication and addition in algebra...

F# Data: New type provider library

Tomas Petricek — Thu, 28 Mar 2013 03:23:41 GMT

When F# 3.0 type providers were still in beta version, I wrote a couple of type providers as examples for talks. These included the WorldBank type provider (now available on Try F#) and also type provider for XML that infered the structure from sample.
For some time, these were hosted as part of FSharpX and the authors of FSharpX also added a number of great features.

When I found some more time earlier this year, I decided to start a new library that would be fully focused on data access in F# and on type providers and I started working on F# Data. The library has now reached a stable state and Steffen also announced that the document type providers (JSON, XML and CSV) are not going to be available in FSharpX since the next version.

This means that if you're interested in accessing data using F# type providers, you should now go to F# Data. Here are the most important links:

Before looking at the details, I would like to thank to Gustavo Guerra who made some amazing contributions to the library! (More contributors are always welcome, so continue reading if you're interested...)

Announcing: Literate programming tools for F#

Tomas Petricek — Tue, 22 Jan 2013 17:35:36 GMT

For some time now, I've been writing my F# blog posts (and other F# articles published elsewhere) by combining F# code snippets and Markdown formatting. In fact, I even wrote a Markdown parser in F# so that I can post-process documents (to generate references etc). You can read about the Markdown parser in an upcoming F# Deep Dives book - currently, it is available as a free chapter!

During the Christmas break, I finally found enough time to clean-up the code I was using and package it properly into a documented library that is easy to install and use. Here are the most important links:

To learn more about the tool and how to use it, continue reading!

Processing trees with F# zipper computation

Tomas Petricek — Wed, 19 Dec 2012 14:22:47 GMT

One of the less frequently advertised new features in F# 3.0 is the query syntax. It is an extension that makes it possible to add custom operations in an F# computation expression. The standard query { .. } computation uses this to define operations such as sorting (sortBy and sortByDescending) or operations for taking and skipping elements (take, takeWhile, ...). For example, you can write:

1: query { for x in 1 .. 10 do
2:         take 3
3:         sortByDescending x }

In this article I'll use the same notation for processing trees using the zipper pattern. I'll show how to define a computation that allows you to traverse a tree and perform transformations on (parts) of the tree. For example, we'll be able to say "Go to the left sub-tree, multiply all values by 2. Then go back and to the right sub-tree and divide all values by 2" as follows:

1: tree { for x in sample do
2:        left 
3:        map (x * 2) 
4:        up
5:        right
6:        map (x / 2) 
7:        top }

This example behaves quite differently to the usual query computation. It mostly relies on custom operations like left, right and up that allow us to navigate through a tree (descend along the left or right sub-tree, go back to the parent node). The only operation that does something is the map operation which transforms the current sub-tree.

This was just a brief introduction to what is possible, so let's take a detailed look at how this works...

val query : Linq.QueryBuilder

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.query

val x : int

custom operation: take (int)

Calls Linq.QueryBuilder.Take

custom operation: sortByDescending ('Key)

Calls Linq.QueryBuilder.SortByDescending

type Tree<'T> =
  | Node of Tree<'T> * Tree<'T>
  | Leaf of 'T
  override ToString : unit -> string

Full name: Tree-zipper-query.Tree<_>

union case Tree.Node: Tree<'T> * Tree<'T> -> Tree<'T>

union case Tree.Leaf: 'T -> Tree<'T>

val x : Tree<'T>

override Tree.ToString : unit -> string

Full name: Tree-zipper-query.Tree`1.ToString

match x with
| Node(l, r) -> sprintf "(%O, %O)" l r
| Leaf v -> sprintf "%O" v

type Path<'T> =
  | Top
  | Left of Path<'T> * Tree<'T>
  | Right of Path<'T> * Tree<'T>
  override ToString : unit -> string

Full name: Tree-zipper-query.Path<_>

union case Path.Top: Path<'T>

union case Path.Left: Path<'T> * Tree<'T> -> Path<'T>

union case Path.Right: Path<'T> * Tree<'T> -> Path<'T>

val x : Path<'T>

override Path.ToString : unit -> string

Full name: Tree-zipper-query.Path`1.ToString

match x with
    | Top -> "T"
    | Left(p, t) -> sprintf "L(%O, %O)" p t
    | Right(p, t) -> sprintf "R(%O, %O)" p t

type TreeZipper<'T> =
| TZ of Tree<'T> * Path<'T>
override ToString : unit -> string

Full name: Tree-zipper-query.TreeZipper<_>

union case TreeZipper.TZ: Tree<'T> * Path<'T> -> TreeZipper<'T>

val x : TreeZipper<'T>

override TreeZipper.ToString : unit -> string

Full name: Tree-zipper-query.TreeZipper`1.ToString

let (TZ(t, p)) = x in sprintf "%O [%O]" t p

val left : _arg1:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.left

Navigates to the left sub-tree

val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith

val l : Tree<'a>

val r : Tree<'a>

val p : Path<'a>

val right : _arg1:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.right

Navigates to the right sub-tree

val current : _arg1:TreeZipper<'a> -> 'a

Full name: Tree-zipper-query.current

Gets the value at the current position

val x : 'a

val branches : Tree<int>

Full name: Tree-zipper-query.branches

val sample : TreeZipper<int>

Full name: Tree-zipper-query.sample

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

val up : _arg1:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.up

val top : _arg1:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.top

val t : TreeZipper<'a>

val tz : TreeZipper<'a>

Multiple items
val unit : v:'a -> TreeZipper<'a>

Full name: Tree-zipper-query.unit

Build tree zipper with singleton tree

--------------------
type unit = Unit

Full name: Microsoft.FSharp.Core.unit

val v : 'a

val bindSub : f:('a -> TreeZipper<'a>) -> treeZip:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.bindSub

Transform leaves in the current sub-tree of 'treeZip'
into other trees using the provided function 'f'

val f : ('a -> TreeZipper<'a>)

val treeZip : TreeZipper<'a>

val bindT : (Tree<'a> -> Tree<'a>)

val t : Tree<'a>

val current : Tree<'a>

val path : Path<'a>

Multiple items
type TreeZipperBuilder =
  new : unit -> TreeZipperBuilder
  member Current : tz:TreeZipper<'a> -> 'a
  member For : tz:TreeZipper<'T> * f:('T -> TreeZipper<'T>) -> TreeZipper<'T>
  member Left : tz:TreeZipper<'a> -> TreeZipper<'a>
  member Right : tz:TreeZipper<'a> -> TreeZipper<'a>
  member Select : tz:TreeZipper<'a> * f:('a -> 'a) -> TreeZipper<'a>
  member Top : tz:TreeZipper<'a> -> TreeZipper<'a>
  member Up : tz:TreeZipper<'a> -> TreeZipper<'a>
  member Yield : v:'a -> TreeZipper<'a>

Full name: Tree-zipper-query.TreeZipperBuilder

--------------------
new : unit -> TreeZipperBuilder

val x : TreeZipperBuilder

member TreeZipperBuilder.For : tz:TreeZipper<'T> * f:('T -> TreeZipper<'T>) -> TreeZipper<'T>

Full name: Tree-zipper-query.TreeZipperBuilder.For

Enables the 'for x in xs do ..' syntax

val tz : TreeZipper<'T>

val f : ('T -> TreeZipper<'T>)

member TreeZipperBuilder.Yield : v:'a -> TreeZipper<'a>

Full name: Tree-zipper-query.TreeZipperBuilder.Yield

Enables the 'yield x' syntax

val tree : TreeZipperBuilder

Full name: Tree-zipper-query.tree

Global instance of the computation builder

Multiple items
type CustomOperationAttribute =
  inherit Attribute
  new : name:string -> CustomOperationAttribute
  member AllowIntoPattern : bool
  member IsLikeGroupJoin : bool
  member IsLikeJoin : bool
  member IsLikeZip : bool
  member JoinConditionWord : string
  member MaintainsVariableSpace : bool
  member MaintainsVariableSpaceUsingBind : bool
  member Name : string
  ...

Full name: Microsoft.FSharp.Core.CustomOperationAttribute

--------------------
new : name:string -> CustomOperationAttribute

member TreeZipperBuilder.Left : tz:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.TreeZipperBuilder.Left

member TreeZipperBuilder.Right : tz:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.TreeZipperBuilder.Right

member TreeZipperBuilder.Up : tz:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.TreeZipperBuilder.Up

member TreeZipperBuilder.Top : tz:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.TreeZipperBuilder.Top

member TreeZipperBuilder.Current : tz:TreeZipper<'a> -> 'a

Full name: Tree-zipper-query.TreeZipperBuilder.Current

Extracts the current value and returns it

member TreeZipperBuilder.Select : tz:TreeZipper<'a> * f:('a -> 'a) -> TreeZipper<'a>

Full name: Tree-zipper-query.TreeZipperBuilder.Select

Transform the current sub-tree using 'f'

Multiple items
type ProjectionParameterAttribute =
inherit Attribute
new : unit -> ProjectionParameterAttribute

Full name: Microsoft.FSharp.Core.ProjectionParameterAttribute

--------------------
new : unit -> ProjectionParameterAttribute

val f : ('a -> 'a)

custom operation: right

Calls TreeZipperBuilder.Right

custom operation: left

Calls TreeZipperBuilder.Left

custom operation: current

Calls TreeZipperBuilder.Current

Extracts the current value and returns it

custom operation: map ('a)

Calls TreeZipperBuilder.Select

Transform the current sub-tree using 'f'

custom operation: up

Calls TreeZipperBuilder.Up

custom operation: top

Calls TreeZipperBuilder.Top

val tree : TreeZipperBuilder

Full name: Tree-zipper-query.tree

Global instance of the computation builder

val x : int

val sample : TreeZipper<int>

Full name: Tree-zipper-query.sample

custom operation: left

Calls TreeZipperBuilder.Left

custom operation: map ('a)

Calls TreeZipperBuilder.Select

Transform the current sub-tree using 'f'

custom operation: up

Calls TreeZipperBuilder.Up

custom operation: right

Calls TreeZipperBuilder.Right

custom operation: top

Calls TreeZipperBuilder.Top

Applicative functors: definition and syntax

Tomas Petricek — Tue, 21 Aug 2012 14:23:19 GMT

In a recent blog post, Edward Z. Yang talks about applicative functors. He mentions two equivalent definitions of applicative functors - the standard definition used in Haskell libraries (Applicative) and an alternative that has been also presented in the original paper, but is generally less familiar (Monoidal).

The standard definition makes a perfect sense with the standard uses in Haskell, however I always preferred the alternative definition. Edward uses the alternative (Monoidal) definition to explain the laws that should hold about applicative functors and to explain commutative applicative functors, but I think it is even more useful.

The Monoidal definition fits nicely with a trick that you can use to encode applicative functors in C# using LINQ and I also used it as a basis for an F# syntax extension that allows writing code using applicative functors in a similar style as using monads (which is discussed in my draft paper about writing abstract computations in F#). And I also think that commutative applicative functors deserve more attention.

Why type-first development matters

Tomas Petricek — Thu, 16 Aug 2012 00:21:21 GMT

Using functional programming language changes the way you write code in a number of ways. Many of the changes are at a small-scale. For example, you learn how to express computations in a shorter, more declarative way using higher-order functions. However, there are also many changes at a large-scale. The most notable one is that, when designing a program, you start thinking about the (data) types that represent the data your code works with.

In this article, I describe this approach. Since the acronym TDD is already taken, I call the approach Type-First Development (TFD), which is probably a better name anyway. The development is not driven by types. It starts with types, but the rest of the implementation can still use test-driven development for the implementation.

This article demonstrates the approach using a case study from a real life: My example is a project that I started working on with a friend who needed a system to log journeys with a company car (for expense reports). Using the type-first approach made it easier to understand and discuss the problem.

In many ways, TFD is a very simple approach, so this article just gives a name to a practice that is quite common among functional and F# programmers (and we have been teaching it at our F# trainings for the last year)...

The theory behind covariance and contravariance in C# 4

Tomas Petricek — Tue, 19 Jun 2012 14:24:52 GMT

In C# 4.0, we can annotate generic type parameters with out and in annotations to specify whether they should behave covariantly or contravariantly. This is mainly useful when using already defined standard interfaces. Covariance means that you can use IEnumerable<string> in place where IEnumerable<object> is expected. Contravariance allows you to pass IComparable<object> as an argument of a method taking IComparable<string>.

So far, so good. If you already learned about covariance and contravariance in C# 4, then the above two examples are probably familiar. If you're new to the concepts, then the examples should make sense (after a bit of thinking, but I'll say more about them). However, there is still a number of questions. Is there some easy way to explain the two concepts? Why one option makes sense for some types and the other for different types? And why the hell is it called covariance and contravariance anyway?

In this blog post, I'll explain some of the mathematics that you can use to think about covariance and contravariance.

F# in Academia: Present at upcoming events!

Tomas Petricek — Mon, 16 Apr 2012 00:19:04 GMT

The F# language was born as a combination of the pragmatic and real-world .NET platform and functional programming, which had a long tradition in academia. Many useful ideas or libraries in F# (like asynchronous workflows and first-class events) are inspored by research in functional programming (namely, the work on monads, continuations and functional reactive programming).

Exchanging the ideas between the research community and the real-world is one of the areas where F# excels. Indeed, the first applicatiosn of F# inside Microsoft (in the Machine Learning group at Cambridge) were all about this - combining research in machine learning with a language that can be easily used in practice.

However, F# and the F# users also made numerous contributions to the programming langauge research community. Influential ideas that come from F# include active patterns and the F# style of meta-programming for translating F# to JavaScript). I think there is a lot more that the academic community can learn from the F# community, so I'd like to invite you to talk about your ideas at two upcoming academic events!

What, why, when, where and how? Continue reading!

TryJoinads (VII.) - Implementing joinads for async workflows

Tomas Petricek — Fri, 23 Mar 2012 17:21:51 GMT

The article Asynchronous workflows and joinads gives numerous examples of programming with asynchronous workflows using the match! construct. Briefly, when matching on multiple asynchronous workflows, they are executed in parallel. When pattern matching consists of multiple clauses, the clause that matches on computations that complete first gets executed. These two behaviours are implemented by the Merge and the Choose operation of joinads. Additionally, asynchronous workflows require the Alias operation, which makes it possible to share the result of a started asynchronous workflow in multiple clauses.

In this article, we look at the definition of the additional AsyncBuilder operations that enable the match! syntax. We do not look at additional examples of using the syntax, because these can be found in a previous article.

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 (VI.) - Parsing with joinads

Tomas Petricek — Wed, 21 Mar 2012 16:27:06 GMT

In functional programming, parser combinators are a powerful way of writing parsers. A parser is a function that, given some input, returns possible parsed values and the rest of the input. Parsers can be written using combinators for composition, for example run two parsers in sequence or perform one parser any number of times.

Parsers can also implement the monad structure. In some cases, this makes the parser less efficient, but it is an elegant way of composing parsers and we can also benefit from the syntactic support for monads. In this article, we implement a simple parser combinators for F# and we look what additional expressive power we can get from the joinad structure and match! construct. This article is largely based on a previous article "Fun with Parallel Monad Comprehensions", which can be found on the publications page.

TryJoinads (V.) - Implementing the option joinad

Tomas Petricek — Fri, 02 Mar 2012 13:24:21 GMT

This article shows how to implement the joinad structure for one of the simplest monads - the option<'T> type. This is a slightly oversimplified example. The match! construct can be used to write patterns that specify that a monadic value (in this case option<'T>) should contain a certain value, or we can specify that we do not require a value. When working with options, this means the same thing as matching the value against Some and against _, respectively.

However, the example demonstrates the operations that need to be implemented and their type signatures. Later articles give more interesting examples including parsers and asynchronous workflows (and you can explore other examples if you look at the FSharp.Joiands source code at GitHub).

TryJoinads (IV.) - Concurrency using join calculus

Tomas Petricek — Wed, 22 Feb 2012 17:38:40 GMT

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.

TryJoinads (III.): Agent-based programming

Tomas Petricek — Mon, 20 Feb 2012 12:36:10 GMT

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.

TryJoinads (II.): Task-based parallelism

Tomas Petricek — Fri, 17 Feb 2012 13:10:29 GMT

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.

TryJoinads (I.) - Asynchronous programming

Tomas Petricek — Mon, 13 Feb 2012 17:35:44 GMT

Asynchronous workflows provide a way of writing code that does not block a thread when waiting for a completion of long-running operation such as web service call, another I/O operation or waiting for the completion of some background operation. In this article, we look at the new expressive power that joinads add to asynchronous workflows written using the async { ... } block in F#.

Introducing TryJoinads.org

Tomas Petricek — Mon, 13 Feb 2012 16:21:03 GMT

(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...

Programming with F# asynchronous sequences

Tomas Petricek — Thu, 11 Aug 2011 23:30:57 GMT

In F#, we can represent asynchronous operations that do not block threads and eventually return a value of type 'T using asynchronous workflows Async<'T>. Asynchronous workflows can be easily constructed using the computation expression syntax async { ... } and there are also a few combinators that express more advanced composition (such as parallel composition or fork-join parallelism).

Sometimes, we need to use asynchronous operations that return more than just one value. For example, when downloading data from the internet, we would like to create an asynchronous sequence that returns the data in chunks as they become available.

One way to represent asynchronous operations that produce multiple values is to use the IObservable<'T> type from .NET. This isn't always the best option though. Observables implement push-based model, which means that chunks of data are generated as quickly as possible (until all chunks are emitted). What if we wanted to take the chunks one-by-one after the previous chunk is processed?

In this article, I describe asynchronous sequences. An asynchronous sequence is a simple, yet very powerful concept based on asynchronous workflows. It follows the same core model: results are generated on demand and asynchronously. Unlike asynchronous workflows, asynchronous sequences can be called (on demand) to generate multiple values until the end of the sequence is reached.

I first discussed asynchronous sequences with Don Syme, Dmitry Lomov and Brian McNamara in an email thread a long time ago. Thanks to Don for enthusiasm about the concept and for the first implementation of some of the combinators!

Extending Monads with Pattern Matching (Haskell 2011)

Tomas Petricek — Wed, 20 Jul 2011 00:19:37 GMT

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)

Tomas Petricek — Tue, 19 Jul 2011 23:28:29 GMT

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.

Safer asynchronous workflows for GUI programming

Tomas Petricek — Wed, 15 Jun 2011 21:36:40 GMT

In the previous article, I discussed how to use F# asynchronous workflows for creating reactive user-interfaces. One of the main concerns was to avoid blocking the GUI thread (to prevent the user-interface from freezing). The workflow shouldn't perform any CPU-intensive computation when running on the GUI thread.

The standard F# library provides two ways to run a computation on a background thread from an asynchronous workflow. The StartChild operation starts an operation in the thread pool and returns a workflow that can be called using asynchronous (non-blocking) let! construct. The SwitchToThreadPool operation can be called using do! and resumes the rest of the workflow on a background thread.

When using the SwitchToThreadPool operation, we also need to eventually use SwitchToContext to transfer the execution back to the GUI thread (after completing the CPU-intensive calculations). In this article, I describe a variation of F# asynchronous workflows that keeps track of the running thread in the type of the computation. As a result, calling a workflow that should be executed on a GUI thread from a background thread is a compile-time error as opposed to failing at runtime.

Writing non-blocking user-interfaces in F#

Tomas Petricek — Fri, 10 Jun 2011 23:36:16 GMT

F# asynchronous workflows are best known as a way to write efficient I/O operations or as an underlying mechanism of F# agent-based programming (using the MailboxProcessor type). However, they are also very useful for user-interface programming. I think this is a very interesting and important area, so I already wrote and talked about this topic - it is covered in Chapter 16 of my book (there is a free excerpt) and I talked about it at F#unctional Londoners meeting.

Many applications combine user-interface programming (such as waiting for an event asynchronously) with some CPU-intensive tasks. This article looks at an example of such application and I'll explain how to avoid blocking the user-interface when doing the CPU-intensive task. The article starts with an example that is wrong and blocks the user-interface when doing data processing. Then I'll show you two options for fixing the problem. The three most important functions from the standard F# library that I'll discuss are Async.StartChild and Async.SwitchToThreadPool with Async.SwitchToContext.

This is the first article of a mini-series. In the next article, I'll demonstrate a simple wrapper for F# async that makes it more difficult to write wrong programs. The wrapper keeps the desired thread (GUI or background) in the type of the computations and code that would block the user interface will not type-check. But first, let's look at the example...

Explicit speculative parallelism for Haskell's Par monad

Tomas Petricek — Tue, 17 May 2011 13:59:06 GMT

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.

Variations in F#: Research compiler with Joinads and more!

Tomas Petricek — Fri, 25 Mar 2011 00:04:08 GMT

In this article, I'll write about an experimental extension for F# that I call joinads. If you're following my blog, you may have seen an academic paper that I wrote about it some time ago. Anyway, the motivation for the extension is that there are many useful programming models for reactive, concurrent and parallel programming that would deserve some syntactic support in the programming language.

For example, when programming with futures (the Task<T> type), you may want to implement logical "or" operator for tasks that returns true immediately when the first task completes returning true. When programming with events (the IObservable<T> type), we'd like to wait for the event that happens first. Finally, when programming using agents, we sometimes need to wait only for certain types of messages. All of these problems can be solved, but require the use of (sometimes fairly complicated) functions. Joinads make it possible to solve them directly using the match! syntax. For example, here is the "or" operator for tasks:

1: future {
2:   match! after 100 true, after 1000 false with
3:   | !true, _ -> return true
4:   | _, !true -> return true
5:   | !a, !b -> return a || b }

I'll write more about this example (and the implementation) in a later article. This article focuses on the compiler extension itself. I created a first implementation of the idea above during my internship with Don Syme at MSR Cambridge, but then changed it quite a bit when writing the academic paper mentioned above. However, I never released the source code.

Thanks to the open-source release of F# it is now quite easy to modify the F# compiler and make the modifications available, so I decided I should finally release my F# extensions. I also recently blogged about encoding idioms (also called applicative functors) in C#. I was wondering how to do that in F# and so I also created a simple extension computations based on this abstraction. The support for idioms is just an experiment, but it could be useful, for example, for programming with formlets. You'll find more about it at the end of the article.

You can find the source code on my GitHub (there is also a link compiled binaries at the end of the article). The source code is cloned from an F# Mono repository, which means that it should build on Linux and MacOS too.

val future : FutureBuilder

Full name: JoinadsDemo.future

val after : int -> 'a -> Task<'a>

Full name: JoinadsDemo.after

val a : bool

  type: bool
  implements: IComparable
  implements: IConvertible
  implements: IComparable<bool>
  implements: IEquatable<bool>
  inherits: ValueType

val b : bool

  type: bool
  implements: IComparable
  implements: IConvertible
  implements: IComparable<bool>
  implements: IEquatable<bool>
  inherits: ValueType

Beyond the Monad fashion (II.): Creating web forms with LINQ

Tomas Petricek — Mon, 14 Mar 2011 17:14:49 GMT

The LINQ query syntax can be used for various things. Aside from writing queries, you can also use it to encode any monads. This has become a fashionable topic, so you can learn more about it at many .NET conferences (for example GOTO 2011). There are also many blog posts on this topic and I explained it in details in Chapter 12 of my book, which is available as a free sample chapter (PDF).

However, you can also use LINQ syntax for writing different types of computations. In a previous blog post, I introduced idioms (also called applicative functors) and I demonstrated how to use the join syntax in LINQ to write computations based on idioms. We looked at a slightly boring, but simple example - zipping of lists - and we also implemented matrix transposition.

In this blog post, we look at a more exciting example. I explain formlets, which is an idiom for building web forms. Formlets give us an elegant functional way to create reusable components that encapsulate both visual aspect (HTML) and behavior (processing of requests). You can think of them as functional ASP.NET controls. Formlets come from the Links project and they are now used in commercial products like WebSharper. In this article, you'll see that we can (mis)use LINQ to get a nicer syntax for writing code using formlets. My C# implementation of formlets is based on a nice F# formlets by Mauricio Scheffer.

Beyond the Monad fashion (I.): Writing idioms in LINQ

Tomas Petricek — Thu, 10 Mar 2011 13:26:00 GMT

Thanks to LINQ and Erik Meier, monads have become a fashionable topic in the C# developer community. Indeed, no serious developer conference on .NET can get away without having a talk on monads. The attractive thing about LINQ and monads is that the SelectMany operator roughly corresponds to the bind function that defines a monad. In practice, LINQ is used for working with collections of data (IEnumerable<T>), but you can also define bind (i.e. SelectMany) for some other data types and use the LINQ syntax for working with other types. You won't be really using the full LINQ syntax. You'll probably use just nested from clauses (for binding) and select at the end to return the result.

However, monads are not the only notion of computation that we can work with. More interestingly, they are also not the only notion of computation that you can encode using LINQ! In this article, I'll briefly introduce idioms (also called applicative functors), which is another useful abstract type of computations. Idioms can be used for a few things that cannot be done using monads.

A provocative summary of this article is: "Everyone who tells you that LINQ is a monad is wrong!"

The truth is that LINQ syntax can be used for encoding queries (obviously), monads (as you were told), but also for idioms as you'll learn today (and quite possibly for other types of computations). In this article, we look at a basic example, but I'll describe a more complex real-world scenario in the next blog post.

Reactive, parallel and concurrent programming in F# (PADL 2011)

Tomas Petricek — Mon, 25 Oct 2010 00:00:37 GMT

Don Syme blogged about a paper on the F# Asynchrounous Programming Model that I helped to write. Without any doubt, the asynchronous programming features of F# are one of the reason for its success and also influence other teams in Microsoft. However, I'm very glad that there is now also an academic paper that makes this idea accessible to the academic community. I believe that the ideas could evolve in interesting ways when used in other programming languages and also, it is now easier to create research projects that build on top of the F# model.

Don already mentioned that we have another paper accepted at PADL. The paper describes work that started during my internship at Microsoft Research in 2009. It presents a simple language extension for computation expressions that makes them even more useful in some reactive, concurrent and parallel programming models. Note that this is only a research project and there are currently no plans to support the extension in the F# language (although, if there will, eventually, be an open-source F# release, then you'll hear about the extension again...)

Here is the abstract of the paper (accepted at PADL 2011) and a PDF download link:

Joinads: A retargetable control-flow construct for reactive, parallel and concurrent programming

Modern challenges led to a design of a wide range of programming models for reactive, parallel and concurrent programming, but these are often difficult to encode in general purpose languages. We present an abstract type of computations called joinads together with a syntactic language extension that aims to make it easier to use joinads in modern functional languages.

Our extension generalizes pattern matching to work on abstract computations. It keeps a familiar syntax and semantics of pattern matching making it easy to reason about code, even in a non-standard programming model. We demonstrate our extension using three important programming models – a reactive model based on events; a concurrent model based on join calculus and a parallel model using futures. All three models are implemented as libraries that benefit from our syntactic extension. This makes them easier to use and also opens space for exploring new useful programming models.

Download the full text (PDF, pre-publication draft)

The paper can still be revised before the final publication, so any comments and suggestions for improvement are largely welcome. You can contact me either via comments (below) or using email at tomas@tomasp.net. I would be also quite interested to hear from anybody who would like to implement similar feature in other programming languages (for example Haskell or Scala).

The Duality of Object and Event references

Tomas Petricek — Mon, 19 Jul 2010 16:58:05 GMT

Mathematical duality [2] is a very useful and elegant concept that gives us a nice way of speaking about objects or structures that behave in some way exactly conversely. There is no clear definition of what duality is. However, the idea is that when we have two structures that behave conversely and we know that something is true about the first one, then we get the opposite statement about the other structure "for free" (if you know how to translate from one structure to the other).

In this article, I'll talk about an interesting example of duality that (to my best knowledge) wasn't described by anyone before. The two dual structures are references between objects in a normal program and references between events in a reactive application. The statement that is going to become obvious thanks to the duality principle is describing which of the objects (or events) are garbage and can be safely collected by garbage collector.

This topic is in much more details discussed in a paper [4] I wrote with Don Syme and that I presented at the ISMM Workshop (see also my trip report from PLDI). In this article, I'll try to give an accessible description of the most interesting idea from the paper...