Tuesday, August 24, 2010

No exceptions in ParaSail, but exitable multi-thread constructs

We have been mulling over the idea of exceptions in ParaSail, and have pretty firmly concluded that they aren't worth the trouble.  In a highly parallel language, with lots of threads, exception propagation across threads becomes a significant issue, and that is a nasty area in general.  Also, exceptions can introduce many additional paths into a program, making thorough testing that much harder.  And the whole business of declaring what exceptions might be propagated, and then deciding what to do if some other exception is propagated can create numerous maintenance headaches.

There is a feature in ParaSail as currently designed which provides some of the same capabilities of exceptions, but is particularly suited to parallel programming.  This is the "exit with" statement, which allows a construct to be exited with one or more values specified as results, and at the same time terminating any other threads currently executing within the construct.  For example, here is a loop implementing a parallel search of a tree with the first thread finding the desired node exiting and killing off all of the other threads as part of the "exit ... with" statement:

const Result : optional Tree_Id;
for T => Root then T.Left || T.Right
  while T not null concurrent loop
    if T.Value == Desired_Value then
        // Found desired node, exit with its identifier
        exit loop with (Result => T.Id);
    end if;
end loop with (Result => null);

This declares a Result object of type Tree_Id.  It then walks the tree in parallel, starting at Root and continuing with T.Left and T.Right concurrently.  It continues until it reaches "null" on each branch, or some node is found with its Value component matching the Desired_Value.  The value of Identifier at the end indicates the identifier of the node having the desired Value, or null to indicate that no node was found.  The presence of optional in the declaration for Result indicates that its value might be null.

Supporting this kind of intentional "race" seems important in parallel programming, as many problems are amenable to a divide and conquer approach, but it is important that as soon as a solution is found, no further time is wasted searching other parts of the solution space.  The "end ... with" phrase allows the specification of one or more results if the construct ends normally, as opposed to via an "exit ... with" (in this case, ending normally means all threads reach a null branch in the walk of the tree without finding the desired node).  Effectively the "exit ... with" skips over the "end ... with" phrase.

So how does this all relate to exceptions?  Well given the "exit ... with" capability, one can establish two or more threads, one which monitors for a failure condition, and the others which do the needed computation.  The thread monitoring for a failure condition performs an "exit ... with" if it detects a failure, with the result indicating the nature of the failure, and as a side-effect killing off any remaining computation threads.  If the normal computation succeeds, then an "exit ... with" giving the final result will kill off the monitoring thread.  Note that the "exit ... with" statements must occur textually within the construct being exited, so it is visible whether such a premature exit can occur, unlike an exception which can arise deep within a call tree and be propagated out many levels.

As an example of the kind of failure condition which might be amenable to this kind of monitoring, imagine a resource manager object, which provides up to some fixed maximum of some kind of resource (e.g. storage) to code within a block.  This resource manager (which is presumably of a concurrent type) could be passed down to operations called within the block for their use.  Meanwhile, a separate monitoring thread would be created immediately within the block which would call an operation on the resource manager which would suspend the thread until the resource runs out, at which point it would be awakened with an appropriate indication of the resource exhaustion, and any other information that might be helpful in later diagnosis.  On return from this Wait_For_Exhaustion operation, the monitoring thread would do an "exit block with (Result => Failure, ...)" or equivalent, to indicate that the computation required more resources than were provided.  The code following the block would then be able to take appropriate action.

Monday, August 23, 2010

Initial implementation model for ParaSail types

ParaSail supports object-oriented programming, and as such there needs to be some kind of run-time representation for types to support dispatching calls (aka virtual function calls, method calls, etc.).  Most "normal" objects need no run-time type information associated with them, but an object or parameter of a polymorphic type (such as "Int_Expr+") needs some run-time type information to support dispatching calls on its operations.  In addition, each operation of an interface generally needs an implicit parameter identifying its "enclosing" type, to gain access to the module parameters, given that every module is effectively a "generic" module.

Because ParaSail supports multiple inheritance of interfaces (including ad hoc interface matching -- see blog entry on that topic), a simple table of operations for each type with a compile-time-known slot-number in the table doesn't work as it would if ParaSail only supported single inheritance.  Instead we adopt the notion of a "type view" which consists of a pointer to the overall table of operations of the type, as well as an "slot-number mapping" to provide the particular "view" of the type.  The slot-number mapping is a simple vector of operation slot numbers for the operation table, indexed by the interface slot number of the particular interface through which the type is being "viewed."  For example, presume we have an interface "Assignable" with only two operations, say, Assign and Copy, with interface slot numbers one and two.  Given some type with many operations, where the operation slot numbers of 21 and 33 are for Assign and Copy respectively, then the Assignable "view" of the type would have a slot-number mapping of:

      [1 => 21, 2 => 33]

The actual operation table would be a vector of pairs, each pair being a reference to the type from which the code for the operation was inherited, and the reference to the actual code for the operation.  Hence, the operation table for Type_C could be imagined as something like:

     [1 => (Type_A, Op1_Code),
      2 => (Type_B, Op2_Code),
      ...,
     21 => (Type_A, Assign_Code),
     ...,
     33 => (Type_C, Copy_Code),
     ...]

Here we assume that the code for Op1 and Assign originated with Type_A, the code for Op2 originated with Type_B, and the code for Copy originated with Type_C.

In addition to an operation table, a type would have a table of module actuals, one for each module formal parameter.  Module actuals could be themselves "type views," operations, or (constant) objects.

If an interface declared externally-visible components (const or var), these would be represented for uniformity by operations that take a reference to an object of the interface's type and return a reference to the component.  This allows multiple inheritance of such (at least conceptual) components from one or more implemented interfaces, though the actual offset of the components within the object (or whether they are true components in the case of consts) might very well differ from the corresponding components of the interface.

When an operation is called, in addition to its explicit parameters, it would be passed a reference to the type from which it originated.  This would allow it to gain access to the other operations of its module, as well as to the module actuals.  Because ParaSail allows the type from which a type is extended to be overridden (see blog entry on ParaSail extension, inheritance, and polymorphism), the operation table may vary depending on which type is the base for extension (since the type from which a given operation originates could vary).  Hence an operation doesn't necessarily "know" where one of the other operations of its module originates (presuming the operation is inherited rather than redefined within the module's class directly).  

Because each type has its own operation table with pointers to the code for each operation, it is possible for some of the operations to be specially compiled for that type, rather than simply reusing the "generic" code generated when the module was first compiled.  This allows the code to incorporate information about the module actuals (as an optimization), rather than having to use the information only at run-time which is what the "generic" code would do.  Hence, in the example above, the Copy_Code for Type_C might incorporate directly information about the module actuals or the operation table for Type_C, rather than having to index into the table of module actuals or into the operation table at run-time.

Other implementation models are of course possible, but this one seems to have the advantage of uniformity and flexibility, with constant-time run-time performance for making a dispatching call.

Ad hoc interface matching in ParaSail

When a module is instantiated in ParaSail to form a type, actual parameters must be specified for each module formal parameter.  When the module formal is itself a type, the module actual must be a type that matches the formal appropriately.   For example, given:

interface Set<Element_Type is Assignable<>> is
    function Union(Left, Right : Set) -> Set;
    function Unit_Set(Elem : Element_Type) -> Set;
   ...
end interface Set;

we will want to be able to write:

    type My_Int_Set is Set<My_Integer_Type>;

Now the question is whether My_Integer_Type must be based on an interface that is explicitly indicated as extending or implementing Assignable, or should we simply require that My_Integer_Type has all of the operations expected of a type based on Assignable.  In other words, does an actual type match a formal type only if it extends or implements the specified interface, or is ad hoc matching permitted, where at the point of instantiation a check is made that all of the required operations are present?  A similar question would come up when converting an object of a particular type to a polymorphic type (such as Assignable+).

Our initial instincts were to require that the actual type (or the type being converted) explicitly extend or implement the formal type (or the target type).  However, this will tend to cause a proliferation of interfaces being added to the list of implements for any given module, such as Assignable or Comparable or Numeric or ..., and still the actual subset of operations of interest might not be mentioned explicitly. 

Given the above concern, we now favor allowing ad hoc matching requirements for matching of module actuals to module formals, and when converting from a normal type to a polymorphic type.  There are some potential problems during maintenance if the operations of an interface change, but those problems exist anyway, since any code that makes calls on individual operations defined in an interface may suffer maintenance issues when operations change.  Note, however, that adding operations to the actual type, or removing them from the formal type, don't create maintenance issues.

In general, there are many fewer places where modules are instantiated, or conversions to polymorphic types occur, than there are normal calls on operations, and defining and using (presumably abstract) interfaces such as Assignable or Comparable as module formals, if they capture exactly what operations of interest are needed by the module, could reduce rather than increase maintenance problems when trying to decide whether to change an existing operation of some interface.

So the answer to the above question about instantiating Set with My_Integer_Type is now answered as follows:  My_Integer_Type must provide the operations defined in the interface Assignable, but it need not directly or indirectly extend or implement Assignable.  This generally means that the list of interfaces specified in the implements list is there primarily for documentation, and for imposing a linkage such that if additional operations are added to the implemented interface, the need to define the operations is known at the point of module definition, rather than being deferred until some point of use.  This also implies that when ad hoc matching is used, there is a presumption that the module formal (or target type) is very stable and new operations are not expected to be added to it.  A type like Assignable<> certainly qualifies. 

Eliminating the need for the Visitor Pattern in ParaSail

The "Visitor" pattern is one of the more widely recognized patterns identified by the "Gang of Four" in Design Patterns: Elements of Reusable Object-Oriented Software.  Object-oriented programming makes it relatively painless to add more types into a type hierarchy, but it makes it relatively painful to add more operations to an existing type hierarchy.  The Visitor pattern is intended to allow adding more operations without doing major surgery on the original type hierarchy, but it requires the use of a visitor object, plus an additional operation, often called accept, on each type, which turns around and calls a visit operation on the visitor object that is unique to that particular type in the hierarchy.

Object-oriented frameworks like that of Common Lisp Object System effectively eliminate the need for the visitor pattern by allowing the addition of dispatching operations (aka virtual functions, methods, etc.) after the type hierarchy has been established, with CLOS in particular allowing additional methods to be added to preexisting generic functions.

In ParaSail, we propose to support the definition of additional dispatching operations to be used with polymorphic types in a somewhat more modular way.  The basic idea is that an interface hierarchy can be extended horizontally in addition to vertically.  By this we mean that an additional named bundle of operations may be specified for the root interface of an interface hierarchy, and then this same named bundle may be defined for each descendant of this root interface, such that operations from this new bundle may be "dispatched" to when operating on polymorphic objects, just as can be the operations of the original root interface. 

Here is an example based on a simple interface hierarchy used to represent numeric expressions:

interface Expr <Value_Type is Integer<>> is
    function Evaluate(E : Expr) -> Value_Type;
end interface Expr;

interface Binary extends Expr is
    type Binary_Op_Enum is Enum<[#add, #sub, #mul, #div, ...]>;
    function Create(Op : Binary_Op_Enum; Left, Right : Expr+) -> Binary;
    function Evaluate(B : Binary) -> Value_Type;
end interface Binary;

interface Unary extends Expr is
    type Unary_Op_Enum is Enum <[#plus, #minus, #not, #abs, ...]>;
    function Create(Op : Unary_Op_Enum; Operand : Expr+) -> Unary;
    function Evaluate(U : Unary) -> Value_Type;
end interface Unary;

interface Leaf extends Expr is
    function Create(Value : Value_Type) -> Leaf;
    function Evaluate(L : Leaf) -> Value_Type;
end interface Leaf;

    ...

 interface Calculator<Int_Expr is Expr<>> is
    ...
    procedure Print_Value(Str : Output_Stream; E : Int_Expr+) is
        // E is of the polymorphic type Int_Expr+ 
        // so calls on its operations will dispatch.
        const Result := Evaluate(E);   // dispatching call
        Print(Str, Result);
    end procedure Print_Value;
end interface Calculator;

Now if we decide we want to add some more "dispatching" operations, we could either disrupt the existing hierarchy of interfaces by adding the operation to each interface, or we could add an operation to each interface to support the visitor pattern, and use that for defining additional operations.  For ParaSail, we are proposing a third approach:

interface Expr[#output] is
    function Text_Image(E : Expr) -> Univ_String;
    function XML_Image(E : Expr) -> Univ_String;
    ...
end interface Expr[#output];

interface Binary[#output] is
    function Text_Image(B : Binary) -> Univ_String;
    function XML_Image(B : Binary) -> Univ_String;
    ...
end interface Binary[#output];
...

Here we have defined an interface extension labeled "#output".  We could define additional interfae extensions with other labels.  Now we have effectively added Text_Image and XML_Image as dispatching operations of Expr without a need for a visitor pattern and without disrupting the original Expr interface hierarchy.  These operations are available when we refer to "Expr[#output]" rather than simply "Expr".  If we had another extension labeled "#input," we could gain access to both by referring to "Expr[#input | #output]".

Then we could write:

 interface Calculator<Int_Expr is Expr[#input | #output]<>> is
       // Now we can use operations from the #input and #output extensions
       // of Expr when manipulating polymorphic objects of type Int_Expr+
    ...
    procedure Print_Expr_And_Value(Str : Output_Stream; E : Int_Expr+) is
        // E is of the polymorphic type Int_Expr+ 
        // so calls on its operations (including those from the
        // interface extensions #input and #output) will dispatch.

        const Result := Evaluate(E);   // dispatching call.
        Print(Str, Text_Image(E));      // Now display the expression
        Print(Str, " = ");
        Print(Str, Result);                    // and then display its value.
    end procedure Print_Expr_And_Value;
end interface Calculator;

This approach allows the definition of additional dispatching operations in a modular fashion to an existing type hierarchy, while not disrupting existing users.  It seems to provide some advantages over the Visitor pattern approach as well, as the new operations are not second class citizens requiring the construction of a visitor object, etc.