Boost.Http has a new parser

I usually don’t blog about updates on the Boost.Http project because I want as much info as possible in code and documentation (or even git history), not here. However, I got a stimulus to change this habit. A new parser I’ve been writing replaced the NodeJS parser in Boost.Http and here is the most appropriate place to inform about the change. This will be useful info also if you’re interested in using NodeJS parser, any HTTP parser or even designing a parser with a stable API unrelated to HTTP.

EDIT (2016/08/07): I tried to clarify the text. Now I try to make it clear whether I’m refering to the new parser (the new parser I wrote) or the old parser (NodeJS parser) everywhere in the text. I’ll also refer to Boost.Http with new parser as new Boost.Http and Boost.Http with old parser as old Boost.Http.

What’s wrong with NodeJS parser?

I started developing a new parser because several users wanted a header-only library and the parser was the main barrier for that in my library. I took the opportunity to also provide a better interface which isn’t limited to C language (inconvenient and lots of unsafe type casts) and uses a style that doesn’t own the control flow (easier to deal with HTTP upgrade and doesn’t require lots of jump’n’back among callbacks).

NodeJS parser argues you can pause it at any time, but its API doesn’t seem that reliable. You need to resort to ugly hacks[1][2] if you want to properly support HTTP pipelining with an algorithm that doesn’t “go back”. If you decide to not stop the parser, you need to store all intermediate results while NodeJS parser refuses to give control back to you, which forces you to allocate (even if NodeJS parser don’t).

NodeJS parser is hard to use. Not only the callback model forces me to go back and forth here and there, it’ll also force me to resort to ugly hacks full of unsafe casts which also increase object size to provide a generic templated interface[1][2][3][4]. Did I mention that it’ll always consume current data and I need to keep appending data everywhere (this is good and bad, the new parser I implemented does a good job at that)? The logic to handle field names is even more complex because this append stuff[1][2][3]. It’s even more complex because NodeJS won’t always decode the tokens (matching and decoding are separate steps) and you need to decode them yourself (and you need to know a lot of HTTP details).

The old parser is so hard to use that I wouldn’t dare to use the same tricks I’ve used in the new Boost.Http to avoid allocations on the old Boost.Http. So the NodeJS parser doesn’t allocate, but dealing with it (old Boost.Http) is so hard that you don’t want to reuse the buffer to keep incomplete tokens at all (forcing allocation or a big-enough secondary buffer to hold them in old Boost.Http).

HTTP upgrade is also very tricky and the lack of documentation for the NodeJS parser is depressing. So I only trust my own code as an usage reference for NodeJS parser.

However, I’ve hid all this complexity from my users. My users wanted a different parser because they wanted a header-only library. I personally only wanted to change the parser because the NodeJS parser only accepts a limited set of HTTP methods and  it was tricky to properly not perform any allocation. The new parser even makes it easier to reject an HTTP element before decoding it (e.g. a URL too long will exhaust the buffer and then the new Boost.Http can just check the `expected_token` function to know it should reply with 414 status code instead concatenating a lot of URL pieces until it detect the limit was reached).

If you aren’t familiar enough with HTTP details, you cannot assume the NodeJS parser will abstract HTTP framing. Your code will get the wrong result and it’ll go silent for a long time before you know it.

The new parser

EDIT(2016/08/09): The new parser is almost ready. It can be used to parse request messages (it’ll be able to parse response messages soon). It’s written in C++03. It’s header-only. It only depends on boost::string_ref, boost::asio::const_buffer and a few others that I may be missing from memory right now. The new parser doesn’t allocate data and returns control to the user as soon as one token is ready or an error is reached. You can mutate the buffer while the parser maintains a reference to it. And the parser will decode the tokens, so you do not need ugly hacks as NodeJS parser requires (removing OWS from the end of header field values).

I want to tell you that the new parser was NOT designed to Boost.Http needs. I wanted to make a general parser and the design started. Then I wanted to replace NodeJS parser within Boost.Http and parts have fit nicely. The only part that didn’t fit perfectly at the time to integrate pieces was a missing end_of_body token that was easy to add in the new parser code. This was the only time that I, as the author of Boost.Http and as a user of the new parser, used my power, as the author of the parser itself, to push my needs on everybody else. And this token was a nice addition anyway (using NodeJS API you’d use http_body_is_final).

My mentor Bjorn Reese had the vision to use an incremental parser much earlier than me. I’ve only been convinced to the power of incremental parsers when I’ve saw a CommonMark parser implemented in Rust. It convinced me immediately. It was very effective. Then I’ve borrowed several conventions on how to represent tokens in C++ from a Bjorn’s experiment.

There is also the “parser combinators” part of this project (still not ready) that I’ve only understood once I’ve watched a talk from Scott Wlaschin. Initially I was having a lot of trouble because I wanted stateful miniparsers to avoid “reparsing” certain parts, but you rarely read 1-sized chunks and I was only complicating things. The combinators part is tricky to deliver, because the next expected token will depend on the value (semantic, not syntax) of current token and this is hard to represent using expressions like Boost.Spirit abstractions. Therefore, I’m only going to deliver the mini-parsers, not the combinators. Feel free to give me feedback/ideas if you want to.

Needless to say the new parser should have the same great features from NodeJS parser like no allocations or syscals behind the scenes. But it was actually easier to avoid and decrease allocations on Boost.Http thanks to the parser’s design of not forcing the user to accumulate values on separate buffers and making offsets easy to obtain.

I probably could achieve the same effect of decreased buffers in Boost.Http with NodeJS parser, but it was quite hard to work with NodeJS parser (read section above). And you should know that the old Boost.Http related to the parser was almost 3 times bigger (it’d be almost 4 times bigger, but I had to add code to detect keep alive property because the new parser only care about message framing) than the new Boost.Http code related to the parser.

On the topic of performance, the new Boost.Http tests consume 7% more time to finish (using a CMake Release build with GCC under my machine). I haven’t spent time trying to improve performance and I think I’ll only try to improve memory usage anyway (the size of the parser structure).

A drawback (is it?) is that the new parser only cares about structuring the HTTP stream. It doesn’t care about connection state (exception: receiving http 1.0 response body/connection close event). Therefore, you need to implement the keep-alive yourself (which the Boost.Http higher-level layers do).

I want to emphasize that the authors of the NodeJS parser have done a wonderful job with what they had in hands: C!

Migrating code to use the new parser

First, I haven’t added the code to parse the status line yet, so the parser is limited to HTTP requests. It shouldn’t take long (a few weeks until I finish this and several other tasks).

When you’re ready to upgrade, use the history of the Boost.Http project (files include/boost/http/socket-inl.hpp and include/boost/http/socket.hpp) as a guide. If you’ve been using NodeJS parser improperly, it’s very likely your code didn’t have as much lines as Boost.Http had. And your code probably isn’t as templated as Boost.Http anyway, so it’s very likely you didn’t need as much tricks with http_parser_settings as Boost.Http needed.

Tufão project has been using NodeJS parser improperly for ages and it’d be hard to fix that. Therefore, I’ll replace “Tufão’s parser” with this new shiny one in the next Tufão release Tufão 1.4.0 has been refactored to use this new parser. It’ll finally gain It finally received support for HTTP pipelining and plenty of bugfixes that nobody noticed will land landed. Unfortunately I got the semantics for HTTP upgrade within Tufão wrong and it kind of has “forced HTTP upgrade” (this is something I got right in Boost.Http thanks to RFC7230 clarification).

Next steps

I may have convinced you to prefer Boost.Http parser over NodeJS parser when it comes to C++ projects. However, I hope to land a few improvements before calling it ready.

API/design-wise I hope to finish miniparsers for individual HTTP ABNF rules.

Test wise I can already tell you more than 80% of all the code written for this parser are tests (like 4 lines of test for each 1 line of implementation). However I haven’t run the tests in combination with sanitizers (yet!) and there a few more areas where tests can be improved (include coverage, allocate buffer chunks separately so sanitizers can detect invalid access attempts, fuzzers…) and I’ll work on them as well.

I can add some code to deduce the optimum size for indexes and return a parser with a little less overhead memory-wise.

EDIT (2016/08/11)

I’ve added a link that should be here since the first version of this post: https://gist.github.com/vinipsmaker/4998ccfacb971a0dc1bd

It adds a lot of background on the project. This is the proposal I’ve sent to get some funding to work on the project.

Eu não confio no seu julgamento se você não critica sua linguagem de programação

A lógica por trás de tal filosofia é bem simples. Se sua linguagem de programação não possui defeitos, então não há nada para mudar nela, pois ela é perfeita, exatamente como está, imutável, nada precisa mudar. Entretanto, e essa é a parte da argumentação que é menos baseada em consequências lógicas e mais baseada em observações ao meu redor, ainda está para ocorrer o momento em que eu veja um entusiasta de sua linguagem de programação que considere negativo o lançamento de uma nova versão de sua linguagem de programação. Cada uma das mudanças que culminou no lançamento de uma nova versão de sua linguagem de programação era uma carência ou um defeito que existia em sua antiga versão, e os “fãs” só irão reconhecê-lo uma vez que o defeito é corrigido, pois sua linguagem é perfeita, sagrada, livre de questionamentos, um tabu quando se menciona a ideia de defeitos.

Pois bem, eu não acho essa posição de sua parte nenhum pouco honesta, e eu quis fazer esse texto para tentar fazer você refletir um pouco a respeito. Outro motivo é que eu estava há muito tempo sem escrever e esse foi um texto fácil para mim, que fluiu da minha mente para “o papel” encontrando nenhuma barreira ou barreiras imperceptíveis. Eu perdi muito pouco tempo para fazê-lo. É um texto de mera opinião.

A ideia de fazer esse texto me veio após perder bastante tempo para escrever a pauta para um podcast que me convidaram a gravar. O tema do podcast seria a linguagem Rust, e eu, na minha mentalidade de blogueiro que ainda não sabe montar pautas, dediquei 4 páginas da pauta só para elaborar o quão C++ é uma linguagem ruim. Agora você precisa entender que a linguagem C++ foi minha linguagem favorita por 6 anos de tal forma que simplesmente não havia espaço para carinho a outras linguagens de programação, e que eu dediquei muito tempo de minha vida só para entender como eu poderia defender essa linguagem. Hoje em dia, C++ não perdeu meu carinho e ela ainda é minha solução favorita para metade dos problemas que resolvo. Ainda assim, 90% do tempo que dediquei para montar a pauta, foi para criticar C++, e em momento nenhum deixei espaço para que o consumidor daquela pauta/obra pudesse imaginar que eu tenho um apego tão grande por essa linguagem.

Acho que uma boa forma de terminar esse texto é ressaltar que sua linguagem só evolui se você corrigir seus problemas, e isso só vai acontecer uma vez que seus problemas sejam reconhecidos. A “linguagem perfeita” é um termo que só é usado por programadores imaturos, grupo do qual um dia eu também já fiz parte.

Resenha: Introdução à programação com a linguagem C, por Rodrigo Paes

Como discutir programação sem discutir código-fonte? E o livro “Introdução à Programação com a Linguagem C” acerta nesse ponto, com exemplos iluminadores para os conceitos ensinados, e uma disposição de conteúdo gradual e simples que devem tornar o aprendizado efetivo. Como um professor dedicado, o autor deve ter aproveitado seu material, os seus alunos, como um experimento para encontrar exemplos que funcionassem.

Uma preocupação com simplicidade que omite ou adia a preocupação com certos conceitos nos capítulos iniciais. Uma decisão que permite o livro ser fácil de entender e ser tão curto quanto é. É o contrário da especificação da linguagem, apropriado para aprendizado. Entretanto, o livro não deixa de apresentar pequenas nuâncias nos conceitos durante o decorrer da leitura, que só ressaltam a preocupação em fazer os conceitos serem entendidos corretamente, ao explicitar uma consequência ou outra de cada regra, de forma lenta, sem sobrecarregar o aluno, de forma mais efetiva que não se perca em muitas informações para se lembrar. Essa preocupação é bem abrangente e cobre, por exemplo, segurança, terminologia e arquitetura. Um grande exemplo de como conciliar pragmatismo no ensino sem criar um aluno ignorante.

Os trechos “código comentados” ainda possuem o bônus de gradualmente (e de forma lenta, sem forçar sobrecarga de conteúdo), apresentar exemplos sutis de “dividir para conquistar”, “abordagem top-down” e outros bons conceitos para habilidades gerais de solucionar problemas, mas só quando a fundação da linguagem já foi bem explorada e o aluno já deveria estar melhor acostumado com questões de sintaxe, o que acho muito acertado no livro.

Todo o capítulo de recursão é um bônus a parte que estimula o aluno a quebrar a forma de pensar com a qual todo o resto do livro o acostuma e, assim, espero, o estimule a sempre procurar novas formas de resolver problemas e aprender mais, em vez de ficar limitado e satisfeito com o próprio livro.

Esse é um livro que eu recomendaria a qualquer pessoa que nunca teve contato com programação e deseja aprender a programar utilizando a linguagem C.

Boost.Http and Beast.HTTP joining forces

The newest update to the Boost.Http is that I had a long meeting with Vinnie Falco about a possible collaboration and a few changes are going to happen.

The official announcement was sent to the Boost mailing list and is available in the gmane archives.

What this means:

• A lot of work making changes so projects can hopefully be merged in the future.
• API will break again.
• The thing I wasn’t caring about, “HTTP/1.1 oriented interface”, will be provided on a higher-level than simply an HTTP parser. This is what Beast.HTTP already provides.
• Beast.HTTP already provides WebSocket support and HTTP client support.
• We’ll be using a new mailing list to coordinate further development and I invite you to join the mailing list if you’re interested in the future of any of these libraries or HTTP APIs in general.

Boost.Http parser project

I’ll develop a HTTP pull parser for Boost.Http during this summer.

The story starts with Boost not being selected for Google Summer of Code this year. I wanted more funding to spend time on Boost.Http and this was unfortunate.

However, funding from other sources was announced for three projects and Boost.Http was one of the selected projects.

I’d rather work on the request router, but I don’t have a strong design for a request router right now because I’m still experimenting. A weak design would translate on a weak proposal and I decided to propose a HTTP parser.

Misc

An interesting HTTP library that carries some similarities with Boost.Http was announced on the Boost mailing list: Beast.

Uisleandro is working on a request router focused on ReST services for Boost.Http: https://github.com/BoostGSoC14/boost.http/compare/master…uisleandro:router1?expand=1.

Multitasking styles, event loops and asynchronous programming

There was a text that I’ve previously published here in this blog about asynchronous programming, but it was written in Portuguese. Now has come the time that I think this text should be available also in English. Translation follows below. Actually is not a “translation” per si, as I adapted the text to be more pleasant when written in English.

One of the subjects that interest me the most in programming is asynchronous programming. This is a subject that I got in touch since I started to play with Qt around 2010, but I slowly moved to new experiences and “paradigms” of asynchronous programming. Node.js and Boost.Asio were other important experiences worth mentioning. The subject caught me a lot and it was the stimulus for me to study a little of computer architecture and operating systems.

Motivation

Several times we stumble upon with problems that demand continuously handling several jobs (e.g. handling network events to mutate local files). Intuitively we may be tempted to use threads, as there are several “parallel” jobs. However, not all jobs executed by the computer are done so exclusively in the CPU.

There are other components beside the CPU. Components that are not programmable and that do not execute your algorithm. Components that are usually slower and do other jobs (e.g. converting a digital signal into an analog one). Also, the communication with these components usually happen serially, through the fetch-execute-check-interrupt cycle. There is a simplification in this argument, but the fact that you don’t read two different files from the same hard drive in parallel remains. Summarizing, using threads isn’t a “natural” abstraction to the problem, as it doesn’t “fit” and/or design the same characteristics. Using threads can add a complex and unnecessary overhead.

“If all you have is a hammer, everything looks like a nail”

Another reason to avoid threads as an answer to the problem is that soon you’ll have more threads than CPU/cores and will face the C10K problem. Even if it didn’t add an absurd overhead, just the fact that you need more threads than available CPUs will make your solution more restrict, as it won’t work on bare-metal environments (i.e. that lacks a modern operating system or a scheduler).

A great performance problem that threads add comes from the fact that they demand a kernel context-switch. Of course this isn’t the only problem, because there is also the cost involved in creating the thread, which might have a short lifetime and spend most of its lifetime sleeping. The own process of creating a thread isn’t completely scalable, because it requires the stack allocation, but the memory is a global resource and right here we have a point of contention.

The performance problem of a kernel context-switch reminds the performance problem of the function calling conventions faced by compilers, but worse.

Functions are isolated and encapsulated units and as such they should behave. When a function is called, the current function doesn’t know which registers will be used by the new function. The current function doesn’t hold the information of which of the CPU registers will be overridden during the new function lifetime. Therefore, the function calling conventions add two new points to do extra processing. One point to save state into the stack and one to restore. That’s why some programmers are so obsessed into function inlining.

The context-switch problem is worse, because the kernel must save the values of all registers and there is also the overhead of the scheduler and the context-switch itself. Processes would be even worse, as there would be the need to reconfigure the MMU. This multitasking style is given the name of preemptive multitasking. I won’t go into details, but you can always dig more into computer architecture and operating systems books (and beyond).

It’s possible to obtain concurrency, which is the property to execute several jobs in the same period of time, without real parallelism. When we do this tasks that are more IO-oriented, it can be interesting to abandon parallelism to achieve more scalability, avoiding the C10K problem. And if a new design is required, we could catch the opportunity to also take into account cooperative multitasking and obtain a result that is even better than the initially planned.

The event loop

One approach that I see, and I see used more in games than anywhere else, is the event loop approach. It’s this approach that we’ll see first.

There is this library, the SDL low level library, whose purpose is to be just a multimedia layer abstraction, to supply what isn’t already available in the C standard library, focusing on the game developer. The SDL library makes use of an event system to handle communication between the process and the external world (keyboard, mouse, windows…), which is usually used in some loop that the programmer prepares. This same structure is used in other places, including Allegro, which was the biggest competitor of SDL in the past.

The idea is to have a set of functions that make the bridge of communication between the process and the external world. In the SDL world, events are described through the non-extensible SDL_Event type. Then you use functions like SDL_PollEvent to receive events and dedicated functions to initiate operations that act on the external world. The support for asynchronous programming in the SDL library is weak, but this same event loop principle could be used in a library that would provide stronger support for asynchronous programming. Below you can find a sample that makes use of the SDL events:

	#include <string>
	#include <iostream>
	#include <SDL.h>
	#include <SDL_image.h>
	#include "res_path.h"
	#include "cleanup.h"
	/*
	* Lesson 4: Handling Events
	*/
	//Screen attributes
	const int SCREEN_WIDTH = 640;
	const int SCREEN_HEIGHT = 480;
	/*
	* Log an SDL error with some error message to the output stream of our choice
	* @param os The output stream to write the message too
	* @param msg The error message to write, format will be msg error: SDL_GetError()
	*/
	void logSDLError(std::ostream &os, const std::string &msg){
	os << msg << " error: " << SDL_GetError() << std::endl;
	}
	/*
	* Loads an image into a texture on the rendering device
	* @param file The image file to load
	* @param ren The renderer to load the texture onto
	* @return the loaded texture, or nullptr if something went wrong.
	*/
	SDL_Texture* loadTexture(const std::string &file, SDL_Renderer *ren){
	SDL_Texture *texture = IMG_LoadTexture(ren, file.c_str());
	if (texture == nullptr){
	logSDLError(std::cout, "LoadTexture");
	}
	return texture;
	}
	/*
	* Draw an SDL_Texture to an SDL_Renderer at position x, y, with some desired
	* width and height
	* @param tex The source texture we want to draw
	* @param rend The renderer we want to draw too
	* @param x The x coordinate to draw too
	* @param y The y coordinate to draw too
	* @param w The width of the texture to draw
	* @param h The height of the texture to draw
	*/
	void renderTexture(SDL_Texture *tex, SDL_Renderer *ren, int x, int y, int w, int h){
	//Setup the destination rectangle to be at the position we want
	SDL_Rect dst;
	dst.x = x;
	dst.y = y;
	dst.w = w;
	dst.h = h;
	SDL_RenderCopy(ren, tex, NULL, &dst);
	}
	/*
	* Draw an SDL_Texture to an SDL_Renderer at position x, y, preserving
	* the texture's width and height
	* @param tex The source texture we want to draw
	* @param rend The renderer we want to draw too
	* @param x The x coordinate to draw too
	* @param y The y coordinate to draw too
	*/
	void renderTexture(SDL_Texture *tex, SDL_Renderer *ren, int x, int y){
	int w, h;
	SDL_QueryTexture(tex, NULL, NULL, &w, &h);
	renderTexture(tex, ren, x, y, w, h);
	}
	int main(int, char**){
	//Start up SDL and make sure it went ok
	if (SDL_Init(SDL_INIT_VIDEO) != 0){
	logSDLError(std::cout, "SDL_Init");
	return 1;
	}
	//Setup our window and renderer, this time let's put our window in the center
	//of the screen
	SDL_Window *window = SDL_CreateWindow("Lesson 4", SDL_WINDOWPOS_CENTERED,
	SDL_WINDOWPOS_CENTERED, SCREEN_WIDTH, SCREEN_HEIGHT, SDL_WINDOW_SHOWN);
	if (window == nullptr){
	logSDLError(std::cout, "CreateWindow");
	SDL_Quit();
	return 1;
	}
	SDL_Renderer *renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC);
	if (renderer == nullptr){
	logSDLError(std::cout, "CreateRenderer");
	cleanup(window);
	SDL_Quit();
	return 1;
	}
	//The texture we'll be using
	const std::string resPath = getResourcePath("Lesson4");
	SDL_Texture *image = loadTexture(resPath + "image.png", renderer);
	if (image == nullptr){
	cleanup(image, renderer, window);
	IMG_Quit();
	SDL_Quit();
	return 1;
	}
	//Our texture size won't change, so we can get it here
	//instead of constantly allocating/deleting ints in the loop
	int iW, iH;
	SDL_QueryTexture(image, NULL, NULL, &iW, &iH);
	int x = SCREEN_WIDTH / 2 - iW / 2;
	int y = SCREEN_HEIGHT / 2 - iH / 2;
	//Our event structure
	SDL_Event e;
	//For tracking if we want to quit
	bool quit = false;
	while (!quit){
	//Read any events that occured, for now we'll just quit if any event occurs
	while (SDL_PollEvent(&e)){
	//If user closes the window
	if (e.type == SDL_QUIT){
	quit = true;
	}
	//If user presses any key
	if (e.type == SDL_KEYDOWN){
	quit = true;
	}
	//If user clicks the mouse
	if (e.type == SDL_MOUSEBUTTONDOWN){
	quit = true;
	}
	}
	//Rendering
	SDL_RenderClear(renderer);
	//Draw the image
	renderTexture(image, renderer, x, y);
	//Update the screen
	SDL_RenderPresent(renderer);
	}
	//Destroy the various items
	cleanup(image, renderer, window);
	IMG_Quit();
	SDL_Quit();
	return 0;
	}

view raw main.cpp hosted with ❤ by GitHub

There are the GUI libraries like GTK+, EFL and Qt which take this idea one step further, abstracting into an object the event loop that were previously written and rewritten by you. The Boost.Asio library, which focuses on asynchronous operations and not on GUIs, has a class of similar purpose, the io_service class.

To remove your need to write boilerplate code to route events to specific actions, the previously mentioned classes will handle this task for you, possibly using callbacks, which are an old abstraction. The idea is that you should bind events to functions that might be interested in handling those events. Now the logic to route these events belong to the “event loop object” instead a “real”/raw event loop. This style of asynchronous programming is a passive style, because you only register the callbacks and transfer the control to the framework.

Now that we’re one level of abstraction higher than event loops, let’s stop the discussion about event loops. And these objects that we referring to as “event loop objects” will be mentioned as executors from now on.

The executor

The executor is an object that can execute encapsulated units of work. Using only C++11, we can implement an executor that schedules operations related to waiting some duration of time. There is the global resource RTC and, instead of approaching the problem by creating several threads that start blocking operations like the sleep_for operation, we’ll use an executor. The executor will schedule and manage all events that are required. You can find a simple implementation for such executor following:

	#include <thread>
	#include <chrono>
	#include <functional>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	class executor
	{
	public:
	void add_sleep_for_callback(std::chrono::milliseconds ms,
	std::function<void()> cb);
	void run();
	private:
	struct internal_callback
	{
	std::chrono::milliseconds ms;
	std::function<void()> cb;
	};
	std::vector<internal_callback> callbacks;
	std::chrono::milliseconds passed{0};
	};
	void executor::add_sleep_for_callback(std::chrono::milliseconds ms,
	std::function<void()> cb)
	{
	callbacks.insert(std::upper_bound(callbacks.begin(), callbacks.end(),
	[&]() {
	internal_callback ret;
	ret.ms = ms;
	return ret;
	}(),
	[](const internal_callback &l,
	const internal_callback &r) {
	return l.ms < r.ms;
	}),
	[&]() {
	internal_callback ret;
	ret.ms = ms;
	ret.cb = cb;
	return ret;
	}());
	}
	void executor::run()
	{
	while (callbacks.size()) {
	auto cur = callbacks.front().ms - passed;
	passed += cur;
	std::this_thread::sleep_for(cur);
	callbacks.front().cb();
	callbacks.erase(callbacks.begin());
	}
	passed = 0;
	}
	int main(int /*argc*/, char */*argv*/[])
	{
	typedef std::chrono::milliseconds milli;
	executor ex;
	ex.add_sleep_for_callback(milli{5000}, []() {
	std::cout << "5000ms passed" << std::endl;
	});
	ex.add_sleep_for_callback(milli{1000}, []() {
	std::cout << "1000ms passed" << std::endl;
	});
	ex.add_sleep_for_callback(milli{3000}, []() {
	std::cout << "3000ms passed" << std::endl;
	});
	ex.run();
	return 0;
	}

view raw executor.cpp hosted with ❤ by GitHub

This code reminds me of sleepsort.

In the example, without using threads, it was possible to execute the several concurrent jobs related to waiting time. To do such thing, we gave the executor the responsibility to share the RTC global resource. Because the CPU is faster than the requested tasks, only one thread was enough and, even so, there was a period of time for which the CPU was idle.

There are some concepts to be extracted from this example. First, let’s consider that the executor is an standard abstraction, provided in some interoperable way among all the code pieces that makes use of asynchronous operations. When a program wants to do the wait asynchronous operation, the program request the operation start to some abstraction — in this case it’s the executor itself, but it’s more common to find these operations into “I/O objects” — through a function. The control is passed to the executor — through the method run — which will check for notification of finished tasks. When there are no more tasks on the queue, the executor will give back the control of the thread.

Because there is only one thread of execution, but several tasks to execute, we have the resource sharing problem. In this case, the resource to be shared is the CPU/thread itself. The control should go and come between some abstraction and the user code. This is the core of cooperative multitasking. There are customization points to affect behaviour among the algorithms that execute the tasks, making them give CPU time to the execution of other tasks.

One advantage of the cooperative multitasking style of multitasking is that all “switch” points are well defined. You know exactly when the control goes from one task to another. So that context switch overhead that we saw earlier don’t exist — where all register values need to be saved… A solution that is more elegant, efficient and green.

The object that we passed as the last argument to the function add_sleep_for_callback is a callback — also know as completion handler. Think about what would happen if a new wait operation was requested within one of the completion handlers that we registered. There is an improved version of the previous executor following:

	#include <thread>
	#include <chrono>
	#include <functional>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	class executor
	{
	public:
	void add_sleep_for_callback(std::chrono::milliseconds ms,
	std::function<void()> cb);
	void run();
	private:
	struct internal_callback
	{
	std::chrono::milliseconds ms;
	std::function<void()> cb;
	};
	std::vector<internal_callback> callbacks;
	std::chrono::milliseconds passed{0};
	};
	void executor::add_sleep_for_callback(std::chrono::milliseconds ms,
	std::function<void()> cb)
	{
	ms += passed; // NEW!!!
	callbacks.insert(std::upper_bound(callbacks.begin(), callbacks.end(),
	[&]() {
	internal_callback ret;
	ret.ms = ms;
	return ret;
	}(),
	[](const internal_callback &l,
	const internal_callback &r) {
	return l.ms < r.ms;
	}),
	[&]() {
	internal_callback ret;
	ret.ms = ms;
	ret.cb = cb;
	return ret;
	}());
	}
	void executor::run()
	{
	while (callbacks.size()) {
	auto cur = callbacks.front().ms - passed;
	passed += cur;
	std::this_thread::sleep_for(cur);
	callbacks.front().cb();
	callbacks.erase(callbacks.begin());
	}
	passed = 0;
	}
	int main(int /*argc*/, char */*argv*/[])
	{
	typedef std::chrono::milliseconds milli;
	executor ex;
	ex.add_sleep_for_callback(milli{5000}, []() {
	std::cout << "5000ms passed" << std::endl;
	});
	ex.add_sleep_for_callback(milli{1000}, [&ex]() {
	std::cout << "1000ms passed" << std::endl;
	ex.add_sleep_for_callback(milli{2000}, []() {
	std::cout << "3000ms passed" << std::endl;
	});
	});
	ex.run();
	return 0;
	}

view raw executor.cpp hosted with ❤ by GitHub

This implementation detail reminds me of the SHLVL SHELL variable.

An interesting case is the case from the JavaScript language. JavaScript has a kind of “implicit executor”, which is triggered when the VM reaches the end of your code. In this case, you don’t need to write codes like “while (true) executor.run_one()” or “executor.run()“. You only would need to register the callbacks and make sure there are no infinite loops until the executor gets the chance to be in control.

With the motivation introduced, the text started to decrease the use of mentions to I/O for reasons of simplicity and focus, but keep in mind that we use asynchronous operation mostly to interact with the external world. Therefore many operation are scheduled conditionally in response to the notification of the completion of a previous task (e.g. if protocol invalid, close socket else schedule another read operation). Proposals like N3785 and N4046 define executors also to schedule thread pools, not only timeouts within a thread. Lastly it’s possible to implement executors that schedule I/O operations within the same thread.

Asynchronous algorithms represented in synchronous manners

The problem with the callback approach is that we no longer have a code that is clean and readable. Previously, the code could be read sequentially because this is what the code was, a sequence of instructions. However, now we need to spread the logic among lots of lots of callbacks. Now you have blocks of code that are related far apart from each other. Lambdas can help a little, but it’s not enough. The problem is know as callback/nesting hell and it’s similar to the spaghetti code problem. Not being bad enough, the execution flow became controverted because the asynchronous nature of the operations itself and constructs like branching and repetition control structures and even error handling assume a representation that are far from ideal, obscures and difficult to read.

One abstraction of procedures very important to asynchronous programming is coroutines. There is the procedure abstraction that we refer to under the name of “function”. This so called “function” models the concept of subroutine. And we have the coroutine, which is a generalization of a subroutine. The coroutine has two more operations than subroutine, suspend and resume.

When your “function” is a coroutine — possible when the language provides support to coroutines — it’s possible to suspend the function before it reaches the end of execution, possibly giving a value during the suspend event. One example where coroutines are useful is on a hypothetical fibonacci generating function and a program that uses this function to print the first 10 numbers of this infinite sequence. The following Python code demonstrate an implementation of such example, where you can get an insight of the elegance, readability and and reuse that the concept of coroutines allows when we have the problem of cooperative multitasking:

	from itertools import islice
	def fibonacci():
	a,b = 0,1
	yield(a)
	while True:
	a,b = b,a+b
	yield(a)
	print(list(islice(fibonacci(), 10)))

view raw fibonacci.py hosted with ❤ by GitHub

This code reminds me of the setjmp/longjmp functions.

One characteristic that we must give attention in case you aren’t familiarized with the concept is that the values of the local variables are preserved among the several “calls”. More accurately, when the function is resumed, it has the same execution stack that it had when it was suspended. This is a “full” implementation of the coroutine concept — sometimes mentioned as stackful coroutine. There are also stackless coroutines where only the “line under execution” is remembered/restored.

The N4286 proposal introduces a new keyword, await, to identify a suspension point for a coroutine. Making use of such functionality, we can construct the following example, which elegantly defines an asynchronous algorithm described in a very much “synchronous manner”. It also makes use of the several language constructs that we’re used to — branching, repetition and others:

	std::future<void> tcp_reader(int total)
	{
	char buf[64 * 1024];
	auto conn = await Tcp::Connect("127.0.0.1", 1337);
	do
	{
	auto bytesRead = await conn.read(buf, sizeof(buf));
	total -= bytesRead;
	}
	while (total > 0);
	}
	int main() { tcp_reader(1000 * 1000 * 1000).get(); }

view raw await.cpp hosted with ❤ by GitHub

Coroutines solve the complexity problem that asynchronous algorithms demand. However, there are several coroutines proposals and none of them was standardized yet. An interesting case is the Asio library that implemented a mechanism similar to Duff’s Device using macros to provide stackless coroutines. For C++, I hope that the committee continue to follow the “you only pay for what you use” principle and that we get implementations with high performance.

While you wait for the standardization, we can opt for library-level solutions. If the language is low-level and gives the programmer control enough, these solutions will exist — even if it’s going to be not portable. C++ has fibers and Rust has mioco.

Another option to use while you wait for coroutines it not to use them. It’s still possible to achieve high performance implementation without them. The big problem will be the highly convoluted control flow you might get.

Completion tokens

While there is no standardized approach for asynchronous operations in the C++ language, the Boost.Asio library, since the version 1.54, adopted an interesting concept. The Boost.Asio implemented an extensible solution. Such solution is well documented in the N4045 proposal and you’ll only find a summary here.

The proposal is assumes that the callback model is not always interesting and can be even confusing sometimes. So it should be evolved to support other models. Now, instead receiving a completion handler (the callback), the functions should receive a completion token, which adds the necessary customization point to support other asynchronous models.

The N4045 document uses a top-down approach, first showing how the proposal is used to then proceed to low-level implementation details. You can find a sample code from the document following:

	string // task<string>
	read(string file, string suffix, // read(string file, string suffix)
	yield_context yield) { // __async {
	istream fi = open(file, yield); // istream fi = __await open(file);
	string ret, chunk;
	while((chunk = fi.read(yield)).size()) // while((chunk = __await fi.read()).size())
	ret += chunk + suffix;
	return ret;
	}

view raw n4045 example.cpp hosted with ❤ by GitHub

In the code that you just saw, every time the variable yield is passed to some asynchronous operation (e.g. open and read), the function is suspended until the operation is completed. When the operation completes, the function is resumed in the point where it was suspended and the function that started the asynchronous operation returns the result of the operation. The Fiber library, shortly mentioned previously, provides a yield_context to the Asio extensible model, the boost::fibers::asio::yield. It’s asynchronous code written in a synchronous manner. However, an extensible model is adopted because we don’t know which model will be the standard for asynchronous operations and therefore we cannot force a single model to rule them all.

To build an extensible model, the return type of the function needs to be deduced (using the token) and the value of the return also needs to be deduced (also using the token). The return type is deduced using the token type and the returned value is created using the token passed as argument. And you still have the handler, which must be called when the operation completes. The handler is extracted from the token. The completion tokens model makes use of type traits to extract all information. If the traits aren’t specialized, the default behaviour is to treat the token as a handler, turning the approach compatible with the callback model.

Several examples are given in the N4045 document:

• use_future
• boost::fibers::asio::use_future
• boost::fibers::asio::yield
• block
• …

The std::future approach have meaningful impact on performance and this is not cool, like explained in the N4045 document. This is the reason why I don’t mention it in this text.

Signals and slots

One alternative that was proposed to the model of callbacks is the signals and slots approach. This approach is implemented in libgsigc++, Boost, Qt and a few other libraries.

This proposal introduces the concept of a signal, which is used to notify an event, but abstracts the delivery of the notification and the process of registering functions that are interested in the event. The code that notifies events just need to worry about emitting the signal every time the event happens because the signal itself will take care of handling the set of registered slots and stuff.

This approach usually allows a very decoupled architecture, in opposition of the very verbose approach largely used in Java. An interesting effect, depending on the implementation, is the possibility to connect one signal to another signal. It’s also possible to have multiple signals connected to one slot or one signal connected to multiple slots.

The signal usually is related to one object, and when the object is destroyed, the connections are destroyed too. Just like it’s also possible to have slot objects that automatically disconnect from connected signals once destroyed, so you have a safer abstraction.

Given signals are independently implemented abstractions and usable as soon as they are exposed, it’s naturally intuitive to remove the callback argument from the operations that initiate asynchronous operations to avoid duplication of efforts. If you go further in this direction, you’ll even remove the own function to do asynchronous operations, exposing just the signal used to receive notifications, your framework you’ll be following the passive style instead active style. Examples of such style are the Qt’s socket, which doesn’t have an explicit function to request the start of the read operation, and the POCO library, which doesn’t have a function to request that receiving of a HTTP request.

Another detail which we have in signals and slots approach is the idea of access control. In the Qt case, signals are implemented in a way that demands the cooperation of one preprocessor, the own Qt executor and the QObject class. In the Qt case, the control access rules for emitting a signal follow the same rules for protected methods from C++ (i.e. all children classes can emit signals defined in parent classes). The operation of connecting a signal to another signal or a slot follows the same rules of public members of C++ (i.e. anyone can execute the operation).

In the case of libraries that implement the signal concept as a type, it’s common to observe a type that encapsulate both, the operation to emit the signal and the operation to connect the signal to some slot (different from what we see in the futures and promises proposal, where each one can have different control access).

The signals and slots approach is cool, but it doesn’t solve the problem of complexity that is solved with coroutines. I only mentioned this approach to discuss better the difference between the active style and the passive style.

Active model vs passive model

In the passive model, you don’t schedule the start of the operations. It’s what we commonly find in “productive” frameworks, but there are many questions that this style doesn’t answer quite well.

Making a quick comparison between the libraries Qt and Boost.Asio. In both libraries, you find classes to abstract the socket concept, but using Qt you handle the event readyRead using the readAll method to receive the buffer with the data. In contrast, using Boost.Asio, you start the operation async_read_some and pass the buffer as argument. Qt uses the passive style and Boost.Asio uses the active style.

The readyRead event, from Qt, acts independently from the user and requires a buffer allocation every time it occurs. Then some questions arise. “How can I customize the buffer allocation algorithm?”, “how can I customize the application to allow recycling buffers?”, “how do I use a buffer that is allocated on the stack?” and more. The passive model doesn’t answer questions like these, then you need to fatten the socket abstraction with more customization points to allow behaviours like the ones described. It’s a combinatorial explosion to every abstraction that deals with asynchronous operations. In the active model, these customizations are very natural. If there is any resource demanded by the operation that the developer is about to start, the developer just need to pass the resource as an argument. And it’s not only about resource acquisition. Another example of question that the passive model doesn’t answer well is “how do I decide whether I’m gonna accept a new connection or postpone to when the server is less busy?”. It’s a great power to applications that are seriously concerned about performance and need fine adjustments.

Besides performance and fine tuning, the passive model is also causes trouble to debugging and tests thanks to the inversion of control.

I must admit that the passive model is quite good to rapid prototyping and increasing productive. Fortunately, we can implement the passive model on top of the active model, but the opposite is not so easy to do.

Bonus references

If you like this subject and want to dig more, I suggest the following references:

• Five things that make Go fast.
• Basic Boost.Asio Anatomy.
• The Proactor Design Pattern: Concurrency Without Threads.
• Execution context.
• await 2.0: Stackless Resumable Functions.
• A proposal to add a utility class to represent expected monad – Revision 2.

Boost.Http rejected

Previously I informed that my library was about to be reviewed by the Boost community. And some time ago, this review happened and a result was published.

The outcome of the Boost review process was that my library should not be included in Boost. I think I reacted to the review very well and that I defended the library design with good arguments.

There was valuable feedback that I gained through the review process. Feedback that I can use to improve the library. And improvements to the library shouldn’t stop once the library is accepted into Boost, so I was expecting to spend more time in the library even after the review, as suggested by the presence of a roadmap chapter on the library documentation.

The biggest complaint about the library now was completeness. The library “hasn’t proven” that the API is right. The lack of higher-level building blocks was important to contribute to the lack of trust in current API. Also, if such library was to enter in Boost, it should be complete, so new users would have a satisfying first impression and continue to use the library after the initial contact. I was worried about delivering a megazord library to be reviewed in just one review, but that’s what will happen next time I submit the library to review. At least I introduced several concepts to the readers already.

Things that I planned were forgotten when I created the documentation and I’ll have to improve documentation once again to ensure guarantees that I had planned already. Also, some neat ideas were given to improve library design and further documentation updates will be required. Documentation was also lacking in the area of tutorial. Truth be told, I’m not very skilled in writing tutorials. Hopefully, the higher-level API will help me to introduce the library to newbies. Also, I can include several tutorials in the library to improve its status.

There was an idea about parser/generator (like 3-level instead 2-level indirection) idea that will require me to think even more about the design. Even now, I haven’t thought enough about this design yet. One thing for sure is that I’ll have to expose an HTTP parser because that’s the only thing that matters for some users.

A few other minor complaints were raised that can be addressed easily.

If you are willing to discuss more about the library, I have recently created a gitter channel where discussions can happen.

And for now, I need to re-read all messages given for the review and register associated issues in the project’s issue tracker. I’d like to have something ready by January, but it’ll probably take 6 months to 1 year before I submit the library again. Also, the HTTP client library is something that will possibly delay the library a lot, as I’ll research power users like Firefox and Chromium to make sure that the library is feature-ready for everybody.

So much work that maybe I’ll submit the library as a project on GSoC again next year to gather some more funding.

Also, I’d like to use this space to spread two efforts that I intend to make once the library is accepted into Boost:

• A Rust “port” of the library. Actually, it won’t be an 1:1 port, as I intend to use Rust’s unique expressiveness to develop a library that feels like a library that was born with Rust in mind.
• An enhanced, non-slow and not resource-hungry implementation (maybe Rust, maybe C++) of the trsst project.

EDIT (2016/03/20):

And for now, I need to re-read all messages given for the review and register associated issues in the project’s issue tracker.

That part is done: https://github.com/boostgsoc14/boost.http/issues?utf8=%E2%9C%93&q=is%3Aissue+label%3Aboost-review+

I’d like to have something ready by January, but it’ll probably take 6 months to 1 year before I submit the library again.

I think I was being too optimistic when I commented “6 months”. It’d only be possible to complete it within 6 months if Boost.Http was the only project I was developing. Of course I have a job and university and the splitted focus wouldn’t allow me to finish the library in just this small amount of time.

Monads

Faz algum tempo desde a última vez que escrevo sobre algum padrão de projeto. O último texto que lembro foi o texto sobre CRTP, e nesse tempo meu conhecimento sobre programação aumentou, minhas habilidades comunicativas aumentaram e eu passei a escrever textos melhores. O texto que fiz sobre CRTP, nem acho importante. Entretanto, decidi fazer um texto para explicar monads, pois existe toda essa tradição de que, ao compreender o que é monad, você atinge uma epifania satisfatoriamente envolvente, você sente um desejo incontrolável de tentar compartilhar esse conhecimento com toda a humanidade, e você FALHA, mas, até pior que isso, seu manual é diferente e as pessoas vão perder até mais tempo tentando aprender o que é monad, pois agora há até mais textos confusos que acumulamos.

Eu, é claro, demorei muito tempo para aprender monads, apesar de estar usando monads há bastante tempo. Quando finalmente aprendi o que é monad, percebi o quão simples é esse conceito. Devo essa compreensão ao Douglas Crockford.

Introdução

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

Entendeu? Eu também não, e esse tipo de explicação era uma das razões para eu ter demorado a aprender.

Uma coisa importante para prosseguir com a explicação, é deixar claro os termos utilizados. E o primeiro termo que pretendo deixar claro é o de valor. Em programação funcional pura, não é tão raro assim evitar o uso do termo variável e usar, no lugar, o termo associar (binding em inglês), para indicar que um nome está se referindo a algum valor. Quando você se refere a variável, talvez implicitamente você assuma que você pode mudar o valor dessa variável, mas nem sempre é essa a mensagem que queremos comunicar. Há também o termo objeto, do paradigma de programação orientada a objetos, que podemos usar no lugar do termo variável, mas o termo objeto também carrega  outras informações que podem não ser necessárias para a explicação que estamos tentando passar. Por essas razões, eu vou, durante o texto, tentar usar o termo valor, mas se você substituir esse termo por objeto ou variável, ainda é provável que o texto continue fazendo sentido.

Há também o termo função, que em programação pode acabar tendo um significado diferente. Em programação, há o termo subrotina, que não equivale ao termo de função na matemática. Entretanto, algumas linguagens de programação usam o termo função para se referir ao conceito de subrotina, criando uma situação de falso cognato. Para “diminuir” a confusão, passamos a chamar de funções puras, as funções que possuíam o mesmo significado que as funções possuem em matemática. Essa curiosidade não é tão importante para o entendimento de monads, mas é bom que você comece a consumir algumas informações relacionadas para estar estimulado o suficiente quando a explicação de monads aparecer.

Ainda no tópico de funções, temos a diferença de funções membros e funções não-membros. Funções membros são funções que recebem o this/self, que fazem parte de alguma classe e não são métodos estáticos, funções que chamamos de métodos na programação orientada a objetos. Funções não-membros são funções livres, que não fazem parte de nenhuma classe. Quando eu me referir a uma função que recebe a e b como argumentos, as duas situações exemplificadas no seguinte código são interpretações válidas:

	class X {};
	void foo(X a, int b);
	class Y
	{
	public:
	void foo(int b);
	};
	int main()
	{
	int b;
	// Interpretação #1
	{
	X a;
	foo(a, b);
	}
	// Interpretação #2
	{
	Y a;
	a.foo(b);
	}
	}

view raw member functions and free functions.cpp hosted with ❤ by GitHub

Nos dois casos, temos uma função foo que recebe a e b como argumentos. Há até esforços para tornar a sintaxe de chamada de funções em C++ mais uniforme. A linguagem Rust está ligeiramente à frente nessa corrida, enquanto outras linguagens já chegaram lá.

Você pode enxergar monad como um padrão de projeto, e, dentro desse padrão de projeto, há o “objeto” que de fato representa o monad. Assim como ocorre no padrão Singleton, onde o mesmo termo, Singleton, se refere (1) ao padrão de projetos e a (1) um objeto que respeita algumas características. Estou citando o padrão Singleton, porque esse é, pela minha experiência, o padrão mais famoso e mais fácil de entender. A parte importante para manter em mente é que monad é um valor, mas, em alguns momentos, pode ser que eu me refira a monad como um padrão de projeto.

Valores embrulhados

Em alguns cantos na terra da programação, podemos encontrar valores que são embrulhados. Por exemplo, temos a classe Integer, na linguagem Java, que embrulha um valor primitivo int. Temos também, em C++, a classe auto_ptr<T>, que embrulha um valor do tipo T. Instâncias dessas classes não são monads.

Valores embrulhados por outro valor são isolados, tornando-se acessíveis somente a partir de uma interface. Eles não podem ser acessados diretamente, pois estão embrulhados em outro valor, seja lá qual for o propósito. No caso da classe Integer, você precisa usar a função intValue para acessar o valor embrulhado. No caso da classe auto_ptr<T>, você precisa usar a função que sobrecarrega o operador de desreferenciamento da classe.

Monads também embrulham valores. Monads são valores que embrulham outros valores e apresentam três propriedades. Entretanto, eu só vou informá-las ao final do texto.

Função unit e função bind

Unit é uma função que recebe como argumento o valor a ser embrulhado e retorna o monad. É também conhecido como construtor em outros locais. Seria o “construtor” do monad.

	function unit(val) {
	return { /* ... */ val /* ... */};
	}

view raw unit monad function.js hosted with ❤ by GitHub

Bind é uma função que recebe dois argumentos, um monad e uma função que tenha a “mesma assinatura” de unit, e retorna um novo monad. Usei a expressão “mesma assinatura” entre aspas, pois, na verdade, a situação não precisa ser tão estrita assim. O tipo de retorno pode ser um monad diferente, mas o argumento de entrada precisa ser do mesmo tipo ou compatível.

	// LEMBRETE: monad é um padrão, e sua implementação não precisa ser exatamente assim:
	function bind(monad, f) {
	return f(monad.value);
	}
	// bind também podia ser uma função-membro, possibilitando algo do tipo:
	monad.bind(f_1).bind(f_2).bind(f_3);

view raw monad bind function.js hosted with ❤ by GitHub

Em um monad, deve existir uma forma de acessar o valor embrulhado através da função bind, mesmo que essa não seja a única forma de acessar o valor, e mesmo que a função receba outro nome que não seja bind. Daí que encontramos algumas discussões usando termos como “monadic operations“.

A ideia por trás dessa estrutura é a componibilidade. Talvez não seja tão incrível para eu ou você, pois estamos acostumados a ter outras ferramentas disponíveis, mas parece ser um conceito incrível para os programadores da comunidade de programação funcional pura.

Em Haskell, monads costumam ser usados para isolar comportamentos que não são livres de efeitos colaterais, como I/O. Rust, uma linguagem que possui “;”, não precisa de monads, mas o núcleo de seu sistema da tratamentos de erros é feito em cima das ideias de monads.

Alguns monads

Maybe

Maybe é um monad, em alguns locais recebendo o nome de Option ou optional, e às vezes nem sequer obedecendo as propriedades de um monad. O propósito de Maybe é simples: possivelmente armazenar um valor. Você pode encarar esse monad como uma abstração que lhe permite expressar a semântica de valores opcionais, que em C são representados através de ponteiros que possivelmente possuem o valor NULL, ou em Java, onde qualquer objeto pode ser null.

O legal desse monad é que você ganha segurança, pois verificar pela existência do valor para então acessá-lo não acontece. É mais seguro, porque, no modelo antigo, era possível você tentar acessar o valor esquecendo de verificar antes se ele existia, esquecer do if. Com o padrão de monad/Maybe, você só usa a função bind que já recebe o valor “extraído” e ela só é chamada se o valor for diferente de None.

	int non_maybe_version(int *v)
	{
	if (v)
	return *v;
	return 0;
	}
	int maybe_version(Maybe<int> v)
	{
	int ret = 0;
	v.bind([&ret](int v) {
	ret = v;
	});
	return ret;
	}

view raw maybe.cpp hosted with ❤ by GitHub

A verdade é que esse monad fica bem mais legal se houver suporte a nível de linguagem para exhaustive pattern matching, como ocorre em Rust. Em Rust, a abstração que equivale a esse monad é a abstração Option.

Na verdade, o exemplo de código anterior usa um bind “não-conformante”, pois a função/closure passada como argumento não retorna outro monad, mas escrevi mesmo assim para ser breve. Pattern matching costuma ser mais interessante para acessar o valor e você abstrai outros comportamentos que são mais interessantes para serem encapsulados como “operações monádicas” (a documentação da abstração Option em Rust é um ótimo exemplo).

Result

Se Maybe é a abstração para valor-ou-nada, Result é a abstração para valor-ou-erro. Suponha uma função que converta uma string para um inteiro de 32 bits. Erros podem acontecer e pode ser que você queira usar o Maybe<int> como retorno da função, mas talvez seja interessante diferenciar o porquê da função ter falhado, se foi devido a uma string inválida ou overflow, por exemplo.

Result como monad é bem interessante, porque lhe permite encadear uma cadeia de ações e, caso alguma delas retorne erro, a cadeia para, e o erro é armazenado, sem que você precise explicitamente verificar por sua existência. Na linguagem Rust, até existe uma macro, try!, que torna o código até mais legível a agradável.

É interessante ter operações monádicas em Result que só atuam em um dos valores (o esperado ou o valor de erro), então você teria Result<T, E>::map e Result<T, E>::map_err.

Future

Futures e promises se referem a um padrão na computação para abordar o problema de concorrência e dependência de dados. Nesse padrão, o future é um valor que embrulha o resultado, que é computado assincronamente. Alguma função como get pode ser usada para obter o resultado e, caso não esteja pronto, a thread atual é bloqueada até que ele esteja disponível.

A adição de operações monádicas permite definir uma API que anexe continuações que seriam executadas quando o resultado estiver pronto, livrando-lhe do problema de bloquear a thread atual (que essencialmente mata o paralelismo). C++ é uma linguagem que atualmente possui abstrações de futures e promises, mas não possui as operações monádicas que tornariam essa abstração muito mais agradável de ser utilizada, como é explicado em um bom texto do Bartosz Milewski.

Programadores de NodeJS querem usar futures para se livrar de códigos profundamente aninhados (também conhecido como nesting hell). Futures são monads que podem livrar o programador da verificação explícita de erros para cada operação. Se bind for uma função-membro, o aninhamento infernal é, de fato, eliminado. O benefício é um ganho na legibilidade que pode ter grandes consequências como produtividade aumentada e diminuição de erros.

As três propriedades de um monad

	unit(value).bind(f) === f(value);
	monad.bind(unit) === monad;
	(monad.bind(f).bind(g)
	=== monad.bind(function(value) { return f(value).bind(g); }))

view raw monad axioms.js hosted with ❤ by GitHub

A terceira propriedade existe para garantir ordem. E isso é importante para composibilidade.

Conclusão

Utilidade. A utilidade de você entender monads é que agora, quando os programadores de Haskell invadirem sua comunidade de programação, você vai entender o que eles querem dizer por monad. A utilidade se resume a comunicação, mas eu não recomendo que você use o termo monad para documentar abstrações que você crie que modelem o conceito de monad, pois é inútil. Dizer que uma abstração modela o conceito de monad não vai me fazer querer usar tal abstração. Demonstrar a utilidade da abstração vai me fazer querer usá-la e omitir o termo monad não vai tornar a demonstração mais longa ou menos clara. Só use o termo monad para questão de comunicação, quando você estiver tentando se comunicar com programadores de Haskell.