More electronic ink on ParaSail

Another nice article on ParaSail just came out, in the on-line journal EEJournal:

    http://www.eejournal.com/archives/articles/20120718-language/

This article came out of a very pleasant interview over lunch at a Paris bistro with Dick Selwood, one of the EEJournal editors.  So imagine a discussion of ParaSail while we multitasked over bread, cheese, and red wine... ;-)

Rev 3.0 of alpha release 0.5 available; suppports multi-thread exit/return

We have just released a significant update to the ParaSail compiler and virtual machine, revision 3.0 of the alpha release 0.5:

    http://bit.ly/Mx9DRb

This release is the first to support a "return" or "exit" from inside a parallel construct (such as a concurrent loop or a block with statements separated by "||").  Such a return or exit terminates all of the other picothreads inside of the construct being exited, before returning or exiting with the specified value.  What this means is that you can write parallel loops or other algorithms with multiple picothreads "racing" to find the answer, with the first one to do the "exit loop with xxx;" or "return yyy;" providing the answer, with the other picothreads automatically terminated.  This is a natural way to write certain kinds of parallel algorithms, and now ParaSail makes it quite easy to get the automatic shutdown and cleanup desired for such cases.  A simple example "locked_exit.psl" is included in the "examples" subdirectory of the release, to illustrate such a "multi-thread" exit.

If you have any trouble downloading, installing, or testing out this new release, please don't hesitate to post a response to this note.

Implementation of a directed graph in ParaSail

Below is an implementation of a (pointer-free) directed graph in ParaSail, as promised in the EETimes.com article ParaSail : Less is More with Multicore.
  [ see http://www.eetimes.com/design/embedded/4375616/ParaSail--Less-is-more-with-multicore ]

// Example ParaSail program -- Directed Graph module

// Copyright (C) 2011-2012, AdaCore, New York, NY
// To be used only for Personal, Academic, or Evaluation Purposes;
// Not for Commercial Production Use.
// Report errors at http://groups.google.com/group/parasail-programming-language

interface DGraph<Element is Assignable<>> is
  // Interface to a Directed-Graph module

    type Node_Id is new Integer<1..10**6>;
      // A unique id for each node in the graph

    type Node_Set is Countable_Set<Node_Id>;
      // A set of nodes

    func Create() -> DGraph;
      // Create an empty graph

    func Add_Node(var DGraph; Element) -> Node_Id;
      // Add a node to a graph, and return its node id

    op "indexing"(ref DGraph; Node_Id) 
      {Node_Id in DGraph.All_Nodes()}
      -> ref Element;
      // Return a reference to an element of the graph

    func Add_Edge(var DGraph; From, To : Node_Id)
      {From in DGraph.All_Nodes(); To in DGraph.All_Nodes()};
      // Add an edge in the graph

    func Successors(ref const DGraph; Node_Id) -> ref const Node_Set
      {Node_Id in DGraph.All_Nodes()};
      // The set of successors of a given node

    func Predecessors(ref const DGraph; Node_Id) -> ref const Node_Set
      {Node_Id in DGraph.All_Nodes()};
      // The set of predecessors of a given node

    func All_Nodes(DGraph) -> Node_Set;
      // The set of all nodes

    func Roots(DGraph) -> Node_Set;
      // The set of all nodes with no predecessor

    func Leaves(DGraph) -> Node_Set;
      // The set of all nodes with no successor
end interface DGraph;

class DGraph is
  // Class defining the Directed-Graph module

    interface Node<> is
      // Local definition of Node structure
        var Elem : Element;
        var Succs : Node_Set;
        var Preds : Node_Set;
    end interface Node;

    var G : Vector<Node>;
      // The vector of nodes, indexed by Node_Id

    const Debug : Boolean := #false;

    func Boundary_Set(DGraph; Nodes : Countable_Range<Node_Id>;
      Want_Roots : Boolean) -> Node_Set is
      // Recursive helper for exported Roots and Leaves functions
        if Debug then
            Println("Boundary_Set for " | Nodes.First | ".." | Nodes.Last);
        end if;
        const Len := Length(Nodes);
        case Len of
          [0] =>
            return [];
          [1] =>
            if Want_Roots?
                Is_Empty(Predecessors(DGraph, Nodes.First)):
                Is_Empty(Successors(DGraph, Nodes.First))
            then
                // This is on the desired boundary
                return [Nodes.First];
            else
                // This is not on the desired boundary
                return [];
            end if;
          [..] =>
            // Divide and conquer
            const Half_Way := Nodes.First + Len / 2;
            return 
              Boundary_Set(DGraph, 
                Nodes.First ..< Half_Way, Want_Roots) |
              Boundary_Set(DGraph,
                Half_Way .. Nodes.Last, Want_Roots);
        end case;
    end func Boundary_Set;

  exports

    func Create() -> DGraph is
      // Create an empty graph
        return (G => []);
    end func Create;

    func Add_Node(var DGraph; Element) -> Node_Id is
      // Add a node to a graph, and return its node id
        DGraph.G |= (Elem => Element, Succs => [], Preds => []);
        return Length(DGraph.G);
    end func Add_Node;

    op "indexing"(ref DGraph; Node_Id) -> ref Element is
      // Return a reference to an element of the graph
        return DGraph.G[ [[Node_Id]] ].Elem;
    end op "indexing";

    func Add_Edge(var DGraph; From, To : Node_Id) is
      // Add an edge in the graph
        DGraph.G[ [[From]] ].Succs |= To;
        DGraph.G[ [[To]] ].Preds |= From;
    end func Add_Edge;

    func Successors(ref const DGraph; Node_Id) -> ref const Node_Set is
      // The set of successors of a given node
        return DGraph.G[ [[Node_Id]] ].Succs;
    end func Successors;

    func Predecessors(ref const DGraph; Node_Id) -> ref const Node_Set is
      // The set of predecessors of a given node
        return DGraph.G[ [[Node_Id]] ].Preds;
    end func Predecessors;

    func All_Nodes(DGraph) -> Node_Set is
      // The set of all nodes
        return 1 .. Length(DGraph.G);
    end func All_Nodes;

    func Roots(DGraph) -> Node_Set is
      // The set of all nodes with no predecessor
        return Boundary_Set
          (DGraph, 1 .. Length(DGraph.G), Want_Roots => #true);
    end func Roots;

    func Leaves(DGraph) -> Node_Set is
      // The set of all nodes with no successor
        return Boundary_Set
          (DGraph, 1 .. Length(DGraph.G), Want_Roots => #false);
    end func Leaves;
end class DGraph;

func Test_Graph() is
  // A test program that manipulates a directed graph of univ-enums

    type DGE is DGraph<Univ_Enumeration>;

    func Build_Graph() -> New_G : DGE is
      // A function that builds up a graph of Univ_Enumerations
        New_G := Create();  // Create the empty graph

        const Hello := New_G.Add_Node(#hello);
        const There := New_G.Add_Node(#there);
        const Stranger := New_G.Add_Node(#stranger);

        New_G.Add_Edge(Hello, There);
        New_G.Add_Edge(There, Stranger);
        New_G.Add_Edge(Hello, Stranger);

    end func Build_Graph;
       
    func Print_Nodes(DGE; Nodes : DGE::Node_Set; Indent : Univ_String := " ")
      // Display the elements of a node set, with the given indent
    is
        for S in Nodes loop
            Println(Indent | DGE[S]);
        end loop;
    end func Print_Nodes;

    func Print_Succs(DGE; N : DGE::Node_Id) is
      // Display the successors of a given node
        Println("Successors of " | DGE[N] | " (node " | N | ")");
        Print_Nodes(DGE, DGE.Successors(N));
    end func Print_Succs;

    // Now build the graph and display some info on the graph

    var Gr : DGE := Build_Graph();

    Println("Roots of graph:");
    Gr.Print_Nodes(Gr.Roots());

    Println("Leaves of graph:");
    Gr.Print_Nodes(Gr.Leaves());
    
    Println("All nodes, and their successors:");
    for N in All_Nodes(Gr) forward loop
        Gr.Print_Succs(N);
    end loop;
end func Test_Graph;

Rev 2.6 of alpha release 0.5 now available

Revision 2.6 of the 0.5 alpha release of the ParaSail compiler and virtual machine is now available:

  http://bit.ly/LZvZc2

This new release includes a number of enhancements, as well as much more stable support for synchronization via concurrent objects.  The enhancements include: conditional expressions (using either "(if X then Y else Z)" or "X? Y : Z" syntax; initial implementation of compile-time checks for race conditions; container "comprehensions" -- an iterator inside a container aggregate, such as:

  [for I in 1..N => I**2]

to create a table of squares.  See the release notes for all the details.

ParaSail in print

An article entitled "ParaSail: Less is More with Multicore" was published recently on eetimes.com (and its affiliates) Here is a link to a newsletter where the editor (Bernie Cole) highlights the article:

    http://i.cmpnet.com/audiencedevelopment/newsletters/06-21-2012-EmbeddedNL.html

Here is a direct link to the article:

    http://www.eetimes.com/design/embedded/4375616/ParaSail--Less-is-more-with-multicore

In addition to the above, a subset of this blog is also now available online in a somewhat more polished format as a section of the following Ada User Journal issue (covers Sept 2009 to February 2011):

    http://www.ada-europe.org/archive/auj/auj-32-1.pdf

Finally, we participated in the New England Programming Languages and Systems Symposium on June 1 at the University of Southern Maine:

    http://www.nepls.org/Events/26/

Here are the slides we presented:

   https://groups.google.com/group/parasail-programming-language/attach/25ebc77d83d31736/ParaSail_NEPLS_Jun_2012.pps?part=4&authuser=0

Identifying "new" vs. "overriding" operations when extending a module

We have recently implemented inheritance of operations and components using the extends keyword in ParaSail.  One of the frequent problems with inheritance is that the programmer might think they are or are not overriding an inherited operation when they explicitly declare an operation, but in fact they are wrong.

Object-oriented languages have addressed the issue of overriding "intent" in various ways.  In C#, a method must have the word "override" if it overrides (as opposed to hides), and may have the word "new" if it doesn't.  In Java 5+, there is an "@Override" annotation.  In Eiffel, "redefine" may be used to indicate overriding.  In Ada 2005, "overriding" or "not overriding" may be indicated.  In C++11, the (non-reserved) keyword "override" may be used to indicate the intent to override.

Our initial design for ParaSail lacked any way to indicate overriding intent, but given the fact that essentially all mainstream object-oriented programming languages now have that ability, it seemed like an oversight.  Therefore, we now allow an interface that extends another to separate the overridings from the new operations.  Here is an example of an Expr interface, and an interface Binary that extends it:

interface Expr<> is
    type Type_Enum is Enum<[#bool, #int, #real, #array, #record];>;

    abstract func Eval(E : Expr) -> Univ_Real;
      // Operation to evaluate expression tree to a univ-real result
    abstract func Display(E : Expr; Indent : Univ_Integer := 0);
      // Operation to display an expression tree in an indented format

    func Init_Type(T : Type_Enum; Count : Univ_Integer) -> Expr;
      // Create an initialized Expr object as needed for
      // creating a class-aggregate in any descendant of Expr.
      // Such a constructor is needed because Expr has hidden
      // components (the "Type" component is hidden).
end interface Expr; 

interface Binary<> extends Expr is
    type Binop is Enum<[#plus, #minus, #times, #divide, #pow]>;

    // Override abstract "Expr" operations
    func Eval(B : Binary) -> Univ_Real;
    func Display(B : Binary; Indent : Univ_Integer := 0);

    // Override inherited constructor, which "becomes" abstract
    // because Binary has its own constructor, and hence might have
    // its own private components.
    func Init_Type(T : Expr::Type_Enum; Count : Univ_Integer) -> Binary; 

  new
    // Define constructor for Binary nodes
    func Create(Op : Binop; Left, Right : Expr+) -> Binary;
end interface Binary;

The reserved word new, if present, separates the declarations which are overriding inherited operations, from the declarations which correspond to new operations.  The compiler will complain if declarations in the first set do not override an inherited operation, or declarations in the second set do override an inherited operation.

One open design question at the moment is whether an operation should be declared before or after new if it implements an operation declared in an interface named in the implements list, but does not override an operation inherited from the parent interface named after extends.  It is not actually overriding anything that was inherited, but it is not really new since it is presumably intended to match an existing operation in some implemented interface. 

My sense is that we will catch more errors by requiring that an operation that comes after new is really new, and does not override an inherited operation nor does it implement an operation of an implemented interface.  And for those who like to think that operations are effectively inherited from implemented (as opposed to extended) interfaces, then distinguishing the two kinds of inheritance (interface inheritance vs. implementation inheritance) might be confusing. 

Note that one issue is that ParaSail allows an interface to implement another parameterless interface without mentioning it explicitly in the implements list.  This provides a kind of ad hoc matching and reduces the number of interfaces that need to be mentioned explicitly.  This kind of ad hoc matching is clearly not considered when checking the proper placement of the new separator.

Rev 2.1 of alpha release 0.5 now available

Revision 2.1 of the alpha 0.5 release of the ParaSail prototype compiler and virtual machine is now available:

http://bit.ly/y06SQW

This includes a new set of modules for supporting Matrix/Vector arithmetic, and more robust support for combining inheritance, type inference, and "generic" operations.  This allows the interfaces Col_Vec and Row_Vec to be extensions of the interface Matrix, with a generic "*" operator that can combine a Matrix and a Col_Vec to produce another Matrix, or a Col_Vec and a Matrix to produce a Row_Vec.  Similarly a Transpose operation can convert a Col_Vec into a Row_Vec, or one kind of Matrix into another.  See the "mat_vec.psi" and "mat_vec.psl" files in the "example" subdirectory for illustrations of this.