ANI: implicit, safe, guaranteed deadlock-free parallelism

I’ve been involved in the ANI community lately and I’ve wanted to blog about it, but couldn’t bring myself to come up with some code samples, since its such an early work-in-progress. I finally managed to muster up enough motivation to talk about some of the existing sample code instead, so here we are.

The most important question is “What is ANI and why is it interesting?” and this is exactly what I hope to answer.

ANI is a (very early) work-in-progress parallel programming language based on the dataflow paradigm. Currently, anic (the ANI compiler) can parse the source code, but cannot yet generate any runtime code. Hopefully I will be able to give a real, live demonstration soon.
What makes ANI interesting is that it aims to be fast, safe and easy to use and it achieves this by building on a solid dataflow-based core language. The compiler and runtime are to ensure that an ANI program will make use of available processing cores, in parallel, and that this implicit parallelism will never deadlock. That is, ANI is parallel and safe.
ANI programs also manage memory in such a way that the programmer will not have to manually handle allocation and freeing of memory, but the runtime also does not need a complex or slow garbage collector. This is achieved by the way that ANI manages the dataflow core – it always knows what data is in use and when it can be freed.
Because of these features, ANI is a very different language to the imperative languages we are used to and, therefore, may seem quite complex and difficult, but once the core concepts are understood, the language becomes surprisingly easy. So, lets take a look at these core concepts.

The ANI language is built around a handful of base concepts, namely latches, streams, filters and pipes. I will introduce each in turn.

• A pipe is a sequence of instructions through which data flows and the core construct through which ANI moves data from operation to operation. A pipe is executed sequentially and multiple pipes will execute in parallel, side by side. When a pipe requires data from a latch or a stream, it may block while waiting for the latch or stream to produce data – that is, become non-empty.

• A latch is a placeholder for a value, not unlike a variable in imperative languages. Latches may be empty – containing no value at all – or they may be initialized. You can, of course, put a value into a latch later and you can take the value out again, making the latch be empty once again. The important part, however, is that when a latch contains a value, any pipes which are blocking to receive its value become runnable and are scheduled to be executed.

• A stream is a queue of latches. Values can be fed into a stream and into a pipe, where it can be processed.

• A filter is a piece of code through which values may flow, as part of a pipe. Filters may alter or consume values from the pipe. For example, a filter could take in a pair of numbers and add them.

So, what does ANI look like? The following sample program demonstrates the major constructs which make up the ANI language. This program, taken from the ANI test code, runs a combination of a realtime clock and a simple textual calculator, running in parallel. The user is prompted to enter a number, followed by one of +, -, * or / and then another number. The calculation is performed and the result is output on the next clock tick. The three parts – input, calculation and clock tick/output – can all execute in parallel.

@std.in;

a  = [[int\]]  <- 0;
op = [[char\]] <- ' ';
b  = [[int\]]  <- 0;
r  = [[int\]]  <- 0;

0 {
    clock => [[int ms]] {
        ("\r" + ms/1000.0 + ": " + a + op + b + "=" + r) ->std.out;
        1 std.delay
        (ms+1) clock
    }
};

inLoop => {
    \in ->a
    \in ->op
    \in ->b
    inLoop
};

\\op ?? {
    '+': (\a + \b)
    '-': (\a - \b)
    '*': (\a * \b)
    '/': (\a / \b)
       : 0
} ->r;

I will now disect the program and explain each part in turn.

@std.in;

a  = [[int\]]  <- 0;
op = [[char\]] <- ' ';
b  = [[int\]]  <- 0;
r  = [[int\]]  <- 0;

The @std.in; adds the in latch from the std package to the current namespace. The rest of this code snippets defines and initializes latches for the programs internal use. int\ means a latch to hold an integer, char\ means a latch to hold a single character. [[datatype]] is how objects are constructed in ANI. So, for example, [[int\]] constructs a latch which can hold an integer. The <- value assigns the specified value to the newly constructed object and the = binds it to an identifier so it can be referred to later. So, the first line creates an integer latch, initializes it to zero and binds the name a to it.

The next code block is a little more involved.

0 {
    clock => [[int ms]] {
        ("\r" + ms/1000.0 + ": " + a + op + b + "=" + r) ->std.out;
        1 std.delay
        (ms+1) clock
    }
};

The easiest way to understand this code snippet is by starting with clock => [[int ms]] {. What this line does is creates a pipe named clock, which takes an integer value (bound to the name ms). The => means that any values to the left of the name (in this case 0) will flow into the pipe – that is, it is defined and used in place. If = had been used instead, then 0 would have had to have been sent to clock with 0 clock, somewhere outside of its definition. The code inside { … } is the body of the clock pipe.

The first line in the clock pipe first concatenates a bunch of strings (implicitly converting the values of a, op, b and r to strings).  ms is divided by 1000.0 before being converted to a string. For example, if ms contains 2345, a contains 2, b contains 5, r contains 7 and op contains ‘+‘, then the expression inside the parentheses would evaluate to “\r2.345: 2+5=7” (and \r is a carriage return). The final part of this line, ->std.out, sends this string to std.out which causes it to be output to the screen. The semicolon at the end of the line means that this is the end of the pipe and a new pipe is started (but both are sub-pipes of the clock pipe, which continues until the } is reached. Basically, clock forks into two parallel pipes). This pipe and the next may be executed concurrently, every time clock is sent a value.

The second pipe sends 1 to std.delay, causing this pipe to be delayed (or paused) for (at least) 1 millisecond and then the pipe continues. The final part of this pipe adds 1 to the value of ms and passes it to clock – this causes these two pipes to be executed again, but this time ms has been incremented by one. Essentially, this defines a feedback loop, which causes clock (and therefore its two sub-pipes) to be executed in 1 millisecond increments, printing the current state of the calculator (a, b, op and r) each time.

The next code block prompts the user for input to the calculator:

inLoop => {
    \in ->a
    \in ->op
    \in ->b
    inLoop
};

Just like with clock, this defines a named pipe, but this time it doesn’t take in any values. Instead it executes three input commands before recursively calling itself, causing the program to loop endlessly, asking for input on each iteration. \in unlatches the in latch, which causes the program to wait for user input, which it returns when the user presses the return key. The ->a sends this value to the latch, a. This is repeated for op and b. Note that the in latch is a node\ and its values are implicitly converted to int and char, as appropriate.

\\op ?? {
    '+': (\a + \b)
    '-': (\a - \b)
    '*': (\a * \b)
    '/': (\a / \b)
       : 0
} ->r;

This final code block executes every time op has received a new value. This is done by destreaming the op latch. Simply unlatching it would have removed the value once, but it would not trigger the following pipe again the next time it receives a value.

The ?? initializes a pattern matching construct – essentially, the value on the pipe (the value destreamed from op) is matched against each of the values specified before the : on each line in the following block and the code on the right is executed for whichever value is matched – or the last one, where the value is omitted, is executed if none match. The code that is executed on a match simply unlatches a and b and applies the appropriate operator to them, depending on what the value of op was. The result of this calculation is then sent into r.

So, we can see how the calculator has received its values, performed its calculations and put the result into r. On its next iteration, the clock would pick up these values and they would be output. At the same time as all of this is happening, the user may be typing the next set of inputs for the calculator. In fact, the input, output/clock and the calculations may all be ocurring in parallel, at the same time.

Advertisement