circuit

library for structured async programming



Documentation

Contents

  • Overview
  • Problem
  • Solution
  • What is circuit
  • How it works
  • Composition of circuits
  • Debugging
  • Error handling
  • Timeouts
  • Running circuits in isolates
  • Spies
  • Profiler
  • Under the hood
  • Correspondence between asynchronous and synchronous constructs
  • Toward better syntax

Overview

Circuit library provides the level of abstraction that simplifies thinking about asynchronous programs and writing asynchronous code.

Features:

  • structured, readable asynchronous code
  • "then" callback hell is gone!
  • automatic parallelization and chaining
  • comprehensive error handling: synchronous and asynchronous errors are handled by the same interface. No error is left behind!
  • built-in support of isolates
  • debugging: all you want to know is printed
  • built-in performance analyzer: no sampling, accurate timing
  • small and intuitive API: just browse through this write-up - and you are ready to go!

Problem

Let's start with a trivial example.

Suppose we have a function that computes x + y asynchronously and returns result via Future, e.g.

Future<int> add(a, b) => new Future(() => a + b);

Our goal is to come up with the implementation that allows evaluation of expressions like

  • (1 + 2) + (3 + 4), or
  • (1 + 2) + (3 + 7) + (5 + 10), or even
  • ((1 + 2) + (3 + 4)) + ((5 + 6) + (7 + 27))

Moreover, we expect the system to run independent computations in parallel, so that (1 + 2) in the example above runs in parallel with (3+4), etc.

Solution

The following program computes 1+2+3+4.

Future<int> add4(a, b, c, d) {
  return new Circuit([
      (@out sum1) => sum1 << add(a, b), 
      (@out sum2) => sum2 << add(c, d), 
      (sum1, sum2, @out result) => result << add(sum1, sum2)
   ]);
}
main() {
   add4(1, 2, 3, 4).then(print); // prints 10
}

What is circuit

Circuit can be viewed as a set of interconnected gates. In the example above, there are 3 gates: first computes a + b, second - c + d, third - adds partial sums.

Gate is a device that reads inputs from input latches, and writes output into output latches.

Each gate defines its input and output latches and a dart function to be called as soon as all inputs are defined.

Latch is a device that accepts Future as input and produces value of this Future as output (when complete). To load future to latch, use "<<" operator.

Each gate gets activated at most once within a single run of circuit (important!).

For outside world, Circuit looks like a Future (Circuit implements Future interface). Circuit completes as soon as "result" latch gets defined.

When circuit completes, it stops propagating latch events to gates (in other words, circuit disintegrates).

Notice that according to the above definitions, gates that can run in parallel, will run in parallel automatically

How it works

Here's annotated version of the above example.

Future<int> add4(a, b, c, d) {
  // array of gate functions is passed as parameter to constructor
  return new Circuit([
      // gate 0: no inputs, output latch: sum1
      (@out sum1) => sum1 << add(a, b),
      // gate 1: no inputs, output latch: sum2 
      (@out sum2) => sum2 << add(c, d), 
      // gate 2: inputs sum1, sum2, coming from completed latches; output latch "result" 
      // "result" is a magic name: when it's complete, circuit completes entire operation.
      (sum1, sum2, @out result) => result << add(sum1, sum2)
   ]);
}

Please note that when "sum1" appears as output parameter (@out sum1), Circuit passes Latch "sum1" to gate function; When it appears as input, Circuit passes already known value of sum1. (That's the basis of entire concept: Latch is a device that "transforms" Future into value).

There's only one operator defined for Latch: "<<" - it loads Future into Latch. Latch can accept normal (non-future) value, too - it converts it to Future automatically, using new Future(value);

Now, we can reconstruct the sequence of events in our 1+2+3+4 circuit:

  • circuit analyzes its own structure and figures out how gates are connected.
  • it figures out that gates 0 and 1 do not depend on any parameters, and can be executed immediately (in fact, they are scheduled as microtasks).
  • circuit invokes gates 1 and 2 in parallel (because their execution conditions are met)
  • each of gates 0, 1 loads Future into latch. Now system cannot do anything until these Latches are complete
  • after latch sum1 completes (suppose it completes first), circuit checks whether this is enough to execute some gate - but it's not! Because gate 2 also needs "sum2" value, which is not known yet
  • after latch sum2 completes, both sum1 and sum2 are known, so circuit executes gate 2.
  • gate 2 loads future into "result" latch. Until the latch fires with result, circuit again has nothing to do.
  • latch "result" completes. Circuit completes operation. Whoever called the circuit, receives result through "then" handler.

NOTE: you may wonder what happens if you misspell some of input/output parameter names in gates. When circuit analyzes its structure, it will (most likely) find this out, and throw an error. Same happens when you have circular dependencies etc. Some extra checks are enabled automatically in checked mode.

Composition of circuits

Because circuit IS a future, it can be used to define "bigger" circuits. E.g. In some other circuit, one of the gates can be written simply as

  new Circuit([
    // ...
    (x, y, z, t, @out w) => w << add4(x, y, z, t),
    // ...
  ]

Important property of modular circuit is that outer circuit knows its structure; it's aware of the fact that latch w is not just a Future, but Circuit!

Where does this knowledge come into play? It enables some features that are otherwise difficult to implement, e.g. stop child circuits when parent circuit fails; print recursive debug trace; collect performance statistics, etc. Read on for details.

Debugging

When you set circuit.debug=1 for a circuit, you get trace of internal events printed (which applies recursively to all children). Let's rewrite our main function as:

main() {
   add4(1, 2, 3, 4)..debug=1..then(print); 
}

You get the following printout

add4> LatchCompleted sum1 = 3
add4> LatchCompleted sum2 = 7
add4> LatchCompleted result = 10
add4> CircuitCompleted result=10

If you sent debug level to 2, you get much more than that: all internal events during circuit lifetime get logged. Internally, tracer is implemented as a variant of "spy" - generic feature of circuit that allows you to set listener to internal events you are interested in. More about it in later sections.

Error handling (asynchronous catch/finally)

When any latch completes with an error, or gate function throws synchronously, error event is generated internally in the circuit. In the above example of "add4", if any such thing occurs, circuit will complete with an error, which, of course, can be caught like any other error returned by Future, e.g.

main() {
   add4(1, 2, 3, 4)..debug=1..then(print).catchError((e, st)=>print(e)); 
}

However, you can intercept error in the circuit itself, and undertake some attempt of recovery (or whatever you like), by adding special "error gate" to the circuit:

  new Circuit([
    // ...
    (error) { print("busted: $error"); }, // prints the error event 
    // ...
  ]

Error gate is allowed to have output parameters, so it can write to latches (some restrictions apply - see below), or it can throw another error. If error gate throws (synchronously), whole circuit completes with an error. If it doesn't throw, execution continues as if nothing had happened (this is no different from regular "catch").

Unlike other gates, error gate can be called many times during a single run of circuit. To find out which latch or gate caused the error, error gate should analyze its input. Error gate is allowed to write to latch that earlier completed with error, thus "correcting" the error. e.g.

(error, @out f) { 
  if (error is LatchErrorEvent && error.latch.name == "f")
     f << 42;
  else
     throw error;
}

In a word, error gate is asynchronous equivalent of "catch" block in normal sequential programs. But what about "finally"? There's another gate for it, it's called "complete":

  new Circuit([
    // ...
    (complete) { /* some cleanup */ },
    // ...
  ]);

"Complete" gate is called upon circuit termination - both on success and failure. Value of "complete" input contains an event, which you can analyze to find more details about the reasons for completion (events will be covered later in this write-up). Both "error" and "complete" gates are implemented as variants of general concept of spies, they just filter only specific types of events.

NOTE: names "error" and "complete" are chosen to be consistent with API of Futures. Otherwise, I would probably use slightly different names :-)

Unlike standard Future API, Circuit allows to receive events (including errors) from circuit that is already completed. These events may come from stray Futures and have no effect on overall result of Circuit. Such events are called "Zombie" events. You can catch Zombie events by setting up a spy (see below). Sometimes it's more convenient to process zombie events internally, in the circuit itself. Special "zombie" gate can be used for this purpose:

  new Circuit([
    // ...
    (zombie) { /* do something about zombie */ },
    // ...
  ]);

Timeouts

Since Circuit implements a Future, it supports standard setTimeout method of Future. However, this method of setting timeout has certain disadvantages (Future returned by "timeout" has independent existence, which is unlikely what you want, especially in the context of Circuit).

Circuit provides a simpler setter timeLimit(Duration d), which behaves more intuitively: it generates internal "cancel" command upon timeout expiration, with all usual consequences (like calling "complete" gate with error event, notifying parent circuit, cancelling child circuits etc).

Running circuits in isolates

Circuit library makes possible to call functions in isolates, with all wiring done automatically by library logic. It allows executing any global function, including those running circuits. Example:

  new Circuit([
    // ...
    (x, y, z, t, @out w) => w << iCall(#add4,[x, y, z, t]),
    // ...
  ]);

The circuit launched in this manner becomes integral part of overall circuit infrastructure (error processing, debugging, profiling etc all work as usual, except that spies across isolate boundaries are not supported for performance reasons).

By default, library creates a single isolate and redirects all iCall requests to it. In the next versions, you will be able to control the number of isolates by setting ICallProxy.numberOfIsolates=n, with automatic load balancing. Note that creating more than 1 isolate if you have just 2 cores might be counterproductive anyway.

By default, entry point of isolate is "boot.dart" - file should reside in the same directory as your main script. Code of boot.dart may look like this:

import 'package:circuit/circuit.dart';
//plus your own imports
main(args, msg) {
   // initialization of your own stuff, and then
   iBoot(msg);
}   

IMPORTANT: you can use iCall facility independently of the rest of the Circuit. Debug flag won't work in Isolates when run in Dartium (will be simply ignored), because "print" from isolates is not (yet?) supported by dart.

Spies

You can set up spies to listen to all internal events. As stated above, many features of circuit are internally implemented using same mechanism. By exploiting spies, we can implement some add-ons like better debugger (e.g. with graphical visualization). To set up a spy, listen to "events" stream of circuit:

add4(1,2,3,4).events.listen((ev)=>/*...*/);

Profiler

Using built-in profiler provided by Circuit, you can get timing data for each circuit, gate and latch. Profiler API:

  • Circuit.profiler.start()
  • Circuit.profiler.stop();
  • Circuit.profiler.statistics

Statistics is returned as a map (print it to find out what is inside). It would be nice to build more user-friendly viewer for profiler data - volunteers are welcome.

NOTE: profiler uses Stopwatch from dart:core. Stopwatch is very slow itself (there's an open bug for this). Until Stopwatch is fixed, profiler may slow down execution. In add4 benchmarks, the slowdown is 30+%. In real applications using IO, the effect won't be that dramatic.

Under the hood

Circuit uses reflection to find the names of parameters of each gate function, creates corresponding latches (internally) and uses internal event loop to orchestrate the whole operation. Reflection takes time, so the results of reflection are cached. Circuit name serves as a key to this cache; library derives the name of circuit from context (owner declaration); it should be globally unique among all circuits. (In case of conflicts, user should specify name explicitly, via second parameter of Circuit constructor). Due to caching and other devices, performance of circuit (for all practical purposes) is close to that of "raw" operations over Futures. Memory footprint of the cache is very low. For now, library works in VM and dartium only. To support javascript, Circuit will eventually provide a transformer to make all necessary data available to javascript.

Correspondence between asynchronous and synchronous constructs

One of the goals of the library is to provide intuitive asynchronous equivalent to "normal" sequential programming style. Here is the map of correspondence:

  • Sequence op1; op2, ... opN : circuit with N gates
  • function: circuit
  • return from function: set "result" output
  • loop: use stream operations (asyncMap, asyncFold etc)
  • if/else: use gate with two outputs, e.g @out x, @out y that sets either output x OR output y, depending on condition
  • composition: circuits used as sub-circuits in a larger circuit (as a variant, you can write recursive circuits).
  • catch: use "error" gate
  • throw: just use "throw" in synchronous part of gate. On top of that, if any latched future completes with error, it's equivalent to "throw".
  • finally: use "complete" gate

Toward better syntax

The argument can be made that the following syntax could be more readable:

Future<int> add4(a, b, c, d) {
  (@out sum1) => sum1 << add(a, b);
  (@out sum2) => sum2 << add(c, d); 
  (sum1, sum2, @out result) => result << add(sum1, sum2);
  return new Circuit.fromContext();
}

Implementing this syntax is currently possible, but difficult (requires special transformer). Need to discuss.