Encoding monadic computations in C# using iterators Tomas Petricek Charles University in Prague, Faculty of Mathematics and Physics tomas@tomasp.net Abstract. Many programming problems can be eas- ming mechanism based on shared memory, which ily solved if we express them as computations with some avoids the need for explicit locking [3]. non-standard aspect. This is a very important problem, be- The motivation for this article is that we want to cause today we’re struggling for example to efficiently pro- be able to use the techniques just described in a main- gram multi-core processors and to write asynchronous code. stream and widely used C# language. The main con- Unfortunately main-stream languages such as Java or C# tributions of this paper are following: don’t support any direct way for encoding unrestricted non- standard computations. In languages like Haskell and F#, • As far as we’re aware, we show for the first time this can be done using monads with syntactic extensions they provide and it has been successfully applied to a wide that monadic computations can be encoded in C# range of real-world problems. In this paper, we present in a syntactically convenient way without placing a general way for encoding monadic computations in the any restrictions on the C# statements that can C# 2.0 language with a convenient syntax using an exist- be used inside the computation. This can be done ing language feature called iterators. This gives us a way to purely as a library without changing the language use well-known non-standard computations enabling easy using widely adopted C# 2.0 features (Section 3). asynchronous programming or for example the use of soft- • We use the presented technique to implement a li- ware transactional memory in plain C#. Moreover, it also brary that makes it easier to write scalable multi- opens monads in general to a wider audience which can threaded applications that perform long running help in the search for other useful and previously unknown I/O operations. We demonstrate it using several kinds of computations. case study examples (Section 4). • Finally, we describe a method for systematical en- coding of arbitrary monadic computation in C# 1 Introduction (Section 5). This technique can be used for imple- menting other useful computations such as soft- In functional programming languages such as Haskell ware transactional memory and others. and F#, monadic computations are used to solve wide There are several related projects, mostly con- range of problems. In Haskell [5], they are frequently cerned with asynchronous programming (Section 6), used to deal with state or I/O, which is otherwise diffi- but our aim is wider and focuses on monadic computa- cult in a purely functional language. F# uses monadic tions in general. However, asynchronous computations computations to add non-standard aspects such as can nicely demonstrate the problem. asynchronous evaluation, laziness or implicit error handling to an existing piece of code written in F#. In this article, we’ll prefer the F# point of view, meaning 1.1 Asynchronous computations in C# today that we want to be able to adjust C# code to execute differently, using additional aspects provided by the Since we’re using asynchronous computations as the monadic computation. primary real-world motivation for this paper, we The primary motivation for this work is that should first 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 first 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 workflows [16] which make it easy to write 4: var read = strm.Read(buffer, 0, 1024); communication with the web and other I/O operations in the natural sequential style, but without blocking On lines 2 and 4 we’re performing I/O operations threads while waiting. In Haskell, monadic compu- that can take a long time, but that aren’t CPU tations are used for example to implement software bounded. When running the operation, the executing transactional memory, which is a concurrent program- thread will be blocked, but it cannot perform any other 62 Tomas Petricek work in the meantime. If we wanted to run hundreds computations that is already defined 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 significant 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 in- cluding for example the while loop: 1: var req = HttpWebRequest.Create(url); 2: req.BeginGetResponse(a1 => { 1: let downloadUrl(url:string) = async { 3: var rsp = req.EndGetResponse(a1); 2: let req = HttpWebRequest.Create(url) 4: var strm = rsp.GetResponseStream(); 3: let! rsp = req.AsyncGetResponse() 5: strm.BeginRead(buffer, 0, 1024, a2 => { 4: let strm = rsp.GetResponseStream() 6: int read = strm.EndRead(a2); 5: let buffer = Array.zeroCreate(8192) 7: // ... 6: let state = ref 1 8: }, null); 7: while !state > 0 do 9: }, null); 8: let! read = strm.AsyncRead(buffer,0, 8192) 9: Console.WriteLine("got {0}b", read); In this context “asynchronous” means that the pro- 10: state := read } gram invokes start of the operation, registers a call- back, 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 specifies 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 first 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 difficult, because value binding. This means that instead of simply as- we 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 specifies non-standard behavior of the model does not in principle increase the CPU par- operation. In this case the behavior is that the opera- allelism in the application, but it still significantly 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 defines the meaning of other primitive constructs such number of (expensive) threads the application creates. as the while loop or returning the result from a func- tion. These primitive operations are exposed as stan- 2 Background dard methods with well-defined type signatures: Bind : Async<’a> * (’a -> Async<’b>) -> To write non-blocking asynchronous code, we can use Async<’b> continuation passing style where the next piece of code Return : ’a -> Async<’a> to execute after an operation completes is given as While : (unti -> bool) * Async -> a function as the last argument to the operation. In Async the snippet above we’ve written the code in this style explicitly, but as we’ve seen this isn’t a satisfying so- The first two functions are standard operations lution. that define the abstract monadic type as first described in [18]. These operations are also called bind 2.1 F# asynchronous workflows and unit. The Bind member takes an existing compu- tation and a function that specifies how to produce In F#, we can use asynchronous workflows, which subsequent computation when the first one completes is one particularly useful implementation of monadic and composes these into a single one. The Return Encoding monadic computations in C# 63 member builds a computation that returns the given to the console, so the program above shows the “gen- value. The additional While member takes a predicate erating” message directly followed by “got” for num- and 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 ex- pressions, the F# compiler syntactically transforms • The iterator body can contain usual control struc- the code into code composed from the calls to these tures such as loops or exception handlers and the primitive operations. The translated version of the compiler automatically turns them into a state previous example can be found in the online supple- machine. mentary material for the article [12]. • The state machine can be executed only to a cer- tain point (explicitly specified by the user using yield return), then paused and later resumed 2.2 C# Iterators again by invoking the MoveNext method again. One of the non-standard computations that is very of- ten used in practice is a computation that generates In many ways this resembles the continuation pass- a sequence of values instead of yielding just a single ing style from functional languages, which is essen- result. This aspect is directly implemented by C# it- tial for monadic computations and F# asynchronous erators [2], but without any aim to be more generally workflows. useful. In this article, we show that it can be used in a more general fashion. However, we start by briefly introducing iterators. The following example uses it- 3 Monadic computations in C# erators to generate a sequence of all integers: Now that we’ve introduced asynchronous workflows 1: IEnumerator GetNumbers() { in F# (as an example of monadic computations) and 2: int num = 0; C# iterators, we can ask ourselves the question 3: while (true) { whether iterators could be used for encoding other 4: Console.WriteLine("generating {0}", num); 5: yield return num++; non-standard computations then code that generates 6: } a sequence. 7: } The key idea of this article is that it is indeed pos- sible to do that and that we can write standard C# li- The code looks just like ordinary method brary to support any monadic computation. In this with the exception that it uses the yield return section, we’ll briefly introduce how the library looks keyword to generate elements a sequence. The while using the simplest possible example and in section 5 loop may look like an infinite loop, but due to the we’ll in detail explain how the encoding works. 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 Using option computations quence lazily one by one. The returned object of type IEnumerator can be used in the following way: As the first example, we’ll use computations that pro- duce value of type Option<’a> 1 , which can either 1: var en = GetNumbers(); contain no value or a value of type ’a. The type can 2: en.MoveNext(); be declared using F#/ML notation like this: 3: Console.WriteLine("got {0}", en.Current); 4: en.MoveNext(); type Option<’a> = Some of ’a | None 5: Console.WriteLine("got {0}", en.Current); Code that is composed from simple computations 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 computa- erated by the compiler. The variables used inside the tion. In practice this is useful for example when per- method 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 snip- pet) updating the state of the state machine. This also 1 In Haskell, this type is called Maybe and the correspond- executes all side-effects of the iterator such as printing ing computation is known as Maybe monad. 64 Tomas Petricek after performing every single step of the computation, AsStep : Option<’a> -> OptionStep<’a> which significantly complicates the code 2 . OptionResult.Create : ’a -> OptionResult<’a> To show how the code looks when we apply our encoding of the option computation using iterators, The first method creates an object that corre- we’ll use method of the following signature: sponds to the monadic bind operation. It takes the op- tion value and composes it with the computation that ParseInt : string -> Option 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 specified 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 re- sult of the computation will again be the option type. 3.2 Executing option calculation 1: IEnumerator ReadInt() { When we write code in the style described in the previ- 2: 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 computa- 6: 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 invoking the Apply method: The code reads a string from the console and calls the ParseInt method to get optNum value, which has Option v = ReadInt().Apply(); a type Option (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 defined To perform the value binding, we use the AsStep for the IEnumerator type. Its type signa- method 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 -> Option<’a> the code may or may not be executed, depending on The type parameter (in the case above int) speci- whether the MoveNext method of the returned state fies what the expected return type of the computation machine is called again or not. When optNum contains is, because this unfortunately cannot be safely tracked a value, the rest of the code will be called and we can in the type system. Running the code with different access the value using the Value property (line 7)3 . inputs gives the following console output: Finally, the method calculates the result (line 7) 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 ex- ecuting 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 de- turn. 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 2 meaning that the Apply method will only build a com- We could as well use exceptions, but it is generally ac- putation from the C# compiler generated state ma- cepted that using exceptions for control flow is a wrong chine. practice. In this case, the missing value is an expected 4 option, so we’re not handling exceptional condition. 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 [1]. Encoding monadic computations in C# 65 The encoding of non-standard computations 4 Case study: asynchronous C# wouldn’t be practically useful if it didn’t allow us to compose code from primitive functions and as we’ll see As discussed in the introduction, writing non-blocking in the next section, this is indeed possible. 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 fol- with two different types. The methods we write using lows the same encoding of monadic computations as the iterator syntax return IEnumerator, the one in the previous section, but uses a different 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 fol- ple methods, we need to invoke method return- lowing method reads the entire content of a stream ing IEnumerator from another method in a buffered way (using 1kb buffer) 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 ReadToEndAsync(Stream s) them. { 2: var ms = new MemoryStream(); 3: byte[] bf = new byte[1024]; 1: IEnumerator TryCalculate() { 4: int read = -1; 2: var n = ReadInt().Apply().AsStep(); 5: while (read != 0) { 3: yield return n; 6: var op = s.ReadAsync(bf, 0, 1024). 4: var m = ReadInt().Apply().AsStep(); AsStep(); 5: yield return m; 8: yield return op; 6: var res = m.Value + n.Value; 9: ms.Write(bf, 0, op.Value); 7: yield return OptionResult.Create(res); 10: read = op.Value; 8: } 11: } 12: ms.Seek(0, SeekOrigin.Begin); 13: string s = new StreamReader(ms). When the method needs to read an integer, it calls ReadToEnd(); the ReadInt to build a C# state machine. To make 14: yield return AsyncResult.Create(s); the result useable, it converts it into a value of type 15: } Option (using the Apply method) and finally 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 specified buffer 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). first input was a valid number. Otherwise the result of The encoding of asynchronous computations is es- the 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 difference 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 workflows 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. 66 Tomas Petricek 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 define 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 straight- nously download the entire web page. However, we forward task that could be even performed by a very first 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-specific operations. composing asynchonous computations is also straight- Indeed, these are the two operations bind and unit forward: that are used to define monadic computations in func- tional programming (“O” is a shortcut for “Option”): 1: var stream = resp.Value.GetResponseStream(); 2: var html = ReadToEndAsync(stream). Bind : O<’a> -> (’a -> O<’b>) -> O<’b> 3: Execute().AsStep(); Return : ’a -> O<’a> 4: yield return html; 5: Console.WriteLine(html.Value); The bind operation uses the function provided as the second parameter to calculate the result when the The listing assumes that we already have a re- first 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 else- putations are delayed, meaning that we’re just con- where, so we won’t discuss it in detail. You can for ex- structing a function that can be executed later. This ample refer to [11]. We’ll just assume that we already makes it possible to compose large number of compu- have OptionM type with the two operations exposed tations and spawn them in parallel. The runtime then as static methods. uses only a few threads, which makes it very efficient and scalable. You can find full example that shows how to start the download in the online supplemen- 5.1 Defining iterator helpers tary material for the article [12] As a first thing, we’ll implement helper objects that 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 op- more 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 look- high-level language features (e.g. while loop), so it ing at the interface type: would in addition also require a decent amount of com- ments6 . interface IOption { Option BindStep(Func> k); } 5 Encoding arbitrary monads The BindStep method is invoked by the extension As we’ve seen in the previous two sections, writing that executes the non-standard computation (we’ll dis- monadic computations in C# using iterators requires cuss it later in section 5.2). The parameter k specifies several helper objects and methods. In this section, a continuation, that is, a function that can be exe- we’ll look how these helpers can be defined. 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 defining 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 [10]. This means that we can’t the interface looks like this: 6 The source code implementing the same functionality in the usual style can be found in [12] Encoding monadic computations in C# 67 class OptionStep : MonadStep, IOption { the monadic computation. The purpose of the itera- internal Option Input { get; set; } tor isn’t to create a sequence of values, so we need to public Option BindStep(Func> k) execute it in some special way. The following example { shows an extension method Apply that turns the iter- return OptionM.Bind(Input, ator into a monadic value. In case of options the type MakeContinuation(k)); of the value is Option<’a> but note that the code } } will be exactly the same for all computation types. class OptionResult : MonadReturn, IOption static class OptionExtensions { { public static Option Apply internal OptionResult(T value) : base(value) (this IEnumerator en) { { } if (!en.MoveNext()) public Option BindStep (Func> throw new InvalidOperationException k) { ("Enumerator ended without a result!"); return OptionM.Return(GetResult()); return en.Current.BindStep(() => } en.Apply()); } } 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 itera- uses the monadic bind operation and gives it the input tor to the next occurrence of the yield return state- as the first 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 ex- in 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 [15] gives a good overview as the parameter. This cannot be done in a statically in the context of the Scala language. Perhaps the eas- type-checked way, so we use the inherited GetResult iest option to implement is to use a trampoline [17]. method that performs dynamic type conversion. Fi- nally, the OptionResult.Create and AsStep meth- 5.3 Translation semantics ods are just simple wrappers that construct these two objects in the syntactically most pleasant way. To formalize the translation in a more detail, we’ve also developed a translation semantics for the library. 5.2 Implementing iterator evaluation We first define 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 68 Tomas Petricek presented in this article. The grammar of the language many functional features to C++, including monads, extension as well as the semantic rules are available in which means it should be possible to use it for re- the online supplementary material [12]. implementing some examples from this paper. There are also several libraries that use C# itera- tors for encoding asynchronous computations. CCR [7] 6 Related work and conclusions is a more sophisticated library that combines join pat- terns with concurrent and asynchronous program- There is actually one more way for writing ming, which makes it more powerful than our encod- some monadic computations in C# using the recently ing. On the other hand it is somewhat harder to use for added query syntax. The syntax is very limited, but simple scenarios such as those presented in this paper. may be suitable for some computations. We’ll briefly Richter’s library [13] is also focused primarily on review this option and then discuss other relevant re- asynchronous execution. It uses yield return primitive lated work and conclusions of this paper. slightly differently - to specify the number of opera- tions that should be completed before continuing the 6.1 LINQ queries execution of the iterator. The user can then pop the results from a stack. As many people already noted [8], the LINQ query syntax available in C# 3.0 is also based on the idea of monad and can be used more broadly than just 7 Conclusions for encoding computations that work with lists. The following example shows how we could write the com- In this paper, we have presented a way for encoding putation with option values using LINQ syntax: monadic computations in the C# language using iter- ators. We’ve demonstrated the encoding with two ex- 1: Option opt = 2: from n in ReadInt() amples - computations that work with option values 3: from m in ReadInt() and computations that allow writing of non-blocking 4: let res = m + n asynchronous code. 5: select res; The asynchronous library we presented is useful in practice and would alone be an interesting result. The implementation of library that allows this kind However, we described a general mechanism that can of syntax is relatively easy and is described for exam- be useful for other computations as well. We believe ple in [11]. This syntax is very restricted. In it allows that using it to implement for example a prototype non-standard value bindings corresponding to the bind of software transactional memory support for C# can operation using the from keyword (lines 2 and 3), stan- bring many other interesting results. dard value bindings using the let construct (line 4) and returning of the result using select keyword (line 5). However, there are no high-level imperative constructs References such as loops which were essential for the asynchro- nous example in section 4. With some care, it is pos- 1. G.M. Bierman, E. Meijer, M. Torgersen: Lost in trans- lation: formalizing proposed extensions to C#. In Pro- sible to define several mutually recursive queries, but ceedings of OOPSLA 2007. that still makes it hard to write complex computations 2. ECMA International.: C# Language Specification. such as the one in section 4. 3. T. Harris, S. Marlow, S. Peyton-Jones, M. Herlihy: On the other hand, query syntax is suitable for Composable memory transactions. In Proceedings of some monadic computations where we’re using only PPoPP 2005. a limited language. Parser combinators as described 4. L. Hoban: Monadic parser combinators us- for example in [6] can be defined using the query syn- ing C# 3.0. Retrieved May 2009, from tax [4]. In general, C# queries are a bit closer to writ- http://blogs.msdn.com/lukeh/archive/2007/08/19/ ing monads using the Haskell’s list comprehension no- monadic-parser-combinators-using-c-3-0.aspx tation, while using iterators as described in this article 5. P. Hudak, P. Wadler, A. Brian, B.J. Fairbairn, J. Fasel, is closer to the Haskell’s do-notation. K. Hammond et al.: Report on the programming lan- guage Haskell: A non-strict, purely functional lan- guage. ACM SIGPLAN Notices. 6.2 Related work 6. G. Hutton, E. Meijer: Monadic parser combinators. Technical Report. Department of Computer Science, The principle of using a main-stream language for en- University of Nottingham. coding constructs from the research world has been 7. G. Chrysanthakopoulos, S. Singh: An asynchronous used with many interesting features including for ex- messaging library for C#. In proceedings of SCOOL ample Joins [14]. FC++ [8] is a library that brings Workshop, OOPSLA, 2005. Encoding monadic computations in C# 69 8. B. McNamara, Y. Smaragdakis: Syntax sugar for FC++: lambda, infix, monads, and more. In Proceed- ings of DPCOOL 2003. 9. E. Meijer: There is no impedance mismatch (Language integrated query in Visual Basic 9). In Dynamic Lan- guages Symposium, Companion to OOPSLA 2006. 10. A. Moors, F. Piessens, M. Odersky: Generics of a higher kind. In Proceedings of OOPSLA 2008. 11. T. Petricek, J. Skeet: Functional Programming for the Real World. Manning, 2009. 12. T. Petricek: Encoding monadic computations us- ing iterators in C# 2.0 (Supplementary mate- rial). Available at http://tomasp.net/academic/ monads-iterators.aspx 13. J. Richter: Power threading library. Retrieved May 2009, from http://www.wintellect.com/ PowerThreading.aspx 14. C.V. Russo: The Joins concurrency library. In Pro- ceedings of PADL 2007. 15. M. Schinz, M. Odersky: Tail call elimination on the Java Virtual Machine. In Proceedings of BABEL 2001 Workshop on Multi-Language Infrastructure and In- teroperability. 16. D. Syme, A. Granicz, A. Cisternino: Expert F#, Apress, 2007. 17. D. Tarditi, A. Acharya, P. Lee: No assembly required: Compiling standard ML to C. School of Computer Sci- ence, Carnegie Mellon University. 18. P. Wadler: Comprehending monads. In Proceedings of ACM Symposium on Lisp and Functional Program- ming, 1990.