Vjeux

It’s very trendy to bash at Computer Science degrees saying that it costs a lot of time and money and at the end, you haven’t learned much useful things for your day job. My experience going to EPITA, a French school in Paris, has been the complete opposite!

I started programming when I was around 10. By 13, I was already being contracted for real money by someone in the US (Hi Thott!). So, when I started EPITA at 18, I already had a ton of experience as a self-taught programmer. My biggest fear was: “Would I learn something new?” and, I did learn a ton! I know wouldn’t have done all the impactful things I have at Facebook without it.

What struck me was that I already knew a lot and I knew there was a lot left to learn, but I didn’t really know what nor how to get started learning it on my own.

Big Themes

Here are some themes where I learned entirely new domains of knowledge at school, many of which I would likely not have learned, or at least not as in depth if I didn’t do a CS degree.

• C: I’ve written a ton of C at school and it was super annoying but learning how to do manual memory management, use pointers and have raw access to memory was a huge breakthrough in how I understood how code was actually running.
• Data Structures and Algorithms. I had 6 hours of courses per day for 2 years. There’s so much to learn! What’s interesting is that you don’t need any of it to build what you want, but once you hit scale and you want to optimize and maintain it, knowing about all of them become critical!
• OCaml: The whole idea of manipulating immutable lists via recursion to actually do something useful at the end was very weird. Even though I still despise this style of programming, there are good ideas behind it and React is a good example of a practical system that makes use of them.
• Source Control: I used to change index2.php on the production machine and cp it to index.php using sftp when I was happy with my changes… for a website with 1 million unique visitors a day… It was fun and scary, but I wouldn’t go back to that in a million years!
• Assembly: Learning how a computer works from nand gates all the way to assembly was really mind blowing. There are so many levels of abstractions happening between the hardware and some piece of JavaScript that executes in the browser that it’s hard to believe it works and isn’t crazy slow.
• Machine Learning (it wasn’t hype at the time) is really not that magical. It’s a bunch of heuristics in order to massage the data in a way that it can be separated by a line. It also made me happy that finally all the linear algebra I’ve learned for years was useful to something. (Math was also useful for all the signal processing stuff with fourrier transform!)
• Academia. My theory is that nothing is new, everything has already been explored but because people there insist on using latex with maths symbols everywhere and publish to closed platforms, it doesn’t get the reach it deserves.
• Tradeoffs. If I were to summarize all the learnings, it’s probably that there is not one perfect solution. There’s usually a bunch of solutions with different sets of tradeoffs and you need to find the least shitty one. It was a sad realization but gave me a much better framework to work with.

Specific School Projects

What was awesome about EPITA is that not only we had classes like any normal school but also a ton of actual non-trivial projects to implement. Here are some that had a profound impact on me:

• Reimplementing Warcraft 3 from scratch. I learned so much about parsing (and reverse engineering) data structures, the whole 3D rendering space… But also having a project with a team of 4 people for an entire year and how to sell. It was a pretty awesome first year project 🙂
• Reimplementing malloc from scratch (btw, printf uses malloc which makes debugging interesting…). Learned so much about memory management and running firefox using my malloc was so awesome!
• Reimplementing bash from scratch. I learned a ton about how to parse and execute programming languages and how crazy the unix low level apis are. I’m still using this knowledge today when writing scripts thanks to this project.
• Implementing a regex execution using OCaml. OCaml is –really– good for working with well defined data structures and algorithms (I have big reservations for anything else outside of this narrow scope…). Since I’m using regexes almost on a daily basis, it’s been super helpful.
• We had 4-hour machine exams every couple of weeks for a year where you basically have to solve as many interview-style problems as possible. This was so much fun and helped to land a job at Facebook.
• Implement the fastest possible fuzzy finder. I learned so much about orders of magnitude in perf: just opening the file in JavaScript took way too long, C is faster… malloc is really slow, custom bump allocator is better. Smaller structs is better, bit packing ftw. Pre-computing data for heuristics can dramatically help.

And many more… but that’s a good enough list for now!

Actual Use Cases

Now, the big question is: but did you use any of that at work? And the answer is yes, so many times!

• Small thing but when building our open source websites, I wanted to only write next: page in the markdown and not have to have to write prev nor have a global index and yet have an table of content. It took me a second to realize that I had a list of edges of a graph and I needed to rebuild a graph from it. Because I’ve written so many graph traversals at school, it took me under an hour to build it correctly.
• EPITA enforced strict lint rules where for each violation you’d lose 2 points (out of 20) for all your assignments. The trick is that you were only given a pdf with the rules and no program to verify them, so you had to learn them the hard way. This motivated me years later to work on prettier so that we can have the benefits of a consistent codebase, the less hardcore way…
• When I was pitched React for the first time, it sounded to me crazy that re-rendering everything could be fast, but once I was proved it was not the case, I already knew it would work. I already made the mental journey of all thinking about the tree traversals, functional programming paradigms… It didn’t sound foreign to me as it did for so many other people.
• I’ve spent a lot of time building lint rules, codemods, extended syntax, pretty printers… because I’ve had excellent courses on how to parse and execute programming languages and had to build many at school, the challenge was not about learning how it works but more how to actually implement it in the context of JavaScript.
• While on the photos team at Facebook, one of the issue was that we cropped photos in a terrible way. Building an algorithm to find the best crop turned out to be manageable because I knew how to read the literature around existing approaches. Once I settled on one, I already wrote a ton of similar algorithms so it was just a matter of writing code down with little challenge.

Conclusion

I could have gotten a well paying programming job right out of high school as a web developer, but going to EPITA made me such a better programmer because I’ve been exposed in depth to a lot of areas that I would likely have never gone on my own.

Now, if I see a problem on a web developer task, I also know that changing the programming language, using machine learning, writing code in a more C-like way, using other data structures and algorithms… are possible tools to solve that problem. More importantly, if I need to use those, I can implement them because I’ve already done similar things in the past.

Your experience may vary, but for me, getting a CS degree at EPITA was a really good decision and I would do it again if I had to.

This is the third (and last) presentation about my work on Climb at the LRDE. During the first one I tackled genericity on data structures, the second was about genericity on values and this one talks about genericity on algorithms.

Climb – Property-based dispatch in functional languages

Abstract: “Climb is a generic image processing library. A generic algorithm interface often requires several different specialized implementations. Olena, a C++ library, solves this using properties.

We present a way to dispatch a function call to the best specialized implementation using properties in a dynamic programming language: Common Lisp. Then, we introduce examples of algorithms and properties used in image processing.”

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

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
• 17×17 Challenge
• N-Queens
• Send More Money

// 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];
  }
}

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]

// 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]

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;
  }	
}

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]);
  }
}

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);
  }
}

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

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];

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

{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];
}

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

$(“ul.tabs”).tabs(“div.panes > div”);

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:

• Guide to Constraint Programming
• Constraint Programming Course (French)
• Constraint Programming Blog

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).

The Bistromathique is an Arbitrary Precision Calculator EPITA project where the main focus is optimization. The input can be in any base (up to 250) and the following operations have to be performed: Addition, Subtraction, Multiplication, Division, Modulo.

Base Representation

Going back and forth a textual representation to a computable representation is the first part of the project and several optimizations are possible at this step.

Binary Representation

Encoding the numbers as binary allows you to make the best use of the processor calculation unit. There is no space lost and the number being represented as an uninterrupted series of 0 and 1 can be added and subtracted directly with the hardware.

However, in order to convert the number for a base B representation to a base 2 requires roughly n divisions by B. And to reconvert it back requires another n multiplications. This can be affordable for applications that uses the same numbers again and again but in our case, this cost is prohibitive.

The other major drawback is that you are required to have the multiplications and divisions (and therefore addition and subtraction) in order to have the numbers in the right form to start working on the operations … In summary, you have to code all these operations before being able to test them!

char Representation

The binary representation not being possible, the solution that comes in mind is to put each digit into a char (8 bits). Since we are limited up to a base of 250, any base will fit. This comes at a price, there is a lot of space wasted, and it increases as the base size decreases.

We are in a 1 to 1 relation between the input and the represented number, this way we can store the represented number inside the input. This prevents from allocating memory at this step. The conversion can be efficiently done, each character goes through vector of 256 slots storing its representation and a magic value used as a non valid input. One final trick is to add a non number at the end of the input to remove a end of input check in the loop.

Filling more

A char can store values up to 256. If we are working on base 16 we could store two digits into 1 char and thus divide by 2 the number of digits. Additions are therefore 2 times faster and even more for n log n operations such as multiplication.

Calculating the number of digits to fill into a char is quite straightforward however some caution has to be taken during the transition. We have to know in advance the length of the input to decide how to start filling the digits. If you can fit 2 digits per char, if the number is even then it goes as expected, but if the number is odd you have to place 0 at the beginning to fill the gap.

Even: [1] [2] [3] [4] -> [12] [34]
Odd (Naive): [2] [3] [4] -> [23] [4?]
Odd (Smart): [2] [3] [4] -> [02] [34]

This method works well but requires 2 passes for each number and a special case at the beginning of each number. Not enough to stop us from using it.

Using a larger representation

Now that we filled the char at its maximum, why stick with it? This should ring a bell since you know that common architecture is 32-bit, and from now we are talking about a 8-bit representation. We would be tempted to change the char to an int (32-bit) or even a long (64-bit) that could benefit from register optimizations.

Moving away from a char, we lose the assumption that the output being smaller (or equal) than the input. Without it, this is no longer possible to work in place. We now have to compare the cost of a reduction in the number of operations and the cost of the memory allocation.

The overhead happens for values that are represented in less than 4 characters for an int representation. This is a maximum 3-characters overhead possible for each number, which is negligible. We could eat the operation character but we are left with 2 characters. I haven’t found a solution to stay in place yet and this minor problem prevents from accessing a great speed up.

To be continued …

It has been one month that the third year (called Ing1) of EPITA started and this is a recap of the interesting projects that I developed.

malloc (1 week)
The goal of this mini-project is to improve our knowledge of memory management by implementing the C standard library memory allocator (malloc, free, realloc). Implementation using the Binary Buddy technique:

• List of free blocks of size 2^k.
• Split and Merge using adjacent block of the same size called buddy.
• Insertion and Deletion in O(log n).
• 32 & 64 bit ready.

find (1 week)
find is a very well known UNIX command used to satisfy research upon files and directories.

• File listing and options parsing with error handling.
• -name: Filtering using globbing.
• -newer, -atime, -size, -inum, -type, -links: Filtering off information sources. Handles -/+ for “less/more than”.
• -perm: Filtering based on permission expressed in octal (0777) or symbolic (u+rwx,go=r) notation.

fnmatch (10 hours)
fnmatch is a function that implements globbing. It returns whether the string matches the pattern. This is mainly used to filter out files (eg: *.txt) or text search in databases (eg: LIKE ‘%Text%’).

• *: any character 0 or more times.
• ?: any character 1 time.
• [abcA-Z]: any character from the class.
• *: escaping.

Libstream (10 hours)
I/O functions are slow hence they should be called few time as possible. This is why they are typically buffered. The project is to recode all the I/O buffered functions of the C standard library as they are defined by the Single UNIX Specifications V3.

• fopen, fclose, fgetc, fputc, fflush: Core functions to handle buffered I/O at a character level.
• fseek, ftell, frewind: File positioning functions.
• fread, fwrite, fgets, fputs, fgetdelim: Helper functions to use buffered I/O at a string level.
• tinyPrintf: Basic string formatting (%d, %u, %s, %c, %o, %x without modifiers).