Many programming problems can be easily solved if we express them as computations with some non-standard aspect. This is a very important problem, because today we're struggling for example to e±ciently program multi-core processors and to write asynchronous code. Unfortunately main-stream languages such as Java or C# don't support any direct way for encoding unrestricted nonstandard computations. In languages like Haskell and F#, this can be done using monads with syntactic extensions they provide and it has been successfully applied to a wide range of real-world problems. In this paper, we present a general way for encoding monadic computations in the C# 2.0 language with a convenient syntax using an existing language feature called iterators. This gives us a way to use well-known non-standard computations enabling easy asynchronous programming or for example the use of software transactional memory in plain C#. Moreover, it also opens monads in general to a wider audience which can help in the search for other useful and previously unknown kinds of computations.
ming mechanism based on shared memory, which
avoids the need for explicit locking [
The motivation for this article is that we want to
be able to use the techniques just described in a
mainstream and widely used C# language. The main
contributions of this paper are following:
² As far as we're aware, we show for the ¯rst time
that monadic computations can be encoded in C#
in a syntactically convenient way without placing
any restrictions on the C# statements that can
be used inside the computation. This can be done
purely as a library without changing the language
using widely adopted C# 2.0 features (Section 3).
² We use the presented technique to implement a
library that makes it easier to write scalable
multithreaded applications that perform long running
I/O operations. We demonstrate it using several
case study examples (Section 4).
² Finally, we describe a method for systematical
encoding of arbitrary monadic computation in C#
(Section 5). This technique can be used for
implementing other useful computations such as
software transactional memory and others.
In functional programming languages such as Haskell
and F#, monadic computations are used to solve wide
range of problems. In Haskell [
The primary motivation for this work is that should ¯rst clarify what problem we want to solve is.
monadic computations are very powerful technique for Let's start by looking at naive synchronous code that
dealing with many modern computing challenges downloads the ¯rst kilobyte of web site content:
caused by the rise of multi-core processors and dis- 1: var req = HttpWebRequest.Create(url);
tributed web based applications. The standard F# li- 2: var rsp = req.GetResponse();
brary uses monadic computations to implement asyn- 3: var strm = rsp.GetResponseStream();
chronous work°ows [
In this context \asynchronous" means that the program invokes start of the operation, registers a callback, transfers the control to the system and releases This function downloads the entire content of the current thread, so that it can perform other work. a web page in a loop. Although it doesn't use the data In the snippet above, we're starting two operations in any way and only reports the progress, it nicely on lines 2 and 5 and we're using the C# 3.0 lambda demonstrates the principle. Its body is an async block, function notation \=>" to specify the callback func- which speci¯es that the function doesn't actually run tion that will be eventually invoked. the code, but instead returns a value representing com
The code above is far less readable than the ¯rst putation that can be executed later. synchronous version, but that's not the only prob- In the places where the original C# code executed lem. To download the whole page, we'd need to call asynchronous operations, we're now using the let! the BeginRead method in a loop until we fetched the Keyword (lines 3 and 8), which represents monadic whole page, but that's ridiculously di±cult, because value binding. This means that instead of simply aswe can't use any higher level constructs such as the signing value to a symbol, the computation invokes while loop when writing code using nested callbacks. Bind operation that is provided by the async value For every simple problem, the programmer has to ex- (called computation builder) giving it the rest of the plicitly write a state machine using mutable state. code wrapped inside a function as an argument. The
It is worth pointing out that using asynchronous Bind member speci¯es non-standard behavior of the model does not in principle increase the CPU par- operation. In this case the behavior is that the operaallelism in the application, but it still signi¯cantly tion is executed asynchronously. improves the performance and makes the application The computation builder (in this case async) also more scalable because it considerably reduces the de¯nes the meaning of other primitive constructs such number of (expensive) threads the application creates. as the while loop or returning the result from a function. These primitive operations are exposed as standard methods with well-de¯ned type signatures: work in the meantime. If we wanted to run hundreds computations that is already de¯ned in F# libraries. of downloads in parallel, we could create hundreds This feature hasn't been described in the literature of threads, but that introduces signi¯cant overheads before, so we quickly review it here. (such as allocation of kernel objects and thread stack) When we wrap code inside an async block, the and also increases context switching. The right way to compiler automatically uses continuation passing style solve the problem on the .NET platform is to use the for specially marked operations. Moreover, we can use Asynchronous Programming Model (APM): all standard language constructs inside the block including for example the while loop: To write non-blocking asynchronous code, we can use continuation passing style where the next piece of code to execute after an operation completes is given as a function as the last argument to the operation. In the snippet above we've written the code in this style explicitly, but as we've seen this isn't a satisfying solution.
that de¯ne the abstract monadic type as ¯rst
described in [
Async<'b> Return : 'a -> Async<'a> While : (unti -> bool) * Async<unit> ->
Async<unit> 2.2
member builds a computation that returns the given to the console, so the program above shows the \genvalue. The additional While member takes a predicate erating" message directly followed by \got" for numand a computation and returns result that executes bers 0 and 1. There are two key aspects of iterators the computation repeatedly while the predicate holds. that are important for this paper:
When compiling code that uses computation
expressions, the F# compiler syntactically transforms
the code into code composed from the calls to these
primitive operations. The translated version of the
previous example can be found in the online
supplementary material for the article [
One of the non-standard computations that is very
often used in practice is a computation that generates In many ways this resembles the continuation
passa sequence of values instead of yielding just a single ing style from functional languages, which is
essenresult. This aspect is directly implemented by C# it- tial for monadic computations and F# asynchronous
erators [
The code looks just like ordinary method with the exception that it uses the yield return keyword to generate elements a sequence. The while loop may look like an in¯nite loop, but due to the way iterators work, the code is actually perfectly valid and useful. The compiler translates the code into a state machine that generates the elements of the se- 3.1 quence lazily one by one. The returned object of type IEnumerator<int> can be used in the following way:
in F# (as an example of monadic computations) and C# iterators, we can ask ourselves the question whether iterators could be used for encoding other non-standard computations then code that generates a sequence.
The key idea of this article is that it is indeed possible to do that and that we can write standard C# library to support any monadic computation. In this section, we'll brie°y introduce how the library looks using the simplest possible example and in section 5 we'll in detail explain how the encoding works.
1: var en = GetNumbers(); 2: en.MoveNext(); 3: Console.WriteLine("got {0}", en.Current); 4: en.MoveNext(); 5: Console.WriteLine("got {0}", en.Current);
The call to the GetNumbers method (line 1) re- that return this type can return None value at any turns an object that represents the state machine gen- point, which bypasses the entire rest of the computaerated by the compiler. The variables used inside the tion. In practice this is useful for example when permethod are transformed into a local state of that ob- forming series of data lookup that may not contain the ject. Each call to the MoveNext method (lines 2 and 4) value we're looking for. The usual way for writing the runs one step of the state machine until it reaches the code would check whether the returned value is None next yield return statement (line 5 in the earlier snippet) updating the state of the state machine. This also 1 In Haskell, this type is called Maybe and the correspondexecutes all side-e®ects of the iterator such as printing ing computation is known as Maybe monad.
duce value of type Option<'a> 1, which can either contain no value or a value of type 'a. The type can be declared using F#/ML notation like this: type Option<'a> = Some of 'a | None AsStep : Option<'a> -> OptionStep<'a> OptionResult.Create : 'a -> OptionResult<'a> after performing every single step of the computation, which signi¯cantly complicates the code 2.
To show how the code looks when we apply our encoding of the option computation using iterators, we'll use method of the following signature:
sponds to the monadic bind operation. It takes the option value and composes it with the computation that ParseInt : string -> Option<int> follows the yield return call. The second method builds a helper that represents monadic unit opera
The method returns Some(n) when the parameter tion. That means that the computation should end is a valid number and otherwise it returns None. Now returning the speci¯ed value as the result. we can write code that reads a string, tries to parse it and returns 10 times the number if it succeeds. The result of the computation will again be the option type. 3.2 Executing option calculation 1: IEnumerator<IOption> ReadInt() { When we write code in the style described in the previ2: Console.Write("Enter a number: "); ous section, methods like ReadInt only return a state 3: var optNum = ParseInt(Console.ReadLine()); machine that generates a sequence of helper objects 4: var m = optNum.AsStep(); representing bind and unit. This alone wouldn't be at 5: yield return m; all useful, because we want to execute the computa6: Console.WriteLine("Got a valid number!"); tion and get a value of the monadic type (in this case 7: var res = m.Value * 10; Option<'a>) as the result. How to do this in terms of 8: yield return OptionResult.Create(res); standard monadic operations is described in section 5, 9: } but from the end user perspective, this simply means
The code reads a string from the console and calls invoking the Apply method: the ParseInt method to get optNum value, which has Option<int> v = ReadInt().Apply<int>(); a type Option<int> (line 3). Next, we need to per- Console.WriteLine(v); form non-standard value binding to access the value and to continue running the rest of the computation This is a simple piece of standard C# code that only when the value is present. Otherwise the method runs the state machine returned by the ReadInt can return None as the overall result straight ahead. method. Apply<'a> is an extension method 4 de¯ned
To perform the value binding, we use the AsStep for the IEnumerator<IOption> type. Its type signamethod that generates a helper object (line 4) and ture is: then return this object using yield return (line 5).
This creates a \hole" in the code, because the rest of Apply : IEnumerable<IOption> -> Option<'a> the code may or may not be executed, depending on whether the MoveNext method of the returned state The type parameter (in the case above int) specimachine is called again or not. When optNum contains ¯es what the expected return type of the computation a value, the rest of the code will be called and we can is, because this unfortunately cannot be safely tracked access the value using the Value property (line 7)3. in the type system. Running the code with di®erent
Finally, the method calculates the result (line 7) inputs gives the following console output: and returns it. To return from a non-standard compu- Enter a number: 42 Enter a number: $%?! tation written using our encoding, we create another Got a valid number! None helper object, this time using OptionResult.Create Some(420) method. These helper objects are processed when executing the method. Strictly speaking, Apply doesn't necessarily have
To summarize, there are two helper objects. Both to execute the code, because its behavior depends on
of them implement the IOption interface, which the monadic type. The Option<'a> type represents
means that they can both be generated using yield re- a value, so the computation that produces it isn't
deturn. The methods that create these two objects have layed. On the other hand the Async<'a> type, which
the following signatures: represents asynchronous computations is delayed
meaning that the Apply method will only build a
com2 We could as well use exceptions, but it is generally ac- putation from the C# compiler generated state
macepted that using exceptions for control °ow is a wrong chine.
practice. In this case, the missing value is an expected
option, so we're not handling exceptional condition. 4 Extension methods are new feature in C# 3.0. They
3 The F# code corresponding to these two lines is: let! are standard static methods that can be accessed using
value = optNum dot-notation as if they were instance methods [
The encoding of non-standard computations 4 wouldn't be practically useful if it didn't allow us to compose code from primitive functions and as we'll see in the next section, this is indeed possible.
As discussed in the introduction, writing non-blocking code in C# is painful even when we use latest C# features such as lambda expression. In fact, we haven't even implemented a simple loop, because that would 3.3 Composing option computations make the code too lengthy. We've seen that monadic computations provide an excellent solution 5 and we've seen that these can be encoded in C# using iterators.
When encoding monadic operations, we're working As next, we'll explore one larger example that folwith two di®erent types. The methods we write using lows the same encoding of monadic computations as the iterator syntax return IEnumerator<IOption>, the one in the previous section, but uses a di®erent but the actual monadic type is Option<'a>. monad to write asynchronous code that doesn't block When writing code that is divided into multi- the tread when performing long-running I/O. The folple methods, we need to invoke method return- lowing method reads the entire content of a stream ing IEnumerator<IOption> from another method in a bu®ered way (using 1kb bu®er) performing each written using iterators. The following example uses read asynchronously. the ReadInt method from the previous page to read two integer values (already multiplied by 10) and add 1: IEnumerator<IAsync> ReadToEndAsync(Stream s) them. {
Case study: asynchronous C#
the ReadInt to build a C# state machine. To make 14: the result useable, it converts it into a value of type 15: } Option<int> (using the Apply method) and ¯nally uses the AsStep method to get a helper object that The code uses standard while loop which would be can be used to bind the value using yield return. previous impossible. Inside the body of the loop, the
We could of course provide a method composed method creates an asynchronous operation that reads from Apply and AsStep to make the syntax more con- 1kb of data from the stream into the speci¯ed bu®er venient, but this paper is focused on explaining the (line 6) and runs the operation by yielding it as a value principles, so we write this composition explicitly. from the iterator (line 7). The operation is then exe
The previous example also nicely demonstrates the cuted by the system and when it completes the iterator non-standard behavior of the computation. When it is resumed. It stores the bytes to a temporary storage calls the RadInt method for the second time (line 4) and continues looping until the input stream is fully it does that after using non-standard value binding processed. Finally, the method reads the data using (using yield return on line 3). This means that the StreamReader to get a string value and returns this user will be asked for the second number only if the value using AsyncResult.Create method (line 14). ¯rst input was a valid number. Otherwise the result of The encoding of asynchronous computations is esthe overall computation will immediately be None. sentially the same as the encoding of computations
Calculating with options nicely demonstrates the with option values. The only di®erence is that the principles of writing non- standard computations. We method now generates a sequence of IAsync values. can use non-standard bindings to mark places where Also, the AsStep method now returns an object of type the code can abandon the rest of the code if it already AsyncStep<'a> and similarly, the helper object used knows the overall result. Even though this is already 5 To justify this, we can say that asynchronous work°ows useful, we can make even stronger point to support are one of the important features that contributed to the idea by looking at asynchronous computations. the recent success of the F# language. for returning the result is now AsyncResult<'a>. write code that is generic over the monadic type Thanks to the systematic encoding described in sec- (e.g. Option<'a> and Async<'a>). As a result, we tion 5, it is very easy to use another non-standard need to de¯ne a new set of helper objects for each type computation once the user understands one example. of computation. To make this task easier, we provide
The method implemented in the previous listing two base classes that encapsulate functionality that is very useful and surprisingly, it isn't available in can be reused. The code that we need to write is the the standard .NET libraries. We'll use it to asynchro- same for every computation, so writing it is a straightnously download the entire web page. However, we forward task that could be even performed by a very ¯rst need to asynchronously get the HTTP response, simple code-generator tool. so we'll write the code as another asynchro- In this section, we'll look at the code that needs nous method using iterator syntax. In section 3.3, to be written to support calculations working with we've seen how to compose option computations and option values that we were using in section 3. The since the principle is the same, it isn't surprising that code uses only two computation-speci¯c operations. composing asynchonous computations is also straight- Indeed, these are the two operations bind and unit forward: that are used to de¯ne monadic computations in functional programming (\O" is a shortcut for \Option"): 1: var stream = resp.Value.GetResponseStream(); 2: var html = ReadToEndAsync(stream). 3: Execute<string>().AsStep(); 4: yield return html; 5: Console.WriteLine(html.Value); Bind : O<'a> -> ('a -> O<'b>) -> O<'b> Return : 'a -> O<'a>
the second parameter to calculate the result when the
The listing assumes that we already have a re- ¯rst parameter contains a value. The unit operation
sponse object (resp). So far we haven't seen how to ac- wraps an ordinary value into an option value. The
tually start the download, because asynchronous com- implementation of these operations is described
elseputations are delayed, meaning that we're just con- where, so we won't discuss it in detail. You can for
exstructing a function that can be executed later. This ample refer to [
Implementing the functionality we presented are returned from the iterator. We've seen that we in this section asynchronously using the usual style need two helper objects - one that corresponds to bind would be far more complicated. For example, to imple- and one that corresponds to unit. These two objects ment the ReadToEndAsync method we need two times share common interface (called IOption in case of opmore lines of very dense C# code. However, the code tion computations) so that we can generate a single also becomes hard to read because it cannot use many sequence containing both of them. Let's start by lookhigh-level language features (e.g. while loop), so it ing at the interface type: would in addition also require a decent amount of comments6. interface IOption {
Option<R> BindStep<R>(Func<Option<R>> k); 5
}
As we've seen in the previous two sections, writing that executes the non-standard computation (we'll dismonadic computations in C# using iterators requires cuss it later in section 5.2). The parameter k speci¯es several helper objects and methods. In this section, a continuation, that is, a function that can be exewe'll look how these helpers can be de¯ned. cuted to run the rest of the iterator. The continuation
Unfortunately, C# doesn't support higher-kinded doesn't take any parameters and returns an option
polymorphism, which is used when de¯ning monads in value generated by the rest of the computation. The
Haskell and is available in some object-oriented lan- implementation of the helper objects that implement
guage such as Scala [
(this IEnumerator<IOption> en) { if (!en.MoveNext()) throw new InvalidOperationException
("Enumerator ended without a result!"); return en.Current.BindStep<R>(() =>
en.Apply<R>()); } } class OptionStep<T> : MonadStep<T>, IOption { internal Option<T> Input { get; set; } public Option<R> BindStep<R>(Func<Option<R>> k) { return OptionM.Bind(Input, MakeContinuation(k)); } } class OptionResult<T> : MonadReturn<T>, IOption { internal OptionResult(T value) : base(value) { } public Option<R> BindStep<R> (Func<Option<R>> k) { return OptionM.Return(GetResult<R>()); } }
The OptionStep<'a> type has a property named Input that's used to store the option value from which the step was constructed using the AsStep method. The method starts by invoking the MoveNext When the BindStep method is executed the object method of the generated iterator to move the iterauses the monadic bind operation and gives it the input tor to the next occurrence of the yield return stateas the ¯rst argument. The second argument is more in- ment. If the return value is false, the iterator ended teresting. It should be a function that takes the actual without returning any result, which is invalid, so the value extracted from the input option value as an ar- method throws an exception. gument and returns a new option value. The extracted If the iterator performs the step, we can access the value can be used to calculate the result, but there is next generated helper object using the en.Current no way to pass a value as an argument back to the it- property. The code simply invokes BindStep of the erator in the middle of its evaluation, which is why the helper and gives it a function that recursively calls the function given as the parameter to BindStep method Apply method on the same iterator as the argument. doesn't take any parameters. Note that when the helper is OptionResult<'a>, the
As we've seen in the examples, the continuation isn't used, so the recursion terminates. OptionStep<'a> helper exposes this value as the It is worth noting that for monadic computations Value property. This property is inherited from the with zero operation we can also write a variant of MonadStep<'a> type. The MakeContinuation which the Apply method that doesn't require the iterator we use to build a parameter for monadic bind oper- to complete by returning a result. In that case, we'd ation is also inherited and it simply stores the input modify the method to return a value constructed by obtained from bind into Value, so that it can be used the monadic zero operation instead of throwing an exin the iterator and then runs the parameter-less con- ception in the case when the iterator ends. tinuation k. Finally, there are also some problems with using
The OptionResult<'a> type is a bit simpler. It possibly deeply nested recursive calls in a language
has a constructor that creates the object with some that doesn't guarantee the use of tail-recursion. We
value as the result. Inside the BindStep method, it can overcome this problem by using some technique for
uses the monadic unit operation and gives it that value tail-call elimination. Schinz [
also developed a translation semantics for the library.
5.2 Implementing iterator evaluation We ¯rst de¯ne an abstract language extension for C#
that adds monadic compuations as a language feature
Once we have an iterator written using the helpers to C# in a way similar to F#. Then we show that any
described in the previous section, we need some way code written in the extended C# can be translated
for executing it using the non-standard behavior of to the standard C# 2.0 by using the iterator encoding
presented in this article. The grammar of the language
extension as well as the semantic rules are available in
the online supplementary material [
There is actually one more way for writing some monadic computations in C# using the recently added query syntax. The syntax is very limited, but may be suitable for some computations. We'll brie°y review this option and then discuss other relevant related work and conclusions of this paper. 6.1
many functional features to C++, including monads, which means it should be possible to use it for reimplementing some examples from this paper.
There are also several libraries that use C#
iterators for encoding asynchronous computations. CCR [
Richter's library [
As many people already noted [
However, we described a general mechanism that can be useful for other computations as well. We believe that using it to implement for example a prototype of software transactional memory support for C# can bring many other interesting results.
The implementation of library that allows this kind
of syntax is relatively easy and is described for
example in [
However, there are no high-level imperative constructs such as loops which were essential for the asynchronous example in section 4. With some care, it is possible to de¯ne several mutually recursive queries, but that still makes it hard to write complex computations such as the one in section 4.
On the other hand, query syntax is suitable for
some monadic computations where we're using only
a limited language. Parser combinators as described
for example in [