On porting code
2019-11-26
Of late, my main side project has been rug, a stripped-down Git implementation which I’m building in Rust. I’m following along James Coglan’s excellent book Building Git where he lays out how he went about building the same project, in Ruby.
In essence, my project boils down to porting James’s code1 into Rust. But why bother with this at all? After all, porting code from one language to another is probably not on your top ten list of cool project ideas. Building something new will always be exciting. But I do think that at least as far as personal projects are concerned, porting a piece of code gets a bad rap. They can be a great learning experience and while it may not match the thrill of starting something afresh, can be plenty exciting to work on.
Working to re-write a piece of software in another language is a great way to dive deep into how the project works. With Git, you learn how the files, directories and commits in a repo are stored as objects, what happens as you are staging each hunk of your work and how diffing works. And so much more. To be sure, you could read an article or watch a video explaining how any of these things work but grappling with actual code to implement a functionality will give you a far superior understanding of things.
Besides the technical nuances of the software’s functionality, porting code will also expose you to how the project itself is architected. What are the entities the project deals with and what is the high-level structure of the project? What layers are there and why is it layered this way and not some other way? These are problems you will face when working on your own personal and professional projects. Choosing a well-designed system to study and port can give you some new perspectives on how to think about such things.
Translating a project from one language to another can also be a great
opportunity to get acquainted with a new language. I had done some
Rust before working on rug
but this project has been
large enough that I’ve been able to go deeper into both the language
and the ecosystem. For example, the last two days I’ve been working on
replacing the ad-hoc CLI argument parsing code with a wonderful Rust
library called clap
. With Rust, there are plenty of new concepts,
and sometimes it just takes some practice using it to get used to the
language.
Hopefully, I’ve convinced you that choosing to port a piece of software as your next programming side-project is at least worth considering. As I said earlier, building something entirely new has it’s thrills. But diving into a codebase and understanding it deeply enough to be able to port it to another language can also be immensely satisfying.
Which itself is a port(sorta) of the original Git codebase, but this is not really relevant for this post.
[return]
Piping output to a pager
2019-10-28
When you run git diff
on a project where you’ve made more than a
screenful of changes, the output is automatically redirected to a
pager and you can browse through your changes using the familiar
less
interface. This post shows a minimal example piping output to
less
.
To achieve this, git
creates a pipe and spawns a new process, whose
purpose is to exec the pager.
int fds[2];
if (pipe(fds) == -1) {
perror_die("pipe");
}
int child_pid = fork();
Let’s start by looking at the parent process, even though in the code
this case is handled last. The STDOUT of the parent process is aliased
to the write end of the pipe, so any further printing in the parent
process writes stuff to fds[WRITE_END]
. Once we’re done, we close
the write end of the pipe to signal EOF to the child process.
We wait for the child process to exit since otherwise control returns to the shell.
switch (child_pid)
// ...
default: { /* Parent */
/* STDOUT is now fds[WRITE_END] */
dup2(fds[WRITE_END], STDOUT_FILENO);
/* parent doesn't read from pipe */
close(fds[READ_END]);
/* "Business" logic which determines what to actually print */
int num_lines = 1024;
if (argc > 1) {
num_lines = atoi(argv[1]);
}
print_n_lines(num_lines);
fflush(stdout);
/* Signal EOF to the pager process */
close(STDOUT_FILENO);
int stat_loc;
waitpid(child_pid, &stat_loc, 0);
break;
}
The STDIN of the new process is aliased to the read end of the
pipe. Anything being printed in the parent process is thus now an
input to the pager process. After setting up STDIN, this process runs
less
.
switch (child_pid) {
case 0: { /* Child(pager) */
/* Pager process doesn't write to pipe */
close(fds[WRITE_END]);
/* Make READ_END of pipe pager's STDIN */
dup2(fds[READ_END], STDIN_FILENO);
/* F -> quit-if-one-screen */
/* R -> preserve color formatting */
/* X -> don't send some special instructions eg. to clear terminal screen before starting */
char *less_argv[] = {"less", "-FRX", NULL};
int exec_status = execvp(less_argv[0], less_argv);
fprintf(stderr,
"execvp failed with status: %d and errno: %d\n", exec_status, errno);
break;
}
// ...
} // switch
The full example can be found in this gist. You can also check out the Ruby and Rust implementations of this.
Myers' diff algorithm in Clojure
2019-10-21
If you’re a programmer, you’re probably fairly comfortable with
understanding and interpreting diff patches of the kind that git
and
other version control systems use. In this post we’ll walk through a
Clojure implementation of the Myers’ diff algorithm, which is the
algorithm used by Git.
I have been implementing Git following along James Coglan’s book “Building Git”– you can check out the project here. The project itself is in Rust but I thought it might be an interesting exercise to implement the algorithm in Clojure.
Edit graph
Say we want to turn a file with the lines A,B,C
into A,C,E
. The
Myers’ diff algorithm finds out the shortest edit script that does
so. The algorithm works on an edit graph as shown above– a rightward
traversal from one vertex to another indicates deletion of a line from
the old file; a downward traversal indicates insertion of a line from
the new file.
Also notice that in our example ABC -> ACE
there are two lines which
are the same(A & C). Myers’ algorithm leverages this to produce the
shortest edit script. In our edit graph above, you can see that where
lines are equal we have drawn dotted lines to indicate diagonal
traversals which require neither insertion nor deletion. The Myers’
algorithm maximizes the number of diagonal traversals in the edit
script it produces1.
Let’s walk through the output Myers’ algorithm produces for our example above:
The first character is the same in both files so take the first
diagonal down. Then delete B
. The third character in the old
file(C
) is the same as the second in the new file so keep it and do
a diagonal traversal again. Then insert E
. This series of edits on
the old file has produced our desired new file, and so we stop.
Finally, before we dive into the algorithm, we have one more addition
to the edit graph. We will draw downward-diagonals across the graph,
also called k-lines. Each k-line has the equation k = x - y
.
Implementation
The maximum number of operations(insertions or deletions) the edit
script can have is len(old) + len(new)
– in this case we would be
deleting every line in the old file and inserting every line from the
new file.
We iterate through 0 to maximum number of operations and see what the
farthest point along each k-line we can go. In the reduce
, we can
see that our accumulator is a tuple with v
and trace
.
v
maps each k
to the farthest x
we have found so far along that
k-line. We can discard the y
values since we can easily compute
them(y = x - k
).
trace
is a vector of the v
s we’ve seen so far.
We can see that the function ultimately returns trace
. This will be
used to reconstruct the path that we took along the graph.
(defn shortest-edit [a b]
(let [max (+ (count a) (count b))
[_ trace] (reduce (fn [[v trace] d]
(let [[found-end? farthest-xs] (get-farthest-xs-for-d v a b d)
[new-v new-trace] [(merge v farthest-xs)
(conj trace v)]]
(if found-end?
(reduced [new-v new-trace])
[new-v new-trace])))
[{1 0} []]
(range 0 (inc max)))]
trace))
To get to a line k, we can either go down from k+1 or go right from
line k-1. We use the move-down?
function to decide whether to move
down or right:
(defn move-down?
[v d k]
(or (= k (- d))
(and (not= k d)
(< (get v (dec k))
(get v (inc k))))))
If k=-d, it is not possible to go right from k-1, so go down from k+1.
If k=d, it is not possible to go down from k+1, so go right from k-1.
Otherwise, go down if
v[k-1] < v[k+1]
.What this expression in the predicate is saying is: if we are further along on the k+1 line, we want to go down to meet the k line. Else go right from the k-1 line.
Next, in get-farthest-xy-along-k*
we figure out what the farthest
(x,y) we can reach in this round d
along the k
line given the v
map we’ve built so far. a
and b
contain the lines that we want to
diff. This simply uses move-down?
as described above; then if
possible walks down any diagonals.
(defn get-farthest-xy-along-k*
[v d a b k]
(let [x (if (move-down? v d k)
(get v (inc k))
(inc (get v (dec k))))
y (- x k)
;; walk down diagonals
[x y] (loop [[x y] [x y]]
(if (and (< x (count a))
(< y (count b))
(= (get a x) (get b y)))
(recur [(inc x) (inc y)])
[x y]))]
[x y]))
get-farthest-xs-for-d
iterates from -d to d(both inclusive), 2 steps
at a time2 and stores the farthest x
for each k
, returning
early if we reach the bottom-right corner in our edit graph.
(defn get-farthest-xs-for-d
[v a b d]
(let [get-farthest-xy-along-k (partial get-farthest-xy-along-k* v d a b)]
(reduce (fn [[found-end? k->x] k]
(let [[x y] (get-farthest-xy-along-k k)]
(if (and (>= x (count a))
(>= y (count b)))
(reduced [true k->x])
[found-end? (assoc k->x k x)])))
[false {}]
(range (- d) (inc d) 2))))
So far, we’ve built up functions that give us a trace:
myers.core> (shortest-edit (clojure.string/split "ABCABBA" #"")
(clojure.string/split "CBABAC" #""))
[{1 0}
{1 0, 0 0}
{1 1, 0 0, -1 0}
{1 1, 0 2, -1 0, -2 2, 2 3}
{1 5, 0 2, -1 4, -2 2, 2 3, -3 3, 3 5}
{1 5, 0 5, -1 4, -2 4, 2 7, -3 3, 3 5, -4 3, 4 7}]
myers.core>
Now, let’s look at how to turn this into a diff.
Backtracking and producing the diff
This next function will take an input a trace and output an edit
sequence. Each element in the edit-sequence is of the form [prev-x
prev-y x y]
.
This time we start from the bottom-right node of the edit graph. In each iteration, we figure out the previous (x,y)– also walking back up diagonals if required.
(defn trace->edit-seq
[n m trace]
(let [[_ edit-seq]
(reduce (fn [[[x y] edit-seq] [d v]]
(let [k (- x y)
prev-k (if (move-down? v d k)
(inc k)
(dec k))
prev-x (get v prev-k)
prev-y (- prev-x prev-k)
[[x y] edit-seq] (loop [[x y] [x y]
edit-seq edit-seq]
(if (and (> x prev-x) (> y prev-y))
(recur [(dec x) (dec y)]
(conj edit-seq
[(dec x) (dec y) x y]))
[[x y] edit-seq]))
edit-seq (if (pos? d)
(conj edit-seq [prev-x prev-y x y])
edit-seq)]
[[prev-x prev-y] edit-seq]))
[[n m] []]
(reverse (map vector (range) trace)))]
(reverse edit-seq)))
Once we have an edit sequence, printing the diff is pretty straightforward:
(defn diff
[a b]
(for [[prev-x prev-y x y] (trace->edit-seq (count a)
(count b)
(shortest-edit a b))]
(let [a-line (get a prev-x)
b-line (get b prev-y)]
(cond
(= x prev-x) {:op :ins
:content b-line}
(= y prev-y) {:op :del
:content a-line}
:else {:op :eql
:content a-line}))))
(defn print-diff
[diff]
(doseq [{:keys [op content]} diff]
(let [d-out (case op
:ins (format "+%s" content)
:del (format "-%s" content)
:eql (format " %s" content))]
(println d-out))))
Summary of recent reading(July-September 2019)
2019-09-30
The Little Elixir & OTP Guidebook by Benjamin Tan Wei Hao: an introduction to the Elixir programming language and the OTP framework that comes with it. It focusses on Elixir’s concurrency features and shows you what OTP can do(the book mostly focusses on
GenServer
s andSupervisor
s) without spending too much time on the language itself– the idea being to get someone already familiar with functional programming excited about the features that set Elixir apart.The book is slightly outdated and has a couple of typos but I found it a worthwhile read– it’s relatively quick to work through and the book tries to build up a good mental model of what OTP behaviours offer and when to use them. Of note is the chapter showing how you might implement a
Supervisor
using aGenServer
.Atomic Habits by James Clear: on how to cultivate good habits and cull out bad ones. And why you should focus on building up good habits in the first place. I don’t know how valuable for me this was personally. The book was easy enough to read, and it says sensible things. The problem is that I never find myself actively applying things I learn from books like these.
Exhalation by Ted Chiang: collection of short sci-fi stories. I liked it just as much as the author’s first book Stories of Your Life and Others. I don’t know if there is a name for the flavor of science fiction that Chiang writes, but he really nails it. I especially liked that the book included Chiang’s notes on what he was going for when he was constructing each story.
Orca by Steven Brust: book 7 of the Vlad Taltos series. The series seemingly seems to get better with every book. This book in the series is still fantasy and not financial thriller, but at times it tries to be. Also loved that big parts of the book are from the perspective of Kiera, Vlad’s friend and renowned thief.
[spoiler] Vlad agrees to help a woman with her land getting foreclosed in exchange for her help healing Savn. This leads to the investigation of the death of Fyres, a shady Orca businessman. Vlad soon realizes that the situation involves a much larger scam and big banks covering up a murder for fear of going under if truth comes to light. [/spoiler]
Dragon by Steven Brust: the next book in the Vlad Taltos series. I found some stretches of the book a bit of a chore to read, even though this is still a short book. Although that might have been because I took a longish break when reading the book.
[spoiler] Vlad enlists in Morrolan’s army for war against Fornia, a Dragon who’s stolen something from Morrolan. [/spoiler]
Summary of recent reading(April-June 2019)
2019-06-30
Peak by Anders Ericsson and Robert Pool: a book on deliberate practice by one of the researchers who originally coined the term. This book lays out a framework for how to achieve expertise. Briefly, this goes as follows: identify what skills and mental representations an expert possesses, design a step-by-step program where you build up that skill, get feedback on what you’re doing wrong, focus on your weaknesses as you practice. The book emphasizes mental representations as essential to expertise– as chess players study games for many, many hours they see not just individual pieces but learn to identify larger patterns in any configuration. Deliberate practice is about building similar mental representations in any skill you want to master.
Overall, I think this book is a worthwhile read. You’ve probably encountered the idea of deliberate practice elsewhere by now, and the authors lay down exactly what that entails. The book can be a bit dry at times– it tries to stay firmly grounded on facts, and that means citing one study after another. But I did find the description of how Benjamin Franklin designed a program to practice his writing skills to be really cool.
Backstabbing for Beginners by Michael Soussan: an insider’s account of the United Nations operation overlooking sanctions imposed on Saddamn Hussein’s Iraq. The book is very open about the many failings(including incompetence, naivete and downright corruption) of the Oil-for-Food program and the people involved. And how Saddam Hussein benefitted massively, to the detriment of the people of Iraq, by exploiting these failings.
I found the book really well-written, and highly recommend it.
Phoenix by Steven Brust: This is book 5 of the Vlad Taltos series. I’ve reviewed the earlier ones, and I can definitely stick to my recommendation for this series– these books are short and entertaining. I’m reading them in order of publication date; in terms of chronological order, this book follows book 3(Teckla).
Athyra by Steven Brust: Book 6 of the Vlad Taltos series. This one’s written in a different voice and centers around a different character, although the protagonist of the series– Vlad– still plays a significant role. Still really fun.