Last year, I've done a one-hour presentation of Mathematical Morphology in front of other students. Here are the slides:

The talk is over. Check out the Slides & Video.

For several months now I've been surveying my friends and teachers at EPITA and I came to the conclusion that they have absolutly no idea what Javascript really is. In order to help them discover a language that is getting a lot of traction nowadays, I'm organizing a 2-hour presentation on the subject.

If you know how to program and are interested in learning sexy advanced Javascript, you are more than welcome to attend this presentation. It will be Tuesday 25th October from 6:30pm to 8:30pm at EPITA Amphi Master (Metro Porte d'Italie). If you are in Paris at this time and speak French, do not hesitate to send me a mail at [email protected], I will explain how to get there 🙂

I've written a more lengthy explanation about my motives and presentation's content in the LRDE bulletin L'air de rien #23:

Edito par Olivier Ricou (Enseignant-Chercheur)

[...] Ce numéro est aussi l’occasion de mettre en valeur un étudiant du LRDE un peu fou, il aime Javascript, mais fort sympathique et qui sait partager sa passion. Il le fait à travers un article ici, mais aussi le mardi 25 octobre à 18h40 dans l’amphi masters (entrée libre). [...]

Présentation Javascript

Les sites tels que Gmail, Facebook et Google Maps sont des exemples classiques d'utilisation de Javascript. Mais saviez-vous que l'interface de Windows 8 ou les extensions de Chrome et Firefox sont écrites en Javascript? Ou qu'il est possible d'écrire des serveurs web en Javascript grâce à Node.js ?

Javascript est partout et pourtant, je me suis rendu compte en parlant autour de moi que personne ne connaissait réellement ce langage. C’est pourquoi je vous invite à une présentation de deux heures sur le sujet le Mardi 25 Octobre en Amphi Master de 18h40 à 20h40.

Javascript, le language

Pour commencer, un petit peu d'histoire. Brendan Eich raconte qu'il a pensé et implémenté le premier prototype de Javascript en 10 jours en 1995. En effet, Javascript est un langage qui contient un nombre extrêmement restreint de concepts. Cette idée provient du monde des langages fonctionnels tels que Lisp, Haskell ou Caml. Le génie de Javascript c'est d'avoir su s'écarter d'un modèle mathématique parfait au profit d'un confort d'utilisation pour le développeur.

Javascript a pour objectif d'être utilisé par le plus grand nombre de personnes. La syntaxe du langage a été fortement inspirée du C et ne contient aucune fantaisie. Cela rend le code source lisible et compréhensible par n'importe quel informaticien. Le language a été conçu pour exécuter un maximum de programmes, même mal formés. Par exemple, une heuristique va rajouter des point-virgules manquant. Au final, la barrière d'entrée au Javascript est très faible.

Lambda Fonctions et Objects

Javascript tire sa puissance de deux concepts fondamentaux: les Lambda fonctions et les Objets. La présentation a pour objectif principal de vous apprendre à manipuler ces deux outils. En guise d'introduction au langage, je montrerais comment reproduire des paradigmes de programmation connus, en particulier la Programmation Orientée Objet.

Le navigateur est un environnement hostile. Dans un site cohabitent une multitude de modules Javascript développés par des personnes différentes. On peut citer le site lui-même, les publicités, les commentaires, les statistiques, le bouton "like", etc. Nous verrons brièvement l'utilité des objets et des fonctions pour se placer dans l'un des trois points de vue suivant : être un citoyen respectueux, fortifier son code contre les attaquants ou au contraire s'amuser avec le code des autres.

Un langage dynamique

A l'école nous avons principalement étudié des langages de programmation statiques comme le C, C++ et Caml. Javascript quant à lui fait parti de la catégorie des langages dynamiques comme le PHP, Ruby ou Python. Les fonctionnalités de ces derniers ont pour objectif de simplifier la vie du développeur en s'éloignant des contraintes de la machine ou des théories mathématiques de typage. De ce fait, les langages dynamiques sont de plus en plus utilisés.

Nous étudierons les changements apportés par cette nouvelle façon de penser. Par exemple, les chaînes de caractères sont utilisées de façon quasi systématique afin de faciliter le débuggage, les objets sont construits à la volée dans définir leur structure dans un fichier séparé pour gagner du temps, etc.

Qui suis-je ?

Cette présentation n'est pas le fruit du hasard. Je me suis longuement intéressé à Javascript et aux langages dynamiques durant ces dernières années.

Le traitement d'image est largement developpé en utilisant des langages statiques en raison de l'important besoin en performance. Mon sujet de recherche au LRDE est d'adapter des concepts dynamiques tels que les lambda fonctions ou chaînage de méthode aux problématiques de traitement d'image

Je travaille en parallèle des cours pour la société Curse qui réalise des sites internet pour les joueurs de jeux en ligne dont World of Warcraft. J'utilise au quotidien Javascript, Python et PHP. Mes découvertes sont mises en ligne sur un blog : http://vjeux.com/.

À Épita, j'ai pu utiliser un langage de programmation dynamique dès ma première année. Lua est intégré dans Fooo, un remake de Warcraft III, afin de permettre des interfaces de jeu facilement personnalisables.

During the last 6 months as part of the LRDE (EPITA Research & Development Lab), I've been working on Climb, a Common Lisp image processing library. I've written a report and presented it. You can download the slides and report.

Climb - Chaining Operators & Component Trees

Abstract: Climb is a generic image processing library designed to be used for rapid prototyping. The implementation of two component trees algorithms impacts Climb in several ways: the definition of values is extended, new site sets are added and debugging utilities are improved.

A detour is taken to understand the Method Chaining design pattern popularized by the Javascript jQuery library. The pattern is adapted to both the image processing domain and Common Lisp and is extended to introduce a parallel notation as well as better control flows.

One of my class at EPITA is about Constraint Programming. This is a technique to solve problems with

  • A huge number of possible solutions. (2^1000 is not uncommon)
  • Discrete variables (they can take a bounded number of values).

I wanted to share this method with you because it is able to solve an impressive number of problems without writing any line of code. How? Because it is declarative. You write the problem (CSP: Constraint Satisfaction Problem) and the solver is in charge of finding the solution.

Here are some basic examples. I used the trial version of IBM ILOG for all those examples.

Sudoku

The Sudoku is a perfect target for Constraint Programming.

// Variables
range Size = 0..8;
dvar int Sudoku[Size][Size] in 1..9;
 
// Constraints
subject to {
  forall(i in Size) {
    forall (j, k in Size: j != k) {
      // Lines & Columns
      Sudoku[i][j] != Sudoku[i][k];
      Sudoku[j][i] != Sudoku[k][i];
 
      // Squares
      Sudoku[(i % 3) * 3 + (j % 3)]
          [(i div 3) * 3 + (j div 3)]
      != 
      Sudoku[(i % 3) * 3 + (k % 3)]
          [(i div 3) * 3 + (k div 3)];
    }
  }
 
  // Initial Input  
  forall (i, j in Size) {
    PreSolve[i][j] != 0 => Sudoku[i][j] == PreSolve[i][j];
  }
}

Sadly, Constraint Programming allows to solve instantly all the sudokus. I chose the World Hardest Sudoku as an example.

PreSolve = [
[0 0 5  3 0 0  0 0 0]
[8 0 0  0 0 0  0 2 0]
[0 7 0  0 1 0  5 0 0]
 
[4 0 0  0 0 5  3 0 0]
[0 1 0  0 7 0  0 0 6]
[0 0 3  2 0 0  0 8 0]
 
[0 6 0  5 0 0  0 0 9]
[0 0 4  0 0 0  0 3 0]
[0 0 0  0 0 9  7 0 0]
];
 
// Solution
[1 4 5  3 2 7  6 9 8]
[8 3 9  6 5 4  1 2 7]
[6 7 2  9 1 8  5 4 3]
 
[4 9 6  1 8 5  3 7 2]
[2 1 8  4 7 3  9 5 6]
[7 5 3  2 9 6  4 8 1]
 
[3 6 7  5 4 2  8 1 9]
[9 8 4  7 6 1  2 3 5]
[5 2 1  8 3 9  7 6 4]
  • Number of branches : 8
  • Number of fails : 0
  • Total memory usage : 1.1 Mb
  • Time spent in solve : 0.02s

17x17 Challenge

I discovered the 17x17 Challenge. You have to assign one color per element of a matrix such as there is not any rectangle with all the corners of the same color.

// Variables
dvar int Board[1..N][1..N] in 1..C;
 
// Constraints
subject to {
  forall (i, j in 1..(N - 1)) {
    forall (w in 1..(N - i), h in 1..(N - j)) { 
      ! (Board[i][j] == Board[i + w][j] 
      && Board[i][j + h] == Board[i + w][j + h]
      && Board[i][j + h] == Board[i + w][j]);
    }
  }
}
// Input
int C = 14;
int N = 4;
 
// Solution 14x14
[1 1 2 4 3 3 2 1 4 4 1 3 4 4]
[2 4 1 1 2 4 3 2 1 3 4 4 4 3]
[2 3 4 3 1 2 2 3 2 3 4 2 1 4]
[4 2 3 2 3 1 4 1 3 3 2 2 4 1]
[4 2 3 3 1 3 2 4 1 2 1 4 2 4]
[1 3 3 1 1 1 4 4 2 4 4 1 3 3]
[3 2 2 4 2 4 4 1 2 3 3 1 1 2]
[3 1 1 4 4 1 1 2 3 2 4 3 1 3]
[3 3 2 1 3 4 3 4 4 2 1 2 1 1]
[1 4 3 2 2 2 4 3 1 2 3 3 1 4]
[3 1 4 1 4 3 4 3 4 2 2 4 3 2]
[1 4 4 4 2 3 3 4 3 1 3 2 2 1]
[4 4 2 3 4 2 3 2 1 4 2 3 2 1]
[4 1 4 3 3 4 2 2 1 1 3 1 3 2]
  • Number of branches : 1,586,955
  • Number of fails : 774,500
  • Total memory usage : 13.6 Mb
  • Time spent in solve : 89.40s
  • Search speed (br. / s) : 17,750.3

For grids smaller than 14x14, the result is found instantly. A 14x14 takes 1min30. And for 15x15, I let it run during 24hours without any result 🙁 This naive approach will not give a solution any time soon for a 17x17 grid.

N-Queens

The 8-Queen problem and it's generalization to a NxN board is trivial to write in Constraint Programming.

There are three ways to code the problem. The unknown can be the board (boolean for the Queen presence) or the Queen position. A naive Queen position can be expressed with two coordinates X and Y. If we analyze the problem just a bit, we see that only one Queen can be per column. So we just store the column position of all the Queens.

The methods are sorted by speed of execution. The Board version is much slower than the Column one.

Board

dvar boolean Board[Size][Size];
 
subject to {
  forall (i in Size) {
    // One Queen per Line
    sum (j in Size) (Board[i][j]) == 1;
 
    // One Queen per Column
    sum (j in Size) (Board[j][i]) == 1;
  }
 
  forall (i, j, k, l in Size: i != k && j != l) {
    // One Queen per Diagonal
    abs(i - j) == abs(k - l) => Board[i][j] + Board[k][l] < = 1;
  }	
}

Queen

dvar int QueenX[Size] in Size;
dvar int QueenY[Size] in Size;
 
subject to {
  forall (i, j in Size: i != j) {
    // One Queen per Line
    QueenX[i] != QueenX[j];
 
    // One Queen per Column
    QueenY[i] != QueenY[j];
 
    // Diagonals
    abs(QueenX[i] - QueenX[j]) != abs(QueenY[i] - QueenY[j]);
  }
}

Column

range Size = 1..N;
 
dvar int Column[Size] in Size;
 
subject to {
  forall (i, j in Size: i != j) {
    // One Queen per Line
    Column[i] != Column[j];
 
    // Diagonal
    abs(Column[i] - Column[j]) != abs(i - j);
  }
}

Here is an example of result for a standard 8x8 board.

int N = 8;
 
|---|---|---|---|---|---|---|---|
|   |   |   |   |   | X |   |   |
|---|---|---|---|---|---|---|---|
|   |   |   | X |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   | X |   |   |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   |   |   |   |   |   | X |
|---|---|---|---|---|---|---|---|
|   |   |   |   | X |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   |   |   |   |   | X |   |
|---|---|---|---|---|---|---|---|
| X |   |   |   |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   | X |   |   |   |   |   |
|---|---|---|---|---|---|---|---|

Since the 8x8 example is instant to process, I made it run on a 100x100 board. You have to believe me to know that the result is correct 🙂

int N = 100;
Column = [65 42 71 32 58 90 88 93 61 19 76 56 67 89 23 10 15 60
  70 52 28 40 1 95 22 85 63 43 54 29 4 24 96 68 73 18 3 38 26 100 34
  99 17 14 6 79 37 49 51 72 62 57 59 45 78 25 94 46 86 13 77 5 35 41
  82 97 12 48 8 91 21 98 87 84 7 9 66 81 92 75 39 50 11 80 36 2 27 74
  64 20 16 47 55 30 33 31 53 69 83 44];
  • Number of branches : 30,958
  • Number of fails : 12,535
  • Total memory usage : 17.4 Mb
  • Time spent in solve : 12.17s

Send More Money

Here we try to solve the Send More Money problem. We have to find what are the unique values for S, E, N, D, M ... such as this equation is true:

   S E N D
 + M O R E
 ---------
 M O N E Y

The implementation is fairly straightforward. We use 4 more variables that will be the carries.

{string} Letters = {"S", "E", "N", "D", "M", "O", "R", "Y"};
range Digit = 0..9;
 
dvar int Values[Letters] in Digit;
dvar int Carry[1..4] in 0..1;
 
subject to {
  allDifferent (Values);
 
  Values["M"] != 0;
 
                              Carry[4] == Values["M"];
  Values["S"] + Values["M"] + Carry[3] == Values["O"] + 10 * Carry[4];
  Values["E"] + Values["O"] + Carry[2] == Values["N"] + 10 * Carry[3];
  Values["N"] + Values["R"] + Carry[1] == Values["E"] + 10 * Carry[2];
  Values["D"] + Values["E"]            == Values["Y"] + 10 * Carry[1];
}

And we get instantly the following result:

   9 5 6 7
 + 1 0 8 5
 ---------
 1 0 6 5 2

Behind the scene, the algorithm used is Branch & Bound. It uses Look-ahead to reduce the domain definition of the variables and Backjumping in order to backtrack to the first instanced variable that caused a problem. There are heuristics to know the order of the variables to instanciate. A common approach is to try first the "hardest" variables in order to remove as many branches as possible.

If you want to know more, here are some links:

I have integrated the LRDE (EPITA Research & Development Lab) few months ago as a student and this is my first research presentation.

Climb - A Generic and Dynamic Approach to Image Processing

Abstract: "Climb is a generic image processing library. A case study of the erosion algorithm from mathematical morphology highlights the issues of a non-generic implementation. Structures such as Image, Site Set and Accumulator are defined to solve them. Genericity is even increased by the concept of Morphers: a way to alter the communication between an object and the outside world. All these additions are done using the dynamic aspect of Lisp that allows for rapid prototyping."

Presentation

The oral presentation is in French. The slides (Download) are not readable in the video due to the poor recording quality, please scroll the slideshare at the same time you are viewing the video.

Technical Report

Along with the presentation, I have written a 20-pages technical report (Download).