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!

Computing Unions and Differences for Sets of Time Durations

Timeline

This article presents an algorithm to compute set union and set minus in a specific context. Each set is a set of contiguous stretches on a real line.

Problem Description

Union

Consider a scenario where two people are teamed up to contribute to a particular task, say attending to an infant child. As long as any one of them is available to look after the child, it's fine. For other times, they probably would have to look for an alternative arrangement. The time any one person is available can be represented as a set of durations. The time for which at least one of the two persons is available is nothing but the union of the sets of durations during which each one of them is available.

Set Minus

Consider a scenario when two people are looking for a slot wherein both are available for a discussion. This can be thought of a difference between the the available time of one person and the busy time of the other.

Solution Approach

The solution approach makes use of a variable level which keeps track of the starts and ends of durations. After placing all the important time instants on a time line, we scan the time line from left to right.

While computing union, we use the following strategy to set the level during our scan of the timeline:

1. Each time any of the duration begins, we increment level by 1.
2. Each time any of the durations ends, we decrement level by 1.

As per the above, the stretches of the timeline with level = 0 indicate stretches when none of the two sets is present.

The rest of the timeline will have positive values of level indicating that at least one of the two sets is present there.

In another pass of the timeline, we now collect all the continuous stretches of the timeline where level is not zero. This gives us the set of durations corresponding to the union of the two sets.

While computing set minus, we employ the following strategy for maintaining level.

1. The starting point of a duration in the first set and end of a duration in the second set cause level to be incremented by 1.
2. The end point of a duration in the first set and start of a duration in the second set cause level to be decremented by 1.

As per the above, the stretches of the timeline with level = 1 indicates stretches in the difference between the first set and the second.

In another pass, we collect the set of contiguous portions of the timeline where level = 1. This is our answer of set minus.

Extensions

The union and setminus functions can be used to implement other useful set operations on the above kind of sets, viz. complement and intersection.

Implementation

Representation of the sets

We represent the sets of durations as lists of pairs. s1 and s2 in the above figure (Timeline) have been represented as follows:

  s1 = [(1, 5), (8, 10), (15, 20)]
  s2 = [(2, 4), (6, 12), (16, 21)]

Code Design

When we implement the above two algorithms as two completely separate functions union and setminus, we realise that they have a very common structure. This gives us the motivation to try and capture this commonality between the two functions in a piece of re-usable code. We do so by designing a higher-order function make_function, which is parameterised by another function which captures the specific elements of the two functions. f1 and f2 are the two functions capturing these specificities of union and set minus.

The make_function function prepares a function and returns it as a result. the two functions union and setminus are created by calling make_function with f1 and f2 as arguments respectively. Note that this could have been implemented alternatively by embedding a call to make_function in union and setminus. This is a perfectly good option when union and setminus get used only once. However, considering a scenario where union and setminus may get called several times in a larger program, the strategy used here will lead to a slightly improved speed, not to mention improved readability (arguable).

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

# utility function for the implementation of union def f1(s1, s2): START = 1 END = -1 l = [] for (s, e) in s1: l.append((s, START)) l.append((e, END)) for (s, e) in s2: l.append((s, START)) l.append((e, END)) return sorted(l, key = lambda (x, y): x) #utility function for implementation of setminus def f2(s1, s2): START1 = 1 END1 = -1 START2 = -1 END2 = 1 l = [] for (s, e) in s1: l.append((s, START1)) l.append((e, END1)) for (s, e) in s2: l.append((s, START2)) l.append((e, END2)) return sorted(l, key = lambda (x, y): x) # Higher order function to create union and setminus functions def make_function(f): # boilerplate function to be returned from make_function after being plugged with f. def g(s1, s2): level = 0 result = [] l = f(s1, s2) for (t, SE) in l: print (t, level) last = level level += SE if level == 1 and last == 0: start = t if level == 0 and last == 1: end = t result.append((start, end)) return result return g union = make_function(f1) setminus = make_function(f2) def t1(): s1 = [(1, 5), (8, 10), (15, 20)] s2 = [(2, 4), (6, 12), (16, 21)] print union(s1, s2) def t2(): s1 = [(1, 5), (8, 10), (15, 20)] s2 = [(2, 4), (6, 12), (16, 21)] print setminus(s1, s2) if __name__ == "__main__": t1() t2()

set.py

Showing the Lady Her Right Place

The eight queen puzzle is a well-known problem having been used in teaching algorithms design techniques and programming. The problem is simple: place 8 queens and place them on a chess board such that none of them is in the line of attack of any other. Does such a solution exist? Yes. 92 of them, apparently (keep reading).

In fact, finding a solution manually doesn't turn out to be too hard, but may be an interesting exercise if you are interested in that kind of puzzles. But our objective here is to find an algorithmic solution. That is, to write an algorithm that finds us the solution to the problem. Again, it's a solved problem. The algorithm is all there. Nothing new. But implementing it was a challenge nevertheless.

Let me try and summarise the approach as follows:

Firstly, a bit of staring at the problem will reveal that each queen must have her own row (column).

Consequently, a succinct representation of a solution would be a list of numbers corresponding to the column in which the queen is placed, the knowledge that they are placed in separate rows being implicit.

For example, to represent the following solution:

-----------------------------------------
|    |    |    |  X |    |    |    |    | 
-----------------------------------------
|    |    |    |    |    |  X |    |    | 
-----------------------------------------
|    |    |    |    |    |    |    |  X | 
-----------------------------------------
|    |    |  X |    |    |    |    |    | 
-----------------------------------------
|  X |    |    |    |    |    |    |    | 
-----------------------------------------
|    |    |    |    |    |    |  X |    | 
-----------------------------------------
|    |    |    |    |  X |    |    |    | 
-----------------------------------------
|    |  X |    |    |    |    |    |    | 
-----------------------------------------

 we just say:

[3, 5, 7, 2, 0, 6, 4, 1]

Now, for some bit of notations. Let's say we have come up with a positioning pos. We say, satisfy(pos, i), when the sublist of pos from i to 7 (denoted by pos[i:]) forms a satisfying solution, i.e. no pair of elements in pos[i:] attack, or conflict with, each other. The above very satisfactory condition can be described declaratively as follows:

for i < 7, satisfy(pos, i) <=> satisfy(pos, i + 1) and for all j in [i + 1...7], conflict(pos[i], pos[j]) = false

for i = 7, satisfy(pos, i)

which means satisfy(pos, i) is true if and only if satisfy(pos, i+1) is true and the ith element of pos (pos[i]) doesn't conflict with any of the subsequent elements. And the recursion bottoms up with i = 7, for which satisfy(pos, i) is true no matter what.

That's all the notation I can bear before I really dive into the algorithm, which is what I really want to present. But the above also pretty completes the conceptual groundwork for writing the algorithm, which is nearly a lexical replication of the above thought. And that should convince you why recursive thinking is such a good way of designing algorithms: because it allows you to write your algorithms as declaratively as possible. What may have appeared to be very complex a phenomenon if thought of as a procedure, becomes ridiculously simple if thought of as a condition to be satisfied.

#!/usr/bin/python
import random
from counter import *

def conflict(a, b, diff):
 return (a == b) or abs(a - b) == diff

def satisfy(lst):
 if(len(lst) == 1):
  return True
 if(satisfy(lst[1:])):
  for i in range(1, len(lst)):
   if(conflict(lst[0], lst[i], i)):
    return False
  return True

def solve(pos):
 inc = makeCounter_rec(8)
 while(not satisfy(pos)):
  pos = inc(pos)
 return pos

The function satisfy works recursively, calling itself as it goes down the board, one row at a time looking for smaller and smaller partial solutions.

Did you notice that this algorithm uses a base-8 counter to sweep through the search space of all solutions (which is 8 raised to 8)? And that should answer any doubt as to the practical application of the counter program that I presented here.

You want to see the above running? Just add the below main function to the above code.

if __name__ == '__main__':
 sol = solve([random.randint(0, 7)%8 for i in range(8) ])
 print sol

Want to see a pretty printed solution? Add the below function somewhere in the above code:

def printSolution(sol):
 hline = '-----------------------------------------'
 print hline
 for pos in sol:
  print '| ',
  for i in range(8):
   if(i != pos):
    print '  | ',
   else:
    print 'X | ',
  print
  print hline
 

...and add the following line in your main function shown above:

 printSolution(sol)

If you want to go ahead and find all the solutions, here's the function and the modified main function:

def solveAll():
 inc = makeCounter_rec(8)
 solutions = []
 pos = [0] * 8
 n = 0
 while(True):
  solution = solve(pos)
  if(solution in solutions):
   break
  else:
   print solution
   solutions.append(solution)
   pos = inc(solution)
   n = n + 1
 print 'found ' + str(n) + ' solutions.'
 return solutions

If you print out the output of this function, after running for a couple of minutes, it will show you all the solutions of the problem. As mentioned above, they turn out to be 92 in number.