ScalPL 1.1: A few enhancements to the book

[This post was slightly edited on 1/30/14 to correct errors in the examples in part 4.]

In devising any language, there are trade-offs between utility, precision, consistency, and implementability.  Scalable Planning Language (ScalPL) as defined in the book "Scalable Planning" (the version which I'll here refer to as ScalPL 1.0) is no different, and when there have been questions, I've decided to err on the conservative side:  If I couldn't convince myself that a construct was useful, precise, and fairly efficiently implementable, I typically ruled against adding it, or I have added a rule preventing its use in problematic ways.  In some cases, I have overdone it, and set out here to correct some of those, but I make few apologies:  It's easier to add constructs (or constructions) over time than to first say they are available in the language and remove them after people begin to rely on them.

Here are four constructs that I have now decided should be part of ScalPL, even though the book either does not describe them, or explicitly rules against them.  I'll heretofore call the version of ScalPL with these included ScalPL 1.1.  If you are not already intimately familiar with ScalPL 1.0 (e.g. haven't read the book), these will mean little to you (since they haven't been introduced in such detail here on the blog yet), and other posts on this blog will continue to be self-explanatory.  Some of these have been long considered (since before the book was written), and left out primarily because I didn't realize how useful or implementable they might be.  Others were simply poorly considered.  Most of them deal with resource arrays.

The four new constructs are: (1) Resource arrays that allow for non-integer indices, (2) bindall role bindings for resource arrays permitted for actons/tactics (formerly outlawed), (3) a more useful form of "bindany" role binding for resource arrays (to provide access to the index being bound to), and (4) a new form of role binding that is unpredictable (though it would normally be considered predictable).

1. New Rule:  Resource arrays allow any type for indices

In section 13.1.1 of the book (page 230), when introducing arrays, it says (in the second sentence):

Each element is uniquely identified/addressed within the array by an index consisting of a tuple (i.e. fixed-length sequence) of integers.

Since an index is only an addressing scheme to uniquely identify elements, and there is no constraint on the number of elements in an array or how those elements are to be stored relative to one another, the constraint that indices consist only of integers is not justified, and any number of languages (even perl) have demonstrated the productive use of non-integer indices.  Since any integer is legal in ScalPL, a work-around (to use other kinds of indices) simply requires finding a function to map the indices you want to use onto the set of integers (that is, a bijection).  For example, if you want to allow character strings, you could simply use the character values in some code (e.g. ASCII) concatenated together.

Since ScalPL must already permit efficient storage of sparse arrays, it must already manage the storage of non-sequentially-indexed elements, so there is really no significant benefit to limiting indices to be integers.  In ScalPL 1.1, any type of indices will be allowed.

2. New rule:  Bindall bindings should be permitted for some actons (tactics)

In section 13.1.2 (page 232), I say that by default, binding a role of a context to an array (called a "bindall" binding) binds to all (potentially infinity) elements of that array.  Then in the second paragraph, first line, I say:

Because of this, the activity within the context in this (default, infinite) case cannot be an acton, because that would require infinitely elements to become ready before the acton could activate, and the activation would need to result in issuing a transition to all infinity of them, taking infinite time (in the general case).

I have decided that there are certainly cases where working around this constraint would be much more difficult than just removing it.  Specifically, if the binding has nodata (i.e. neither observe nor replace) permission, then such a binding would only require that the Director check and (if necessary) transition all of the control states of all the elements at once.  Even restricting such tactic/acton bindall bindings to activate on, and transition to, only the initial control state would be sufficient to provide important functionality -- e.g. to allow an acton (perhaps $null) to activate only if an array is "empty", in the sense that all of its control states have the initial control state.  This could be accomplished without this extension by having the planner explicitly maintain a count, in a separate resource, of the number of elements having or not having a particular control state, and manually update it each time the control state of an element changes.  But since that count is already effectively maintained in the internal implementation, this is essentially wasted and confusing effort.

3. New Rule:  A new form of binding, similar to bindany

In 13.1.3 (and Figure 12.3(b)), I introduce the bindany binding, which uses a ? prefix and allows binding to any element of the array having the control state specified by its access dot.  It has at least two shortcomings: That the activity within the context cannot detect the index of the element which is eventually bound to the role; and that constraints on indices cannot be made between different roles, such as that those roles must all be bound to the same index.  In the past, I've considered addressing the first of these by offering a special function within tactics/actons which would retrieve the index to which the role which was bound, but making such information about the binding (including the possibility that the role might not be bound to an array at all) available to the activity would violate the important concept that an activity's behavior is a function of only its observable content states.

It turns out that both shortcomings can be fairly easily addressed with the notation shown here, which allows a "free" role (bound to nothing, _x and y here) to be used as the primary for one or more reduction binding modifiers (as defined in 13.2 and 13.2.1).  If (and only if) there is some content state for this role (i.e. an index) such that the reductions result in secondary roles bound to ready array elements (i.e. with control state matching their access dot), then the role will be considered ready, and that content state will be observed on the role.  As described in 1, above, the content may be of type other than integer. This is somewhat similar to the "special function" approach described in the previous paragraph, but because the index information is delivered to the activity on a role (like all other legitimate information to an activity), it breaks no rules and is applicable to both strategies and tactics.  Note that _x in the example is anonymous, so is not accessible by the activity in the context, but it still ensures that the first index of resource array a equals the second index of array b, as per the associated reduction binding modifiers.

4. New Rule:  Suppressed predictability

Throughout the book, the concept of predictability is discussed.  Specifically, a role binding is considered predictable if and only if it has no replace permission (i.e. it either has nodata or observe permission only) and all of the transition bindings are to a single control state (i.e. all of the transition dots have the same color/pattern).  The reasoning is that, when a plan accesses a resource through a predictable role binding, its almost obvious what the new content and control state of the resource will be after the access:  i.e. the same (unchanged) content state, and the control state associated with the transition binding(s).  Seemingly, the only reason the Director (or human observer) can't just predict these in advance (i.e. the reason for the "almost" above) is that the activity could fail to issue any transition (sometimes called issuing the bottom transition), leaving the resource unavailable altogether.  So ScalPL actually defines that a transition will eventually be issued for any predictable role.  This permits some very important and useful optimizations, often performed by the Director, as detailed in Chapter 4, by pretending that the transition has been issued even before it has.  These optimizations include efficient sharing and buffering, even with no effort expended by the planner.

This is especially useful for atomic activities (e.g. actons, resulting from activating tactics). The problem is, there are other cases (using strategies) when it is actually useful for the optimization not to be done, for it not to be assumed that the transition will always be issued, or at least, not at just any old time.  A common reason for wanting to not assume this is that the relative timing of that transition relative to others issued by the same (non-atomic) activity is important -- such as that the transition should only occur after other transitions (on other roles) have been issued from that activity.  Future editions of the book will go into more depth on this issue.

There are already "work-around" ways to explicitly suppress these predictable optimizations in these troublesome cases -- making the role binding "unpredictable" -- such as by simply changing nodata or observe permissions on those role bindings to replace (observe and update) permission, or by adding extra unused transitions to roles of a plan, which can be bound to unused control states in their parents.  But these are obtuse, in effect fooling not only the Director about what is actually happening, but human reviewers as well.


So I hereby propose some new "unpredictable" syntax which simply declares that a role binding which otherwise looks predictable should nonetheless not be predicted.  A question mark (?) is especially good for suggesting unpredictability, but is already used as a role name prefix for "bindany" bindings.  So for unpredictability, I will suggest putting a question mark next to the transition binding itself, within the resource rectangle, as show here (left top).  If colors are used to signify transition bindings, a colored question mark could potentially be used in place of the transition binding dot (as on the left bottom).

It also seems useful to declare within a strategy that any parent which binds this strategy (within a context) should recognize that certain roles are intended to be unpredictable, and that those roles should therefore be bound with unpredictable bindings.  I will suggest two different potential syntaxes:  Either prefixing the formal resource name itself with a question mark, or including a question mark in the transition box of the formal resource, as shown here (which represents a possible xstrategy for the context in the previous example).  Since this construct is sensibly only permitted for formal resources with a single dot in their transition box, the dot there could (again) itself be replaced with a colored question mark (if colors are used).

I still have some reservations about adding this construction, because I fear it may be over-used.  Specifically, even a predictable role for a strategy cannot be predicted to perform a transition before that role (i.e. its formal resource) is even accessed by an activity within the strategy.  So a declaration of unpredictability is really only needed when a formal resource within the strategy must be accessed early (e.g. observed), but the transition from that resource should be delayed until later (like a in the example, which may be accessed several times by multiple before finally completed by wrapup).

Conclusion

Again, these are described primarily for those who have read the book.  The use of many of these will described (hopefully shortly) in upcoming blog posts.