Reactive programming

This tutorial is a walk through the most basic elements of a Mote Runner on-mote application.

Wireless sensors and embedded programming are inherently all about reacting to external events in the most resource-efficient way. That is, embedded applications do not work in a self-directed fashion but rather are notified whenever an event occurs that is of interest to the application. In response, the application then performs some (typically) short burst of processing, possibly changing its state, and possibly triggering operations that eventually may result in further events. So, conceptually there is a finite state machine underlying the code whose transitions are triggered by events.

In Mote Runner, applications therefore consist simply of a set of classes that derive from or register with certain system classes and services as required. The application then merely waits until it is invoked by the system to react to an event for which it is registered. Typical examples are communication, sensor, or timer events. That is, an application is passive until triggered; there is no threading. For the initial “wiring” of an application, the system invokes the static constructors of all the application classes during installation of that application. This allows the application to allocate any objects or register with any system services.

N-Queens

“The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen’s moves. The queens must be placed in such a way that no two queens would be able to attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard, where solutions exist only for n = 1 or n ≥ 4.” [Wikipedia] So, how many distinct solutions exist if two solutions that differ only by symmetry operations (rotations and reflections) of the board are considered identical? This is the problem we want our mote to answer.

A simple C# application that counts the number of distinct solutions is shown below. The static constructor is invoked at installation time, and this constructor then allocates the Queens object and iterates through all distinct solutions by repeatedly invoking the compute function until all solutions have been found.

   
using com.ibm.saguaro.system;

namespace com.ibm.moterunner.tutorial.nqueens {

    public class Queens {
	const int N = 8;	// number of queens
	int[] B, L, R, V;
	int[] S;


	static Queens () {
	    Queens Q = new Queens();

	    int n, max = 0;
	    
	    Q.init();
	    while ((n = Q.compute()) > 0)
		max = n;
	
	    // max is the number of distinct solutions
	}


	private Queens () {
	    B = new int[N];
	    L = new int[N];
	    R = new int[N];
	    V = new int[N];
	    S = new int[3];
	    
	    init();
	}


	private void init () {
	    B[0] =
	    L[0] =
	    R[0] =
	    V[0] =
	    S[0] =
	    S[1] = 0;		// a, i
	    S[2] = (N-1);	// j
	}


	private int compute () {
	    int p, j, i, vv, lv, rv;
	    int[] b;
	    
	    b = B;
	    vv = (int)V[(i = S[1])]; lv = (int)L[i]; rv = (int)R[i];

	    for (p = (int)(1 << (j = S[2]));;) {
		if ( ((p&vv) == 0) && ((p&rv) == 0) && ((p&lv) == 0) ) {
		    b[i] = (int)j;
		    
		    if (i != N-1) {
			V[++i] = (int)(vv = (int)       (p|vv));
			R[i]   = (int)(rv = (int)((uint)(p|rv)>>1));
			L[i]   = (int)(lv = (int)      ((p|lv)<<1));
			j = (int)(N-1);
			p = (int)(1 << (N-1));
			continue;
		    }
		    
		    if (b[N-2] > j) {
			S[1] = (int)(N-2);
			S[2] = j;
		    } else {
			for (S[1] = (int)(N-3);
			     ((S[2] = (int)(b[S[1]] - 1)) < 0);
			     S[1]--);
		    }
		    
		    return (int)(++S[0]);
		}
		
		if (j != 0) {
		    p = (int)((uint)p >> 1);
		    j--;
		    continue;
		}
		
		do {
		    if (i-- == 0) {
			init();
			return 0;
		    }
		} while ((j = (int)(b[i] - 1)) < 0);
		
		p = (int)(1 << j);
		vv = V[i]; lv = L[i]; rv = R[i];
	    }
	}	
    }
}
			

Communication

When installed on a mote, however, the counting should be started by some third party and the number of distinct solutions found should be reported back to that party in response. For such basic communication, Mote Runner provides the SystemEvent callback service. Once registered, the system invokes an application-defined callback function for various events, especially for incoming messages. These messages are effectively relayed to the application by the on-mote mote manager and, as such, are delivered by an event of type SYSEV_MESSAGE_RELAY. The application, in turn, can answer the message sender by reusing the message buffer and returning the payload length from its callback function.

For the N-Queens application we change the static constructor to register a callback function to be triggered for system events. This callback function, which is invoked by external messages sent to the application, counts the number of distinct solutions and eventually fills the result into the pdu buffer to be sent automatically by the system to the originator of the request.

	static Queens () {
	    Queens Q = new Queens();
	    SystemEvent evt = new SystemEvent(Q.callback);
	    Assembly.setSystemEventCallback(evt);
	}

	...
	
	public int callback (uint type, PDU pdu) {
	    if (type != Assembly.SYSEV_MESSAGE_RELAY)
		return -1; // no reply

	    int n, max = 0;
	    
	    init();
	    while ((n = compute()) > 0)
		max = n;
	    
	    Util.set16be(pdu.buffer, 0, (uint)max);
	    return 2; // number of bytes to send back
	}
		      	

Please note that in Mote Runner, the int and long data types are automatically mapped to 16 bits and 32 bits, respectively, instead of the usual 32 bits and 64 bits, respectively.