Using "=?" in ParaSail to implement "==", "!=", "<=", ">=", etc.

Here is a simple ParaSail feature.  It is often the case that a user-defined type will have its own definition for equality and comparison.  However, it is always a bit of an issue to make sure that "==" and "!=" are complements, and similarly for "<" and ">=", ">" and "<=".  ParaSail skirts this issue by requiring the user to define only one operator, "=?", which returns a value from the enumeration Less, Equal, Greater, Unordered.  The comparison and equality operators are defined in terms of "=?" (which is pronounced "compare"), in the natural way:

• "==" -- Result of "=?" is Equal
  
• "!="  -- Result of "=?" is not Equal
  
• "<"   -- Result of "=?" is Less
  
• ">"   -- Result of "=?" is Greater
  
• "<=" -- Result of "=?" is Less or Equal
  
• ">=" -- Result of "=?" is Greater or Equal
  

"Unordered" is used for types with only a partial ordering (or no ordering at all).  "Ordered" is defined as the subtype containing only the values "Equal," "Less," and "Greater."  The typical generic "Sort" operation would expect a "=?" operator whose result is guaranteed (via a postcondition) to be within the "Ordered" subtype.

The "=?" operator can be used explicitly if desired, which is often convenient when searching a binary tree:

    case Desired_Key =? Node.Key of
        Equal :   return Node;
        Less :    return Search(Node.Left, Desired_Key);
        Greater : return Search(Node.Right, Desired_Key);
    end case;

This would be another situation where the "=?" would be required to return an Ordered result, since we don't have an alternative that handles "Unordered."

ParaSail's implicit parallelism

As mentioned in the original overview of ParaSail, implicit parallelism is at the heart of ParaSail (and of its name!).  Every procedure/function call with multiple parameters involves implicit parallelism, in that all of the parameters are evaluated in parallel.  Handoff semantics is used for writable parameters, meaning that a (non-concurrent) object that is writable by one parameter evaluation, isn't available to any other parameter evaluation.  Operations on concurrent objects are not ordered.

Furthermore, in a sequence of statements, the only default limitation on parallelism is that imposed by operations on non-concurrent objects.  Parallelism can be inhibited by using ";;" instead of merely ";" to separate two statements.  This forces sequencing for operations on concurrent objects, which would otherwise not have any specified order.  By contrast, "||" can be used to indicate that parallelism is expected, and it is an error if there are conflicting operations on non-concurrent objects in the statements on either side of the "||".  That is, two statements separated by "||" are executed effectively in parallel, just as though there were embedded within two different parameter evaluations to a single procedure or function call.

For example:

    X := F(A, B);
    Y := G(B, C);;
    Z := H(R, S) || Z2 := Q(R, T);

As implied above by the formatting, "||" has highest precedence (binds most tightly), ";" next, and ";;" lowest (binds least tightly).  So in the above, the assignments to X and Y are ordered only if that would be required by the shared use of B (at least one of them has B as a writable parameter).  The assignments to Z and Z2 occur in parallel, and it would be an error if the shared use of R is unsafe (e.g. because R is writable by one or both, and is not a concurrent object).  The assignments to X and Y will complete before beginning the assignments to Z and Z2 (though of course, a "very intelligent" compiler might still find parts that can be executed in parallel because they can't possibly affect one another).  In all cases the evaluations of the parameters to a single procedure/function call happen in parallel.

Parentheses can be used to override the precedence for the statement separators:

    (M := N(A, B) ;; P := T(A, X)) ||
      (J := K(X, Y); M2 := N2(Y, Z));

In the above the assignment to M completes before the assignment to P starts.  The assignments to J and M2 occur in parallel unless the shared use of Y makes that unsafe.  And the assignments to M and P occur in parallel with the assignments to J and M2, and it is an error if there are conflicts due to shared use of X.

Note that ";" is both a statement separator and a statement terminator.  On the other hand, ";;" and "||" are only meaningful as statement separators.

Implicit parallelism also shows up in ParaSail loops.  The iterations of a for loop in ParaSail are executed as though each iteration were separated from the next by a ";", but with no particular ordering on the iterations.  A particular ordering may be specified by using the forward or reverse keyword, which effectively puts a ";;" between the iterations. Alternatively, the concurrent keyword may be used to indicate that the iterations should be effectively separated by "||", in which case it is an error if there are any conflicts due to operations on a non-concurrent variable.  For example:

    // compute sum of array A 
    for I in 1..10 loop
        Sum += A[I];
    end loop;

    // find last element equal to Z
    for I in 1..10 reverse loop
        if A[I] == Z then
             Last_Z := I;
             exit loop;
        end if;
    end loop;

    // sum the arrays B and C to produce A
    for I in 1..10 concurrent loop
        A[I] := B[I] + C[I];
    end loop;

Not too surprisingly, an exit loop statement is only permitted in a forward or reverse loop.

As illustrated above, parallelism is the default in ParaSail.  It is our belief that that is the only way that programmers will learn to take full advantage of the multicore world.  That is, in ParaSail, it is more work to create non-parallel algorithms than to create parallel ones, so programmers, being fundamentally a lazy lot, will end up writing mostly parallel algorithms in ParaSail.

We will cover ParaSail's structured synchronization mechanism (concurrent interfaces) in another post.

Scala closures as poor man's mocks

Groovy has this feature that you can use a closure whenever you need an interface with one method only. A class implementing the interface is automatically created, and the closure provides the implementation of this single method. This process is called closure coercion and is particularly convenient to make tests readable and concise.

I'm not yet sure about the relative advantages of such code everywhere, since there might be ambiguities or the intent might be obscured. Tests usually contain a lot of boilerplate, though, so I'm all for making them more concise. Except for readability, people would be more likely to write a test if it doesn't take much effort to create yet another trivial mock.

Who tests your tests though? You don't need to answer. Still, the page about implementing interfaces in Groovy warns of this trap: "Be careful that you don't accidentally define the map with { }". Type safety could help sometimes when writing tests. Or at least that's a very good excuse to try to emulate this Groovy feature in Scala.

In Scala there are implicit conversions, which help define a controlled way to coerce a value to a different type. We cannot automatically convert all closures to all possible single-method interfaces in scope, but we can choose several we are using especially often (as it happens in tests). For instance, if we want to use a mock of java.lang.Readable often enough, we could define the following implicit conversion:

import java.nio.CharBuffer

implicit def fun2readable(f: Function1[CharBuffer,Int]): Readable =
  new Readable { def read(cb: CharBuffer) = f(cb) }

So now everywhere we need a Readable, we might just drop in the appropriate closure instead (technically, this is not a mock, but a stub):

val readable: Readable = {cb: CharBuffer => cb.put("12 34"); 5}
val s = new java.util.Scanner(readable)
assert (s.nextInt == 12)

Compare this with the Groovy version:

def readable = { it.put("12 34"); 5 } as Readable
def s = new Scanner(readable)
assert s.nextInt() == 12

In the Scala version, we are explicitly defining the type of the variable in order to force the implicit conversion. In methods, where Readable is expected as an argument, explicitly naming the type will not be necessary, whereas in Groovy you always need to coerce using "as Readable":

val s = new java.util.Scanner({cb: CharBuffer => cb.put("12 34"); 5})

So in Scala you're trading some verbosity up front for some conciseness in all of the code where the implicit conversion is visible. Furthermore, the type checker guarantees that only closures with the correct signature are converted to the interface in question (i.e. with an input of CharBuffer and output of Int) and will flag a compile-time error otherwise.

The reader might be tempted to also emulate map coercion, but beware of an unexpected difficulty: it's not easy to define both a closure (with one argument) and map coercion. Since a Map in scala is a function and due to type erasure, the compiler won't know whether to substitute the Map or the Function!

Can you generate these implicits automatically without defining them? Maybe with a Scala compiler plugin, but then you lose some of the transparency of knowing which implicits you've defined.

ParaSail has no global variables

ParaSail has no global variables.  So how does that work?  Global variables have long been recognized as trouble makers in the software world, and they get much worse in a language with lots of parallelism.  But can we eliminate global variables completely?  ParaSail tries to do that by eliminating any notion of statically allocated variables.  In C or C++, global variables are those marked static or extern, or in a language with modules/packages like Ada, global variables are those declared at the module level.  Although their declaration might be hidden, such variables still represent global, variable state, and still create trouble.

In ParaSail, interface modules are generic types, and class modules implement interfaces.  That is, after providing generic parameters to an interface, you end up with a type.  Any variable declared in a class is what is often called an instance variable, that is, there is one per object of the type defined by the class.  There is nothing corresponding to what are called class variables.  In other words, the variables declared in a class will always be effectively fields/components of some enclosing object.  You can of course also have local variables inside the body of a procedure or function, but these are never statically allocated; they are stack-resident variables only (automatic in C parlance).

So what do we have instead?  In many cases, we simply substitute local variables declared in some relatively high-level procedure or function body, which are then passed (by reference) to other operations as parameters.  In ParaSail, passing a variable as a parameter generally has handoff semantics, meaning that it can't be simultaneously passed to multiple operations that might execute in parallel, nor can it be passed twice to the same operation as two different parameters (thereby eliminating certain kinds of aliasing problems).

When it is necessary to have a data structure that can be accessible to multiple operations running in parallel, the data structure must be explicitly designed for concurrent access.  In other words it must be a concurrent data structure.  In ParaSail, an interface may be specified as a concurrent interface, and then all objects of a type defined by the interface support concurrent access.

Containers represent a kind of middle ground, where the enclosing container might be designed for concurrent access, but the individual elements might not be, and so handoff semantics would again apply to the individual elements.

There may be some concurrent interfaces that typically have exactly one object; that is they are typically singleton interfaces.  For example, the file system, or the database manager, or the system clock.  ParaSail provides a conceptual global singleton Context interface for these, whose singleton object has one component for each such singleton interface, identified using the name of the interface.  The Context must appear as a parameter for operations that ultimately need access to one of these singleton interfaces, signifying that the operation has potential side effects on these singleton objects.  It would always be preferable to pass in the actual singleton objects needed, but as a convenience, the Context pseudo-object is available. 

The Context pseudo-object is provided as a parameter to the main entry point of a ParaSail application, so that it can gain access to these singletons and pass them on to callers.  If an operation has a Context parameter, and its caller also has a Context parameter, then the caller's parameter is passed automatically to the operation if not specified explicitly.  The Context parameter may be read-only ("in") or read-write ("in-out"/"var").  Not surprisingly, the actual Context parameter must be read-write if the formal is read-write.

ParaSail Topics to come

The prior entries gave an overview of ParaSail.  Over the next few weeks I hope to write additional entries about:

• ParaSail has no global variables, so how does that work?
• how iterators, streams and for-loops are interrelated in ParaSail;
• using a single compare primitive ("=?") in ParaSail to implement "==", "!=", "<=", ">=", etc.
  
• ParaSail's implicit parallelism and structured synchronization;
• ParaSail private interfaces and interface namespace hierarchy; 
• ParaSail's use of region-based storage management rather than object-at-a-time garbage collection;
  
• ParaSail's use of compile-time checks (mostly), run-time checks (goal is to never need them), and exceptions (only when complexity or race-conditions make them necessary);
  
• how attributes like taintedness (i.e. might this data come from a malicious source?) or physical units (e.g. meters/second, years, ...) can be "layered" onto existing types, along with appropriate pre- and postconditions, to provide additional security, safety, or correctness checking.  Add-on attributes can also be associated with statements or other ParaSail constructs, such as an attribute indicating whether a given statement or operation is potentially blocking (that is, it might wait indefinitely on some queue or some other synchronization structure), or the total amount of stack space required by a given statement or operation.
  

So stay tuned.  If you as a reader have other topics you would be interested in seeing further elaborated, please post a comment to that effect.