C++11 Variadic template factory member function fun! Building a FBP directed graph class.

photopin cc

Better by variadic design?

TL;DR The libfbp library needs a directed graph container for the ensemble of communicating components that makes FBP programming as easy and error free as possible. Achieving these goals by giving the directed graph class the responsibilities for creation, storage, lifetime and execution of its components and connections poses the challenge of how to implement generic factory methods that allow the creation of a zoo of unknowable components and connections?  C++11/14 variadic template metaprogramming to the rescue!

Mathematical Semantics for FBP - Graph Theory

photopin cc

In search of descriptive and inferential semantics for FBP.

TL;DR In trying to develop mathematical semantics for FBP, in order to reason about FBP programs and design experiments to test hypotheses, it is proposed that Graph Theory (GT) can describe the properties and behaviours of an FBP program. Which is nice.

The value of defining mathematically based compliance design criteria for libfbp is that such a definition could serve as a standard. Such a precise specification for any FBP implementation informs the programmer using it that they can rely on certain axiomatic behaviours and, being a modular programming paradigm, be assured of the reliable conjunction of FBP modules from widely differing sources. 

Beyond its immediate utility then, developing mathematical semantics for libfbp/FBP at an early stage will hopefully forestall problems with the quality of libfbp programs—as Brookes states[1] 

“Clearly, no program can be more reliable than the implementation of the language in which it is expressed for input to a computer.”

The benefits to FBP go beyond quality issues and extend to the potential for the formal proof of correctness for a libfbp program. Given that each libfbp component is in, and as of, itself an isolated Von-Neumann machine, then Hoare-style logics for sequential languages based on state-transformation semantics are particularly suited to the way a component functions. 

In this way the modular approach to building a FBP program provides islands of correctness communicating via connections. Subsequently, and given proof of conformity with the mathematical model, FBP developers have powerful mathematical tools at their disposal to formally prove correctness. 

The question then arises as to what mathematical semantics are most appropriate for describing libfbp program structure or rather its form?

A CSP approach to FBP Components: #3 RUN the livelock component #4 CHAOS the unpredictable component

Just because you're doing something doesn't mean everything is going well!

TL;DR The CSP process RUN represents livelock[1] and the entirely unpredictable mix of livelock and/or deadlock[2] is represented by the CHAOS process. Despite the difficulty in detecting these 2 worse case scenarios they are embodied as libfbp components.

The distributed deadlocked component that is failing to progress can be detected[2] by limiting the amount of time that a component will tolerate failing to progress. A much harder situation detect is one of livelock where a component will engage in any Information Package (IP) without making any meaningful progress. Harder still to detect is that chaotic component which can either engage in any IP or refuse to engage in any IP - it is in a superposition of livelock and deadlock!

A CSP approach to FBP Components: #2 SKIP success component.

Successful termination.

TL;DR  The next primitive CSP process to emulate in libfbp is SKIP for successful termination.

Given that the theory of Communicating Sequential Processes (CSP) is not a programming language but rather a mathematical notation for process algebra, nevertheless, there are a number of concurrent programming languages based on CSP; for example occam and Ada .

A CSP approach to FBP Components: #1 STOP the broken component.

Handling the broken component.

TL;DR FBP originates from the unashamedly pragmatic narrative tradition of software development and, consequently, lacks any mathematical semantics. The Theory of CSP is proposed not only as mathematical semantics for FBP but also a basis for its design and implementation. (Which I discuss at length in my Masters Thesis.)

As previously discussed here, it is clear that FBP falls into the Message Passing Model (MPM) of concurrency models. Further, message passing between isolated processes is a rudimentary description of not only FBP but also of Sir Tony Hoare's Communicating Sequential Processes (CSP)[1].

libfbp component interface

One Interface to rule them all, One Interface to find them,
One Interface to bring them all and in the Scheduler bind them
In the Land of Execution Models where the Programs lie.

TL;DR A PXM API for the libfbp PPM Components whereby; the underlying execution service can view each Component as an enqueuer of message requests[1] composed of C++11 function<void()> types behaving as functors[2]. 

The primary strategic goal here is that the libfbp implementation of Flow-Based Programming (FBP) as a Parallel Programming Model (PPM), though the FBP paradigm is a lot more more than simply a PPM, should be agnostic to its underlying Program eXecution Model (PXM) but must, never-the-less, provide an Application Programming Interface (API) that remains versatile in its implementation. 

Part (3/3): A general purpose thread-safe internally synchronized message queue.

Proxies: Who's wearing the trousers? 

TL;DR I want to be able to do this:

producer_active_object(enqueuer_proxy(concurrent_queue));
consumer_active_object(dequeuer_proxy(concurrent_queue));

Today' reference will mostly be:

The proxy pattern[1] provides restricted or modified access to hidden or protected resources. There are a few subsets of proxies:

• remote proxy
• virtual proxy
• protection proxy
• smart reference

The kind of proxy that the message_queue type needs is combination of the last 2 that offers:

• Access to the head and tail of the message queue via its various private enqueue and dequeue member functions.
• Counting the number of references to the message queue and closing it down when either there are no more interested consumer(s) or the producer(s) have finished producing. 

Okay so the design choices are to either:

1. Have a zoo of some_message_queue types each with member functions for generating their own proxies that use the extremely useful friendship C++ language feature[2]
2. Select a specific some_message_queue policy from the zoo and wrap it in a generic message_queue type which dishes out the head and tail proxies.

Well at least there is no goat in this problem so in true Monty Hall style 

"Let's see what's behind door number 2..." 

Part (1/3): A general purpose thread-safe internally synchronized message queue.

"The English can form a queue of 1"

Flow-Based Programming (FBP) [1], Communicating Sequential Processes (CSP) [2] and Active Objects (AO) [3] rely on message passing between otherwise environmentally opaque conccurent components. 

There are lots of ways of providing this communication[4], be that synchronous or asynchronous, but one of the most frequently used is that of a message queue.

The principle reference for my development of the concurrent queues is the, totally excellent, The Art of Multiprocessor Programming (Herlihy & Shavit 2008)

Part (1/3): I'm a Lumberjack and I'm okay.

"Logging is a critical technique for troubleshooting and maintaining software systems."[1]

I would also add that logging is a critical technique for recording a variety of metrics when conducting software analysis and experimentation.

Therefore, I need a thread-safe, asynchronous and fast data serializing framework-not only in order to develop libfbp but also to experiment with it.

There are some great libraries out there already[2] but where's the fun and learning in that?