Introduction to ScalPL and L23 Executive Summary

Introduction to ScalPL and L23
Revision 1.0/Prelim
Copyright © 2005 David DiNucci
All Rights Reserved

Abstract/Executive Summary

Current formal computer and modeling languages lack one or more important properties required for many complex planning and software engineering tasks, properties such as:

The ability to describe a system as it continuously evolves through the development cycle, from high-level design to low-level design to executable code
Object orientation-i.e. ability to build and use abstract data types w/inheritance, and express the relationships between those objects/classes
The ability to express and exploit data parallelism, functional parallelism, and non-deterministic and partial orderings
The ability to describe tasks such that they will be portable and efficient among different sequential, parallel and distributed platforms, including those with high communication latencies
Sufficient formality to permit static analysis for various correctness properties (e.g. liveness, safety, lack of unwanted non-determinism)
Debuggability (i.e. ability to reveal actual behavior in real-world situations)
The ability to leverage existing tools, languages, and techniques where they apply
The ability to mitigate hardware unpredictability by facilitating efficient recovery of lost state
Allowance for production systems to grow and change to accommodate unforeseen needs

A good concurrent software engineering language would require all of these properties, and the lack of such languages is negatively impacting the economics of computing across a wide spectrum, including:

the acceptance of multicore and multithreaded chips
the practicality of increasing chip speed through asynchronous logic
the viability of parallel/cluster and grid computing
the exploitability of web services
the manageability of outsourced software development

The Scalable Planning Language (ScalPL^TM) described here is a high-level visual language which can be used much like the popular Unified Modeling Language (UML) to develop, specify, and model plans and programs, but fills some needs above which UML doesn't. A ScalPL visual plan can evolve all the way from high level design to final executable code, in which case the design remains an integrated part of the code. A ScalPL plan/program is composed of modules with interfaces engineered to selectively and dynamically bind those modules tightly together into a monolithic program or to let them easily decompose into tasks/threads for environments where that is advantageous. When so decomposed, intermodule communication is efficient in all sorts of mult-threaded, mult-core, parallel, distributed, and grid environments, without rewriting the plan/program.

A high-level ScalPL plan, called a strategy, is created from three primary kinds of graphical constructs: Situations, represented by circles, where activities occur; Places, represented by rectangles, where passive content (data or information) resides while waiting to be acted upon; and Roles, represented by lines/arrows between circles and rectangles, specifying the roles which various places (and their contents) will play in various situations. This simple notation, reminiscent of Petri Nets, is expressive enough to diagram how computer modules, human organizations, or any number of other active and passive entities should (or do) interrelate and interact. The underlying communication model between activities (via places) does not favor any particular implementation, being efficient and portable between platforms based on traditional "whiteboard" memory, shared memory, and message-based communication.

Instead of specifying the precise order in which various activities must take place, a ScalPL planner uses colors to specify important local states scattered throughout the plan, and uses color matching to specify the combinations of states which must hold for each activity to be allowed to take place. The states (and therefore colors) transition as the result of each activity, allowing overall action to be visualized as a set of color-based finite state machines. Unlike other methodologies, this approach makes both data flow and control flow statically apparent in a single diagram, and allows the plan to be statically analyzed for reachability, liveness, and safety properties in a piecewise, localized fashion. Instead of being totally sequenced/ordered, activities take place in partial orders, which can be visualized as directed acyclic graphs (DAGs).

The planner can specify implementations for activities within a strategy (high-level plan), each either in the form of another "sub" strategy, facilitating hierarchical decomposition of strategies to any depth, or in the form of a task (low-level ScalPL plan). Tasks can be specified using any language (e.g. computer language or specification language) chosen by the planner to fulfill project requirements. ScalPL does not facilitate nor impede further analysis inside of tasks, but is designed to allow tasks to efficiently access place contents to facilitate I/O, persistence, and communication with other tasks. A task-based activity can be technically regarded as either a special form of function or as an atomic transaction, and since all plans can ultimately be specified down to the task level, all ScalPL plans can be considered as collections of atomic transactions or as an unconventional composition of functions.

Using additional notations and extensions, ScalPL provides for strategies to also serve as atomic transactions (like tasks), and/or to serve as classes from which objects can be instantiated. (In the class/object interpretation, situations are object bindings, activities are object activations, roles are method interfaces, and places are messages and/or variables.) Other notations permit the specification of arrays of places and of delegation of roles, and other mechanisms allow the replication of activities and situations, the dynamic assignment of activities to situations, and the dynamic selection of array elements to play roles within specific situations. Together, these constructs and notations facilitate the construction of plans/programs with dynamic dependences, of classes which inherit interfaces and functionality (activities) from others, and of data parallel plans in which the amount of concurrency scales with the amount of data being acted upon.

To illustrate the power, flexibility, and expressiveness of these constructs, two examples are covered in detail: A parallel sort, closely related to quicksort, and a matrix multiplication. This document does not go into any depth regarding software engineering aspects or theory of the language, but does describe how to use a simple tool, called L23^TM, to enter and edit ScalPL plans.