Topological Sorting with NetBSD

I needed to sort a file of Thun function definitions by their inter-dependencies, a classic topological sort. I'm working in a little NetBSD VM running on Qemu and I'm trying to avoid installing things on it, especially Python, so I wanted to do this using only the usual Unix/POSIX tools that come with a default install.

The definitions are listed in the defs.txt file one-per-line with the name of the function followed by the definition. Here is a representative snippet:

swapd [swap] dip
swoncat swap concat
swons swap cons
tuck dup swapd

Remove Square Brackets

The first step is to remove the brackets '[' and ']' from the file and replace them with spaces. These are the only "special" characters in the syntax of Thun, everything else is either a symbol, an integer literal, or one of the two Boolean literals. This is easily done with tr:

cat defs.txt | tr "[]" " "

Which would output:

swapd  swap  dip
swoncat swap concat
swons swap cons
tuck dup swapd

Generate Graph

Now the list of deps without brackets must be changed into a list of node pairs defining edges in the dependency graph. This is easily achieved with awk:

awk '{for (i=2; i<=NF; i=i+1) {if ($i !~ /^[0-9]+$/) {print $1 " " $i}}}'

For each line, for each field after the first, if that field is not an integer literal, print the first field followed by that field. This results in:

swapd swap
swapd dip
swoncat swap
swoncat concat
swons swap
swons cons
tuck dup
tuck swapd

This is suitable input to tsort. It would also be easy to adapt this to output a dot file for graphvis and generate some nice graphics of the, um, graph.

This whole thing could probably have been done just with awk, if I knew more awk. But I like how simple and concise this is.

Topological Sort

Now that we have the graph edges we can feed them to the tsort program (typically used in linking) to generate the topo-sorted order of the definitions. (The '-r' switch tells tsort to output the nodes with the dependent node listed after the nodes they depend on, which is how I want them for inscription into the Thun dictionary. This way the parser will reuse names it has already allocated for dependencies of definitions when parsing those definitions' body expressions. It's a small gain, sure, but why not?)

tsort -r

Output:

swap
dip
dup
swapd
cons
concat
tuck
swons
swoncat

Of course, here there's only one dependency (other than the built-in basis functions swap, dip, dup, cons, and concat) between tuck and swapd, so maybe I should have chosen a more intricate snippet, eh?

The only thing left is to sort the original defs.txt file by the topo order. That's not hard, but it does require an axuliary database.

Use a Database

When I looked up how to sort one file by means of another all the answers relied on grep. For each of the field values in the sorted index file, grep the original file for that field, thus outputting lines from the original file in the order that the index field values appear in the index file. Just what we want.

Now this is a classic quadratic algorithm, which would be bad if we had a large dataset, however the real problem is that I couldn't figure out how to do this (not without some shell code, but I want to avoid that for the sake of simplicity.) The xargs program can be used to supply the index field values from the index file to some other program, like grep, to find the corresponding line in the defs.txt file, but the grep program expects the pattern to come before the filename to search and I couldn't figure out how to do that. (I think it's possible with GNU grep but I haven't checked. This is on stock NetBSD.)

So we can't use grep, but we can use a simple hash db.

First we have to make it:

db -w -C -f defs.txt hash defs.hash.db

The '-w' means write, the '-C' means create the db file, and the '-f defs.txt' means read the keys and values from the defs.txt file (which thankfully is already in a suitable format.)

Now we can use it:

... | xargs -L 1 db -q -O " " hash defs.hash.db

Here we are piping the output of tsort into xargs using the '-L 1' option to tell it that each invocation of db should process only one input argument (the index field value). The db program searches the hash database file using the index field value as key and prints out the result. The '-q' switch tells it to silently ignore missing keys so that basis functions and Boolean literals cause no output, and the '-O " "' option indicates that the key (the name of the function) should be separted from the value (the body of the function) by a space rather than the default tab character. The result is that we get the definitions printed back out by the db program in the order that they appear in the index file. Pretty neat, eh?

You don't even have to write out the index file, it can be done with pipes. (You do have to generate and delete the database file though, but that's not a problem.)

cat defs.txt \
| tr "[]" " " \
| awk '{for (i=2; i<=NF; i=i+1) {if ($i !~ /^[0-9]+$/) {print $1 " " $i}}}' \
| tsort -r \
| xargs -L 1 db -q -O " " hash defs.hash.db > sorted_defs.txt

It was a lot of fun figuring all this out. The man pages were very helpful! All in all, I really like NetBSD. It's cozy.