Uncompetitive Programming (part 2)

 This is a continuation of the part 1 of this article. It presents an example of solving a problem that appears in a competitive programming site. The method of solving is utterly useless if you look at from the CP lens. It took me an order of magnitude more time and effort to come up with this solution. I don't know if my solution would pass in the online evaluation, particularly in terms of time-performance. I will try to procure a typical CP-style solution which would do well in CP evaluation and paste it here. My solution doesn't claim to be that.

And yet, I claim that this solution is superior in many important ways than a typical CP solution.

• It was built systematically.
• Options were given their due attention before one was taken and proceeded with while others were let go of.
• I spent quite a lot of time writing down my thoughts clearly in a way that is understandable to a reader.
• The code follows closely the final design.
• The code is readable to anyone who knows CS and programming. No special training for competitive programming is needed. There is some focus on performance, but not at the expense of readability or intuitiveness of the solution. 

I claim that this style, which is very very different from that of competitive programming, is the de facto style of practical programming. It is not something that any competitor programmer would be able to do given enough time. It involves a style of thinking, communication and programming that is very difficult if not impossible to learn in a CP setting. It requires a shift in mindset.

I hope that you will read the rest of this article and you will be able to see the differences w.r.t. to CP that I am trying to bring out here. I don't want to disparage CP. To do well in CP, one requires certain skills which are also quite valuable in real world. All I want to say is that CP not even the most important take on programming, let alone being the only one. Takeaways:

• Programming is like an art. It's as much about experience as about output.
• Ability to do thorough thinking is more important than thinking fast.
• Ability to communicate through written words and pictures is more important than hacking. 
• Readability is a far more important quality of a code than squeezing every cycle out of your processor.

Case Study

Problem

The problem can be found here. We solve a slight variant (or subproblem) of this problem. 

Our variant: We consider a sequence of slots. Some of these slots are empty while some are filled. The goal is to bring all elements to occupy contiguous slots. For this, we allowed to move any element from one slot to another (empty) slot with unit cost. Our algorithm has to compute the minimum cost to achieve this for a given initial state.

Our solution can be easily extended to solve the original problem.

Code

The code can be found in this GitHub repository.

Analysis and Design (Informal)

Our objective is to place all identical symbols adjacent to each other. The goal is to do so in minimum number of moves. The cost of each move, irrespective of the distance of the move, is 1.

The algorithm should compute the cost of moving, not necessarily do the moves as such.

The algorithm tries to avoid the following:

• Make repeated moves
• 
  Cause a gap to be created.
• 
  
  
  
  
• Move a ball to a place/position from which an identical ball has been moved out.

Strategy 1

Identify sets of contiguous positions occupied by balls (symbols) of a particular colour (description).

For example:

Use interval as a pivot and compute the cost of filling the gap on either sides of the pivot.

For example: For the above example, using I1 as the pivot.

However, the above is not the most optimum way of achieving contiguous interval.

The above transformation results in a contiguous interval in just one move.

Each pivot interval may have up to 2 adjoining gaps. To fill any gap, we follow the policy of using the extreme balls (symbols).

Hence, after identifying a pivot, we have to identify the adjoining gaps. For, filling each gap, we have to explore using the extreme balls, which could be up to two on each direction.

Heuristic: If there exists a gap whose length is greater than or equal to the length of an extreme interval, use the same to fill the gap.

Why: Removal of an extreme interval causes a gap to disappear.

The above method has a serious shortcoming, it looks like. For each pivot, there are two gaps adjoining. For each of these gaps, the candidate balls to use are also up to two (from extreme interval). This is a fertile pattern for an exponential growth in complexity. Each step will lead to 4 options as the subsequent step. N such steps will lead to 4 raised to N options proliferating. Of course, in the worst case.

Dynamic Programming to the Rescue

I think, dynamic programming can help here.

Suppose a trace of creating a contiguous interval has the following steps:

The total cost of 

Recursively:

This is good because can be recursively defined in terms of its tail.

If there is another trace 

If we wish to find the minimum cost of getting from a state s, it's just the minimum of the sum of the cost of getting from s to its next state plus the minimum to get to a contiguous state from there.

For example, in the following figure:

Now, the implication of this observation is that once the minimum cost of getting from a state to a contiguous state is computed, it can be memoised and used/reused anytime we reach that state through any other path. This will collapse a tree of states into a dag potentially contracting the state space explosion caused by the 4 raised to N growth discussed earlier.

There are still an exponential number of states. Suppose there are N slots and M balls. Then the number of states possible is N choose M, which unfortunately can be an exponential, and this may kill our algorithm.

The way to restrict the above explosion may be to avoid exploring non-viable options and making only smart moves. For example,

is a useless transition. Our initial idea of moving balls from the extremes can be a good option.

Local Summary

• We are gravitating towards a recursive design.
• We memoise the minimum cost per state
• We may want to remember the states visited in the current trace being explored to prevent looping.
• It's better to design computation of the next steps in a way that they inherently prevent us from visiting an already visited state.
• prevent exploring useless states, by preferably ensuring that each step leads to the improvement in some 'health' indicator (greedy approach).
• However, a greedy approach mustn't lead us to miss out on optimal solutions.

The skeleton of the algorithm now looks like this:

ALGORITHM

Note that the above is a recursive algorithm.

M(s) = nil will happen when s is being visited for the first time.

The rate of convergence of the algorithm will depend on nextstate function. The smaller the average size of n, the faster will be the convergence.

Computing next states

Let's use a simple method to begin with.

As long as a state has gaps, we keep filling those gaps by moving balls in the end (extremes) to the gaps. To limit useless possibilities, we can fill each gap starting from its left end.

For a state with g gaps the number of next states could be 2g.

Each step by definition has unity cost.

Note that we have (at least for now) given up our earlier representations of intervals.

I would like to note down a couple of observations here:

1. By choosing always a ball at the extreme end to fill intermediate gaps, we are sure to always shrink the spread, never extend it along any of its ends. Hence, the length of the slots (strings) is not important.
2. We have taken the above strategy with gut feeling that it will not miss out the best moves leading to a minimum cost. This should ideally be proved.

State representation

Again, following gut feeling, let's choose binary string representation. It appears that it will lead to simpler implementation of the functions we wish to implement. We may or mayn't be right here.

Move

We begin by defining the move function.

move: state ⤫ int ⤫ int --> state

For example:

move([0, 1,1,1,0,1], 5, 4) = [0, 1, 1, 1, 1, 0]

Gaps:

FIGURE

gaps([0,1,1,0,0,1,0,0,0,1,1,0]) = {[3,4], [6,7,8]}

Note that we exclude the unoccupied slots in the two ends.

So,

gap: state -> set of (list of int)

A function that gets us the extreme positions of the state would be helpful.

Ends

ends: state --> (int, int)

For example:

• ends([0, 1,1,1,0,1] = (1, 5)
• ends([0,1,1,0,0,1,0,0,0,1,1,0]) = (1, 10)

Now, next move functions:

Next Moves

nextmoves: state --> set of (int, int)

nextmoves computes the cross product of the ends and gaps.

For example:

Using nextmoves, we can compute the next states.

Next states

next_states(s) = {move(s, a, b) for all (a,b) in next_moves(s)}

This function can be plugged into the min_cost function above to obtain the complete algorithm.

Conclusion

To conclude, I would (again) like to bring your notice back to the point that this post comprises of rough notes; they have been written more as an aid to my own thinking, not as a representation of the final output of my thoughts. Consequently, some of the ideas which we broached in the early part of the article disappear as we proceed along. For example, the idea of representing intervals (because it was too unnecessarily complicated), or the first iterative algorithm (because our main approach itself changed). Similarly, there was a thought (almost a passing one) about making the algorithm greedy. Turns out that the algorithm we settled with is greedy. But we never again put a conscious thought in that direction after mentioning it once. A more finished article would be shorter, including only the ideas which survived till the end and found their way into the final implementation. However, that would lose track of all the ideas we explored and rejected, and the chronological order in which they appear and sometimes faded away. Note that even the ones we drop on the way have their value: they are the steppingstones to where we finally arrived. 

So, there! An uncompetitive style of programming! In this, we look at the problem from various angles. We contemplate on various options. Sometimes, our contemplation may seem idle -- as if we are more interested in the beauty of the process of thinking, instead of the result. I will share a secret here: the above is actually not fully untrue! We do care about the result, but we don't want to miss out on the fun part.

We are concerned about efficiency. We are also concerned about the time it takes to implement the program. We are concerned about the brevity of our code. But above all these, we are concerned about the readability of our code. We write a code which is understandable by a lay programmer and follows our design very closely. Programs are not just instructions to machines; they are meant to be read by humans too! 

Uncompetitive Programming (part 1)

I recently had an interesting discussion with one of my young relatives -- a second year engineering student in computer science -- who, like many of his age, is fascinated by the idea of competitive programming. Competitive programming (CP) involves solving algorithmic problems/puzzles by writing programs. These problems typically involve some CS theory, particularly in data structures and algorithms. There are many online sites which provide practice ground for CP aspirants. The pinnacle of this, to the best of my knowledge, is ICPC. One of our alums went on to the World finals. This contributed in a big way to his getting recruited by Google, USA with a record-breaking salary. This achievement set off a CP culture in our institute which has been going strong since. Some of our brighter students gravitate towards the CP culture, with dreams of becoming the next Google hire.

CP emphasises on CS fundamentals. To rise in the CP community, one needs to be good with algorithms, some basic mathematical thinking and in coding in at least one programming language. As CP happens in time-bound environment, one needs to develop quick thinking skills. Undoubtedly, CP aspirants are closely followed by top hirers. They have their fundamentals right, they are smart and fast, and they function well under extreme pressure -- exactly the qualities top companies are looking for in their new employees, right?

Yet, I believe that CP is not for everyone. And by that, I don't mean that people who can't handle the high pressure and expectation of CP shouldn't do it. That, of course, goes without saying. But what I mean is that, with all its good things, CP ends up testing the programmers for a limited set of skills, and misses out on many others which may be equally or more important than the ones which are tested in CP.

I would like to draw a parallel with academic assessments. Take IIT JEE. About 30 years ago, when we were school students preparing for college entrances, IIT JEE used to be viewed as an ultimate test of academic brilliance. While, its focus was restricted to science and mathematics, it was perceived as a reasonably reliable metric of measuring natural intelligence. To crack JEE, you needed to be someone. Conversely, if you have cracked JEE, you are someone. 

Things have changed since then. IIT JEE, like all assessments, has devolved into a pattern now. Because of the coveted status of IITs, there are millions who dream to crack JEE. And there are people who have made billion-dollar businesses out this aspiration. They have studied the JEE pattern and have developed methods of preparing students so that they can do well in JEE, not because they are very intelligence, but because of hard practice that has drilled the JEE pattern into their minds. Acing JEE is no more a surefire indicator that you are built differently. It's definitely about hard work and a lot of practice. But, to a large extent, it may be an indicator of something negative -- probably, you are more competitive than academically brilliant; and these are two entirely different things. Such high competition may now be routinely excluding brilliant students with potential to become groundbreaking engineers from entering IITs because they are not able to handle the psychological pressure of such high competition. It's a tragedy of unprecedented scale!

CP culture has a not-so-hard-to-see similarity with IIT JEE. With growing demand, CP has been attracting students in whom the competitive part dominates their programmer part. By practice-solving hundreds of similar problems, many of these aspirants develop high degree of pattern matching skills, sharpen a bag of tricks to code something up quickly. They are often like overfitted ML models which will do really well in CP-like environments and will do well in just that kind of environment.

A terrible side-effect of this phenomenon is that programming is now increasingly being viewed as a quick-and-dirty problem-solving activity. And many of our bright students don't even consider the possibility that programming is also a creative exercise that can't always be done in high-pressure timebound manner, but through open-ended exploration. Time pressure and open-ended exploration directly conflict with each other; they are two extremes of a spectrum. People who have trained hard to get close to one of these ends of the spectrum are very unlikely to develop well on the other. And we need people at all points in this spectrum.

In real world, CP-style deadline driven algorithm design and coding is not always realistic. Usually, for a task that matters, the solution is not likely to be very cut-n-dry. In such cases, merely a performant code that gives correct results is far from enough as an output. You have to be able to explain clearly to others how you came up with the solutions and how the whole damn thing works. Happily, you would typically have much more time than in CP to come up with such a solution.

A CP-style programmer has certain skills tuned to perform well in the high pressure setting of CP. There's a tendency of pattern matching (with familiar problems) and to hack it to make it work 'somehow'. This mayn't be a good style in many settings where thinking slowly but thoroughly and clearly is more important.

While designing a solution, there may be many false starts. Writing things down in the language of plain English, pictures and mathematics helps us think ahead and correct our course early. Starting to code right away may give us a mistaken sense of early progress but may lead to difficult-to-correct mistakes down the line, particularly when the problem is challenging.

Part 2 of this article presents an example of solving a problem that appears in a competitive programming site. 

I hope that you will be able to see the differences w.r.t. to CP that I am trying to bring out here. 

To conclude this part of the article:

• Programming is like an art. It's as much about experience and aesthetics as about output.
• Ability to do thorough thinking is more important than thinking fast.
• Ability to communicate through written words and pictures is more important than hacking. 
• Readability is (more often) a far more important quality of a code than squeezing every cycle out of your processor.

This is a logical point where it's OK to stop reading. But in case you plan to continue please proceed to part 2 in which I discuss with an example how an uncompetitive programmer would approach a CP problem! 😀

Test Driven Development -- An Example

This post is written as a model answer to an exam question. As I have clarified earlier, this is way too long to be written in the exam. But, it suffices as an example.

The main philosophy of test-driven development is:

• Use test cases as specifications.
• Test cases should be written preferably before the part of the implementation they test. Hence, a newly introduced test would typically fail. Then the code should be modified to make it pass, possibly followed by some refactoring to improve the design.
• We stop coding as soon as we get all test cases to pass.
• If we are thinking of a new feature, or cases within the new feature, we should first write a test case corresponding to that.

These tests become part of the project assets, and can be used later at any point in time. TDD is aligned with agile methodology as it focuses on creating work code as opposed to separate documentation.

First set up the testing environment. For simplicity and self-sufficiency, I have created my own TestResult class.

#include <iostream>

using namespace std;

class TestResult {
public:
	const bool result;
	const string message;

	TestResult(bool r, string m) : result(r), message(m) {}
};

The algorithm for palindrome detection that I want to use is the following:

match S with:

case "" --> raise exception

case "x" --> true

case "xy" --> x = y

case "xS'y" --> x = y /\ pal(S')

This is not the most efficient implementation. But that is not the point here. We intend this to be an illustration of the test-driven methodology.

Going by the above algorithm, the first case we would like to test is that if an empty string is given, the function should throw an exception. The test case for checking this is as follows:

TestResult t1() {
	try {
		isPalindrome("");
		TestResult r(false, "Exception not thrown");
		return r;
	}
	catch (string e) {
		TestResult r(true, e);
		return r;
	}
}

The main function or the driver for now is as follows:

int main() {
	TestResult r1 = t1();
	cout << r1.result << ", " << r1.message << endl;
	return 0;
}

The first cut implementation of the isPalindrome function is as follows:

bool isPalindrome(string s) {
	return true;
}

As you can see, it's designed to fail t1. And when we run it, it indeed does:

0, Exception not thrown

Next we modify the function to make t1 pass.

bool isPalindrome(string s) {
	if(s == "") {
		throw string("Empty string provided");
	}
	return true;
}

t1 passes:

1, Empty string provided

Now, we wish to handle the next case.

case "x" --> true

TestResult t2() {
	try {
		bool ans = isPalindrome("a");
		TestResult r(ans == true, "");
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

This test passes without any need of change to the code.

So, we move over to the next case:

case "xy" --> x = y

TestResult t3() {
	try {
		bool ans = isPalindrome("aa");
		TestResult r(ans == true, "Correct!");
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

This passes:

1, Empty string provided
1, 
1, Correct!

But we need to test this case more, for the subcase when we are expecting a negative answer:

TestResult t4() {
	try {
		bool ans = isPalindrome("ab");
		bool result = ans == false;
		string message = result ? "Correct" : "Wrong answer";
		TestResult r(ans == false, message);
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

As expected, this test case fails:

1, Empty string provided
1, 
1, Correct!
0, Wrong answer

The palindrome function needs to be modified appropriately to make this test case pass:

bool isPalindrome(string s) {
	if(s == "") {
		throw string("Empty string provided");
	}
	if(s.size() == 1) {
	  return true;
	}
	if(s.size() == 2) {
		return s[0] == s[1];
	}
}

Now, t4 passes:

1, Empty string provided
1, 
1, Correct!
1, Correct

Now that we have tested the third case to our satisfaction, we move over to the final case:

case "xS'y" --> x = y and pal(S')

We first add a test case for testing the final case:

TestResult t5() {
	try {
		bool ans = isPalindrome("aba");
		bool result = ans == true;
		string message = result ? "Correct" : "Wrong answer";
		TestResult r(result, message);
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

t5 passes without any need of code change.

1, Empty string provided
1, 
1, Correct!
1, Correct
1, Correct

Let's add t6 to check the negative case:

TestResult t6() {
	try {
		bool ans = isPalindrome("abb");
		bool result = ans == false;
		string message = result ? "Correct" : "Wrong answer";
		TestResult r(result, message);
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

This fails:

1, Empty string provided
1, 
1, Correct!
1, Correct
1, Correct
0, Wrong answer

This requires us to implement another function, say 'sub', which gives us a copy of the passed string with the first and the last character omitted. Formally:

"xS'y"  --> raise exception if S' = ""

--> S' if S' != ""

This should be used on strings with length greater than or equal to 2. We make some code changes to make place for the sub function. We begin with a dummy implementation of sub as follows:

string sub(string s) {
  return "Hello";
}

bool isPalindrome(string s) {
	if(s == "") {
		throw string("Empty string provided");
	}
	if(s.size() == 1) {
	  return true;
	}
	if(s.size() == 2) {
		return s[0] == s[1];
	}
	
	return s[0] == s[s.size() - 1] && isPalindrome(sub(s));
}

The above causes t6 to pass, but breaks t5.

1, Empty string provided
1, 
1, Correct!
1, Correct
0, Wrong answer
1, Correct

We understand that this is because of the erroneous implementation of sub function. So, we turn our attention to sub.

We start with a test case to check its first case:

"xS'y"  --> raise exception if S' = ""

TestResult t7() {
	try {
		string ans = sub("a");
		TestResult r(false, "Exception not thrown");
		return r;
	}
	catch (string e) {
		TestResult r(true, e);
		return r;
	}
}

t7 fails. And we make the requisite code modification to get it to pass.

string sub(string s) {
	if(s.size() < 2) {
		throw string("Insufficient size.");
	}
	return "Hello";
}

For sure, t7 passes:

1, Empty string provided
1, 
1, Correct!
1, Correct
0, Wrong answer
1, Correct
1, Insufficient size.

But t5 is still failing. Clearly, all is not well with sub. Anyway, let's proceed to handle the other case in sub:

--> S' if S' != ""

We jump any ceremony and make the following change to sub:

string sub(string s) {
	if(s.size() < 2) {
		throw string("Insufficient size.");
	}
	string new_s = "";
	for(unsigned int i = 1; i < s.size() - 1; i++) {
		new_s += s[i];
	}
	return new_s;
}

t5 passes:

1, Empty string provided
1, 
1, Correct!
1, Correct
1, Correct
1, Correct
1, Insufficient size.

This has presumably completed our development of the code. However, we need to run it through some more tests before we can call it complete.

TestResult t8() {
	try {
		bool ans = isPalindrome("aba");
		bool result = ans == true;
		string message = result ? "Correct" : "Wrong answer";
		TestResult r(result, message);
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

TestResult t9() {
	try {
		bool ans = isPalindrome("abba");
		bool result = ans == true;
		string message = result ? "Correct" : "Wrong answer";
		TestResult r(result, message);
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

TestResult t10() {
	try {
		bool ans = isPalindrome("aaba");
		bool result = ans == false;
		string message = result ? "Correct" : "Wrong answer";
		TestResult r(result, message);
		return r;
	}
	catch (string e) {
		TestResult r(false, "Exception: " + e);
		return r;
	}
}

To our pleasure, all these new test cases pass in one shot!

1, Empty string provided
1, 
1, Correct!
1, Correct
1, Correct
1, Correct
1, Insufficient size.
1, Correct
1, Correct
1, Correct

This completes the test driven development of the isPalindrome function.

Automating Your Build with Makefiles

I know I am getting into a well-known topic. What more, make is a pretty old technology. We have so many other cooler build automation technologies out there. IDEs like Eclipse and Visual Studio make it unnecessary to write your old build system in the first place.

After the above negative marketing, let me tell you why then I am writing this post: because understanding how dependencies work between the various modules of your software is fundamentally connected to your design thinking. In fact, understanding how make's algorithm works at a high level is worth the effort. I present a prototype implementation of the same below, all of ~30 lines of OCaml code.

A Running Example

(Adapted from a illustrative project by my student Anirudh C.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

(* arith.ml -- begin *) let inc x = x + 1 let dec x = x - 1 let add x y = let rec loop x y = if y = 0 then x else loop (inc x) (dec y) in loop x y let sub x y = let rec loop x y = if y = 0 then x else loop (dec x) (dec y) in loop x y (* arith.ml -- end *) (* circle.ml -- begin*) let pi = 3.141 let area r = pi *. r *. r let circumference r = 2. *. pi *. r (* circle.ml - end *) (* main.ml -- begin *) let main () = print_endline (string_of_int (Arith.add 1 2)); print_endline (string_of_int (Arith.sub 3 2)); print_endline (string_of_float (Circle.area 2.)) let _ = main () (* main.ml -- end *)

In the code shown above, we have three modules, arith (arith.ml, arith.mli), circle (circle.ml, circle.mli) and main (main.ml, main.mli). main uses both arith and circle which are self contained modules. The OCaml implementation of the above idea, therefore, has the following additional files:

arith.cmi: The object code for the interface of arith module

arith.cmo: The object code for the implementation of arith module

circle.cmi: The object code for the interface of circle module

circle.cmo: The object code for the implementation of circle module

main.cmi: The object code for the interface of main module

main.cmo: The object code for the implementation of main module

app: The final executable.

 Here are the listings of the interface files:

1 2 3 4 5 6 7 8 9 10 11 12 13

(* arith.mli -- begin *) val add : int -> int -> int val sub : int -> int -> int (* arith.mli -- end *) (* circle.mli -- begin*) val area : float -> float val circumference : float -> float (* circle.mli - end *) (* main.mli -- begin *) val main: unit -> unit (* main.mli -- end *)

 

The dependencies between the various files is shown by the following directed acyclic graph:

As you can see, the dependencies look a bit complicated, if not a lot. Part of why it's this way has to do with the particular programming language that you are using. For example, OCaml has this idea of object code being generated from the interface files by compiling the .mli file. However, the most important aspect of this structure is agnostic to the programming language. That aspect of the dependencies is its directed acyclic nature. In the dependency graph above, you will find no cycles or loops.

What impact do the above dependency relations have on build automation process. Here is the exhaustive sequence of build steps:

1 2 3 4 5 6 7

ocamlc -c arith.mli # builds arith.cmi ocamlc -c arith.ml # builds arith.cmo ocamlc -c circle.mli # builds circle.cmi ocamlc -c circle.ml # builds circle.cmo ocamlc -c main.mli # builds main.cmi ocamlc -c main.ml # builds main.cmo ocamlc -o app arith.cmo circle.cmo main.cmo # builds app

The first influence is the following: The dependee must always be compiled after all its dependencies have been compiled. The sequence in which the above steps are written respects this order.

The second one is an opportunity of optimisation: When you are building the application, you compile only that part of the application which is depends on any part which has been modified since the last build. For example, if we make a modification in the circle.ml file, which parts of the build process need to be repeated? Looking at the dependency graph we can say that its circle.cmo, and app, because these are only two nodes in the graph from which you can reach circle.ml by following the directed edges of the dependence graph.

 The make Algorithm

The make algorithm allows us to implement the above optimisation. We specify the dependency graph in a makefile. Here's the Makefile for the above application:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

app : arith.cmo circle.cmo main.cmo ocamlc -o app arith.cmo circle.cmo main.cmo arith.cmo: arith.ml arith.cmi ocamlc -c arith.ml circle.cmo: circle.ml circle.cmi ocamlc -c circle.ml arith.cmi : arith.mli ocamlc -c arith.mli circle.cmi : circle.mli ocamlc -c circle.mli main.cmo : main.ml main.cmi arith.cmi circle.cmi ocamlc -c main.ml main.cmi : main.mli ocamlc -c main.mli

 

 

 

make algorithm takes this graph as an input, studies the modification timestamps of all the targets and does just what is necessary (and useful) in the build process of the application. What's the rule to be followed here? Whenever any of the dependencies, say d, of a dependee/target file f was modified after f was modified, f needs to be rebuilt. However, one more bit. The timestamp of f and d is checked only after this rule is applied on d. And recursively. While an untrained human mind may find this a bit mind-bending, it's really a very very simple algorithm.

1 2 3 4 5 6 7 8 9 10

function process_node(n) if(n.deps != {}) then process_node(n') for all n' in n.deps maxdepts = max(timestamps(n.deps)) if(timestamp(n) < maxdepts) then execute(n.action) update_timestamp(n, now) endif endif end

The algorithm above does a depth first traversal starting with the target which we are building. After having processed all the dependencies, it compares the timestamp of the current target with those of all its dependencies. If any one of them is more recently modified than the target, the target is rebuilt by executing its build command.

To round up the article, here's the OCaml implementation of the above algorithm. Even though the code has a good 170 LOC, note that the core algorithm is just 33 lines (L42 to L72). Rest of it is all plumbing and testing code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170

type node = { name : bytes; dependencies : node list; action : bytes; } type timestamp = { n : node; t : int; } let string_of_timestamp ts = "\t(" ^ ts.n.name ^ ", " ^ (string_of_int ts.t) ^ ")" let string_of_timestamps tslist = "[" ^ (let strtss = List.map string_of_timestamp tslist in (List.fold_left (fun x y -> x ^ y ^ "\n") "" strtss)) ^ "]" exception My_exception of string let rec get_timestamp timestamps n' = match timestamps with [] -> raise (My_exception n'.name) | { n; t } :: tl -> if n = n' then t else (get_timestamp tl n') let rec update_timestamp timestamps n' t' = match timestamps with [] -> [] | { n = n; t = t } :: tl -> if n = n' then { n = n'; t = t'} :: tl else { n ; t } :: (update_timestamp tl n' t') let rec max = function [] -> raise Not_found | [h] -> h | h :: t -> let maxt = max t in if h > maxt then h else maxt let rec process_node n ts = let myt = get_timestamp ts n in if (List.length n.dependencies <> 0) then let depts = process_dependencies n.dependencies ts in let maxts = max (List.map (get_timestamp depts) n.dependencies) in if myt < maxts then begin print_endline ("executing " ^ n.action); let ts' = update_timestamp depts n (maxts + 1) in begin print_endline (string_of_timestamps ts'); ts' end end else begin print_endline ("Nothing to be done for " ^ n.name); ts end else begin print_endline ("Nothing to be done for " ^ n.name); ts end and process_dependencies deps ts = let rec loop deps ts = match deps with [] -> ts | d :: deps' -> let ts' = process_node d ts in loop deps' ts' in loop deps ts let arith_mli = { name = "arith.mli"; dependencies = []; action = ""; } let arith_cmi = { name = "arith.cmi"; dependencies = [arith_mli]; action = "ocamlc -c arith.mli" } let arith_ml = { name = "arith.ml"; dependencies = []; action = ""; } let arith_cmo = { name = "arith.cmo"; dependencies = [arith_ml; arith_cmi]; action = "ocamlc -c arith.ml"; } let circle_mli = { name = "circle.mli"; dependencies = []; action = ""; } let circle_cmi = { name = "circle.cmi"; dependencies = [circle_mli]; action = "ocamlc -c circle.mli" } let circle_ml = { name = "circle.ml"; dependencies = []; action = ""; } let circle_cmo = { name = "circle.cmo"; dependencies = [circle_ml; circle_cmi]; action = "ocamlc -c circle.ml"; } let main_mli = { name = "main.mli"; dependencies = []; action = ""; } let main_cmi = { name = "main.cmi"; dependencies = [main_mli]; action = "ocamlc -c main.mli" } let main_ml = { name = "main.ml"; dependencies = []; action = ""; } let main_cmo = { name = "main.cmo"; dependencies = [main_ml; main_cmi; circle_cmi; arith_cmi]; action = "ocamlc -c main.ml"; } let app = { name = "app"; dependencies = [arith_cmo; circle_cmo; main_cmo]; action = "ocamlc -o app arith.cmo circle.cmo main.cmo"; } let ts = [ {n = arith_mli; t = 1}; {n = arith_cmi; t = 0}; {n = arith_ml; t = 0}; {n = arith_cmo; t = 0}; {n = circle_mli; t = 0}; {n = circle_cmi; t = 0}; {n = circle_ml; t = 0}; {n = circle_cmo; t = 0}; {n = main_mli; t = 0}; {n = main_cmi; t = 0}; {n = main_ml; t = 0}; {n = main_cmo; t = 0}; {n = app; t = 0}; ] let t1 () = process_node app ts let t2 () = (update_timestamp ts main_cmo 10) |> string_of_timestamps |> print_endline let t3 () = (get_timestamp ts arith_mli) |> string_of_int |> print_endline; (get_timestamp ts circle_mli) |> string_of_int |> print_endline let _ = t2 () let _ = t1 () let _ = t3 ()

Hope you found the above useful and interesting!