Asynchronous Programming and Computation Expressions
In previous notes ( part I , part II ) about async / await in C # 5, I wrote that a similar approach was implemented in languages like Haskell, F # and Nemerle, but, unlike C #, these languages support a higher level concept, which allows you to implement asynchronous computing in the async / await style as a library, and not at the language level. It's funny that in Nemerle this concept itself is implemented as a library. The name of this concept is monad. In addition to asynchronous calculations, monads allow you to implement other goodies, such as list comprehension, continuation, the transformation of dirty functions into a pure block, through which the state is implicitly pulled, and many others.
Some monads implement such "Wishlist" C # programmers, such as yield collections or yield foreach and yield from lambda expressions.
The purpose of this note is an introduction to asynchronous programming and computation expressions in Nemerle, but it can also be useful to those who study F #, so the implementation of asynchronous programming in Nemerle was done with an eye to it in F #. On the other hand, someone may be interested in how some tasks that are a problem in other languages ( after all asynchronous calls ) are solved using computation expressions in a couple of lines.
')
Probably everyone who realized what a monad is, writes an article about what a monad is. I was no exception. I will try to make the description as concisely as possible so that those who know will remember, and others will be able to understand the further narration.
A monad is a generative pattern whose support is built into the language. The basis for the implementation of this pattern is the following pair:
polymorphic type
and a couple of operations on it
Return allows you to wrap any value into a monad, and Bind to transform it. A very weak analogy can be made with StringBuilder, which is passed an initial value in the constructor parameter, and then modified using the Append * methods.
If you replace F with IEnumerable, then the Bind signature resembles the SelectMany signature from Linq. This is not surprising, since Linq with great reservations is also a monad. By the way, this was interestingly told by Bart De Smet at PDC2010 with the report “LINQ, Take Two - Realizing the LINQ to Everything Dream” ( link ).
If Linq is a monad, then try to draw a simple Linq expression:
using M-operations. At the beginning we declare M-operations:
And rewrite the Linq expression:
It turned out even worse than with Linq, but this is because monad support is not built into C #. In the case of Nemerle, this code can be as follows, we declare M-operations:
And rewrite the Linq expression:
In the beginning, we recall that def in Nemerle is a non-convenient analogue of var in C #, if the ternary operator (? :), and a constructor call does not require new. Now to the point, the comp statement declares the beginning of monadic calculations, the parameter following it provides the M-operations, and then the calculations themselves go.
Compared to Linq, we have three lines, instead of one, but these lines look like ordinary code that works with one variable, and in fact it generates a new collection from the original one. This example is provided for training purposes, below are examples that repeat the usual code is very difficult. We will understand how it works.
defcomp is a magic operator that “turns” the monad (in this case, of type IEnumerable [T]) into a value (of type T), and return, conversely, translates the value into a monad. In fact, there is no magic, just an expression
revealed by the compiler in
If we were discussing the Haskell language, then the story about monads could be finished. But in the case of hybrid languages (functional / imperative), the situation is a bit more complicated, as there are such control structures as conditional, loop and yield operators. To understand how this presents a problem, one can try to express through M-operations monadic calculations, which contain a cycle, and inside the cycle, the defcomp operator.
The solution to this problem is quite simple, you need to add methods to the set of M-operations that deal with the transformation of branch operators and cycles, for example, while it will have the following signature:
And when the compiler encounters a loop whose body contains monadic operators, it first transforms the loop body into a Bind chain, since Bind returns F <T>, then this chain can be wrapped in lambda "() => body ()", like Func <F <T >>, as well, the compiler wraps the loop condition in lambda, and then passes those lambdas to the While m-operation.
Each M-operation should return a monad, but the cycle returns nothing, therefore there is no value that can be wrapped into a monad. For these purposes, the FakeVoid singelton is used.
Now you can give an informal description of the computation expression, it is a monad for imperative languages. In the case of a-la haskell, the compiler rewrites only defcomp and return within monadic calculations, as already noted in the case of imperative languages, the control structures are also rewritten, in the table below are all the operators that are rewritten:
Just a couple of words about M-operations providers. Officially, they are called builders, and when building a computation expression, duck typing is used, that is, builders must contain methods that the compiler uses, but the builder is not required to implement any interface. This solution allows to partially implement builders if it is planned to use not all features in the computation expression. By the way, we have already used this approach when creating the MList builder (only defcomp and return support is implemented).
Another reason why the interfaces are not used is that they impose a stricter condition on the signature of M-operations. Only compatibility of monads and M-operations by type is required. For example, in the examples above it was assumed that the monad has one generic parameter, but it can easily have several of them, for further narration this is not important, but it can be studied using the example of the Continuation monad.
For those who want to write their builders, the best advice is to study the source code of Computation expressions .
Standard builders are built into the Computation Expressions library, and instead of creating an instance of them and passing comp as a parameter, you just need to pass their name as a parameter.
The list builder supports standard language control structures, as well as yield and yieldcomp. As a monad, it uses list [T] (the standard list in Nemerle). This builder is interesting in that it implements two long-standing C # programmers of programmers: yield from lambda and yield collections. In the beginning, we will look at the Linq analogue from the beginning of the article:
As you can see, the list builder allows you to use yield expressions in place without requiring you to declare a function for this, you can also use it instead of Link to objects. It seems to me that this code is much easier to read than the equivalent linq expression.
Consider now another “Wishlist” - the yield of the collection, at the beginning I declare a local function that generates a sequence, and then call it two times and make a collection of collections.
I had to write my own generator instead of using “Enumerable.Range (0, 3)” because of the types: yieldcomp expects a monad for input, its type in this case is list [int], and “Enumerable.Range (0, 3) Returns an IEnumerable [int]. To overcome this inconsistency there is another builder - enumerable.
This builder largely repeats the List builder, only uses IEnumerable [T] as a monad type and allows you to build infinite sequences. Rewrite the last example:
Similar to list and enumerable, the array behaves, only uses array [T] as the monad type.
The most difficult, but very useful builder, in many respects resembles the future async / await in C #. It is used to build asynchronous computing, combining already existing asynchronous computing.
It supports all operations except yield and yieldcomp.
The monad type of this builder is Async [T]. Objects of this type describe an asynchronous calculation, the result of which will be a value of type T (like Task <T> in C #), if the asynchronous operation does not return a value, then instead of T a specific type of FakeVoid is used. The Bind operation, its Async [T] * type (T-> Async [U]) -> Async [U], “continues” the asynchronous computation (of the Async [T] type) with a function; this function takes an object of type T (the result asynchronous calculation) and returns a new asynchronous calculation of the type Async [U].
Another key type is the abstract class ExecutionContext, instances of its descendants are responsible for starting an asynchronous operation (for example, in the current thread, in a thread from the ThreadPool or using SynchronizationContext), here is its signature:
To start an asynchronous operation, call the Start method of the object describing the asynchronous operation (Async [T] class), passing it an object of type ExecutionContext, if the method is called without arguments, then the asynchronous operation is started using ThreadPool.QueueUserWorkItem.
In the extension (async CTP), which allows using the async / wait implementation in C #, there are already a lot of extension methods that complement the existing classes with asynchronous operations. In a library with a monad implementation, async does not provide such extensions, but it does provide an easy way to build them on the basis of already existing primitives. For example, consider a part of the existing HttpWebRequest signature, which is responsible for the asynchronous execution of a query that exists from the first version of the framework:
Now we will create an asynchronous extension, which is suitable for use in monadic calculations using these primitives.
It should be recalled that _ in Nemerle is a special character, in this case currying is used through it (the record f (_) is equivalent to x => f (x)). Similarly, wrappers can be created for any standard asynchronous computing.
Let's try on Nemerle to write something from (C # 101) Async samples, for example, parallel loading of several web pages and printing a header, I dropped the code for the extension GetHtml () and GetTitle (), the article was already dragged out.
The first two lines start asynchronous page load operations, these methods return objects describing asynchronous operations at the time of execution, from the compiler's point of view, the type of these objects Async [WebResponce] (monad). In the next two lines, the monad expands into value, at a different level of meaning, it means waiting for results. In the last lines, the results are processed.
It's funny that the post-reasoning about how to properly ( wait for the results of all the asynchronous calls ) to do in javascript turned out to be very hot: 90 favorites, 100 comments. But back to our example.
The main thing to remember is that a monad is a spawning pattern, you have created a function that describes asynchronous computing, but does not trigger it, so you can start it so PrintTitles (). Start (). GetResult (). In fact, this is very important, since it can serve as a source of errors, if the method returns Async [T], you need to be aware of whether this code runs the calculations or only constructs them . For the difference, you probably should use a naming convention, for example, methods that run calculations must have the Async suffix.
In my second article on async / await in C #, I wrote that processing the results of asynchronous calculations await starts in the SynchronizationContext of the thread that started asynchronous calculations. Nemerle in this regard provides for greater flexibility, it is possible to transfer calculations from one stream to another. Consider a button click handler:
First we get the ExecutionContext, which starts the calculations in the current SynchronizationContext, then we describe the asynchronous operation: Thread.Sleep emulates a heavy calculation, switch the execution context to the execution context of the thread gui and output the result. The calculation itself is run in the thread pool's ExecutionContexts.
It looks like magic, but in fact all this has already happened, callcomp just opens the monad when its meaning is not important. But why then open it at all? The point is the side effects and the state, during the monadic operations the state is dragged through them, the monad has access to this state at the time of disclosure and can change it, which is what happens here. In this example, the state stores information in which context to execute the code, and if this information changes, it switches to the new context. For details, I can recommend to go read the source , they are interesting.
In addition to Async.SwitchTo, there are other interesting monads affecting the flow of execution, for example, Async.Yield says that the execution context has changed, although it does not change it. In some cases, this does nothing, in the case where the ThreadPool was used, this action provokes a jump to another thread from the pool.
In conclusion, I can only note that monads are a very rich topic. In this article, I did not touch on such classic monads as State, Cont (continuation), Maybe (another Wishlist C # fanboy). You can read about them in other articles, I tried to give a practical explanation, thanks to which you can start using asynchronous programming and list / enumerable monads in Nemerle and know what is happening under the hood.
In many ways, the implementation of await / async in the future C # and the monadic approach to asynchronous programming in Nemerle are similar, but there is one note to support await / async the next version of the language is needed, and the asynchronous programming in Nemerle is implemented through monads language, not language).
I will be glad to comment and answer questions.
Some monads implement such "Wishlist" C # programmers, such as yield collections or yield foreach and yield from lambda expressions.
The purpose of this note is an introduction to asynchronous programming and computation expressions in Nemerle, but it can also be useful to those who study F #, so the implementation of asynchronous programming in Nemerle was done with an eye to it in F #. On the other hand, someone may be interested in how some tasks that are a problem in other languages ( after all asynchronous calls ) are solved using computation expressions in a couple of lines.
')
Probably everyone who realized what a monad is, writes an article about what a monad is. I was no exception. I will try to make the description as concisely as possible so that those who know will remember, and others will be able to understand the further narration.
Monads
A monad is a generative pattern whose support is built into the language. The basis for the implementation of this pattern is the following pair:
polymorphic type
interface F<T> { ... } and a couple of operations on it
class M { static public F<T> Return<T>(T obj) { ... } static F<U> Bind<T,U>(F<T> obj, Func<T, F<U>> fun) { ... } } Return allows you to wrap any value into a monad, and Bind to transform it. A very weak analogy can be made with StringBuilder, which is passed an initial value in the constructor parameter, and then modified using the Append * methods.
If you replace F with IEnumerable, then the Bind signature resembles the SelectMany signature from Linq. This is not surprising, since Linq with great reservations is also a monad. By the way, this was interestingly told by Bart De Smet at PDC2010 with the report “LINQ, Take Two - Realizing the LINQ to Everything Dream” ( link ).
If Linq is a monad, then try to draw a simple Linq expression:
var nums = Enumerable.Range(-2, 7); var sqrt = from n in nums where n >=0 select Math.Sqrt(n); using M-operations. At the beginning we declare M-operations:
static class MList { static public IEnumerable<T> Return<T>(T obj) { var list = new List<T>(); list.Add(obj); return list; } static public IEnumerable<U> Bind<T, U>(this IEnumerable<T> obj, Func<T, IEnumerable<U>> fun) { return obj.SelectMany(fun); } static public IEnumerable<T> Empty<T>() { return Enumerable.Empty<T>(); } } And rewrite the Linq expression:
var nums = Enumerable.Range(-2, 7); var sqrt = nums .Bind(n => n >= 0 ? MList.Return(n) : MList.Empty<int>()) .Bind(n => MList.Return(Math.Sqrt(n))); It turned out even worse than with Linq, but this is because monad support is not built into C #. In the case of Nemerle, this code can be as follows, we declare M-operations:
class MList { public Return[T](obj : T) : IEnumerable[T] { def data = List(); data.Add(obj); data } public Bind[T, U](obj : IEnumerable[T], f : T->IEnumerable[U]) : IEnumerable[U] { obj.SelectMany(f) } public Empty[T]() : IEnumerable[T] { Enumerable.Empty() } } And rewrite the Linq expression:
def mlist = MList(); def nums = Enumerable.Range(-2, 7); def sqrt = comp mlist { defcomp n = nums; defcomp n = if (n >= 0) mlist.Return(n) else mlist.Empty(); return Math.Sqrt(n :> double); }; In the beginning, we recall that def in Nemerle is a non-convenient analogue of var in C #, if the ternary operator (? :), and a constructor call does not require new. Now to the point, the comp statement declares the beginning of monadic calculations, the parameter following it provides the M-operations, and then the calculations themselves go.
Compared to Linq, we have three lines, instead of one, but these lines look like ordinary code that works with one variable, and in fact it generates a new collection from the original one. This example is provided for training purposes, below are examples that repeat the usual code is very difficult. We will understand how it works.
defcomp is a magic operator that “turns” the monad (in this case, of type IEnumerable [T]) into a value (of type T), and return, conversely, translates the value into a monad. In fact, there is no magic, just an expression
defcomp n = nums; ... revealed by the compiler in
mlist.Bind(nums, n => ...) Computation expressions
If we were discussing the Haskell language, then the story about monads could be finished. But in the case of hybrid languages (functional / imperative), the situation is a bit more complicated, as there are such control structures as conditional, loop and yield operators. To understand how this presents a problem, one can try to express through M-operations monadic calculations, which contain a cycle, and inside the cycle, the defcomp operator.
The solution to this problem is quite simple, you need to add methods to the set of M-operations that deal with the transformation of branch operators and cycles, for example, while it will have the following signature:
public F<FakeVoid> While<T>(Func<bool> cond, Func<F<FakeVoid>> body) And when the compiler encounters a loop whose body contains monadic operators, it first transforms the loop body into a Bind chain, since Bind returns F <T>, then this chain can be wrapped in lambda "() => body ()", like Func <F <T >>, as well, the compiler wraps the loop condition in lambda, and then passes those lambdas to the While m-operation.
Each M-operation should return a monad, but the cycle returns nothing, therefore there is no value that can be wrapped into a monad. For these purposes, the FakeVoid singelton is used.
Now you can give an informal description of the computation expression, it is a monad for imperative languages. In the case of a-la haskell, the compiler rewrites only defcomp and return within monadic calculations, as already noted in the case of imperative languages, the control structures are also rewritten, in the table below are all the operators that are rewritten:
| defcomp | turns monad into value, meaning close to assignment |
| callcomp | expands the monad, is used when the value is not important |
| return | wraps the argument in a monad, is used at the end of the monadic block, meaning close to returning from the function |
| returncomp | the argument is a monad, returns this monad as the result of a block of monadic calculations, unlike return, does not wrap it again |
| yield | wraps the argument into a monad and performs actions similar to yield return |
| yieldcomp | the argument is a monad, performs actions similar to a yield return, unlike yield does not wrap the argument again |
| if, when, unless, while, do, foreach, for, using, try ... catch ... finally | monadic versions of ordinary control structures |
Just a couple of words about M-operations providers. Officially, they are called builders, and when building a computation expression, duck typing is used, that is, builders must contain methods that the compiler uses, but the builder is not required to implement any interface. This solution allows to partially implement builders if it is planned to use not all features in the computation expression. By the way, we have already used this approach when creating the MList builder (only defcomp and return support is implemented).
Another reason why the interfaces are not used is that they impose a stricter condition on the signature of M-operations. Only compatibility of monads and M-operations by type is required. For example, in the examples above it was assumed that the monad has one generic parameter, but it can easily have several of them, for further narration this is not important, but it can be studied using the example of the Continuation monad.
For those who want to write their builders, the best advice is to study the source code of Computation expressions .
Examples of standard builders
Standard builders are built into the Computation Expressions library, and instead of creating an instance of them and passing comp as a parameter, you just need to pass their name as a parameter.
List
The list builder supports standard language control structures, as well as yield and yieldcomp. As a monad, it uses list [T] (the standard list in Nemerle). This builder is interesting in that it implements two long-standing C # programmers of programmers: yield from lambda and yield collections. In the beginning, we will look at the Linq analogue from the beginning of the article:
def num = Enumerable.Range(-2, 7); def sqrt : list[double] = comp list { foreach(n in num) when(n >= 0) yield Math.Sqrt(n); } As you can see, the list builder allows you to use yield expressions in place without requiring you to declare a function for this, you can also use it instead of Link to objects. It seems to me that this code is much easier to read than the equivalent linq expression.
Consider now another “Wishlist” - the yield of the collection, at the beginning I declare a local function that generates a sequence, and then call it two times and make a collection of collections.
def upTo(n) { comp list { for(mutable i=0;i<n;i++) yield i } } def twice = comp list { repeat(2) yieldcomp upTo(3); } Console.WriteLine(twice); //[0, 1, 2, 0, 1, 2] I had to write my own generator instead of using “Enumerable.Range (0, 3)” because of the types: yieldcomp expects a monad for input, its type in this case is list [int], and “Enumerable.Range (0, 3) Returns an IEnumerable [int]. To overcome this inconsistency there is another builder - enumerable.
Enumerable
This builder largely repeats the List builder, only uses IEnumerable [T] as a monad type and allows you to build infinite sequences. Rewrite the last example:
def twice = comp enumerable { repeat(2) yieldcomp Enumerable.Range(0, 3); } foreach(item in twice) Console.Write($"$item "); //0, 1, 2, 0, 1, 2 Array
Similar to list and enumerable, the array behaves, only uses array [T] as the monad type.
Async
The most difficult, but very useful builder, in many respects resembles the future async / await in C #. It is used to build asynchronous computing, combining already existing asynchronous computing.
It supports all operations except yield and yieldcomp.
The monad type of this builder is Async [T]. Objects of this type describe an asynchronous calculation, the result of which will be a value of type T (like Task <T> in C #), if the asynchronous operation does not return a value, then instead of T a specific type of FakeVoid is used. The Bind operation, its Async [T] * type (T-> Async [U]) -> Async [U], “continues” the asynchronous computation (of the Async [T] type) with a function; this function takes an object of type T (the result asynchronous calculation) and returns a new asynchronous calculation of the type Async [U].
Another key type is the abstract class ExecutionContext, instances of its descendants are responsible for starting an asynchronous operation (for example, in the current thread, in a thread from the ThreadPool or using SynchronizationContext), here is its signature:
public abstract class ExecutionContext { public abstract Execute(computatuion : void -> void) : void; } To start an asynchronous operation, call the Start method of the object describing the asynchronous operation (Async [T] class), passing it an object of type ExecutionContext, if the method is called without arguments, then the asynchronous operation is started using ThreadPool.QueueUserWorkItem.
In the extension (async CTP), which allows using the async / wait implementation in C #, there are already a lot of extension methods that complement the existing classes with asynchronous operations. In a library with a monad implementation, async does not provide such extensions, but it does provide an easy way to build them on the basis of already existing primitives. For example, consider a part of the existing HttpWebRequest signature, which is responsible for the asynchronous execution of a query that exists from the first version of the framework:
public class HttpWebRequest : WebRequest, ISerializable { public override IAsyncResult BeginGetResponse(AsyncCallback callback, object state); public override WebResponse EndGetResponse(IAsyncResult asyncResult); } Now we will create an asynchronous extension, which is suitable for use in monadic calculations using these primitives.
public module AsyncExtentions { public GetResponseAsync(this request : HttpWebRequest) : Async[WebResponse] { Async.FromBeginEnd(request.BeginGetResponse(_, null), request.EndGetResponse(_)) } } It should be recalled that _ in Nemerle is a special character, in this case currying is used through it (the record f (_) is equivalent to x => f (x)). Similarly, wrappers can be created for any standard asynchronous computing.
Let's try on Nemerle to write something from (C # 101) Async samples, for example, parallel loading of several web pages and printing a header, I dropped the code for the extension GetHtml () and GetTitle (), the article was already dragged out.
public PrintTitles() : Async[FakeVoid] { comp async { def response1 = HttpWebRequest.Create("http://www.ya.ru").GetResponseAsync(); def response2 = HttpWebRequest.Create("http://www.habr.ru").GetResponseAsync(); defcomp response1 = response1; defcomp response2 = response2; Console.WriteLine(response1.GetHtml().GetTitle()); Console.WriteLine(response2.GetHtml().GetTitle()); } } The first two lines start asynchronous page load operations, these methods return objects describing asynchronous operations at the time of execution, from the compiler's point of view, the type of these objects Async [WebResponce] (monad). In the next two lines, the monad expands into value, at a different level of meaning, it means waiting for results. In the last lines, the results are processed.
It's funny that the post-reasoning about how to properly ( wait for the results of all the asynchronous calls ) to do in javascript turned out to be very hot: 90 favorites, 100 comments. But back to our example.
The main thing to remember is that a monad is a spawning pattern, you have created a function that describes asynchronous computing, but does not trigger it, so you can start it so PrintTitles (). Start (). GetResult (). In fact, this is very important, since it can serve as a source of errors, if the method returns Async [T], you need to be aware of whether this code runs the calculations or only constructs them . For the difference, you probably should use a naming convention, for example, methods that run calculations must have the Async suffix.
In my second article on async / await in C #, I wrote that processing the results of asynchronous calculations await starts in the SynchronizationContext of the thread that started asynchronous calculations. Nemerle in this regard provides for greater flexibility, it is possible to transfer calculations from one stream to another. Consider a button click handler:
private button1_Click (sender : object, e : System.EventArgs) : void { def formContext = SystemExecutionContexts.FromCurrentSynchronizationContext(); def task = comp async { Thread.Sleep(5000); callcomp Async.SwitchTo(formContext); label1.Text = "success"; } _ = task.Start(SystemExecutionContexts.ThreadPool()); } First we get the ExecutionContext, which starts the calculations in the current SynchronizationContext, then we describe the asynchronous operation: Thread.Sleep emulates a heavy calculation, switch the execution context to the execution context of the thread gui and output the result. The calculation itself is run in the thread pool's ExecutionContexts.
It looks like magic, but in fact all this has already happened, callcomp just opens the monad when its meaning is not important. But why then open it at all? The point is the side effects and the state, during the monadic operations the state is dragged through them, the monad has access to this state at the time of disclosure and can change it, which is what happens here. In this example, the state stores information in which context to execute the code, and if this information changes, it switches to the new context. For details, I can recommend to go read the source , they are interesting.
In addition to Async.SwitchTo, there are other interesting monads affecting the flow of execution, for example, Async.Yield says that the execution context has changed, although it does not change it. In some cases, this does nothing, in the case where the ThreadPool was used, this action provokes a jump to another thread from the pool.
Conclusion
In conclusion, I can only note that monads are a very rich topic. In this article, I did not touch on such classic monads as State, Cont (continuation), Maybe (another Wishlist C # fanboy). You can read about them in other articles, I tried to give a practical explanation, thanks to which you can start using asynchronous programming and list / enumerable monads in Nemerle and know what is happening under the hood.
In many ways, the implementation of await / async in the future C # and the monadic approach to asynchronous programming in Nemerle are similar, but there is one note to support await / async the next version of the language is needed, and the asynchronous programming in Nemerle is implemented through monads language, not language).
I will be glad to comment and answer questions.
Source: https://habr.com/ru/post/108184/
All Articles