Let’s play with Theano


This article will briefly present Theano, a machine learning library and introduce it with a small regression problem.

It will describe how to play with Theano to classify a single word between french or english sets using a classifier over 4 features only :

  • The size of the word divided by 30 (let’s assume there is no word exceeding 30 characters)
  • The vowel ratio
  • Maximum consecutive vowels substring length (divided by the word size)
  • Maximum consecutive consonants length (divided by the word size)

After training over a 6.000 french/english words training set it was able to classify a 230.000 words validation set with a 66.8% success rate.

This is a very simple problem suggested by a friend to test Theano. I think it would be possible to get better results by extracting more features on the word and usng a better classifier, but I chose to keep things simple.

A machine learning library :

Theano is a python library defined as a « linear algebra compiler ». It facilitate multidimensional mathematical expression definition, compilation and evaluation. It also provides a way to compute mathematical expressions with transparent use of a GPU.

Let’s study a little example of code to get a little overview of what is possible with Theano. The goal of this example is to define a matrix-addition function.

As we would do in math we first define the type of our variables :

a = tensor.dmatrix('a')
b = tensor.dmatrix('b')

This mean that a and b are two matrices (the constructor parameter is used by the pretty-printer when an exception is raised for example).

Then, we define the function which takes two matrices in parameter and return the sum of the two matrices.

# We first define the input of the function as :
X = [a, b]
# then the output :
Y = a + b
# Then we ask theano to compile the function f: X -> Y
f = function(X, Y)

At this step, we can use f to compute matrices addition, and the evaluation will use the GPU ! Now, let’s see with a simple regression problem.

What is regression ?

Regression problems are common machine learning problems.

The solution of a regression problem is a function (note that in most of cases d’ is equal to 1) :

To find this function, we only know « examples » of the output of f for a finite set of inputs. This set of examples is called « training-set ». A regression algorithm will learn a function which will fit with the training-set and expect to generalize this function for data outside the training set.

There is also a lot of methods to find this function as :

  • Regression trees
  • Neural networks
  • Linear regression

Each of these methods use a different model. A model is an a priori (also called bias) on the set of function that will fit with the one we are looking for. We only train the model to fit with the training set.

It is impossible to design a machine learning algorithm without this a priori. Without this seed, you would not be able to generalize your functions for unseen examples (for more informations see : bias-variance dilemma).

What is linear regression ?

With linear regression you will be able to approximate functions, using a linear transformation of your input vector. It also modelize your function using a line for a 2-dimensional vector, a plane (3-dimensional), a hyperplane…

f, the model which is your approximation of the targeted function F, is defined as:


W is a weight vector (initially random) :

Your function is also a dot-product between your weight vector and the input. You will also try to learn the best weight vector W to find the best linear approximation f of F on the training-set.

Training-set definition :

Your function will learn using several examples. This set of examples is called the training-set (Ξ). Because your input is a d-dimensional vector weight and you have n examples, your training set will also be a n*d-matrix.

For each training example weight vector Xi (the ith line of  Ξ) you have an output Oi = f(Xi) and an expected output Ei = F(Xi).

Computing the error made :

As you can see, for each example you can compute Oi, the dot product between the ith example and the weight vector. The squared error (positive + differentiable) made on the training is defined as :

The idea of linear regression is to :

  1. compute the gradient vector of the error made on the training-set
  2. iterate a step on the weight vector following the gradient vector direction
  3. recompute the gradient vector
  4. Jump to 1 until k iterations

The error gradient vector is defined as :

This vector gives the error direction for each weight value variation. If we follow the opposite direction of this vector, the error will also fall down.

You can easily calculate the partial derivative of each component of the weight vector, but Theano already do the job for you !

Understand the gradient descent

To understand the gradient descent algorithm, I like to visualize the problem in a 2 dimensional instance.

You want to find a 2-dimensional weight vector W to minimize the error. You know the expression of the error (which depends of w1 and w2) and its gradient.

The algorithm will first pick a random position, then it will follow the highest slope direction to fall down while it’s possible. If will also find a local minimum of the error which is potentially a good approximation of the mysterious function F seen through the examples.

You can just imagine that you throw a ball in the graph and that you let the physics happens while the ball is falling. If you’re not satisfied, just throw it again !

Play with Theano

In our case, we need to approximate a function which gives the probability of a word being a french word given its features : P(french | X). Obviously, the probability of a word being an english word would be 1 – P(french | X).

The result of the function is also contained between [0, 1]. With a linear transform, our result is not bounded. We can use a sigmoid function to get the value of the probability for a given result of the linear transformation.

This function is bounded between 0 and 1 and at the origin, its value is 0.5. It is a also a differentiable function, so we will still be able to compute the error gradient.

Define the data :

TS = tensor.matrix('training-set')
W = tensor.matrix('weights')
E = tensor.matrix('expected')

Define the model and its error:

# O is the matrix (column) containing the output for each example
O = tensor.nnet.sigmoid(tensor.dot(TS, W))
# def_err is the squared error sum for each example
def_err = ((E - O) ** 2).sum()

Compile the error function and its gradient :

# Theano is magic
err = function([W, TS, E], def_err)
grad_err = function([W, TS, E], grad(e, W)) # ...and this is very dark magic

Regression algorithm :

precision = 0.001
# Load the dataset containing the feature for each word of the training set
dataset = load_dataset()
# Load the expected output vector E containing 1.0 for french, 0.0 for english for each word of the TS
expected_output = load_expected_outputs()
# Initial random weight vector
weights = scipy.random.standard_normal((4, 1))

for i in range(100):
    err_val = err(weights, dataset, expected_output)
    err_grad_val = grad_err(weights, dataset, expected_output)
    weights -= precision * error_grad_val
    print("Iteration " + str(i) + ", squared error : " + str(err_val)

print("-------- Training result -------")
print("Final squared error : " + str(err(weights, dataset, expected_output)))
print("Computed weight vector :")

Learn more

You will find a great documentation and a lot of tutorials about this library on deeplearning.net.

Cluster management system

Quick overview

I write this little article to present the features of a new project started few days ago.

I’m coding a cluster management system, to handle multiple workers performing different tasks :

  • artificial intelligence algorithms
  • data-storing
  • anything else…

This system is based on a global management system containing few services concurrently running :

  • a python HTTP server for web administration
  • a python server called dispatcher performing calls to a C task-scheduler library
  • misc network utilities (proxy, load balancer, …)
  • SSH server for CLI administration

A custom shell is available both with SSH and a with small javascript web application to manage the daemon with a command line interface easily ! But it’s only a beginning !

Task scheduling and programming language

The task scheduling algorithm has been tested with a distributed computing spare-time project with François Boiteux and Camille Dollé (https://github.com/Underflow/parallel-computing) on a small cluster in a LAN (20-100 x86 machines). It is for the moment working with a round robin algorithm and tasks are indexed with an hashtable for rapid access. Task priority is not handled yet.

There is both client and server side C library, and even a almost working proof of concept compiler (https://github.com/Underflow/tiny-language) for a custom programming language to write distributed algorithm written with Guillaume Sanchez last year. This language is verry close to C, there is as less as possible side-effects and it implements an operator ‘@’ to prefix funcalls and distribute them to a node easily with low level runtime speed


  • Remote directory
  • Shell commands
  • Package management system
  • Any idea ..?

L’algorithme peut-il dépasser l’homme ?

La question semble à première vue évidente. Les ordinateurs ont permis à l’homme de mettre en application des processus intellectuels sous la forme de suite d’instructions ordonnées, s’exécutant plus rapidement que dans notre cerveau. La mémoire disponible peut largement dépasser ce que notre cerveau est capable de retenir, et n’est soumise à l’oubli ou l’erreur.

De ce point de vue là, la machine semble un prédateur intellectuel de l’homme. Cependant, s’il existe bien un point où la machine semble loin d’égaler les facultés de notre espèce c’est dans sa capacité à s’adapter et trouver, seul, des solutions à des problèmes inconnus. Est-ce réellement le cas ?

Machine de Turing et IA forte ?

Dans ses recherches sur la calculabilité et l’algorithmie, Alan Turing a réussi à formaliser une machine capable d’exécuter une procédure de calcul.

Machine de Turing

Son principe est élémentaire : la machine dispose d’un ruban sur lequel sont inscrit des lettres, d’un état (un nombre par exemple) et d’une table de transition. Le nombre d’états possibles de la machine est fini et à son lancement, elle dispose d’un état initial.

Lorsque la machine démarre, elle lit la première lettre et utilise la fonction de transition qui selon la lettre lue et l’état courant lui indique ce par quoi elle doit remplacer la lettre lue et un déplacement (vers la gauche ou vers à droite du ruban) à effectuer. La tête de lecture du ruban va donc ainsi parcourir et modifier le contenu du ruban jusqu’à arriver à un état  final, où la machine s’arrête.

De nos jours, on qualifie les langages de programmation de « Turing-complet » lorsqu’ils sont capables d’effectuer tous les calculs réalisables sur une machine de Turing.

Si nous réalisons un jour une intelligence artificielle forte (disposant d’une conscience de soi), celle-ci devrait donc pouvoir s’exécuter sur cette machine aussi simpliste pouvant même fonctionner sans électronique. De plus, donnez moi un crayon, une gomme et la table de transition de cette intelligence artificielle et je serai capable de doter ma feuille d’une conscience. Quand un film hollywoodien réussir à me faire imaginer un robot sensible, ici j’ai définitivement du mal à admettre cette possibilité.

Apprendre à être intelligent

Les travaux de recherche actuels en intelligence artificielle visent à reproduire l’intelligence artificielle humaine sur des problèmes spécifiques (agent conversationnel, traitement de la parole, …) et non dans son ensemble.

La piste la plus prometteuse en IA est selon moi l’apprentissage automatique. En effet, quand un problème est trop complexe pour être traité par un algorithme écrit par l’homme, nous pouvons choisir de laisser la machine déterminer elle-même une solution pour résoudre un tel problème. Ce processus est long mais facilite énormément la réalisation d’algorithmes tels que la reconnaissance de caractères.

Beaucoup d’articles concernant l’apprentissage automatique sont trompeurs et laissent sous-entendre que les limites en IA sont imposées par la puissance de calcul vu qu’il suffirait d’apprendre suffisamment longtemps pour avoir un système acceptable.

L’apprentissage automatique fonctionne de la manière suivante :

  1. On définit une « fonction intelligente » dépendant de plusieurs coefficients
  2. On cherche les meilleurs coefficients pour que la fonction soit la plus précise possible
Ce problème est donc un problème d’optimisation (il s’agit de trouver la valeur optimale des coefficients). Or le No Free Lunch Theorem démontre justement qu’il n’existe pas de méthode d’optimisation qui soit efficace pour tous les problèmes d’optimisation possibles. On ne peut donc pas imaginer de super-algorithme d’apprentissage qui soit adaptable à tous les problèmes rencontrés par l’intelligence artificielle.
Cette interprétation est cependant à relativiser. On peut imaginer que l’ensemble des problèmes que l’homme peut traiter est une sous-classe de l’ensemble des problèmes pour lesquels un algorithme d’optimisation général est efficace.

Machines et preuves mathématiques

Un ordinateur peut-il résoudre un problème mathématique jusqu’alors non résolue ? Oui.

Un ordinateur peut être utilisé pour infirmer une preuve en se basant sur l’existence d’un contre exemple. Nous sommes exactement dans l’application des machines de Turing puisqu’il s’agit d’itérer suffisamment de fois pour arriver sur un cas où l’assertion est fausse. L’hypothèse de Riemann, qui a de grandes implications sur la distribution des nombres premiers, a été ainsi testée à l’aide de cette méthode. Les 10 000 000 000 000 premiers 0 ont ainsi été testés sans pour autant trouver de contre exemple. Mais cela ne prouve pas que cela est vrai jusqu’à l’infini !

Lorsqu’une proposition doit être démontrée pour un ensemble fini la machine de Turing peut aussi être utilisée. C’est le cas du théorème des quatre couleurs qui comporte 1478 cas qui ont été vérifiée à l’aide de l’informatique. La démonstration n’a cependant pas été admise, la validité de l’algorithme et de sa correcte exécution n’étant pas prouvée.

Enfin, il existe des algorithmes permettant de vérifier des preuves exprimés dans un langage formel. Ceux-ci s’exécutent en temps polynomial. Une recherche par force-brute d’une preuve mathématique est donc envisageable mais sera alors un problème de classe NP. La question du millénaire « P=NP ? » prend alors toute son importance puisqu’elle impliquerait l’existence d’algorithmes polynomiaux capables de trouver la preuve d’une assertion.

Il faut cependant bien remarquer que dans tous les cas, l’algorithme adopte une méthode calculatoire naïve, ce n’est donc absolument pas un critère permettant de parler d’intelligence mathématique à proprement parler… sauf si P=NP.
Serait-ce la clé ? J’aimerais vivre assez longtemps pour le savoir.


Conférence sur les algorithmes génétiques


Ce Vendredi 25 Janvier je ferai une conference sur les algorithmes genetiques à l’EPITA, rue Pasteur au Kremlin Bicetre.

Mise à jour :

Vous pouvez retrouver l’enregistrement de la conférence sur Daylimotion :

GCONFS – Algo G par epita

Un réseau de neurones artificiels évolutif

Présentation du projet

Vous pouvez trouver les sources de ce projet sur mon github : http://repository.underflow.fr/genetik-perceptron

Le but est d’implémenter un réseau de neurones entraîné par un algorithme génétique avec une abstraction du problème à résoudre suffisante pour être capable d’apprendre à faire un peu tout et n’importe quoi.

Il aura bientôt la possibilité d’être couplé à un programme externe qui lui s’occupera de la simulation du problème (exemple : un jeu vidéo où le réseau de neurones devra apprendre jouer).

Réseaux de neurones artificiels

Commençons par une définition rapide :

« Un réseau de neurones artificiels est un modèle de calcul dont la conception est très schématiquement inspirée du fonctionnement des neurones biologiques. »

Comme l’indique la définition, l’objectif premier d’un réseau de neurones artificiels est d’effectuer un calcul et son principal atout réside dans capacité à apprendre tout seul à le faire, par l’expérience.

Un réseau de neurones artificiels est constitué de neurones artificiels qui sont le plus souvent reliés par couches successives :

Chaque neurone possède n entrées pondérées et 1 sortie qui est reliée à tous les neurones de la couche suivante. La valeur de sa sortie est donnée par l’application à une fonction de transfert de la somme pondérée de ses entrées.

Auteur : Chrislb

Pour plus d’explications : http://fr.wikipedia.org/wiki/Réseau_de_neurones_artificiels

Pour un problème donné par exemple reconnaître un visage d’homme et de femme, on va envoyer en en entrée dans le réseau de neurones la position des yeux, de la bouche, du nez, etc… En fonction des coefficients de chacun des neurones, couche par couche l’information va être traitée, jusqu’au neurone de sortie qui retournera 0 s’il pense qu’il s’agissait probablement d’un homme ou 1 s’il s’agissait d’une femme.

La difficulté réside donc entièrement dans la détermination de la valeur des coefficients à affecter aux différents neurones du réseau.


L’apprentissage équivaut donc à l’ajustement des différents coefficients des neurones du réseau. Un algorithme est très efficace pour ça : la rétropropagation du gradient. Il va tenter d’ajuster automatiquement les poids des connections en fonction de l’erreur commise par le réseau.

J’ai cependant décidé d’expérimenter une technique un peu plus exotique et qui est adaptée à problème où l’on ne peut pas déterminer quelle est l’erreur commise par le réseau mais plutôt quelle a été sa performance pour traiter un problème, à savoir : un apprentissage par le biais d’un algorithme évolutif.

Dans mon précédent billet, j’explique le principe de ces algorithmes, et je l’ai appliqué au cas de l’ajustement des pondérations d’un réseau de neurones et les résultats sont pour l’instant plus qu’encourageants.

Premier test

Le premier test effectué pour l’instant est très simpliste. Il s’agissait d’entraîner un réseau à résoudre (A > 0) XOR (B > 0) avec A la première entrée et B la deuxième entrée.

Le réseau entraîné possède 2 entrées 3 neurones sur la première couche, 3 sur la seconde et 1 pour la couche de sortie.

Pour déterminer le fitness du réseau, j’effectue 10.000 tests avec des entrées tirées aléatoirement sur l’interval [min_int; max_int] et je calcule le pourcentage de bonne réponses au problème. De générations en générations, le réseau va se perfectionner jusqu’à atteindre un score de 100% de bonnes réponses pour les 10.000 entiers tirés aléatoirement :

Best fitness : 55,4%
Best fitness : 60,1%
Best fitness : 67,8%
Best fitness : 69,7%
Best fitness : 73,2%
Best fitness : 71,8%
Best fitness : 74,6%
Best fitness : 72,5%
Best fitness : 73,4%
Best fitness : 72,5%
Best fitness : 73,6%
Best fitness : 76,7%
Best fitness : 76,9%
Best fitness : 77,3%
Best fitness : 75,2%
Best fitness : 75,1%
Best fitness : 76,2%
Best fitness : 77,2%
Best fitness : 83,3%
Best fitness : 91,9%
Best fitness : 92,9%
Best fitness : 93,9%
Best fitness : 94,5%
Best fitness : 93,4%
Best fitness : 93,7%
Best fitness : 94,5%
Best fitness : 94,5%
Best fitness : 97,7%
Best fitness : 92,6%
Best fitness : 94,2%
Best fitness : 98,1%
Best fitness : 97,5%
Best fitness : 98,1%
Best fitness : 98,2%
Best fitness : 98,7%
Best fitness : 98,1%
Best fitness : 98,1%
Best fitness : 98,8%
Best fitness : 98,5%
Best fitness : 99%
Best fitness : 98,8%
Best fitness : 98,3%
Best fitness : 98,2%
Best fitness : 98,6%
Best fitness : 98,5%
Best fitness : 98,4%
Best fitness : 98,5%
Best fitness : 90,7%
Best fitness : 91,5%
Best fitness : 98,3%
Best fitness : 98,6%
Best fitness : 98,6%
Best fitness : 98,7%
Best fitness : 98,9%
Best fitness : 99,2%
Best fitness : 98,5%
Best fitness : 97%
Best fitness : 97,5%
Best fitness : 98,2%
Best fitness : 98,6%
Best fitness : 97,6%
Best fitness : 98,3%
Best fitness : 98,2%
Best fitness : 98,6%
Best fitness : 98,4%
Best fitness : 98,3%
Best fitness : 98,3%
Best fitness : 98,3%
Best fitness : 98,7%
Best fitness : 98%
Best fitness : 97,8%
Best fitness : 98,5%
Best fitness : 98,6%
Best fitness : 99,2%
Best fitness : 99%
Best fitness : 99,5%
Best fitness : 99%
Best fitness : 99,3%
Best fitness : 99,7%
Best fitness : 100%

Et ensuite ?

Je suis actuellement en train de coder le système de communication entre le système d’apprentissage (réseau de neurone + algo génétique) et celui de simulation et d’évaluation (un jeu vidéo par exemple).

A terme, je compte faire apprendre à jouer à pong le réseau de neurones artificiels avec cette méthode !

Un algorithme génétique de dessin

Je viens de terminer un projet que je souhaitais réaliser depuis déjà un petit bout de temps : un algorithme génétique de reproduction d’images. J’ai réalisé ce projet en C pour une question de performance et pour continuer de m’entraîner sur ce langage.


L’objectif de base du programme est de reproduire une image, en utilisant uniquement des carrés de tailles et de couleurs différentes en se servant d’un algorithme génétique.

Voici typiquement le rendu obtenu au bout de quelques minutes de calculs :

Et ici un exemple un peu plus évolué  :

Je remercie au passage Dettorer pour le prêt de son serveur, il aura fallu au total environ 2h de calcul pour générer les 30.000 générations nécessaires à la création de la Joconde.

Les sources sont disponible sur mon github : https://github.com/Underflow/genetik-draw

Un algorithme génétique

Un algorithme génétique se base sur la théorie de l’évolution de Darwin pour résoudre un problème. Il fonctionne donc sur le même principe fondamental que la sélection naturelle des êtres vivants : « l’individu le plus adapté aura plus de chance de se reproduire ».

Note : Pour faire plaisir à ce connard de Chewie il faudrait plutôt parler de la théorie de Lamarck.

Tous les algorithmes génétiques fonctionnent selon le même principe :

  1. On génère une population d’individus avec un ADN aléatoire
  2. On classe les individus selon leur aptitude à résoudre un problème donné
  3. On génère une nouvelle génération d’individus en effectuant des croisements entre les individus de la dernière génération. Les individus les mieux classés ont une probabilité plus forte d’engendrer une progéniture
  4. On effectue des mutations aléatoires sur les individus (avec une probabilité relativement faible pour ne pas produire de générations de dégénérés)
  5. Retour à l’étape 2.

Pour implémenter un algorithme génétique, il faut d’abord définir le sens de l’ADN des individus. C’est à dire à quoi correspondront les données contenu dans l’ADN. Pour faire le parallèle avec les êtres vivants, dans un organisme l’ADN est transcrit en ARN qui est ensuite traduit en protéine.
De la même façon il faut réaliser une fonction de « traduction ». Dans mon cas, la fonction de traduction transforme l’ADN en une image. L’ADN contient en fait les coordonnées des carrés et leur couleur.

Ensuite, il est nécessaire de déterminer une fonction déterminant le fitness des individus, c’est à dire un score d’adaptation au problème à résoudre. J’ai choisi pour ce projet d’utiliser une bête fonction de comparaison d’image. Elle retourne la somme de la différence des couleurs de chaque pixels entre l’image source et celle de l’individu.

Enfin il faut une fonction de croisement (aka crossover) qui mélangera deux ADN pour brasser les générations. Sur mon programme, le croisement s’effectue gène par gène (ou carré par carré si vous préférez) et non pas octet par octet ce qui n’aurait eu aucun sens (ou toute autre méthode de croisement adaptée à d’autres algorithmes génétiques).


Une fois que tout ceci est correctement codé, la magie opère toute seule, et un dessin « correct » arrive très vite à l’écran !

Evolution d’une population

J’aurais pu vous faire un beau graphique, mais j’ai vraiment la flemme. Je vous copie colle le résultat de la sortie console. Le score affiché correspond au pourcentage de ressemblance entre l’image génétique et l’image à reproduire.

Generation : 0 - Best fitness : 69.230701
Generation : 10 - Best fitness : 72.895536
Generation : 20 - Best fitness : 74.464792
Generation : 30 - Best fitness : 75.163049
Generation : 40 - Best fitness : 76.264078
Generation : 50 - Best fitness : 76.895984
Generation : 60 - Best fitness : 77.855822
Generation : 70 - Best fitness : 78.508686
Generation : 80 - Best fitness : 79.311399
Generation : 90 - Best fitness : 79.834519
Generation : 100 - Best fitness : 80.285271
Generation : 110 - Best fitness : 80.652855
Generation : 120 - Best fitness : 81.155114
Generation : 130 - Best fitness : 81.250519
Generation : 140 - Best fitness : 81.679887
Generation : 150 - Best fitness : 81.935676
Generation : 160 - Best fitness : 82.397639
Generation : 170 - Best fitness : 82.737401
Generation : 180 - Best fitness : 83.023686
Generation : 190 - Best fitness : 83.427936
Generation : 200 - Best fitness : 83.569475
Generation : 210 - Best fitness : 83.896074
Generation : 220 - Best fitness : 84.156327
Generation : 230 - Best fitness : 84.421856
Generation : 240 - Best fitness : 84.653619
Generation : 280 - Bestfitness : 85.210001
Generation : 460 - Bestfitness : 87.734134
Generation : 910 - Bestfitness : 90.093073
Generation : 1810 - Bestfitness : 91.600760

Modularité et interfaçage C# <-> langages de scripts via un gestionnaire d’événement (2/2)

Ce billet fait office de suite et fin des deux billets précédents.


L’objectif était de fournir un moyen simple de développer de façon modulaire en C#. J’ai choisi de créer un système de modules basé sur un gestionnaire d’événements pour la communication intra-modulaire et pouvant s’appuyer sur un interpréteur de script.

Le mini-framework, tel qu’il est architecturé peut être utilisé de trois façons différentes :

  1. En tant que gestionnaire d’événements
  2. En tant que framework modulaire
  3. En tant que framework modulaire pouvant charger des modules écrit dans un langage de script

Je n’ai encore pas essayé de tester le système sur un projet de grande envergure, mais je prévois de développer en début d’été un logiciel de traitement de questionnaires à choix multiples pour une entreprise RH et je pense utiliser cet outil. Je publierai donc probablement quelques correctifs après avoir pris conscience de nouvelles problématiques.

Fonctionnement du gestionnaire de modules

Le fonctionnement du gestionnaire d’événement est expliqué dans un précédent billet, et je ne reviendrai pas dessus.

Commençons par la partie concernant la modularité :

Un module est caractérisé par un nom et une version. Il peut demander en prérequis une liste de modules qui devront être préalablement installés pour fonctionner. Le programmeur peut créer autant de modules qu’il le souhaite, en faisant simplement hériter une classe de la classe abstraite ModuleAdapter. Ces modules doivent implémenter la méthode Initialize() servant à initialiser les différents observateurs du module. Cette méthode est automatiquement appelée par le gestionnaire de module.

Au lancement du programme, le développeur doit « installer » les modules à l’aide de la méthode SetupModule de la classe ModuleManager. Ce setup va vérifier vérifier la correcte constitution du module (nom, version, et prérequis), puis vérifier que les prérequis sont installés et enfin appeler la méthode initialize du module.

EventSystem eventSystem = new EventSystem();
ModuleManager moduleManager = new ModuleManager(eventSystem);
moduleManager.SetupModule(new NomDuModule());

Vous constaterez ici que le gestionnaire de module prend en paramètre un système de gestion d’événement. Les modules sont en effet entièrement basés sur la levée d’événements et il est impossible d’utiliser le gestionnaire de module sans les événements.

A l’intérieur d’un module, il est impossible d’utiliser directement le gestionnaire d’événement. Le gestionnaire de modules fait l’intermédiaire en rajoutant une contrainte dans la levée d’un événement : l’émetteur. En effet, désormais un événement possède un émetteur permettant ainsi aux observateurs de filtrer les événements selon les modules les ayant déclenchés.

A l’intérieur d’un module, on doit lever les événements de la façon suivante :

 * RaiseEvent prend en paramètre un module (qui sera l'émetteur de l'événement),
 * un identifiant pour l'événement et des données
this.manager.RaiseEvent(this, "identifiant du type d'événement", [data...]");

De la même façon, vous pouvez demander au gestionnaire de module de créer des observateurs spécifiques à un module :

 * RequestWatcher prend en paramètre un module (qui sera le propriétaire de
 * l'observateur), un filtre pour l'émetteur (seuls les événements émis
 * par l'émetteur spécifiés ne seront traités par l'observateur, un filtre
 * pour l'identifiant du type d'événement et un Effet
                            "nom du module émetteur",
                            "identifiant du type d'événement",
 * Il faut noter qu'il est aussi possible de demander la création d'un
 * observateur sans contrainte sur l'émetteur de la façon suivante :
                            "identifiant du type d'événement",

Ensuite, tout fonctionne automatiquement, vos modules interceptent des événements qu’ils traitent pour relayer à nouveau de nouveaux événements aux autres modules, et ainsi de suite !

Exemple :

Il s’agit de l’implémentation sous forme modulaire du programme bidon présenté en exemple sur le billet sur le gestionnaire d’événements.

Le premier point à remarquer c’est que la classe Program est-elle même un module. Il doit donc être installé, c’est ce qu’on effectue dans le constructeur de Program. Dans la méthode Initialize on ajoute un watcher pour les événements déclenchés lorsqu’un module est installé et on installe un nouveau module (say_hello). Dans la méthode Run() on lève enfin un événement « EntryPoint » qui sera intercepté par d’autres modules.

    class Program : ModuleAdapter
        static void ModuleInstalled(string name)
            Console.WriteLine("Module \"{0}\" successfully installed", name);

        static void Main(string[] args)
            Program prgrm = new Program();

        public Program()
            : base("program", 1.0f, new ModuleManager(new EventSystem()))

        public override void Initialize()
            this.manager.RequestWatcher(this, "module_manager", "installed", Effect.Create(ModuleInstalled));
            this.manager.SetupModule(new SayHello(this.manager));

        public void Run()
            this.manager.RaiseEvent(this, "EntryPoint");

Le contenu du module SayHello :

    class SayHello : ModuleAdapter
        public SayHello()
            this.name = "say_hello";
            this.version = 1.0f;

        public override void Initialize()
             * Note : Un événement déclenché en dehors d'un module porte pour
             * identifiant d’émetteur : "program"
            // L'événement EntryPoint entraine l'appel de la fonction AskName
                  "program", //On n'observe que les événements levés par "program"

        public void AskName()
            Console.WriteLine("What is your name ?");
            string name = Console.ReadLine();
            if (name == "")
                this.manager.RaiseEvent(this, "warning", "The name is empty");
            Console.WriteLine("Hello " + name);

On remarquera que le module déclenche des événements de type « warning » qui sont interceptés par un module de gestionnaire d’erreur et d’avertissements. Ce module n’est pas installé par le développeur mais est automatiquement installé.

    class ErrorHandler : ModuleAdapter
        public ErrorHandler()
            this.name = "error_handler";
            this.version = 1.0f;

        public override void Initialize()
            this.manager.RequestWatcher(this, "error", Effect.Create(this.HandleError));
            this.manager.RequestWatcher(this, "warning", Effect.Create(this.HandleWarning));

        private void HandleError(string error)
            Console.WriteLine(" " + error);
            Console.WriteLine("Press Enter to exit");


        private void HandleWarning(string warning)
            Console.WriteLine(" " + warning);

La communication intra-modulaire fonctionne donc très simplement.

Fonctionnement du gestionnaire de scripts

L’idée est simple : vous gérez vos scripts comme vous l’entendez (qu’importe le langage, le nombre de fichiers, leur nom, les fonctions, …) mais vous devez être capable de créer un ou plusieurs objet de la classe ModuleAdapter avec vos scripts.

Fondamentalement, mon travail sur cette partie s’est résumé à l’écriture de 3 lignes de code :

interface ScriptEngine
    ModuleAdapter CreateModuleFromScript(string folder);

A l’aide de cette interface, vous devrez implémenter vos gestionnaires de scripts qui répondront donc à la contrainte de posséder une méthode générant un module à partir d’un dossier contenant des scripts.
Ceci garanti une parfaite équivalence entre les modules qui sont construits à partir d’un script et les modules qui sont écrits en C#.

Une fois implémenté, c’est simple, il suffit d’installer un module crée à partir du moteur de script :

EventSystem eventSystem = new EventSystem();
ModuleManager moduleManager = new ModuleManager(eventSystem);
ScriptEngine scriptEngine = new LUAScriptEngine();


Bon, je vais quand même prendre le temps de réaliser une ou voire deux implémentations (probablement le LUA parce que le réflexif c’est booo !).


J’ai fini ce projet, je ne sais pas si un équivalent existe déjà, ou si j’ai réinventé la roue carré, à vrai dire peu importe j’ai appris pas mal de choses !

Je met à disposition une archive des mes sources en l’état actuel des choses (il reste surement des erreurs bien cachées, c’est non documenté et mon anglais – pour le nommage – est loin d’être parfait) : Modularité – Mini-framework

Je ferai une release propre des sources quand j’aurais tout bien commenté, surchargé et documenté l’utilisation, c’est à dire d’ici une à deux semaines au maximum…

Modularité et interfaçage C# <-> langages de scripts via un gestionnaire d’événement (1/2)


Dans le dernier article je présentais un gestionnaire d’événement. Pour résumer, celui-ci propose de réaliser des projets en se basant sur des relations cause->effet. Dans l’état actuel des choses, les effets entraînés par des causes (événements) sont contenus dans le code exécutable.

L’idée est maintenant de permettre à l’utilisateur d’un programme de modifier son comportement à l’aide de scripts interceptant les événements levés par le programme et exécutant des actions ayant des répercutions sur la suite de l’exécution du programme. De plus, ce mode de fonctionnement aura l’avantage de pouvoir rendre la conception du programme entièrement modulaire.

Beaucoup de logiciels emploient cette méthode : emacs par exemple, célèbre éditeur de texte avec l’utilisation de scripts en lisp pour la configuration ou le jeu World of Warcraft avec ses addons programmés en LUA.

Le dernier objectif enfin est de proposer une abstraction suffisamment forte pour rendre le fonctionnement compatible avec n’importe quel langage de script interfaçable avec C#.

Fonctionnement actuel

Le programmeur doit ajouter un observateur qui, lorsqu’il verra passer un événement correspondant au type d’événement observé déclenchera un effet (c’est à dire une procédure).
Puis il n’a plus qu’à lever des événements pour entraîner des effets.

EventManager.AddWatcher("Type d'événement observé", Effect.Create(ProcedureAppelée)[, condition]);
EventManager.RaiseEvent("Type d'événement à lever", );

Nouveau fonctionnement

L’actuel fonctionnement restera utilisable, et pourra coopérer avec celui-ci, permettant d’utiliser le moteur d’événement avec des effets codés en C# et/ou dans un langage de script compatible.

A la compilation, le développeur ne sait pas quels scripts seront implémentés par le futur utilisateur, ni leurs besoins, ni les événements qui lanceront l’exécution de ces scripts. Il ne peut donc pas relier des événements à des effets qui n’existent pas encore.
Toutes ces informations seront connues de l’utilisateur lorsqu’il écrira son script, il apparaît donc naturellement que ce sera à lui d’effectuer ces actions.

Un deuxième problème est présent. L’utilisateur aura la possibilité dans ses scripts de libérer des événements. Imaginons un utilisateur mal-intentionné, il pourrait libérer des événements internes au projet qui pourrait entraver son bon fonctionnement. Il faut donc laisser la possibilité au développeur du projet de créer des observateurs d’événements internes qui n’entraîneront aucun effet dans le cas où l’événement a été déclenché par un script (événement public).


Pour la question de la modularité, le principe suivant sera établi : les scripts seront classés en modules repérés par un nom et une version.

Par ailleurs, chaque module comportera :

  • Une fonction d’installation qui permettra d’ajouter effets et observateurs d’événements
  • Des propriétés constantes pour indiquer : le nom du module, sa version et d’éventuels prérequis (d’autres modules nécessaires à son fonctionnement)

Je garanti ainsi une encapsulation parfaite des différents modules, qui pourront malgré tout imposer la présence d’un ou plusieurs autres modules pour s’installer et communiquer à travers des événements interposer avec d’autres modules.

Gestionnaire d’évènements en cascade

Lorsque j’ai eu à réaliser un projet de jeu vidéo cette année, j’ai trouvé un système qui me semble pour l’instant assez performant pour organiser toutes les relations entre toutes les actions du jeu.

Il s’agit d’un gestionnaire d’évènements en cascade qui permet de simplifier énormément la modélisation du projet.

Problématique initiale

La réalisation d’un jeu vidéo (comme tout projet) nécessite de disposer d’un code facilement maintenable et très maniable afin de pouvoir implémenter de nouvelles fonctions lorsque l’on ajoute du contenu au jeu. Il serait impensable de recoder une bonne partie du moteur de jeu pour ajouter un simple objectif !

Dans la plupart des projets que j’ai pu voir (certains sont d’ailleurs très bien codés!) on assiste à de beaux exemples de programmation spaghetti où toutes les fonctionnalités sont mélangées, et où l’ajout d’une nouvelle bricole demande un travail considérable.

En soit, les problèmes commencent dés lors que toutes les parties du projet doivent être rassemblées : moteur graphique, son, …

Prenons l’exemple d’une mini-map affiché dans un coin de l’écran. Un développeur débutant qui voudrait afficher un icône sur la carte lorsqu’un coéquipier meurt se rendrait dans la fonction appelée lorsqu’un coéquipier meurt et lancerait un appel vers une autre procédure qui afficherait l’icône sur la carte. Et pour moi, c’est commencer à emmêler les spaghettis.


Un système d’évènement permettrait dans l’exemple du dessus de propager à travers tous le programme un évènement lorsque le coéquipier meurt. Le module mini-map peut alors simplement attendre que cet évènement se déclenche et afficher l’icône au moment adéquat. Le code n’a absolument pas bougé en dehors du module mini-map ce qui est à mon gout plus joli.

Au lieu de devoir se casser la tête sur de la modélisation, il suffit de réaliser des schémas d’enchaînement cause->effet->cause, ce qui est largement plus naturel que des schémas d’abstraction.


Tout est basé sur trois classes : Effect, Event, Watcher

Un événement selon ma conception objet est défini ainsi :

  • Un événement possède une chaîne de caractère caractérisant son type.
  • Un événement contient des données.

Un effet :

  • Un effet appelle une méthode lorsqu’il se produit et passe en paramètre les données contenu dans l’événement l’ayant déclenché.
  • Cette méthode peut éventuellement déclencher d’autres événements.

Un watcher (observateur) :

  • Un observateur n’observe qu’un seul type d’événement.
  • Un observateur est l’œil d’un unique effet : il intercepte tous les événements se produisant.
  • Lorsque le observateur voit une réponse du bon type il peut appeler une fonction pour savoir s’il est nécessaire de déclencher l’effet ou le déclencher sans test préalable.

Enfin, il faut réaliser une dernière classe pour synchroniser tous les événements, effets et leurs observateurs respectifs, déclencher les callbacks nécessaires, etc…

Grâce à ce système, il est possible de déclencher un événement, qui à son tour déclenchera d’autres événements, qui… et ainsi de suite…


On implémente un système de points dans un jeu pong (l’exemple ne présente aucune utilité pratique, c’est pour expliquer le fonctionnement) :

  • A chaque fois que la balle sors de la table, le programme déclenche un événement de type : « BallIsOut » et contenant dans les données l’index du joueur
  • On implémente un effet UpdateScore qui appelle une fonction incrémentant le score du joueur correspondant à l’index passé en paramètre et qui déclenche ensuite un événement « ScoreUpdated »
  • On implémente un observateur pour les événements du type « BallIsOut » qu’on lie à l’effet UpdateScore.

Graphiquement :

*Le joueur 1 marque un point contre le joueur 2*
*Le programme déclenche un événement : BallIsOut {2}*

BallIsOut {2}   //Entre crochets nous avons les données contenu dans l'événement (en l’occurrence l'index du joueur 2)
        |  Événement interceptée par l'observateur de l'effet UpdateScore
 UpdateScore(2)   ---- déclenche événement --->  ScoreUpdated {2, <nouveau-score>}

On peut ensuite imaginer répéter le processus pour obtenir par exemple :

BallIsOut {index_joueur}
        |  Événement intercepté par l'observateur de l'effet UpdateScore
 UpdateScore(index_joueur)  ---- déclenche événement ---> ScoreUpdated {index_joueur, score_joueur}
                                                                       |  Événement intercepté par l'observateur de l'effet Win
                                                                       |  L'observateur possède une condition : score_joueur > 5
                                                           Win(index_joueur)   -----> Win {index_joueur}

On a ici une cascade d’événement avec la mise à joueur du score, et la victoire du joueur ayant mis le point si son score est supérieur à 5.


Voici l’exemple d’un programme effectuant un scanf puis printf du nom de l’utilisateur.

        public static void DisplayName(string name)
            Console.WriteLine("Bonjour {0}", name);

        public static void AskName()
            Console.WriteLine("Quel est ton nom ?");
            string name = Console.ReadLine();
             * On déclenche un événement de type NameWritten
             * contenant le nom de l'utilisateur
            EventManager.RaiseEvent("NameWritten", name);

        static void Main(string[] args)
             * On ajoute un watcher qui observera les événements du type
             * start et qui entraînera un effet qui appellera la procédure AskName
            EventManager.AddWatcher("start", Effect.Create(AskName));

             * Idem mais avec les événements du type NameWritten et la
             * procédure DisplayName
            EventManager.AddWatcher("NameWritten", Effect.Create(DisplayName));

            //On déclenche un événement de type start sans aucune donnée



Une application réelle de ce système comprend des centaines d’effets possédant plusieurs observateurs, ce qui correspond en réalité à la propagation d’un événement au sein d’un graphe d’événements. J’ai choisi d’utiliser des chaînes de caractères transitant entre les événements pour modéliser les relations entre les nœuds.

Cela rend le système un poil plus lent pour les puristes (à cause de l’utilisation d’un dico et d’un style de programmation par endroits réflexif) mais possède l’avantage de le rendre plus simplement compatible avec un système de script, qui permet alors de multiples possibilités.

Je publierai les sources et toute une doc quand j’aurais trouvé le temps de me créer un repo, que tout sera joliment codé.

Base des programmes Brainfuck compilés

Ce billet est relié avec l’article sur mon projet de programmation d’un compilateur Brainfuck.

data: times 30000 db 0
ptr: dd 0

global main

inc byte [ptr]

dec byte [ptr]

mov eax, [ptr]
inc byte [eax]
mov [ptr], eax

mov eax, [ptr]
dec byte [eax]
mov [ptr], eax

mov edx, 1
mov ecx, [ptr]
mov ebx, 0
mov eax, 3
int 0x80

mov edx, 1
mov ecx, [ptr]
mov ebx, 1
mov eax, 4
int 0x80

mov ebx, 0
mov eax, 1
int 0x80

mov eax, data
mov [ptr], eax
;         COMPILE
 call exit