Un piccolo esempio di generatore in C++…

Qualche giorno fa ho partecipato ad un’interessante discussione, iniziata dall’amico JustB, sull’uso della coppia di chiamate setjmp/longjmp del C e se valesse la pena sfruttarle per emulare le eccezioni del C++ in C.

Avendoci già provato a suo tempo – con esito positivo -, ho confermato questa possibilità, osservando però che l’utilità pratica, a mio giudizio, è scarsa o nulla:

“… il 99% delle guide sul C++ sconsiglia di usare le eccezioni (cfr. post), figurati reimplementarle in C”

Questo però non significa che non si possano fare altre cose interessanti con quelle due funzioni. Così, mi sono ripromesso di mostrargli un altro uso di quelle due “chiamate”. Ed ecco qui l’esempio-risultato.

Costruire un generatore in C

Prima di tutto, giusto per evitare equivoci, è bene precisare a che tipo di generatore mi stia riferendo. Da Wikipedia:

In computer science, a generator is a special routine that can be used to control the iteration behaviour of a loop. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values.

However, instead of building an array containing all the values and returning them all at once, a generator yields the values one at a time, which requires less memory and allows the caller to get started processing the first few values immediately.

In short, a generator looks like a function but behaves like an iterator. Generators can be implemented in terms of more expressive control flow constructs, such as coroutines or first-class continuations.

Detto ciò, lo scopo di questi post è semplice: voglio costruire qualcosa a cui, data una lista, chiedo via via tutti gli elementi, uno per volta. Quel qualcosa, una funzione, deve tuttavia essere in grado di fornire l’elemento successivo rispetto a quello della richiesta precedente.

Nulla di particolarmente complicato di per sè – un paio di variabili dichiarati statici e via -, ma quello che volevo tentare di emulare – o anche solo avvicinare negli effetti – è la yield del C#. Questa istruzione fa da sola tutto quello che ci si aspetta. Prendiamo l’esempio di Wikipedia in C# 2+:

// Method that takes an iterable input (possibly an array)
// and returns all even numbers.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers) {
    foreach (int i in numbers) {
        if ((i % 2) == 0) {
            yield return i;
        }
    }
}

La funzione GetEven riceve una lista (tipo enumerato) di numeri e restituisce il primo elemento pari rispetto all’ultima invocazione. Il meccanismo per cui, trovato un elemento pari nella lista, la funzione torna subito per poi riprendere la ricerca da quel punto nel caso di un’invocazione successiva della funzione è gestita dal compilatore attraverso l’istruzione yield.

In pratica appena prima di ritornare un numero, il compilatore C# in automatico salva dove è arrivato cosicché può riprendere da lì in un secondo momento.

Ecco, lo scopo di questo esempio didattico, è ottenere qualcosa di simile in C++ attraverso il duo setjmp/longjmp “ereditato” dal C.

Qualche spiegazione

L’idea chiave è banale: con la setjmp salviamo il punto dove saltare e con la longjmp ri-saltiamo “dove c’eravamo lasciati alla puntata precedente”.

La realizzazione è un filo più complessa nel senso che il codice che gestisce i salti è racchiuso in una funzione templated, stlNext, adatta ad essere usata su container STL diversi, come vector e deque. Lo spostamento vero e proprio in avanti fra gli elementi viene effettuato attraverso un iteratore costante (giusto per non usare indici e rendere le cose più interessanti).

Per verificare la bontà del meccanismo, un’altra piccola funzione templated di test, printAllElements, itera su tutti gli elementi di un container, fino ad arrivare alla fine, in cui verrà lanciata l’eccezione standard out_of_range.

Potete verificare i salti osservando come l’assegnamento iniziale del riferimento al container input (“[assignment]” verrà stampato sullo standard output) avviene solamente la prima volta che la funzione stlNext viene invocata su quel container.

Per rendere le cose più divertenti, ho aggiunto la possibilità di resettare (cioè ripartire dall’inizio o quasi) stlNext, impostando a true l’omonimo parametro-flag.

Come ho già detto, questo codice va considerato come un puro esempio didattico. Non lo userei mai nè francamente ne vedo l’utilità, avendo fra l’altro già a disposizione gli iteratori nel caso dei container STL. Ero in vena di sperimentare e ho sperimentato, fine della traccia.

In questo post ho parlato di generatori realizzati salvando l’”ambiente” (stack) con la setjmp per poi ritornarci con la longjmp. Questo è il concetto-chiave delle continuazioni: In informatica, una continuazione (continuation in inglese) è un modo per rappresentare lo stato di esecuzione di un programma (vedi anche Stack) ad un punto dato. Molti linguaggi hanno un costrutto che permette di salvare lo stato corrente di esecuzione per poi riprendere l’esecuzione a partire da questo stato in un momento successivo. Tuttavia, non ho voluto indicare esplicitamente questo post come “esempio di continuazione” perchè c’è chi sostiene che quel duo di chiamate C sia troppo semplice e limitato per ottenerne una “seria”, al contrario della ben più potente famiglia di chiamate C di cui fa parte setcontext: setcontext is one of a family of C library functions (the others being getcontext, makecontext and swapcontext) used for context control. The setcontext family allows the implementation in C of advanced control flow patterns such as iterators, fibers, and coroutines. They may be viewed as an advanced version of setjmp/longjmp; whereas the latter allows only a single non-local jump up the stack, setcontext allows the creation of multiple cooperative threads of control, each with its own stack. Altri invece sostengono che setjmp/longjmp bastino già a creare delle continuation, addirittura per emulare in C la Call-with-current-continuation (call/cc) dei linguaggi funzionali come Scheme. Non volendo generare nè partecipare a flamewar sull’argomento, lascio a voi la scelta sulla terminologia che ritenete più corretta e adatta a questo post-esempio.

Il codice

/**
 *	FILE     : CppGeneratorTest.cpp
 *	AUTHOR   : Gian Paolo "JP" Ghilardi (http://rejex.wordpress.com)
 *	LICENSE  : released under the terms of GPL v2.0 ("only")
 *	COMPILE  : g++ -Wall -pedantic CppGeneratorTest.cpp -o CppGeneratorTest
 *	PURPOSE  : simple example showing how to create a sort of generator [1]
 *             in C++ and test it against some standard STL containers
 *
 *	TESTED ON:
 *	- Linux Debian 6.0.3 32-bit, GCC 4.4.5
 *	- Linux Ubuntu 11.10 64-bit, GCC 4.6.1 & Clang++ 2.9
 *	- Windows 7,  x86 32-bit, GCC 4.6.1 & MS VSC++ 2010 SP1 (Release Mode)
 *	- Windows XP, x86 32-bit, GCC 4.6.1 & MS VSC++ 2010 SP1 (Release Mode)
 *
 *	REFERENCES:
 *	[1]: http://en.wikipedia.org/wiki/Generator_%28computer_science%29#C.23
 *	[2]: http://msdn.microsoft.com/en-us/library/9k7k7cf0.aspx
 *	[3]: http://www.sgi.com/tech/stl/Container.html
 *	[4]: http://www.cplusplus.com/reference/clibrary/csetjmp/
 *	[5]: http://www.cplusplus.com/reference/clibrary/csetjmp/longjmp/
 *	[6]: http://www.cplusplus.com/reference/std/stdexcept/out_of_range/
 *	[7]: http://www.cprogramming.com/tutorial/templated_functions.html
 */

#include <csetjmp> // [3, 4]
#include <cstdlib>
#include <iostream>
#include <stdexcept>
#include <string>
#include <deque>
#include <vector>

using namespace std;

template<typename T>
static typename T::value_type stlNext(const T& input, bool reset = false)
{
	static jmp_buf env;
	static int val = -1;

	if(val != -1) // Jump to first saved point (if already set)
	{
		cout << "[jumping]" << endl;
		longjmp(env, 0);
	}

	static typename T::const_iterator iter = input.begin();
	cout << "[assignment]" << endl;

	val = setjmp(env); // Save calling environment for jumps (jump point)
	if(reset == true)  // Handle reset (rewind) request
	{
		cout << "[re-assignment]" << endl;
		iter = input.begin();
	}

	if(iter != input.end()) // Check if we've reached the last jump point
	{
		cout << "[returning next iter]: ";
		return *(iter++);
	}
	else
		throw out_of_range("[ok: last element reached]");
}

template <typename T>
static void printAllElements(T& input, bool reset = false)
{
	  try
	  {
		  while(true)
		  {
			  // Fetching the next element from the generator
			  // Note: using template function type inference (no <>) [7]
			  cout << stlNext(input, reset) << endl;
			  reset = false; // (Just once!)
		  }
	  }
	  catch (out_of_range& oor)
	  {
	      cerr << "Out of Range error: " << oor.what() << endl;
	  }
}

int main (int argc, char ** argv)
{
	cout <<
		"\nC++ GENERATOR EXAMPLE:\n"
		"Simple C example showing how to create/fake\n"
		"a generator in C++ via setjmp/longjmp\n" << endl;

	vector<int> v1;
	for(int i=0; i<10; i++)
	  v1.push_back(i);

	cout << "[Test #1 - int vector]: " << endl;
	printAllElements(v1);

	vector<string> v2;
	v2.push_back("A");
	v2.push_back("B");
	v2.push_back("C");
	cout << "\n[Test #2 - string vector]: " << endl;
	printAllElements(v2);

	v2.push_back("E");
	v2.push_back("F");
	v2.push_back("G");
	cout << "\n[Test #3 inserts and rewind of previous vector]: " << endl;
	printAllElements(v2, true);

	deque<string> d1;
	d1.push_back("H");
	d1.push_back("I");
	d1.push_back("L");
	cout << "\n[Test #4 - string deque]: " << endl;
	printAllElements(d1);

	cout << "\n[end]" << endl;

	return EXIT_SUCCESS;
}

Il codice dal vivo

A dispetto degli avvertimenti sulle diverse implementazioni di setjmp/longjmp, dichiarate spesso come incompatibili, ho testato il codice su diverse piattaforme, ottenendo lo stesso comportamento atteso.

Di seguito uno screenshot del codice, compilato con G++ 4.6.1 e con Clang++ 2.9, in esecuzione sulla recentissima Ubuntu 11.10 64-bit.

Che ne pensate?