About a month ago I started a new programming project. It was a moment of feeling isolate at home, and so I went out to a near café and started scribbling on a piece of paper. I had no goal or idea where I was going, other than spending my time so the next day will start already.

In my battle against the Dark Lord of The Blues I started writing my thoughts. It’s a good exercise both for enhancing writing skill and for raising feelings and thoughts to the surface. And then a faint idea came in: wouldn’t it be nice to compile this text I’ve written and output it in a nice, elegant typeset fashion? Not because it would be useful to have my text nicely typeset, but because it would be useful to write a compiler. I was thinking at the time less of a practical tool I’d want and more of a tool I’d want to create.

  ASDF

Asdf as asdfing, asd F asdfed.  "Asdf!" asd asdfed.  "Asdf!".
"Asdf?" F asdfed, "ASDF?!".  "A, asdf".

Asdf asdf, asdfasdfion as asdfing as.  ...

...

It was easy and straightforward to see the pattern in my text. Maybe because I was free-writing, not writing a complex document such as a math-infected assignment or a term paper packed with tables and page numbers and table of contents and images. Just fluent text: nothing but headings and paragraphs. Yes, my headings are always indented with space and my paragraphs are always delimited with an empty line. Even my sentences are clearly separate from each other with two spaces. To some extent, I have a language there which I can parse!

That was the process in which INSPext was coming out to life. I quickly had a grammar written down that defined how I have always structured my text, in terms of headings and paragraphs. It was a simple grammar, composed of maybe 3 or 4 rules. And this, in fact, encouraged me tremendously to go right ahead and bang out the scanner and parser code.

I thought this would be a small project to spend the day. Nothing worth blogging about. But it’s been a month now that I’ve been playing with this little baby, and so I think it’s time I acknowledge its place among the living. So allow me to introduce: INSPext.

For instance, given the sequence

[As,4s,6h,6h,7d,Kc,Ks]

and the subset

[As,6h]

the output should be

[4s,7d,Kc,Ks]

~$ rails exp
dyld: lazy symbol binding failed: Symbol not found: _rb_intern2
Referenced from: /Users/matan/usr/lib/ruby/1.9.1/gems/hpricot-0.8.1/lib/fast_xs.bundle
Expected in: flat namespace

dyld: Symbol not found: _rb_intern2
Referenced from: /Users/matan/usr/lib/ruby/1.9.1/gems/hpricot-0.8.1/lib/fast_xs.bundle
Expected in: flat namespace

Trace/BPT trap

If the above looks familiar to you try to unset GEM_HOME and see if it resolves your issue:

~$ unset GEM_HOME

Alternatively add $HOME/usr/lib/ruby/1.9.1/bin (or wherever you installed Ruby) to your PATH.

vimdiff in action

vimdiff is an interactive file comparison and merging utility for the command-line. It simply starts Vim in a special mode called the diff-mode. To get started with vimdiff from the command-line,

$ vimdiff oldfile newfile

2 pairs of commands will get you started:

• Navigating: ]c and [c will take you to the next and previous diffs, respectively.
• Merging: dp and do will merge the current diff from the current buffer into the other buffer, and from the other buffer into the current buffer — respectively. dp stands for diff-put and do stands for diff-obtain.

make_snippets.vim

a: [b, c, d]
b: [b, c]
c: [a]

Node a points to neighbour nodes b, c and d. Similarly node c points to neighbour node a. Here is the Ruby code which parses this graph, assuming it comes from stdin:

require 'yaml'
g = YAML::load(STDIN)

I can generate a dot file that visualizes the graph like so:

puts "digraph {"
g.each_key do |v|
  g[v].each { |n| puts "  #{v} -> #{n};" }
end
puts "}"

Visualization of Graph g by graphviz dot

If I want to add support for edge weights then I can do it by changing the input format:

a: {b: 3, c: 3, d: 2}
b: {b: 0, c: 1}
c: {a: 3}

All I’m doing is playing on YAML, so my parsing code need not change. I “added” a feature without changing a single line of code!

It is interesting to find an analogous technique in C++, where I parse a graph into a map. The following code will take a directed, unweighted graph from stdin:

#include<iostream>
#include<algorithm>
#include<iterator>
#include<map>
#include<set>
#include<sstream>
#include<string>

using namespace std;
typedef map<string,set<string> > graph;

int main(int argc, char* argv[])
{
    string line;
    graph g;
    while( getline(cin, line) ) {
        istringstream ss(line);
        string from, to;
        ss >> from;
        graph::mapped_type neighbours;
        copy(istream_iterator<string>(ss),
             istream_iterator<string>(),
             inserter(neighbours, neighbours.end()));
        g.insert(make_pair(from, neighbours));
    }

    return 0;
}

The standard C++ library doesn’t support YAML, but it does provide help for parsing whitespace-delimited input through the iostream library. That’s what the code above takes advantage of. Graph input for the above C++ program will thus look like so:

a b c d
b b c
c a

I leave it as an exercise for you to add support for parsing a weighted graph:

a b 3 c 4 d 5
b b 0 c 1
c a 4