Collaborative Dependency-based Todo Using Makefiles

I once had a project that consisted of many moving parts: a sql procedure, a program to run it against multiple databases and output the results to files, a 3rd party specification for xml meta data describing the extract schema, a program to generate the xml, and on and on. At each stage, there was the potential that customer preference could affect choices made, so progress on each piece could be blocked. I wanted to make sure I could be working on some part of it whenever possible, so I drew up a dependency graph of the project. It occurred to me at the time that a Makefile could easily represent the dependencies, so I wrote a small awk script to translate back and forth between Makefile and tgf so I could generate either from the other.

Recently, @holman asked how people keep track of issues, pulls, next projects, etc. The ensuing conversation was a mixture of web apps, irc bots, and todo text files. Where it seemed to break down was that few people had a good system for managing dependencies across projects and teams or organizations. This got me thinking. Could my Makefile system be extended to work deal with people working in teams?

The basic idea would be that the a Makefile would define the dependencies in the project. My original concept used the existence of a file to indicate a completed task. I figured I could extend this idea to use the location of a file to differentiate between complete tasks and tasks assigned to a particular user. The whole thing could then live in a git repo to allow collaboration.

The result looked something like this:

#Makefile
include todo.mk

application: ui libraryB serviceC

ui: skills/html skills/css skills/javascript

libraryB: skills/math

serviceC: libraryD libraryE skills/rest

libraryD libraryE: skills/sql

---

#todo.mk
vpath % done $(wildcard users/*)

%: todo/%
    @echo In progress: $<

%:
    @echo Next: $@ with $^
    @false

---

#directory listing
done/
Makefile
todo.mk
users/
  dick/
    skills/
      math
      rest
    todo/
  harry/
    skills/
      sql
    todo/
  tom/
    skills/
      css
      html
      javascript
    todo/

---

Typing make will result in:

Next: ui with users/tom/skills/html users/tom/skills/css users/tom/skills/javascript
todo.mk:7: recipe for target 'ui' failed
make: *** [ui] Error 1

So that means ui is the next incomplete task that has all of its prerequisite tasks done. make also found all of the necessary skills belong to tom, so we probably want to assign the task to him with touch users/tom/todo/ui. Once we do that, make will show us:

In progress: users/tom/todo/ui
Next: libraryB with users/dick/skills/math
todo.mk:7: recipe for target 'libraryB' failed
make: *** [libraryB] Error 1

So we can see tasks that are being worked on and also the next task that's ready to start. Let's move things along: touch users/dick/todo/libraryB, touch users/harry/todo/libraryD, mv users/harry/todo/libraryD done/, touch users/harry/todo/libraryE. Now make:

In progress: users/tom/todo/ui
In progress: users/dick/todo/libraryB
In progress: users/harry/todo/libraryE
Next: serviceC with done/libraryD libraryE users/dick/skills/rest
todo.mk:7: recipe for target 'serviceC' failed
make: *** [serviceC] Error 1

Looks like serviceC is the next thing that can be started. But wait. libraryD is done, but it doesn't say that about libraryE. If we've been paying attention, we can see that it's in progress and assigned to harry, but what if we're on a really big project and it we didn't see it? Well, make libraryE:

In progress: users/harry/todo/libraryE

Ok, so it's being worked on. touch users/dick/todo/serviceC, make:

In progress: users/tom/todo/ui
In progress: users/dick/todo/libraryB
In progress: users/harry/todo/libraryE
In progress: users/dick/todo/serviceC
Next: application with ui libraryB serviceC
todo.mk:7: recipe for target 'application' failed
make: *** [application] Error 1

So maybe we can start the application? Let's take a closer look though. make serviceC:

In progress: users/harry/todo/libraryE
In progress: users/dick/todo/serviceC

Okay, so harry needs to finish libraryE, then dick can finish serviceC. Awesome.

This may not be something I'll actually use, and I certainly don't expect you to use it. But it was a fun experiment.

Abusing Canvas to Make a Mandelbrot Viewer

When possible, I generally live in ssh.

I rarely boot my desktop any more. Most of my active work lives on an always-on Raspberry Pi. So I ssh in either from my netbook, wi-phone, or, if I'm trapped on a Windows box, PuTTY.

Really, it's a wonderful protocol. But it has it's shortcomings: topically, graphics and audio. I've experimented with a few different ideas for audio--UDP streams, web servers using chunked encoding, etc.--with mostly unsatisfactory results. If you know of anything that solves this problem, please contact me.

Today's post, however, is about graphics. The de facto standard for dealing with graphics over ssh has always been X forwarding. Unfortunately, it's kind of a joke. Don't get me wrong. I'm thankful for it, but as proponents of the slew of new windowing systems have pointed out, the number of round trips can make the latency unbearable.

So what if we could do something similar to sending audio data via a web server? Only instead of chunks of audio data, we send snippets of javascript manipulating a canvas element? It might turn out to be just as bad as X, but at least it gives me an excuse to learn something.

With that in mind, I started learning a little about the canvas API today. It's a little higher level than blitting pixels to the screen, so I abused it quite severely in my first project, but it got me started.

A while back, I wrote a mandelbrot set visualizer that rendered to the console (due not as much to ssh graphics shortcomings, as to my limited graphics library vocabulary) in c. The implementation is almost verbatim copied from Wikipedia and is naive more than it is performant, but it got the job done at the time. My javascript has never been idiomatic, but I'm at least conversant, so porting it was straightforward.

The initial rendering actually looked so nice, it made me wish I could navigate it interactively. Then I remembered this is javascript, so anything goes. A little googling turned up this StackOverflow answer and after correcting a couple of my arithmetic mistakes, I had a functioning project.

The code is not pretty, but I feel pretty good about how simple it was to get it working. Let me know what you think.

State Machines

I've been enthralled with state machines lately. It's become unhealthy. I don't remember if it started by playing around with lex and yacc, or if it was when I found Mongrel2 and read this post. But from that point on, I've been obsessed with finite state machines, parsers, regular expressions.

Recently, when after a stack overflow question pushed me into hand coding another state machine based parser, I read this blog post, which introduced a method of implementing state machines that I hadn't seen before. I'm sure it's not new. In fact it probably dates back to the era of machine code. But it was new to me, and I like it better than tables or nested conditionals. The basic idea is to break out the code for each state into its own function and then use a function pointer to track the state instead of an enum and switch.

Of course, I couldn't leave well enough alone. I thought I could do one better if I returned the new function pointer instead of storing it in a reference parameter. As it happens, C is a little funny about returning a pointer to a function with the same signature as the function doing the returning... something to do with infinitely recursive type definitions I guess. So the best I could come up with was a struct containing just the function pointer. That doesn't add too much syntactically when calling the functions, and modern compilers optimize it to just returning the function pointer in a register, but returning them becomes a little more unwieldy. You either need to define const structs somewhere (which is no better than enums), declare and define a local struct to be returned (more lines in each function), or restrict to C99 and use compound literals. If you can think of a better way to tackle this, please let me know. Here is how those three look in code.

typedef struct _state state;
struct _state
{
    state (*func)(char);
};

state init(char);
state final(char);

#if CONST
const state INIT = {init};
const state FINAL = {final};
#endif

state
init(char input)
{
#if LOCAL
    state next;
#endif

    switch(input)
    {
#if CONST

    case 'a':
        return FINAL;
    default:
        return INIT;

#elif LOCAL

    case 'a':
        next.func = final;
        return next;
    default:
        next.func = init;
        return next;

#elif C99

    case 'a':
        return (state){final};
    default:
        return (state){init};

#endif;
    }
}

Here's an example of a simple rpn calculator. I decided to go the route of using const structs, even though it pollutes the global namespace. I did this mainly because it maintains C89 compatibility while requiring less typing than locals or the original design of saving to a reference parameter.

#include <stdio.h>
#include <stack.h>

typedef struct state_ state;

struct state_
{
    state (*func)(char);
};

state initial(char);
state number(char);

const state INITIAL = {initial};
const state NUMBER = {number};
const state END;

state
initial(char input)
{
    int a;

    if(input == 'p')
    {
        printf("%i\n", pop());
        return INITIAL;
    }
    else if(input == '+')
    {
        a = pop();
        *top() += a;
        return INITIAL;
    }
    else if(input == '*')
    {
        a = pop();
        *top() *= a;
        return INITIAL;
    }
    else if(input >= '0' && input <= '9')
    {
        ungetc(input, stdin);
        push(0);
        return NUMBER;
    }
    else
    {
        return END;
    }
}

state
number(char input)
{
    if(input >= '0' && input <= '9')
    {
        *top() *= 10;
        *top() += input - '0';
        return NUMBER;
    }
    else
    {
        ungetc(input, stdin);
        return INITIAL;
    }
}

int
main(void)
{
    int ch;
    state s = INITIAL;

    while((ch = getchar()) != EOF && s.func)
    {
        s = s.func(ch);
    }

    return 0;
}

Too Clever For Your Own Good

This is sort of a cross-post. I contributed this as a show for Hacker Public Radio back on 2013-09-25. You can hear the associated podcast here. Sorry about the stale content, but I wanted something to open the blog with right away. I'll try to do better about posting things as I discover them.

This is a story about being so lazy that I'd rather teach the computer to do something than learn how to do it myself. HPR episode 1216 piqued my curiosity, but rather than try to remember my Morse code, I decided I could teach the computer to translate it for me. This episode tells that story.

Commands

Uncompress the audio

sox hpr1216.ogg hpr1216.wav

Get the format data

soxi hpr1216.wav

Figure out how long the wav header is so we can skip it

sox -t raw -b 16 -r 44100 -c 1 -e signed-integer /dev/null empty.wav

Dump the audio data in a text format

hexdump -s 44 -v -e '220/2 "%04x"' -e '"\n"' hpr1216.wav > hpr1216.hex

Convert values near 0 to spaces so it's easier to parse (at least visually)

sed -e 's/000./    /g' -e 's/fff./    /g' hpr1216.hex > hpr1216.space

Run it through the following awk script to make it readable by morse

awk -f morse.awk hpr1216.space > hpr1216.dot

And the script

#morse.awk
#every line
{
    last = this;
    this = $0 ~ /^ *$/; #220 samples near 0, roughly 20ms of silence
}

#consecutive lines of silence or sound
last == this {
    duration++;
}

#sound->silent state transition
!last && this {
    if(duration > 10 && duration < 20) #dit is roughly 18 lines or ~360ms
    {
        printf ".";
    }
    else if(duration > 30 && duration < 40) #dah is roughly 36 lines, 720ms
    {
        printf "-";
    }

    duration = 0;
}

#silent->sound state transition
last && !this {
    if(duration > 30 && duration < 40) #short gap (letter) is roughly 720ms
    {
        printf "\n";
    }
    else if(duration > 80) #medium gap (word) is anything over 1600ms
    {
        printf "\n\n ";
    }

    duration = 0;
}

Use morse to decode the translated output

morse -d < hpr1216.dot > hpr1216.txt

And this is what it looks like

IOS SOS SOS THE STANDARD EMERGENCY SIGNAL IN MORSE CODE. FOR EMERGENCY SIGNALS MORSE CODE CAN BE SENT BY WAY OF IMPROVISED SOURCES THAT CAN BE EASILY KEYED ON AND OFF MAKING IT ONE OF THE SIMPLEST AND MOST VERSATILE METHODS OF TELECOMMUNICATION. THE MOST COMMON DISTRESS SIGNAL IS SOS OR THREE DOTS THREE DASHES AND THREE DOTS INTERNATIONALLY RECOGNIZED BY TREATY. MORSE CODE FROM WIKIPEDIA THE FREE ENCYCLOPEDIA MORSE CODE IS A METHOD OF TRANSMITTING TEXT INFORMATION AS A SERIES OF ON-OFF TONES LIGHTS OR CLICKS THAT CAN BE DIRECTLY UNDERSTOOD BY A SKILLED LISTENER OR OBSERVER WITHOUT SPECIAL EQUIPMENT. THE INTERNATIONAL MORSE CODE ENCODES THE ISO BASIC LATIN ALPHABET SOME EXTRA LATIN LETTERS THE ARABIC NUMERALS AND A SMALL SET OF PUNCTUATION AND PROCEDURAL SIGNALS AS STANDARDIZED SEQUENCES OF SHORT AND LONG SIGNALS CALLED DOTS AND DASHES OR DITS AND DAHS. BECAUSE MANY NON-ENGLISH NATURAL LANGUAGES USE MORE THAN THE 26 ROMAN LETTERS EXTENSIONS TO THE MORSE ALPHABET EXIST FOR THOSE LANGUAGES. EACH CHARACTER LETTER OR NUMERAL IS REPRESENTED BY A UNIQUE SEQUENCE OF DOTS AND DASHES. THE DURATION OF A DASH IS THREE TIMES THE DURATION OF A DOT. EACH DOT OR DASH IS FOLLOWED BY A SHORT SILENCE EQUAL TO THE DOT DURATION. THE LETTERS OF A WORD ARE SEPARATED BY A SPACE EQUAL TO THREE DOTS ONE DASH AND TWO WORDS ARE SEPARATED BY A SPACE EQUAL TO SEVEN DOTS. THE DOT DURATION IS THE BASIC UNIT OF TIME MEASUREMENT IN CODE TRANSMISSION. FOR EFFICIENCY THE LENGTH OF EACH CHARACTER IN MORSE IS APPROXIMATELY INVERSELY PROPORTIONAL TO ITS FREQUENCY OF OCCURRENCE IN ENGLISH. THUS THE MOST COMMON LETTER IN ENGLISH THE LETTER E HAS THE SHORTEST CODE A SINGLE DOT. MORSE CODE IS MOST POPULAR AMONG AMATEUR RADIO OPERATORS ALTHOUGH IT IS NO LONGER REQUIRED FOR LICENSING IN MOST COUNTRIES INCLUDING THE US. PILOTS AND AIR TRAFFIC CONTROLLERS USUALLY NEED ONLY A CURSORY UNDERSTANDING. AERONAUTICAL NAVIGATIONAL AIDS SUCH AS VORS AND NDBS CONSTANTLY IDENTIFY IN MORSE CODE. COMPARED TO VOICE MORSE CODE IS LESS SENSITIVE TO POOR SIGNAL CONDITIONS YET STILL COMPREHENSIBLE TO HUMANS WITHOUT A DECODING DEVICE. MORSE IS THEREFORE A USEFUL ALTERNATIVE TO SYNTHESIZED SPEECH FOR SENDING AUTOMATED DATA TO SKILLED LISTENERS ON VOICE CHANNELS. MANY AMATEUR RADIO REPEATERS FOR EXAMPLE IDENTIFY WITH MORSE EVEN THOUGH THEY ARE USED FOR VOICE COMMUNICATIONS. THERE ARE MANY APPLICATIONS IN LINUX TO HELP YOU LEARN MORSE CODE. CHECK OUT RADIO.LINUX.ORG.AU FOR A LIST OF APPLICATIONS.

A little googling will show that this text is the brief description of Morse code given at the top of its Wikipedia article. Surprisingly, the only transcription error appears to be the first letter as it was slightly overlapped by the intro music. It's also interesting to note that, since music consists of almost no sounds this short, the script was able to extract the data and robustly ignored everything else. In light of this, I probably could have skipped removing the wav header. Additional time could be saved by changing the regex in the awk script to match the raw hex values and thereby eliminate the sed step.