Monday, July 30, 2012

Zero-based indexing for Vector and Univ_String

Whether array indices most "naturally" should start at zero or one remains a surprisingly unresolved question.  Algol, Pascal, Ada, Modula, Eiffel, etc. generally started array indexing at 1, or allowed the programmer to choose the bounds, while C with its model of array indexing being equivalent to pointer arithmetic, requires starting at zero since array indices are interpreted as offsets.

In ParaSail arrays are simply a special case of a container, and indexing is user-definable, so the index need not even be integers, and certainly there is no requirement that the first index be zero, or one, or any specific value.  On the other hand, there are some pre-provided modules such as Vector and Univ_String which allow indexing, and some decision has to be made about whether to start with zero or one.  Because of the Pascal/Ada/Modula heritage, the natural choice was to start with one.

However, there are algorithms where starting with zero is more natural, and there are certainly programmers who are more comfortable with starting indexing with zero, so we have recently added zero-based indexing versions of Vector and Univ_String, namely ZVector and ZString.  So using ParaSail's half-open intervals, one can loop over the contents of a ZVector (or a ZString) with:
    var ZV : ZVector<Univ_Integer> := [1, 3, 5, ...];
    var Sum := 0;

    for I in 0 ..< Length(ZV) loop
        Sum += ZV[I];
    end loop;

Monday, July 23, 2012

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... ;-)

Sunday, July 22, 2012

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.

Monday, July 2, 2012

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;

Sunday, July 1, 2012

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.