Tuesday, September 11, 2012

Scalable Planning Language (ScalPL) = F-Nets + ...

I recently described F-Nets, as well as some reasons I preferred that model to serve as the basis for concurrent/parallel programming.  But I obviously didn't think it was sufficient on its own, or I would have stopped there. So, just what is ScalPL, and how is it different (superior to) F-Nets for programming?  It starts with F-Nets, and adds...

Instead of activating just tactics within a context, in ScalPL an entire F-Net fragment (i.e. a network of tactics and resources) called a strategy can activate within a context.  In other words, a strategy combines other constructs into a single entity/module, and ScalPL defines how the activity (resulting from its activation) interfaces to its context's surroundings (via the role bindings on that context). Among other things, this means that we can create a module (strategy) to behave any way we like with regards to patterns of accepting inputs or producing outputs, or maintaining internal state, or acting (non)atomically or (non)deterministically, rather than being tied to only atomic deterministic modules (i.e. tactics).

First Class Modules
Together, tactics and strategies are called plans.  And since plans (before they are activated) are just a form of static data/information, they can be stored on resources.  Instead of labeling a context with the plan that is to be activated within it, a strategy can be asked to activate the plan that is present on one of its resources.

Clean Termination, Atomic Activation
Since strategies can activate, they should also be able to terminate -- so that they can be reactivated (cleanly) or something else can activate in the same context.  Also, it should be easy to control the activation of a strategy the same way as for a tactic, and in particular, to make it easy to activate a strategy atomically.  ScalPL addresses both of these in simple, logical ways.

Object Orientation (Class Based)
Since a strategy is a first-class entity encapsulating both behavior (i.e. contexts containing plans) and state (i.e. resources), and having a well-defined interface, it is almost an object.  However, to truly be an object, it needs to be able to carry its state with it as it is activated in different contexts, so ScalPL introduces instantiation levels (and instantiation) for resources.  With these, and a few methodologies to deal with them wisely, ScalPL becomes an object-oriented language, with meta-classes.

Inherent in the F-Net model is an assumption that each context is statically bound to a fixed set of resources, and while that may be theoretically sufficient, it doesn't  practically.  At the same time, allowing the role bindings to be determined after activation re-introduces all sorts of complications (with deadlock, etc.) that the F-Nets execution model cleared up.  ScalPL bridges the gap on this by introducing array resources (i.e. sets of resources, each an element of the array, addressable via indices) and a method of specifying which resource elements to which a context is to bind as part of the activation itself.

Data Concurrency/Parallelism
Having arrays isn't enough for data concurrency:  For that, one needs a way to scale the amount of concurrency with the number of elements being processed.  ScalPL provides ways to duplicate/clone contexts, and how many plans they should activate collectively (e.g. one among them all, or one each).

Dynamic Resource Allocation
Since there is no specified spatial relationship between different elements of a resource array (since they could even end up on completely different processors), and the initial control and content state of each resource element is known before/until it is accessed, resource arrays can be (and are, by default) infinite in size, and only those elements actually accessed (and modified) are actually tracked.  This means that elements can be allocated only as they accessed (i.e. bound to).

Each of these properties conforms roughly to chapters in the Scalable Planning book.

Of course, many sequential OO programming languages have the above constructs and/or properties, and a typical approach to constructing a concurrent language is to start there and augment it with concurrent constructs.  That doesn't usually work very well.  Here, we've instead started with a simple computational model (F-Nets) that properly handles the concurrency issues, and have then built it into a complete language.

No comments: