Monday, September 16, 2013

Parallelizing Python and Java

Designing and implementing ParaSail has been a fascinating process.  Achieving parallelism and safety at the same time by eliminating rather than adding features has worked out better than we originally expected.  One of the lessons of the process has been that just a small number of key ideas are sufficient to achieve safe and easy parallelism.  Probably the biggest is the elimination of pointers, with the substitution of expandable objects.  The other big one is the elimination of direct access to global variables, instead requiring that a variable be passed as a (var or in out) parameter if a function is going to update it.  Other important ones include the elimination of parameter aliasing, and the replacement of exception handling with a combination of more pre-condition checking at compile time and a more task-friendly event handling mechanism at run time. 

So the question now is whether some of these same key ideas can be applied to existing languages, to produce something with much the same look and feel of the original, while moving toward a much more parallel-, multicore-, human-friendly semantics.

Over the past year we have been working on a language inspired by the verifiable SPARK subset of Ada, now tentatively dubbed Sparkel (for ELegant, parallEL, SPARK).  For those interested, this experimental language now has its own website: 

    http://www.sparkel.org

Sparkel has essentially all of the power of ParaSail, but with a somewhat more SPARK-like/Ada-like look and feel.  We will be giving a talk on Sparkel at the upcoming HILT 2013 conference on High Integrity Language Technology in Pittsburgh in November:

   http://www.sigada.org/conf/hilt2013

HILT 2013 is open for registration, and it promises to be a great conference, with great talks, tutorials, and panels about model checking, model-based engineering, formal methods, SMT solvers, safe parallelism, etc. (disclaimer -- please note the name of the program chair).

At the upcoming OOPSLA/SPLASH conference, we are giving a talk about applying these same principles to Python and Java.  Super-secret code names for the results of this effort are Parython and Javallel.  The announcement of this talk is on the splashcon.org web site:

    http://splashcon.org/2013/program/tutorials-tech-talks/853-living-without-pointers-bringing-value-semantics-to-object-oriented-parallel-programming

If you are coming to OOPSLA/SPLASH, please stop by to hear the results.  We will also be adding entries over the next couple of months about some of the lessons learned in working to create a safe parallel language when starting quite explicitly from an existing language.

Thursday, September 12, 2013

Revision 4.7 of ParaSail alpha release now available

We are pleased to release alpha revision 4.7 of the ParaSail compiler and virtual machine, available at the same URL:

http://bit.ly/Mx9DRb
 
This release includes a large number of bug fixes, plus the following enhancements:
 
More support for operations on polymorphic types, including binary operations, where it is an error if the two operands have different underlying types, unless the operator is "=?". "=?" is a special case, where rather than an error, it returns #unordered if two polymorphic operands have different underlying types.  This now allows us to define a type like Set and have it work as desired, that is, as a Set holding (almost) any type.

We have a preference now for non-generic operations when there would otherwise be ambiguity between a normal operation and a generic operation of the same name.  This is relevant for the "|" operator on Univ_String.  We have now added To_String and From_String on Univ_String (these are identity operations), which means Univ_String now implements the "Imageable<>" interface.  The new preference rules prevents this from creating ambiguity on | .

We know allow {> ... <} for annotations as a substitute for { ... }.  This will allow us to eventually use { ... } for Set/Map constructors in the PARython dialect.  The new {> ... <} syntax makes annotations a bit more obvious, which seems like a good thing.

Even when still using "then"/"is"/"loop"/"of" instead of ":", we have made "end blah" optional.  Presumably project-specific rules might require "end blah" if the construct is too many lines long (e.g. more than 20 lines).

Highlighting information for the ConTEXT source text editor is under share/tools/... in a file named ConTEXT_ParaSail.chl courtesy of ParaSail user Arie van Wingerden.  Similar information for the "geshi" highlighting system (used by WikiPedia) is in a file called geshi_parasail.php.

Case statements over polymorphic objects are now supported where the case choice has an associated identifier, such as in:

    var E : Expr+ := ...
    case E of
      [L : Leaf] => ...
      [U : Unary] => ...
      [B : Binary] => ...
      [..] =>
    end case;

Note that the specified types for the case choices must be non-polymorphic types at the moment.  In a later release we will support having choices with polymorphic types, such as:

    [SE : Simple_Expr+] => ...
   
where presumably Simple_Expr is an extension of Expr.

We have added function types, of the form:

   func(X : Integer; Y : Float) -> Integer

Basically the same syntax as a "func" declaration but without the func's identifier.  To declare a "func" that takes another "func" as a parameter, you would now use syntax like:

 func Apply
   (Op : func(X : Integer) -> Integer; S : Vector)
     -> Vector

rather than the former syntax:

 func Apply
   (func Op(X : Integer) -> Integer; S : Vector)
     -> Vector

The syntax for lambda expressions has been simplified, so you only specify the names of the inputs, with no mention of the types of the inputs or the outputs.  For example:

  lambda (Y) -> 2*Y
 
is a lambda expression that doubles its input. A lambda expr can be passed as a parameter so long as the type of the formal parameter is a compatible "func" type.  So for example, given the above definition of "Apply", you could write:

 Apply (lambda(Y)->2*Y, [1, 2, 3])

and expect to get "[2, 4, 6]" as the result (presuming "Apply" does the natural thing).
 
We now share the lock between a polymorphic object and the non-polymorphic object it contains; we also share the lock between object and its parent part, if any.  Handle "continue loop"s that exit blocks. Source code has been restructured to more easily handle new parser using same underlying language semantics, to support "Parython" and other language parallelization efforts.

When a "new" type is declared (type T is new Integer<...>) we allow additional operations to be declared immediately thereafter in the same scope, and have them be visible wherever the type is later used, just as though a new module had been defined as an extension of the old module, and the new operations had been declared inside that new module.

When an expression does not resolve, we now provide additional diagnostics to help explain why.