Monday, November 7, 2011

Rev 1.6 of alpha 0.2 release of ParaSail compiler and VM

Here is a new revision (rev 1.6) of the alpha 0.2 release of the ParaSail compiler and virtual machine

The big addition here is a new example, the "drinking philosophers" example (drinking_phils.psl).  This example is a variant on the classic "dining philosophers" example, and makes heavy use of timers and complex dequeue conditions.  A lot of changes under the hood, but no major new features.

Monday, October 24, 2011

Alpha release 0.2 of ParaSail Compiler and Virtual Machine

We are now making available alpha release 0.2 (rev 1.5) of the ParaSail Compiler and Virtual Machine:

This release implements several important additional features, including queued parameters for operations on concurrent objects, floating-point and fixed-point numbers along with the universal type Univ_Real, and timers supporting delay for a time interval and delay until a specified timer value, or until a specific wall clock time. 

This release also includes two different version of the VM, one which simulates multi-threading on a single O/S thread, and another which uses multiple O/S threads to provide true parallelism on a multi-core/multi-processor machine.

Please read the release notes included in the above download for additional information.

Friday, October 14, 2011

Upcoming panels, tutorials, and workshops on ParaSail

ParaSail will be discussed at two panels at the upcoming SPLASH/OOPSLA conference in Portland, Oregon, and will be covered in depth in a tutorial and workshop/birds-of-a-feather session at the upcoming SIGAda conference in Denver. 

The panels at SPLASH/OOPSLA are:
The events at the upcoming SIGAda conference in Denver are:
I believe all of these event are still open for additional attendees.

Thursday, October 13, 2011

Deadlocking the Virtual Machine

As mentioned in an earlier posting, ParaSail has its own virtual machine which directly supports the notion of picothreads, very light-weight threads which are served by heavier-weight server processes (see  We are now compiling and executing various interesting ParaSail examples, and we recently began to see some apparent deadlocks in the virtual machine implementation. 

The actual ParaSail program (N Queens -- see does not have any inherent deadlock itself.  In fact, it only has one concurrent object, a vector of solutions, and the only locking operation used is to add another solution on to the end of the vector.  Nevertheless, we are seeing with a true multi-threaded virtual machine implementation, a deadlock in the virtual machine, such that all forward progress stops.  Like many situations in concurrent programs (at least pre-ParaSail...), these kinds of problems are timing dependent.  In some cases we can get the N-Queens solver for 8 queens to finish, sometimes not.  The version using a single-kernel-thread virtual machine, which merely simulates multi-threading, never has a problem.

So what could be causing the deadlock?  After lots of debugging, a hypothesis has emerged.  We are now in the process of acting on this hypothesis, so we don't know whether it is correct, or whether making a corresponding fix will solve the entire problem.  So here is the hypothesis:

As explained in the posting about the virtual machine (actually, in a comment on that posting), we serve the queue of picothreads associated with a particular server process in a LIFO manner.  But when a server steals threads from another server, it picks up the oldest picothread, i.e. uses FIFO.  This is essentially identical to the approach used in the Cilk thread scheduler (see  Our hypothesis is that it is the stealing of picothreads which is creating the deadlock.

So how could the stealing of threads create a deadlock?  The hypothesized mechanism begins with a server executing a pictothread that gets a lock on an object.  This happens when there is a call on an operation with a locked or queued parameter, or when an individual concurrent object (such as the Solutions vector in N-Queens) is passed to an operation where it is not known to be concurrent (such as the "|=" operation in the Vectors module). 

In the virtual machine implementation, getting a lock means acquiring a mutex or equivalent.  This mutex is automatically released when the operation completes.  However, suppose the operation has internal parallelism.  In ParaSail, parallelism is everywhere, and any operation of any complexity is likely to have some internal parallelism.  The "|=" operation is relatively complex, particularly if the underlying array needs to be expanded before adding on another element to the vector.  So there is plenty of opportunity for some internal parallelism.  That is manifested in the virtual machine by one or more additional picothreads being created and queued on the same server's thread, and then eventually, the server waits for the parallel picothreads to complete.

As soon as new picothreads show up on the server's queue, other servers may start stealing them.  As mentioned above, stealing works FIFO, i.e. oldest first, but if the original server's queue is essentially empty at the moment when a picothread from the locked operation is queued, then it will be the oldest thread on the queue, and so is a candidate for stealing.   So let's presume that this new sub-picothread gets stolen.  And perhaps that was the only picothread spawned by the original server.  When it gets around to waiting for it to complete, it finds it is not yet done, and in fact its own queue is now empty, so it steals from a third server.  So now we have our original server thread which is executing a picothread which is waiting for a subthread, going off and stealing work from some random third server's queue.  Now let's suppose that the thread on that third server's queue wants to get the original lock.  So the original server is now waiting on the lock that it already holds on behalf of some other picothread.  A classic tail-chasing deadlock.  Pretty soon all of the other servers stack up behind this same lock and everything grinds to a halt.

So how do we avoid this problem?  Fundamentally we don't want a server that is holding a lock, to go off and start executing a thread which is not a sub-thread of the original thread which acquired the lock.  If each server and each picothread keeps track of the innermost lock it holds, and locks are chained together so that an inner lock points to the next outer lock, if any, held, then we should be able to avoid the problem.  Whenever a server goes looking for a thread, if it holds a lock, then the thread it chooses must also hold that same lock.  It might also have some additional lock, but it must, somewhere on the chain of locks starting at the innermost one, have the same lock as that held by the server.  This argues for having at least two queues per server, one of picothreads holding no locks, and one of picothreads holding at least one lock.  Then when a queue is served by a server holding a lock, either FIFO or LIFO, it will only look at the queue of picothreads holding at least one lock, and it will ignore those on that queue that don't have the server's lock somewhere in their chain of locks.

Deadlocks are fun -- no doubt about it...

Monday, October 3, 2011

Alpha release of ParaSail Compiler and Virtual Machine

We are very pleased to announce the first, alpha, release of the ParaSail prototype Compiler and Virtual Machine.  This release includes executables for the Mac, Linux, and Windows.  Please visit the ParaSail Google Group to download this release:

Wednesday, September 14, 2011

N Queens Join the Party

We are continuing to work on the ParaSail compiler. Our latest program to compile and run is a parallel but non-recursive version of a solution to the "N Queens" problem. There is an N_Queens module, with a nested Solution_State module used to represent a partial solution. The algorithm starts at column 1 and works toward column N, branching into parallel threads to evaluate each possibility for the next row, and when finding an acceptable one, circling back to the outer loop to march onto the next column. There is a simple Test_N_Queens func at the bottom.  Below that is the result of running the program.


interface N_Queens <N : Univ_Integer := 8> is
    // Place N queens on an NxN checkerboard so that none of them can
    // "take" each other.
    type Chess_Unit is new Integer_Range<-100 .. 100>;
        // An integer type sufficiently big to represent values -100 to +100
    const Rows : Range<Chess_Unit> := 1..N;
    const Columns : Range<Chess_Unit> := 1..N;
    type Row is Chess_Unit {Row in Rows};  // A subrange in 1..N
    type Column is Chess_Unit {Column in Columns};  // A subrange in 1..N
    type Solution is Array<optional Column, Row>;  
      // A "solution" is an array of Column's, indexed by "Row."
      // It indicates in which Column a queen of the given Row is located
      // An example solution would be:  2 8 6 1 3 5 7 4
      //   meaning that the queen in row 1 is at column 2,
      //   the queen in row 2 is at column 8, the queen in
      //   row 3 is at column 6, and so on.
    func Place_Queens() -> Vector<Solution> 
      {for all Sol of Place_Queens => for all Col of Sol => Col not null};
        // Produce a vector of solutions, with the requirement
        // that for each solution, there are non-null column numbers
        // specified for each row of the checkerboard.
end interface N_Queens;

class N_Queens is
    type Sum_Range is Chess_Unit {Sum_Range in 2..2*N};
        // Sum_Range is used for diagonals where the row+column is the
        // same throughout the diagonal.
    type Diff_Range is Chess_Unit {Diff_Range in (1-N) .. (N-1)};
        // Diff_Range is used for diagonals where row-column is the
        // same throughout the diagonal.
    type Sum is Countable_Set<Sum_Range>;
        // This type of set keeps track of which Sum_Range diagonals
        // have a queen on them already.
    type Diff is Countable_Set<Diff_Range>;
        // This type of set keeps track of which Diff_Range diagonals
        // have a queen on them already.

    interface Solution_State<> is
        // We build up a solution state progressively as we move
        // across the checkerboard, one column at a time.
        func Initial_State() -> Solution_State;
        func Is_Acceptable(S : Solution_State; R : Row) -> Boolean;
          // Is_Acceptable returns True if the next queen could be
          // place in row R.
        func Current_Column(S : Solution_State) -> Column;
          // Current_Column indicates which column we are working on.
        func Next_State(S : Solution_State; R : Row) -> Solution_State;
          // Next_State returns a Solution_State produced by
          // adding a queen at (Current_Column(S), R).
        func Final_Result(S : Solution_State; R : Row) -> Solution;
          // Final_Result returns a result produced by adding a queen
          // at (Columns.Last, R) to a solution with all other columns
          // placed.
    end interface Solution_State;

    class Solution_State is
        const C : Column;    // Current column
        const Trial : Solution;  // Trial solution, some col#s still null
        const Diag_Sum : Sum;   // Set of "sum" diagonals in use
        const Diag_Diff : Diff; // Set of "diff" diagnoals in use
        func Initial_State() -> Solution_State is
            return (C => 1, Trial => Create(Rows, null), 
              Diag_Sum => [], Diag_Diff => []);
        end func Initial_State;

        func Is_Acceptable(S : Solution_State; R : Row) -> Boolean is
          // Is_Acceptable returns True if the next queen could be
          // place in row R.
            return S.Trial[R] is null and then
              (R+S.C) not in S.Diag_Sum and then 
              (R-S.C) not in S.Diag_Diff;
        end func Is_Acceptable;
        func Current_Column(S : Solution_State) -> Column is
          // Current_Column indicates which column we are working on.
            return S.C;
        end func Current_Column;

        func Next_State(S : Solution_State; R : Row) -> Solution_State is
          // Next_State returns a Solution_State produced by
          // adding a queen at (Current_Column(S), R).
            return (C => S.C+1, 
              Trial     => S.Trial | [R => S.C],
              Diag_Sum  => S.Diag_Sum | (R+S.C),
              Diag_Diff => S.Diag_Diff | (R-S.C));
        end func Next_State;

        func Final_Result(S : Solution_State; R : Row) -> Solution is
          // Final_Result returns a result produced by adding a queen
          // at (Columns.Last, R) to a solution with all other columns
          // placed.
            return S.Trial | [R => S.C];
        end func Final_Result;

    end class Solution_State;

    func Place_Queens() -> Vector<Solution> 
      {for all Sol of Place_Queens => for all Col of Sol => Col not null}
        // Produce a vector of solutions, with the requirement
        // that for each solution, there are non-null column numbers
        // specified for each row of the checkerboard.
      var Solutions : concurrent Vector<Solution> := [];
      for State : Solution_State := Initial_State() loop
          // Iterate over the columns
          for R in Rows concurrent loop
              // Iterate over the rows
              if Is_Acceptable(State, R) then
                  // Found a Row/Column combination that is not on any diagonal
                  // already occupied.
                  if Current_Column(State) < N then
                      // Keep going since haven't reached Nth column.
                      continue loop Outer_Loop with Next_State(State, R);
                      // All done, remember trial result with last queen placed
                      Solutions |= Final_Result(State, R); 
                  end if;
              end if;
          end loop;
      end loop Outer_Loop;
      return Solutions;
    end func Place_Queens;
end class N_Queens;

func Test_N_Queens() is
    type Eight_Queens is N_Queens<8>;
    var Results := Eight_Queens::Place_Queens();
    Println("Number of results = " | Length(Results));
    for I in 1..Length(Results) forward loop
        const Result := Results[I];
        Print("Result #" | I);
        for J in 1..Length(Result) forward loop
            Print(" " | [[Result[J]]]);
        end loop;
    end loop;
end func Test_N_Queens;

Here is the result of running Test_N_Queens, which is set up to solve the 8-queens problem. It has also been verified to work with 4 queens (2 solutions), 5 queens (10 solutions), and 9 queens (352 solutions). After "quit"ing, a display of threading statistics is provided.

Parsing aaa.psi
Parsing n_queens4.psl
---- Beginning semantic analysis ----
 58 trees in library.
Done with First pass.
Done with Second pass.
Done with Pre codegen pass.
Done with Code gen.

Command to execute: Test_N_Queens

Number of results = 92
Result #1 4 2 5 8 6 1 3 7
Result #2 1 7 4 6 8 2 5 3
Result #3 4 2 8 5 7 1 3 6
Result #4 1 5 8 6 3 7 2 4
Result #5 4 1 5 8 6 3 7 2
Result #6 2 7 3 6 8 5 1 4
Result #7 7 1 3 8 6 4 2 5
Result #8 5 2 4 6 8 3 1 7
Result #9 5 7 1 3 8 6 4 2
Result #10 5 1 8 6 3 7 2 4
Result #11 1 6 8 3 7 4 2 5
Result #12 4 2 7 3 6 8 1 5
Result #13 3 1 7 5 8 2 4 6
Result #14 3 6 2 7 5 1 8 4
Result #15 5 1 4 6 8 2 7 3
Result #16 6 4 2 8 5 7 1 3
Result #17 3 6 2 5 8 1 7 4
Result #18 1 7 5 8 2 4 6 3
Result #19 3 7 2 8 5 1 4 6
Result #20 2 6 1 7 4 8 3 5
Result #21 3 7 2 8 6 4 1 5
Result #22 4 6 8 2 7 1 3 5
Result #23 4 1 5 8 2 7 3 6
Result #24 7 4 2 8 6 1 3 5
Result #25 3 6 8 2 4 1 7 5
Result #26 5 1 8 4 2 7 3 6
Result #27 7 4 2 5 8 1 3 6
Result #28 4 7 5 2 6 1 3 8
Result #29 7 3 8 2 5 1 6 4
Result #30 5 7 2 6 3 1 8 4
Result #31 5 7 2 4 8 1 3 6
Result #32 4 7 3 8 2 5 1 6
Result #33 4 7 1 8 5 2 6 3
Result #34 7 3 1 6 8 5 2 4
Result #35 6 3 7 2 8 5 1 4
Result #36 6 1 5 2 8 3 7 4
Result #37 4 8 1 5 7 2 6 3
Result #38 6 3 1 7 5 8 2 4
Result #39 6 3 7 2 4 8 1 5
Result #40 6 4 1 5 8 2 7 3
Result #41 5 7 2 6 3 1 4 8
Result #42 5 7 1 4 2 8 6 3
Result #43 3 5 2 8 1 7 4 6
Result #44 4 6 1 5 2 8 3 7
Result #45 2 7 5 8 1 4 6 3
Result #46 5 3 1 6 8 2 4 7
Result #47 4 2 7 5 1 8 6 3
Result #48 6 3 1 8 5 2 4 7
Result #49 3 8 4 7 1 6 2 5
Result #50 6 8 2 4 1 7 5 3
Result #51 5 3 1 7 2 8 6 4
Result #52 2 5 7 4 1 8 6 3
Result #53 3 6 2 7 1 4 8 5
Result #54 6 3 1 8 4 2 7 5
Result #55 4 2 8 6 1 3 5 7
Result #56 8 3 1 6 2 5 7 4
Result #57 3 5 8 4 1 7 2 6
Result #58 4 8 1 3 6 2 7 5
Result #59 6 3 5 8 1 4 2 7
Result #60 6 3 7 4 1 8 2 5
Result #61 8 4 1 3 6 2 7 5
Result #62 8 2 5 3 1 7 4 6
Result #63 6 3 5 7 1 4 2 8
Result #64 4 8 5 3 1 7 2 6
Result #65 7 2 6 3 1 4 8 5
Result #66 2 4 6 8 3 1 7 5
Result #67 5 2 4 7 3 8 6 1
Result #68 3 5 2 8 6 4 7 1
Result #69 4 6 8 3 1 7 5 2
Result #70 4 7 5 3 1 6 8 2
Result #71 3 6 4 2 8 5 7 1
Result #72 2 6 8 3 1 4 7 5
Result #73 5 7 4 1 3 8 6 2
Result #74 7 5 3 1 6 8 2 4
Result #75 4 2 7 3 6 8 5 1
Result #76 6 4 7 1 8 2 5 3
Result #77 5 2 6 1 7 4 8 3
Result #78 7 2 4 1 8 5 3 6
Result #79 6 2 7 1 3 5 8 4
Result #80 8 2 4 1 7 5 3 6
Result #81 3 6 8 1 5 7 2 4
Result #82 5 2 8 1 4 7 3 6
Result #83 5 3 8 4 7 1 6 2
Result #84 3 6 8 1 4 7 5 2
Result #85 5 8 4 1 7 2 6 3
Result #86 3 6 4 1 8 5 7 2
Result #87 3 5 7 1 4 2 8 6
Result #88 6 2 7 1 4 8 5 3
Result #89 6 4 7 1 3 5 2 8
Result #90 5 8 4 1 3 6 2 7
Result #91 2 5 7 1 3 8 6 4
Result #92 2 8 6 1 3 5 7 4

Command to execute: quit

Threading Statistics:
 Num_Initial_Thread_Servers : 10
 Num_Dynamically_Allocated_Thread_Servers : 0
 Max_Waiting_Threads (for server task): 74
 Max_Active : 118
 Max_Active_Masters : 133
 Max_Sub_Threads_Per_Master : 87
 Max_Waiting_For_Threads (to finish): 37171

Thursday, September 8, 2011

Another ParaSail example that compiles and runs

Here is a version of parallel Quicksort that now compiles and runs through the ParaSail compiler. This is parallel but non-recursive. It uses a parallel pair of continue loop statements rather than recursion.  It uses "slicing" on the array.  A[..] takes an array and returns a "slice" of the array that contains all elements of the array.  After partitioning the array, the code splits into two threads and then continues with a left "slice" and a right "slice" of the array.  The "<=>" operator performs a swap operation.

There is a simple Test_Sort test function at the bottom.  It uses a very simple random number generator to populate an array and then sort it (twice).

At the very bottom we have the result of running the program.
interface Sorting<Array_Type is Indexable<Comparable<>, Countable<>>> is
    func Quicksort(var A : Array_Type);
          // Sort Arr according to the sorting op "<" which returns
          // True if Left must appear before Right in the sorted order.
          // Before returns False if Left = Right.
end interface Sorting;

class Sorting is
    func Quicksort(var A : Array_Type) is
        // Handle short arrays directly.  Partition longer arrays.
        for Arr : Slice<Array_Type> => A[..] while Length(Arr) > 1 loop
            if Length(Arr) == 2 then
               if Arr[Arr.Last] < Arr[Arr.First] then
                   // Swap elements
                   Arr[Arr.First] <=> Arr[Arr.Last];
               end if;
               // Partition array
               const Mid := Arr[Arr.First + Length(Arr)/2];
               var Left := Arr.First;
               var Right := Arr.Last;
               until Left > Right loop
                 var New_Left := Right+1;
                 var New_Right := Left-1;
                   // Find item in left half to swap
                   for I in Left .. Right forward loop
                       if not (Arr[I] < Mid) then
                           // Found an item that can go into right partitition
                           New_Left := I;
                           if Mid < Arr[I] then
                               // Found an item that *must* go into right part
                               exit loop;
                           end if;
                       end if;
                   end loop;
                   // Find item in right half to swap
                   for J in Left .. Right reverse loop
                       if not (Mid < Arr[J]) then
                           // Found an item that can go into left partitition
                           New_Right := J;
                           if Arr[J] < Mid then
                               // Found an item that *must* go into left part
                               exit loop;
                           end if;
                       end if;
                   end loop;
                 end block;
                 if New_Left > New_Right then
                     // Nothing more to swap
                     // Exit loop and recurse on two partitions
                     Left := New_Left;
                     Right := New_Right;
                     exit loop;
                 end if;
                 // Swap items
                 Arr[New_Left] <=> Arr[New_Right];
                 // continue looking for items to swap
                 Left := New_Left + 1;
                 Right := New_Right - 1;
               end loop;
               // At this point, "Right" is right end of left partition
               // and "Left" is left end of right partition
               // and the partitions don't overlap
               // and neither is the whole array
               // and everything in the left partition can precede Mid
               // and everything in the right partition can follow Mid
               // and everything between the partitions is equal to Mid.
               {Left > Right;
                Right < Arr.Last;
                Left > Arr.First;
                (for all I in Arr.First .. Right => not (Mid < Arr[I]));
                (for all J in Left .. Arr.Last => not (Arr[J] < Mid));
                (for all K in Right+1 .. Left-1 => 
                  not (Mid < Arr[K]) and not (Arr[K] < Mid))}
               // continue with two halves in parallel
               continue loop with Arr[Arr.First .. Right];
               continue loop with Arr[Left .. Arr.Last];
            end if;
        end loop;
   end func Quicksort;
end class Sorting;

func Random(var Seed : Univ_Integer; Mult, Mod : Univ_Integer) 
  -> Univ_Integer is
    Seed := Seed * Mult mod Mod;
    return Seed;
end func Random;

func Test_Sort(Len : Univ_Integer) is
    // For Random
    const Mult := 7**5;
    const Mod := 2**31 - 1;
    var Seed := Len;
    Println("Seed = " | Seed | ", Mult = " | Mult | ", Mod = " | Mod);

    type My_Sorter is Sorting<Vector<Univ_Integer>>;
    var Vec : Vector<Univ_Integer> := [];

    for I in 1..Len loop
        Vec |= Random(Seed, Mult, Mod) mod 100;
    end loop;

    var Vec2 := Vec;

    Println("Before sort, Vec = ");
    for I in 1 .. Length(Vec) forward loop
        Print(" " | Vec[I]);
        if I < Length(Vec) then
        end if;
    end loop;


    Println("After sort, Vec = ");
    for I in 1 .. Length(Vec) forward loop
        Print(" " | Vec[I]);
        if I < Length(Vec) then
        end if;
    end loop;


    Println("After 2nd sort, Vec2 = ");
    for I in 1 .. Length(Vec2) forward loop
        Print(" " | Vec2[I]);
        if I < Length(Vec2) then
        end if;
    end loop;

end func Test_Sort;
Here is the result of compiling and running the program. "aaa.psi" contains the standard ParaSail library of modules. "qsort6.psl" is given above. We are using the compiler interactively here, so we can run stand-alone ParaSail operations. It also can run non-interactively, by giving "-command <operation> <param1> ..." after the list of source file names on the command line. When in interactive mode, it dumps out some virtual machine threading statistics after the user "quit"s. These are at the very bottom. In this example, we have 21 threads active simultaneously at one point during execution.
% pslc aaa.psi qsort6.psl
Parsing aaa.psi
Parsing qsort6.psl
---- Beginning semantic analysis ----
 52 trees in library.
Done with First pass.
Done with Second pass.
Done with Pre codegen pass.
Done with Code gen.
Command to execute: Test_Sort 20

Seed = 20, Mult = 16807, Mod = 2147483647
Before sort, Vec = 
 40, 86, 55, 37, 30, 52, 80, 49, 49, 34, 71, 30, 88, 40, 93, 90, 29, 80, 71, 93
After sort, Vec = 
 29, 30, 30, 34, 37, 40, 40, 49, 49, 52, 55, 71, 71, 80, 80, 86, 88, 90, 93, 93
After 2nd sort, Vec2 = 
 29, 30, 30, 34, 37, 40, 40, 49, 49, 52, 55, 71, 71, 80, 80, 86, 88, 90, 93, 93
Command to execute: quit

Threading Statistics:
 Num_Initial_Thread_Servers : 10
 Num_Dynamically_Allocated_Thread_Servers : 0
 Max_Waiting_Threads (for server task): 6
 Max_Active : 21
 Max_Active_Masters : 17
 Max_Sub_Threads_Per_Master : 6
 Max_Waiting_For_Threads (to finish): 113

Wednesday, September 7, 2011

ParaSail compiler reaches a milestone

The ParaSail compiler has reached a bit of a milestone, in that it now can compile and run what might be considered to be "interesting" programs.  Annotations are not yet enforced, and explicitly concurrent lock-based objects are not yet there, but many other things are working, including implicit and explicit parallelism, dynamic storage management using expandable/shrinkable objects (rather than pointers and garbage collection), fully-shared generic template instantiations, etc.  We are trying to solidify the features that are currently supported so we can make a version of the prototype compiler available for experimentation by others within the next couple of weeks.

Below is one of the "interesting" programs.  This one is an implementation of balanced "AA" trees.  This doesn't illustrate any explicit parallelism, but does illustrate creating and updating interesting data structures without using explicit pointers. Pointer-free data structures allow the compiler to easily understand any aliasing, since there is no hidden sharing between distinct objects. That allows the compiler to eliminate race conditions at compile-time.

Here is the interface to the AA_Tree module. (As a side-note, the program that "HTML"-ized this code was itself written in ParaSail. I've included it at the bottom of this posting.)
interface AA_Tree<Element is Comparable<>> is

    // This module implements a balanced "AA" tree, originally
    // described by Arne Andersson in the "Proceedings of the Workshop
    // on Algorithms and Data Structures," pp 60-71, Springer Verlag, 1993.
    // The following algorithm and descriptions were taken from the
    // WikiPedia article on AA_Tree: 
    // Note that various additional checks for a null tree have been added.

    // Only two operations are needed for maintaining balance in an AA tree.
    // These operations are called skew and split. Skew is a right rotation
    // when an insertion or deletion creates a left horizontal link. Split
    // is a conditional left rotation when an insertion or deletion creates two
    // horizontal right links, which once again corresponds to two
    // consecutive red links in red-black trees.

    op "[]"() -> optional AA_Tree;
        // Create an empty tree

    func Insert(var T : optional AA_Tree; X : Element);
        // input: X, the value to be inserted, and 
        // T, the root of the tree to insert it into.
        // output: A balanced T' including X.

    func Delete(var T : optional AA_Tree; X : Element);
        // input: X, the value to delete, and T, 
        // the root of the tree from which it should be deleted.
        // output: T', balanced, without the value X.

    op "in"(X : Element; T : optional AA_Tree) -> Boolean;

    func Overlapping(T : optional AA_Tree; X : Element) -> optional Element;
        // input: X, the value to find, and T, 
        // the root of the tree to be searched.
        // output: the element equal to or "unordered" relative to X.

    op "|="(var T : optional AA_Tree; X : Element);

    func First(T : optional AA_Tree) -> optional Element;
      // Return first (smallest) element in tree

    func Last(T : optional AA_Tree) -> optional Element;
      // Return last (greatest) element in tree

    func Remove_First(var T : optional AA_Tree) -> optional Element;
      // Remove first (smallest) element in tree

    func Remove_Last(var T : optional AA_Tree) -> optional Element;
      // Remove last (greatest) element in tree

    func Remove_Any(var T : optional AA_Tree) -> optional Element;
      // Remove some element from tree

    func Count(T : optional AA_Tree) -> Univ_Integer;
      // Return a count of the nodes in the tree

end interface AA_Tree;
Here is the class that provides the implementation for the AA_Tree module:
class AA_Tree is
    var Left : optional AA_Tree;
    var Right : optional AA_Tree;
    var Value : Element;
    var Level : Univ_Integer := 0;

    func Node(Value : Element; Level : Univ_Integer; Left : optional AA_Tree;
      Right : optional AA_Tree) -> AA_Tree is
        // Create a new tree.
        return (Left => Left, Right => Right, Value => Value,
          Level => Level);
    end func Node;

    func Is_Leaf(T : optional AA_Tree) -> Boolean is
        return T not null and then
          T.Left is null and then T.Right is null;
    end func Is_Leaf;

    func Leftmost(ref T : optional AA_Tree) -> ref optional AA_Tree is
        for L => T loop
            if L not null and then L.Left not null then
                // Continue with Left until we reach null
                continue loop with L.Left;
                // Found left-most
                return L;
            end if;
        end loop;
    end func Leftmost;

    func Successor(T : optional AA_Tree) -> optional Element is
        // Return element in tree greater than but closest to T.Value
        if T.Right not null then
            return Leftmost(T.Right).Value;
            return null;
        end if;
    end func Successor;

    func Rightmost(ref T : optional AA_Tree) -> ref optional AA_Tree is
        for R => T loop
            if R not null and then R.Right not null then
                // Keep following down Right side
                continue loop with R.Right;
                // Found right-most
                return R;
            end if;
        end loop;
    end func Rightmost;

    func Predecessor(T : optional AA_Tree) -> optional Element is
        // Return element in tree less than but closest to T.Value
        if T.Left not null then
            return Rightmost(T.Left).Value;
            return null;
        end if;
    end func Predecessor;

    func Skew(var T : optional AA_Tree) is
      // input: T, a node representing an AA tree that needs to be rebalanced.
      // output: T' Another node representing the rebalanced AA tree.

        if T not null and then
          T.Left not null and then
          T.Left.Level == T.Level then
            // The current T.Left becomes new root

            // Exchange value of T.Left with root
            T.Value <=> T.Left.Value;
            // Move old root and T.Left.Right over to right side of tree
            T.Left.Right <=> T.Right;
            T.Left.Left <=> T.Right;
            T.Left <=> T.Right;
        end if;
    end func Skew;

    func Split(var T : optional AA_Tree) is
        // input: T, a node representing an AA tree that needs to be rebalanced.
        // output: T' Another node representing the rebalanced AA tree.

        if T not null and then
          T.Right not null and then
          T.Right.Right not null and then
          T.Level == T.Right.Right.Level then
            // T.Right becomes the new root
            // Exchange value and level between root and T.Right
            T.Value <=> T.Right.Value;
            T.Level <=> T.Right.Level;

            // Move old root and T.Right.Left to left side of tree
            T.Left <=> T.Right.Right;
            T.Right.Left <=> T.Right.Right;
            T.Left <=> T.Right;

            // Increment level
            T.Level += 1;
        end if;
    end func Split;

    func Decrease_Level(var T : optional AA_Tree) is
        // input: T, a tree for which we want to remove links that skip levels.
        // output: T with its level decreased.

        if T is null then
        end if;
        var Should_Be : Univ_Integer := 1;

        if T.Left not null then
            Should_Be := T.Left.Level + 1;
        end if;

        if T.Right not null then
            Should_Be := Min(Should_Be, T.Right.Level + 1);
        end if;
        if Should_Be < T.Level then
            T.Level := Should_Be;
            if T.Right not null and then
              Should_Be < T.Right.Level then
                T.Right.Level := Should_Be;
            end if;
        end if;
    end func Decrease_Level;


    op "[]"() -> optional AA_Tree is
        // Create an empty tree
        return null;
    end op "[]";

    // Insertion begins with the normal binary tree search and insertion
    // procedure. Then, as the call stack unwinds (assuming a recursive
    // implementation of the search), it's easy to check the validity of the
    // tree and perform any rotations as necessary. If a horizontal left link
    // arises, a skew will be performed, and if two horizontal right links
    // arise, a split will be performed, possibly incrementing the level of the
    // new root node of the current subtree. Note, in the code as given above,
    // the increment of T.Level. This makes it necessary to continue checking
    // the validity of the tree as the modifications bubble up from the leaves.
    func Insert(var T : optional AA_Tree; X : Element) is
        // input: X, the value to be inserted, and 
        // T, the root of the tree to insert it into.
        // output: A balanced T' including X.

        // Do the normal binary tree insertion procedure. 
        // Set the result of the recursive call to the correct 
        // child in case a new node was created or the
        // root of the subtree changes.

        if T is null then
            // Create a new leaf node with X.
            T := Node(X, 1, null, null);
        end if;

        case X =? T.Value of
          [#less] =>
            Insert(T.Left, X);
          [#greater] =>
            Insert(T.Right, X);
          [#equal | #unordered] =>
            // Note that the case of X == T.Value is unspecified. 
            // As given, an insert will have no effect. 
            // The implementor may desire different behavior.
        end case;

        // Perform skew and then split. 
        // The conditionals that determine whether or
        // not a rotation will occur or not are inside 
        // of the procedures, as given above.

    end func Insert;

    // As in most balanced binary trees, the deletion of an internal node can
    // be turned into the deletion of a leaf node by swapping the internal node
    // with either its closest predecessor or successor, depending on which are
    // in the tree or on the implementor's whims. Retrieving a predecessor is
    // simply a matter of following one left link and then all of the remaining
    // right links. Similarly, the successor can be found by going right once
    // and left until a null pointer is found. Because of the AA property of
    // all nodes of level greater than one having two children, the successor
    // or predecessor node will be in level 1, making their removal trivial.
    // To re-balance a tree, there are a few approaches. The one described by
    // Andersson in his original paper is the simplest, and it is described
    // here, although actual implementations may opt for a more optimized
    // approach. After a removal, the first step to maintaining tree validity
    // is to lower the level of any nodes whose children are two levels below
    // them, or who are missing children. Then, the entire level must be skewed
    // and split. This approach was favored, because when laid down
    // conceptually, it has three easily understood separate steps:
    //     Decrease the level, if appropriate.
    //     Skew the level.
    //     Split the level.
    // However, we have to skew and split the entire level this time instead of
    // just a node, complicating our code.

    func Delete(var T : optional AA_Tree; X : Element) is
        // input: X, the value to delete, and T, 
        // the root of the tree from which it should be deleted.
        // output: T', balanced, without the value X.

        if T is null then
            // Not in tree -- should we complain?
        end if;

        case X =? T.Value of
          [#less] =>
            Delete(T.Left, X);
          [#greater] =>
            Delete(T.Right, X);
          [#equal] =>
            // If we're a leaf, easy, otherwise reduce to leaf case. 
            if Is_Leaf(T) then
                T := null;
            elsif T.Left is null then
                // Get successor value and delete it from right tree,
                // and set root to have that value
                const Succ := Successor(T);
                Delete(T.Right, Succ);
                T.Value := Succ;
                // Get predecessor value and delete it from left tree,
                // and set root to have that value
                const Pred := Predecessor(T);
                Delete(T.Left, Pred);
                T.Value := Pred;
            end if;
          [#unordered] =>
            // Not in tree; should we complain?
        end case;

        // Rebalance the tree. Decrease the level of all nodes in this level if
        // necessary, and then skew and split all nodes in the new level.

        if T is null then
        end if;

        if T.Right not null then
        end if;
    end func Delete;

    op "in"(X : Element; T : optional AA_Tree) -> Result : Boolean is
        for P => T while P not null loop
            case X =? P.Value of
              [#less] =>
                continue loop with P.Left;
              [#greater] =>
                continue loop with P.Right;
              [#equal] =>
                return #true;
              [#unordered] =>
                return #false;
            end case;
        end loop;
        return #false;  // Not found
    end op "in";

    func First(T : optional AA_Tree) -> optional Element is
      // Return first (smallest) element in tree
        if T is null then
            return null;
            return Leftmost(T).Value;
        end if;
    end func First;

    func Last(T : optional AA_Tree) -> optional Element is
      // Return last (greatest) element in tree
        if T is null then
            return null;
            return Rightmost(T).Value;
        end if;
    end func Last;

    func Remove_First(var T : optional AA_Tree) -> Result : optional Element is
      // Remove first (smallest) element in tree
        Result := First(T);
        if Result not null then
            Delete(T, Result);
        end if;
    end func Remove_First;

    func Remove_Last(var T : optional AA_Tree) -> Result : optional Element is
      // Remove last (greatest) element in tree
        Result := Last(T);
        if Result not null then
            Delete(T, Result);
        end if;
    end func Remove_Last;

    func Remove_Any(var T : optional AA_Tree) -> Result : optional Element is
      // Remove some element from tree
        if T is null then
            return null;
        end if;
        Result := T.Value;
        if Result not null then
            Delete(T, Result);
        end if;
    end func Remove_Any;

    func Count(T : optional AA_Tree) -> Univ_Integer is
      // Return a count of the nodes in the tree
        if T is null then
            return 0;
            return Count(T.Left) + Count(T.Right) + 1;
        end if;
    end func Count;

    op "|="(var T : optional AA_Tree; X : Element) is
        Insert(T, X);
    end op "|=";

    func Overlapping(T : optional AA_Tree; X : Element) -> optional Element is
        // input: X, the value to find, and T, 
        // the root of the tree to be searched.
        // output: the element equal to or "unordered" relative to X.
        if T is null or else T.Value is null then
            return null;
            case X =? T.Value of
              [#less] =>
                return Overlapping(T.Left, X);
              [#greater] =>
                return Overlapping(T.Right, X);
              [#equal | #unordered] =>
                // Close enough
                return T.Value;
            end case;
        end if;
    end func Overlapping;

end class AA_Tree;
Here is a small test program for AA_Tree:
func Test_AA_Tree(A : Univ_Integer; B : Univ_Integer; C : Univ_Integer) is
    type Univ_Tree is AA_Tree<Univ_Integer>;
    var T : Univ_Tree := [];
    var X : Univ_Integer := A;

    Insert(T, A);
    Println("Count = " | Count(T) | " after insert of " | A);
    Insert(T, B);
    Println("Count = " | Count(T) | " after insert of " | B);
    Insert(T, C);
    Println("Count = " | Count(T) | " after insert of " | C);

    Insert(T, A);
    Println("Count = " | Count(T) | " after another insert of " | A);

    Println(A | " in T = " | [[A in T]]);
    Println(B | " in T = " | [[B in T]]);
    Println(C | " in T = " | [[C in T]]);
    Println("7 in T = " | [[7 in T]]);

    for E := Remove_First(T) then Remove_First(T) while E not null loop
        Println("Remove_First = " | E);
    end loop;

    Println("Count after loop : " | Count(T));

    for I in 1..10 forward loop
        Insert(T, I);
        Println("Count = " | Count(T) | " after insert of " | I);
    end loop;

    for L := Remove_Last(T) then Remove_Last(T) while L not null loop
        Println("Remove_Last = " | L);
    end loop;

    Println("Count after loop : " | Count(T));

    for J in 1..10 reverse loop
        Insert(T, J);
        Println("Count = " | Count(T) | " after insert of " | J);
    end loop;

    Println("Count after loop : " | Count(T));

    Println("Overlapping(T, 5) = " | Overlapping(T, 5));

    for Z := Remove_Any(T) then Remove_Any(T) while Z not null loop
        Println("Remove_Any = " | Z);
    end loop;

    Println("Count after loop : " | Count(T));

    for K in 1..10 loop
        Insert(T, K);
        Println("Count = " | Count(T) | " after insert of " | K);
    end loop;

    for F := Remove_First(T) then Remove_First(T) while F not null loop
        Println("Remove_First = " | F);
    end loop;

    Println("Count after loop : " | Count(T));

end func Test_AA_Tree;
Here is the ParaSail program that was used to "HTML"-ize the listings above (as well as the one below!). Not terribly sophisticated, but illustrates some of the character handling:
func Html_Escape(C : Univ_Character) -> Univ_String is
    // Do single-character escapes
    case C of
      ['<'] =>
        return "&lt;";
      ['>'] =>
        return "&gt;";
      ['&'] =>
        return "&amp;";
      ['\\'] =>
        return "\\";    // Prevent "Print" from expanding control chars
      [..] =>
        return "" | C;  // Convert character into a string
    end case;
end func Html_Escape;

func Htmlize_Line(Orig : Univ_String) -> Result : Univ_String is
    // bold lower case words that are not in comments or
    // character, string, or enum literals

    Result := "";
    var I := 1;
    const L := Length(Orig);
    var State : Univ_Enumeration := #other;
    while I <= L loop
        var C := Orig[I];
        case C of
          ['\\'] =>
            if State == #string_literal or else State == #char_literal then
                // skip next character no matter what it is
                if I < L then
                    Result |= Html_Escape(C);
                    I += 1;
                    C := Orig[I];
                end if;
            end if;
          ['/'] =>
            if I < L and then Orig[I+1] == '/' then
                // comment, italicize it
                Result |= "<i>" | Html_Escape(C);
                while I < L loop
                    I += 1;
                    Result |= Html_Escape(Orig[I]);
                end loop;
                Result |= "</i>";
                C := null;
            end if;
          ['a' .. 'z'] =>
            if State == #other then
                // Presume this is a reserved word, so bold it
                Result |= "<b>" | C;
                while I < L and then Orig[I+1] in 'a' .. 'z' loop
                    I += 1;
                    Result |= Orig[I];
                end loop;
                Result |= "</b>";
                C := null;
            end if;
          ['#' | '0'..'9' | 'A' .. 'Z' | '_'] =>
            // Presume this is not a reserved word, pass through as is
            if State == #other then
                State := #unreserved;
            end if;

          ['"'] =>
            if State == #string_literal then
                // End of string literal
                State := #other;
            elsif State != #char_literal then
                State := #string_literal;
            end if;

          ['\''] =>
            if State == #char_literal then
                // End of char literal
                State := #other;
            elsif State != #string_literal then
                State := #char_literal;
            end if;

          [..] =>
            if State != #string_literal and then State != #char_literal then
                State := #other;
            end if;
        end case;

        if C not null then
            Result |= Html_Escape(C);
        end if;
        I += 1;
    end loop;

end func Htmlize_Line;

func Htmlize() is
    // Htmlize the standard input, 
    //  putting the result on the standard output
        const Line : Univ_String := Readln();
        if Line is null then
            // End of file indicated by "null"
            exit loop;
        end if;
    end loop;
end func Htmlize;

Friday, September 2, 2011

ParaSail on Intel Parallel Programming Talk video

The talk about ParaSail at OSCON 2011 generated a nice bit of media attention, and as a result we were invited to be on the Intel Software Network "Parallel Programming Talk" video show.  The show is now online at:

There is a relatively long intro discussion of about 8 minutes, and then we get into the nitty gritty of ParaSail.

Saturday, July 30, 2011

A load-and-null-out operation

As we have continued to write more programs in ParaSail, we have found the pointer-free expandable-object data structuring primitives very interesting to use.  A simple tree structure can be defined as:

interface Binary_Tree<Element_Type is Assignable<>> is
    var Left, Right : optional Binary_Tree;
    var Contents : Element_Type;
end interface Binary_Tree;

In most cases you would keep this structure private by declaring it inside the class defining the Binary_Tree module rather than declaring it in the externally-visible interface, but this illustrates the basic structuring technique, using optional to allow recursive structures to be created. 

Because there are no pointers, only sub-objects, essentially any arbitrarily complex data structure can be copied using a simple assignment:
  var Copy_Of_Tree : optional Binary_Tree := Original_Tree;

This will create a copy of Original_Tree, no matter how complex it is.  Similarly, we can expand a tree by assigning a new tree into its Left or Right subtree:
  Original_Tree.Left := Copy_Of_Tree;

So what did the above two assignments do?  Well they made a complete copy of the Original_Tree, and then assigned that copy into the left subtree of the Original_Tree, wiping out whatever was in the left subtree before.  But we now have a complete copy of what was in the Original_Tree.Left before in Original_Tree.Left.Left.  And Original_Tree.Left.Right is now identical in structure to Original_Tree.Right.  We could have done this without explicitly declaring the intermediate "Copy_Of_Tree" object, with the same effect:
  Original_Tree.Left := Original_Tree; 
I'm not sure whether what we just did was of any use, but it does give you a feel for the power of expandable objects.  The user doesn't have to write explicitly any deep copy operation, since from ParaSail's point of view, these are just subobjects, and ":=" assigns the whole thing, including all of the subobjects. 

The old contents of the left-hand side of an assignment are wiped out, and automatically reclaimed immediately -- no need for the user to write a deep reclaim operation.  We don't need to wait for a garbage collector to decide whether it is safe to reclaim the storage associated with the old contents, since there is no sharing between objects in ParaSail.  If we overwrite the contents of an object or part of an object, whatever was there before can be reclaimed without danger of creating any dangling references.

Here is another example:
  Original_Tree := Original_Tree.Left;
This wipes out the old contents of Original _Tree and replaces it with a copy of its left subtree.  But there seems to be some unnecessary copying going on here.  The underlying sequence is:
  • Make a copy of Original_Tree.Left
  • Reclaim the old contents of Original_Tree
  • Overwrite it with the copy of Original_Tree.Left
This makes a complete copy of Original_Tree.Left, and then proceeds to reclaim all of Original_Tree (including the left subtree), and then stores the copy of the left subtree back into Original_Tree.  But wouldn't it make more sense to just carve off the left subtree, leaving behind a stub (i.e. null), then reclaim Original_Tree which now has a null left subtree, and then set Original_Tree to be the carved-off left subtree?  In fact, if the compiler were somewhat smarter, that is exactly what it would do, and should be expected to do, since it knows that Original_Tree.Left is about to be destroyed by the assignment to Original_Tree, so saving its content and replacing it with null rather than making a complete copy of it would be equivalent and more efficient.  Be that as it may, it is conceivable that there are times when the compiler can't see what is obvious to us, or perhaps the compiler is still just a prototype and isn't quite as smart as it will be eventually (;-).  In that case, we might want to be able to be explicit in cases where we want to fetch the value of an object or a part of an object, and after we fetch the value we want to set the object to null, or perhaps to some other appropriate value.

Given this situation, which seems like it might come up fairly frequently when making structural modifications to a data structure (such as rebalancing the tree), or destructively removing elements from a data structure (e.g. "Remove_First(Queue)"), we believe it might be useful to have a notion of load-and-null-out.  That is, we want the value of Original.Left_Tree, but after fetching the value, we are "done" with it, so set it to null.  This means we may not need to make a copy of the subobject, since it has been carved out of its old enclosing object, with a null left behind.

We considered various notations for representing load-and-null-out, and came up with the notion of a deferred assignment, that is an assignment where before we overwrite the left-hand-side, we fetch its old value and return it.  This is reminiscent of the compare-and-swap operation, or fetch-and-add, or the post increment X++ of C (and PDP-11/Vax-11 fame, for those familiar with those older DEC machines).  Here is a tentative notation for a deferred assignment:

   Original_Tree := (Original_Tree.Left ::= null); 

What the "::= null" operation means is to fetch the value of Original_Tree.Left, and after doing so, assign it to null.  One could imagine generalizing this extra ':' notation to support post-increment:

X := A[(I :+= 1)]; 

This would mean fetch the value of I, and after doing so, apply the "+= 1" operation to it.  It is not obvious whether this generalization is a good idea, or just cute.  But the deferred assignment of null seems like an operation that will be quite useful in the pointer-free world of ParaSail, to provide more control when restructuring a complex object.

Monday, July 25, 2011

Adapting one interface to implement another

We bumped into an interesting problem in ParaSail recently.  We have an abstract module Countable which has the following interface:
abstract interface Countable<> is
    op "+"(Left : Countable; Right : Univ_Integer) -> Countable;
    op "+"(Left : Univ_Integer; Right : Countable) -> Countable;
    op "-"(Left : Countable; Right : Univ_Integer) -> Countable;
    op "-"(Left, Right : Countable) -> Univ_Integer;
    op "=?"(Left, Right : Countable) -> Ordering;
end interface Countable;
This interface is used when defining a "countable interval" such as "X .. Y" where you want to be able to iterate from X up to Y, even though X and Y are not themselves of an integer type. For example, if X and Y are characters, it makes sense to define an interval such as 'a' .. 'z' and there is a desire to be able to go from 'a' to the next character in the interval, so by using the "+" operator from Countable that is easy to do. Just add 1. Similarly, we can iterate through the interval in reverse by subtracting 1. Or we can find out how big is the interval X..Y by computing (Y - X) + 1, where we are using the second "-" operator.

Other examples of "countable" types are representations of time, where you can add and subtract some number of clock ticks, or compute the number of clock ticks between two times, even if the "time" type itself isn't necessarily represented as a single integer. And in general any ordered enumeration type (such as Enum<[#monday,#tuesday,#wednesday, ...]>) might want to be considered Countable, so that intervals can be defined and manipulated.

A Countable_Set abstraction would be useful as a way to represent sets of Countable elements, while still efficiently representing contiguous ranges of values such as "1..1000" as part of the set. For example:
interface Countable_Set<Element_Type is Countable<>> is
    op ".."(Left, Right : Element_Type) -> Countable_Set;
    op "|"(Left, Right : Countable_Set) -> Countable_Set;
    op "in"(Left : Element_Type; Right : Countable_Set) -> Boolean;
    func Count(CS : Countable_Set) -> Univ_Integer;
end interface Countable_Set;
Implementing the Count function clearly will need to make use of the "+" or "-" Countable operations. But this now brings us to the question, is Integer itself a Countable type? Can we legally write Countable_Set<Integer>? Well if we look at the binary "+" and "-" operators for Integer we see:
interface Integer<...> is
    op "+"(Left, Right : Integer) -> Integer;
    op "-"(Left, Right : Integer) -> Integer;
end interface Integer;
These don't actually match the operators expected for a Countable type. And if we were to simply add the missing operators, we would create significant ambiguity, since "X + 1" could either resolve to the existing Integer,Integer->Integer "+" or to the added Countable one, Integer,Univ_Integer->Integer "+". Not ideal.

More generally, we can see a situation where a useful abstraction, such as a Countable_Set, expects a type parameter such as Countable<>, and the type we have is close but is missing some of the required operations, and we don't really want to add the missing operations for general use because of ambiguity, or they don't quite do the right thing, or whatever. Ideally we would want to make them available for implementing a given interface or interfaces, but not for general use.

Some languages provide mechanisms for addressing problems like these. In Eiffel, as part of inheriting from another class the derived class can rename some of the operations. With that approach, on inheriting these Countable operations we would rename them to something like "Countable_Plus" and "Countable_Minus" and then define them to do whatever we want. In C++ it is possible to disambiguate particular operations by specifying from which base type they are inherited.

In ParaSail we are pursuing somewhat of a different approach. Essentially we are allowing a module to publicly declare that it is implementing various operations that might be needed to be considered "Countable" or "Hashable" or whatever, while not making them available for "general" use. Here is how the ParaSail Integer module solves the Countable conundrum:
interface Integer<...> is
    op "+"(Left, Right : Integer) -> Integer;
    op "-"(Left, Right : Integer) -> Integer;
      for Countable
    op "+"(Left : Integer; Right : Univ_Integer) -> Integer;
    op "+"(Left : Univ_Integer; Right : Integer) -> Integer;
    op "-"(Left : Integer; Right : Univ_Integer) -> Integer;
    op "-"(Left, Right : Integer) -> Univ_Integer;
end interface Integer;
You can also omit the "for Countable" part and then the operations are available to implement any other module's interface.  But the key thing is that you cannot call these operations directly on an Integer type.  You can only invoke them when "viewing" an Integer as a "Countable" object.  You can have multiple sections after "implements" each section starting with "for Interface1, Interface2, ..." if there are several different sets of operations that need to be implemented to satisfy the needs for different sets of interfaces.  In general situations like this are expected to be rare, but when you bump into one, it is useful to have a way to avoid the ambiguity and still satisfy the needs of the other interface.

Saturday, July 23, 2011

Another slight shift in syntax

As we use ParaSail more, we are making some additional small changes in syntax.  The first one has to do with allowing a component to be declared as a reference to another object.  The ability to return a short-lived object reference is important for user-defined indexing.  We also imagine that certain data structures will want to incorporate references as components.  Such data structures will not allow assignment, but nevertheless they can be useful for iterating over some other data structure.    For example, one might have a complex tree structure, and then an iterator over the structure which contains a reference to the current item in the tree, and references to the enclosing nodes in the tree, so that given the iterator one can generate a reference to the next element of the tree (presuming some ordering such as depth-first left-to-right).

Currently, object references are recognized by using "=>" rather than ":=" for defining their initial value.  However, that is somewhat subtle, and for a component, the initial value can't be specified when the component is declared.  Having already used the term "ref" for parameters that act as references, we have chosen to change the syntax for other objects that are references by explicitly using the term "ref" for them as well.  For example:
    ref X => M[I];
    ref const R => T.Right;
    ref var L => T.Left; 

A "ref" by itself means that the reference is a read-write reference only if the object to which it refers is a variable.  Explicitly using "ref const" makes the reference read-only even if the object to which it refers is a variable.  Explicitly using "ref var" makes the reference read-write, and requires the object to which it refers to be a variable.  So the first example above creates a reference to the Ith element of M, providing read-write access only if M is a variable, the second creates a read-only reference to the Right component of T, and the third creates a read-write reference to the Left component of T, and requires that T itself is a variable.

Having adopted the use of "ref", we can now leave off the "=> obj" part and simply specify a type, and in that way declare a component which will be a reference. Here is an example of an iterator that walks over a tree structure. It uses a "ref" component to point to a particular node in the tree:
    class Tree_Iterator is
        ref Current_Node : Tree_Node;
        var Enclosing_Node : optional Tree_Iterator;
        var Which_Child : Child_Index; 
        func First_Item(ref Root : Tree_Node) -> Tree_Iterator is
            // Return leftmost child of Root to start the iteration
            return Leftmost_Child
              ((Current_Node => Root, Enclosing_Node => null, Which_Child => 0));
        end func First_Item;

        func Leftmost_Child(It : Tree_Iterator) -> Tree_Iterator is
             // Return iterator designating leftmost child
             if Num_Children(It.Current_Node) == 0 then
                 // We are at the leftmost child already
                 return It;
                 // Recurse down the left side
                   (Current_Node => It.Current_Node[1],
                    Enclosing_Node => It,
                    Which_Child => 1);
             end if;
        end func Leftmost_Child;

        func Next_Item(It : Tree_Iterator) -> optional Tree_Iterator is
            // Advance iterator to next item in left-to-right depth-first walk
            if It.Enclosing_Node is null then 
                // All done
                return null;
            elsif It.Which_Child < Num_Children(It.Enclosing_Node.Current_Node) then
                // Return next child of same enclosing node
                return Leftmost_Child
                  ((Current_Node => It.Enclosing_Node[It.Which_Child + 1],
                    Enclosing_Node => It.Enclosing_Node,
                    Which_Child => It.Which_Child + 1));
                // Recurse to go to next sibling of enclosing node
                return Next_Item(It.Enclosing_Node);
            end if;
        end func Next_Item;
    end class Tree_Iterator; 

This Tree_Iterator has a component that is a reference to a node in a tree, an optional Tree_Iterator for the enclosing node in the tree, and an indication of which child the current node is of the enclosing node.

By specifying simply "ref" rather than "ref var" or "ref const" for the Current_Node reference, we are saying that it is a reference to a variable when the enclosing Tree_Iterator object is a variable.

Any type that has a (constructor) function in its interface that takes a "ref" input and produces a new object of the type as an output is presumed to be burying the "ref" somewhere in the object. (Of course the compiler can just "look" in the class and see this, but a client of the module wants to know strictly from looking at the interface.) If the objects of a type incorporate a reference within them, then objects of that type do not permit assignment, since references in ParaSail are always required to be short-lived. The result of such a constructor function therefore can only be used to initialize a new object, be passed as a parameter, or be used to define the next value for a loop variable. The result of such a function cannot be assigned as the new value for an existing object.

Now that we are using "ref" explicitly for objects and components, it makes the syntax used for parameters, where "ref" comes after the parameter name and the ":", seem inconsistent. Hence we are changing the syntax for parameters to more closely match that of objects and components:
    operation_input ::= 
       id ':' type [ := default ]
     | 'var' id ':' type
     | 'ref' [ 'var' | 'const' ] id ':' type
     | 'global' [ 'var' ] id ':' type
     | [ 'locked' | 'queued' ] [ 'var' ] id ':' type 

   operation_output ::=
       [ id ':' ] type
     | 'ref' [ 'var' | 'const' ] [ id ':' ] type

For example:
    func Append(var L : List; E : Element);
    op "indexing"(ref V : Vector; I : Index) -> ref Element;
    func Get_Next(queued var Q : Queue) -> Element;
We will be posting a new draft of the ParaSail reference manual reflecting these changes shortly to the ParaSail google group:

Wednesday, July 13, 2011

Everything in a func?

Here is an issue which is trivial semantically, but potentially has a more substantial effect on the look and feel of the language.  Currently, reflecting to some extent the Pascal heritage, ParaSail uses the terms "function," "procedure," and "operator" for the various kinds of operations.  Functions must have at least one output, procedures may not have any outputs, and operators may have zero or more outputs, but have a name given in quotes and are used for defining operations that connect into special syntax or semantics, such as unary or binary operators, implicit conversions from universal types, etc.

As we go about creating more examples in ParaSail, and compare with various other recent languages, we find the use of these three distinct terms not particularly helpful, and certainly more verbose than most other languages.  On the other hand, the terms do communicate something about the appropriate use of the operations.

We are now leaning toward replacing all three terms with the term "func".  Our sense is this would give the syntax a somewhat less heavy, and perhaps more modern feel.  We would retain the requirement to echo the term at the end of the operation, hence:

func GCD(X, Y : Integer) -> Integer is
    case X =? Y of
      [#less] => return GCD(X, Y mod X);
      [#equal] => return X;
      [#greater] => return GCD(X mod Y, Y);
    end case;
end func GCD;

func Print(F : ref var File; X : Integer) is
    if abs X >= 10 then
        Print(F, X/10);
    end if;
    Print(F, '0' + (X rem 10))
end func Print;

func "|"(X : Set; E : Elem) -> Set is
    return Union(X, Make_Set(E)); 
end func "|";

The above three "func"s would be "function GCD," "procedure Print," and operator "|" using the current ParaSail syntax.  Given that we are already abbreviating "constant" to const and "variable" to var in ParaSail, it doesn't seem inconsistent to adopt a standard abbreviation here for function/procedure/operator, and func is one that appears in a number of languages.

Now this is an issue about which anyone and everyone probably has an opinion...

Thursday, July 7, 2011

Implementing concurrent loops in ParaSail

The implementation of the ParaSail compiler and virtual machine (see are proceeding apace.  Basic support is there for interfaces, classes, operators, functions, procedures, module instantiations, object and type declarations, if, case, while, and assignment statements, user-defined indexing, parallel evaluation of expressions, parallel execution of statements on either side of a "||", etc.  However, a big gap at the moment is for loops, and in particular concurrent for loops.

For loops are a bit unusual in ParaSail, as they support both a continue loop and an exit  loop (i.e. "break") capability in the presence of parallelism.  Here is an example using continue loop:
for X => Root while X not null loop
    case X.Kind of
      [#leaf] => Process(X.Data);
      [#unary] =>
          continue loop with X => X.Operand;
      [#binary] =>
          continue loop with X => X.Left;
          continue loop with X => X.Right;
    end case;
end loop;
Here is an example using exit loop:
const Result : Id_Type; 
for X => Root then X.Left || X.Right while X not null 
  concurrent loop
    if X.Value == Desired_Value then
        exit loop with Result => X.Id;
    end if;
end loop with Result => null;
This first example processes an expression tree, and creates parallelism by using an explicit continue loop statement in concert with a concurrent sequence ("||") construct. The second example searches a binary tree and creates parallelism by both the use of concurrent loop and by having two values in the then part of the for loop header, which will result in the execution of the loop splitting into two separate threads at each binary node.

The semantics of saying concurrent loop rather than simply loop is that the next iteration starts before even starting the current iteration.  If we had said simply loop in the second example, then it would first check the Root node to see if it has the Desired_Value, and only if it did not would we proceed on to the next iteration(s), at which point we would check both the Left and Right subtrees (presuming both were non-null).  Since we said concurrent loop, the iteration on the Left and Right subtrees begins in parallel with executing the loop body on the Root.

The semantics of the exit loop statement are that all other threads within the loop being exited are stopped, and when the thread first reaching the exit loop is the only thread remaining, the assignments specified by the with-values clause are performed.  If the loop ends normally without an exit loop, then the assignments specified by the end with-values clause are performed.  The net effect is that if the Desired_Value is in the tree, Result ends up with the Id of that node.  If it is not found, Result ends up null.

See and for more details about the generalized for loop capabilities.

So given all of the above, what should be the implementation model for a for loop in ParaSail?  As mentioned in the blog entry on the ParaSail virtual machine (PSVM -- see link in first paragraph above), the implementation uses pico-threads to represent the potential parallelism in the code.  There are PSVM instructions for invoking a separate operation, or a local block, as a separate parallel pico-thread.  Currently this is used to support parallel evaluation of expressions or concurrent sequences ("||"), where each operand of a call on an operation, or each side of "||",  can be evaluated in its own pico-thread.  In fact, the compiler is a bit smarter than that, and it doesn't bother to create a pico-thread if the computation of the operand involves only simple built-in operations (such as basic arithmetic, numeric comparisons, etc.).  If it involves an out-of-line call then it becomes a candidate for being turned into a pico-thread (this is clearly an area for tuning of the compiler as more experience is gained).

So it makes sense for the body of a concurrent loop, or a loop that gains parallelism through multiple parallel "next" values or explicit uses of continue loop inside a concurrent sequence, to be executed as a separate pico-thread.  The compiler can turn the loop body into a local operation, with the parameter(s) being the loop index (or indices).  A continue loop is essentially a (tail) recursive call on this local loop-body operation, with the parameter being the next value specified in the with-values clause.  Similarly, if there are explicit "next" values given after then in the loop header, these can be handled using (parallel) calls on the loop-body operation, with the "next" value as the parameter.

Rather than using tail recursion, an alternative is to use a parallel call followed by a return, with the pico-thread for the parallel call being associated with a pico-thread master that controls the entire loop.  At the outer level, the whole loop can then be executed by creating the pico-thread master, and then starting the loop off with a parallel call on the loop-body operation, followed by waiting for the pico-thread master to be complete. 

The overall flow would be:
  • Create pico-thread master.
  • Initiate parallel-call on loop-body operation with parameter referring to initial value of loop index, presuming initial value satisfies the while condition (if any).
  • Wait for pico-thread master to be complete.
At the end of an iteration of a loop, or at a continue loop statement, the flow would be:
  • Determine next value(s) for loop index.  
  • Initiate parallel call(s) on loop-body operation with parameter referring to next value, presuming value satisfies the while condition (if any).
  • Return from the loop-body operation (don't wait for the call(s) to complete).
At the beginning of an iteration of a concurrent loop, the flow would be:
  • Determine next value(s) for loop index.  
  • Initiate parallel call(s) on loop-body operation with parameter referring to next value, presuming value satisfies the while condition (if any).
  • Perform the loop body for the current value.
  • Return from the loop-body operation (don't wait for the call(s) to complete).
When reaching an exit loop statement, the flow would be:
  • Tell pico-thread master of loop to terminate all but the current thread.
  • Wait for other threads to terminate.
  • Perform with-values assignment(s).
  • Return from the loop-body operation.

When the master is complete:
  • If there is a with-values clause on the end loop and the master completed normally, as opposed to being terminated early by an exit loop statement:
    • Perform the assignment(s) specified by the end loop with-values clause.

Friday, June 3, 2011

Upcoming presentations on ParaSail -- Edinburgh and Portland

This summer we will be presenting on ParaSail at:
You can still register for both of these conferences. For OSCON, there is a 20% registration discount if you use the code "os11fos".

Wednesday, May 25, 2011

When null isn't just null -- value representation in ParaSail

The qualifier optional may be applied to any type in ParaSail, effectively producing a type with one additional value, namely the null value.  In many languages, null is only used for pointer types, and is often represented as a zero address.  In ParaSail, we want to be able to add the null value to any type without presuming that the zero value is available for that purpose, so this means that the representation for null will vary depending on the particular type.

For simple types, coming up with a null value is pretty straightforward.  For unsigned integer types, a value one greater than the maximum value could be used for null.   For example, given an unsigned type going from 0 to 100, the value 101 could be used to represent null.  Similarly, for enumeration types that use an internal unsigned integer representation, such as 0 for #false and 1 for #true, the null value could be represented by one more than the maximum internal unsigned integer code, for example 2 for the null value of an optional Boolean type.  For a signed integer type, one less than the minimum value might make sense, particularly on a 2's complement machine where there is one "extra" negative value anyway.  So for a 64-bit signed integer, one might use -2**63+1 .. 2**63-1 for "normal" values of the type, and reserve -2**63 for the null value.  Most floating point representations include the notion of "Not a Number" (NaN), and some NaN value would make sense for null.  Since there are no run-time checks in ParaSail (checking all being done at compile-time), it would be fine to use a "non-signaling" NaN for null.

For more complex types, the representation for null is a bit more interesting.  One common kind of type would be a simple "wrapper," that is, a type defined by a class that has exactly one var component.  For example:
class Box<Contents_Type is Assignable<>> is
    var Contents : Contents_Type;
    function Create(Value : Contents_Type) -> Box is
      return (Contents => Value);
    end function Create;
end class Box; 
In this case, it would be nice to have the wrapper type use exactly the same representation as that of the underlying component type (e.g. Contents_Type).  This would mean that the null value for the wrapper would be the same as the null value for the component type.  This does mean that the component type must not itself be marked as optional, as then there would be no way to distinguish the wrapper being non-null but containing a single null component, from the case where the wrapper itself is null.

So our conclusion is that a wrapper type can use the same representation as its component type so long as the component type is not itself marked optional.  If the component type is itself marked optional, then the wrapper needs to allow for its "own" representation for null, which might in some cases be accommodated by simply allowing for yet one more value if the component type is "simple," or a level of indirection for a more complex component type.

Now what about more complex types?  For example, a type defined by a class with multiple var components:
class Pair<Element_Type is Assignable<>> is
    var Left : Element_Type;
    var Right : Element_Type;
    function Cons(Left, Right : Element_Type) -> Pair is
      return (Left => Left, Right => Right);
    end function Cons;
end class Pair;  
One obvious representation for a type with multiple components is as a sequence of memory cells long enough to accommodate the representation of each of the components, and then some provision for representing null, which could be by piggy-backing on one of the components if it is not itself allowed to be null, or by adding an additional bit to indicate null-ness.  However, in our initial (prototype, ParaSail-Virtual-Machine-based) implementation, we have chosen to represent every object using a single 64-bit memory cell.  This basically means that if the value cannot fit in a single 64-bit cell, it will need to use a level of indirection.  To simplify further, we won't be doing any "packing" initially, so even if the components are each quite short (such as booleans), we will nevertheless go to an indirect representation.  We do anticipate supporting packed arrays, but that would initially be handled by doing explicit shifting and masking, rather than by building in the notion of packing into the ParaSail Virtual Machine instruction set.  In the ParaSail Virtual Machine, pretty much everything occupies a single 64-bit word.

So back to the initial question -- how will we represent objects with multiple components (or with a single component whose type is marked optional)?  And how will we represent null for such objects?  One important thing to remember is that (large) ParaSail objects live in regions, and the regions are associated with stack frames.  Whenever assigning a value to an object, if the new value can't "fit" in the same space as its current value, then the space for the old value needs to be released and the space for the new value needs to be allocated, in the appropriate region.  Since a "ref var" parameter (or subcomponent thereof) might be assigned a new value, it won't necessarily be known at compile-time what region the object being assigned "lives" in.  This suggests that every value for a large object must identify its region, so that its space can be released back to that region when it is freed, and so that the new value can be allocated in that region.  This same requirement applies even if the object has a null value to begin with.  Hence, we are left with the conclusion that a null value for a "large" type needs to identify its region.

Another issue for "large" objects is that we need to know how to reclaim the entire "subtree" of subcomponents when we release the enclosing object.  In some cases we will know the type at compile-time, but in the case of polymorphic objects, or in cases where the type of the object is a formal type parameter of the enclosing module, we won't necessarily know.  This implies that we may want to have some kind of "type-id" associated with large objects.  This then results in the following representation for large objects:

    A 64-bit pointer to:
         [Region, Type-Id, component1, component2, component3, ...]

where the Type-Id provides enough information to know which of the components are themselves "large" and hence need to be recursively released.  In addition, there would probably be a special null Type-Id, which would allow the "is null" operation to be implemented relatively efficiently by comparing the Type-Id against some kind of standard "Null-Type-Id" value.  Each region would only need a single null value, which pointed back to the region, and had the Null-Type-Id.  Such null objects would not be reclaimed if they were the "old" value of the left-hand side of an assignment, since there is only one such value per region, and it is shared among all objects in that region currently having a null value.

So to summarize, we now see that null is not a single value, but rather each simple type potentially has its own representation for null, and for "large" types that use a level of indirection, there is a separate null value for each region.  So the "is null" operation is not necessarily a simple check for equality with the global null value, but instead would depend on the type, and in particular for "large" objects, would be a check of the Type-Id field of the object to see if it has the Null-Type-Id.

On a final note, when a function returns "large" values, it needs to be "told" in which region to allocate the value(s) being returned.  One simple way to do this is for the "large" output parameter(s) to be initialized with a (large) null value by the caller.  Since such a null value identifies the region, the function can use that information when allocating the space for the returned value.

Monday, May 9, 2011

Updated YACC grammar for ParaSail

Here is a more up-to-date YACC grammar from ParaSail.  It uses "--" for comments, but otherwise is pretty vanilla "yacc" syntax.

-- YACC Grammar for ParaSail

-- Single-character delimiters --
%token ',' ';' ':' '.'
%token '+' '-' '*' '/' 
%token '?'
%token '(' ')' '[' ']' '<' '>' ''
%token '|' 
%token '='    -- for error recovery only
%token PRIME -- '''

-- Compound delimiters --
%token COMPARE -- "=?"
%token EQ   -- "=="
%token NEQ  -- "!="
%token GEQ  -- ">="
%token LEQ  -- "<="
%token POWER  -- "**"
%token ASSIGN -- ":="
%token SWAP   -- ":=:"
%token DOT_DOT -- ".."
%token OPEN_CLOSED_INTERVAL -- "<.."
%token OPEN_INTERVAL -- "<..<"
%token CLOSED_OPEN_INTERVAL -- "..<"
%token DOUBLE_COLON  -- "::"
%token REFERS_TO  -- "=>"
%token GIVES    -- "->"
%token IMPLIES    -- "==>"
%token SEQUENCE   -- ";;"
%token PARALLEL   -- "||"
%token PLUS_ASSIGN -- "+="
%token MINUS_ASSIGN -- "-="
%token TIMES_ASSIGN -- "*="
%token DIVIDE_ASSIGN -- "/="
%token POWER_ASSIGN -- "**="
%token CONCAT_ASSIGN -- "|="
%token AND_ASSIGN -- "and="
%token OR_ASSIGN -- "or="
%token XOR_ASSIGN -- "xor="

-- Literals --
%token Char_Literal
%token Enum_Literal
%token Integer_Literal 
%token Real_Literal
%token String_Literal

-- Identifier --
%token Identifier 

-- Reserved words --
%token ABS_kw
%token ABSTRACT_kw
%token ALL_kw
%token AND_kw
%token BEGIN_kw   -- used for error recovery only
%token BLOCK_kw
%token CASE_kw
%token CLASS_kw
%token CONCURRENT_kw
%token CONST_kw
%token CONTINUE_kw
%token EACH_kw
%token ELSE_kw
%token ELSIF_kw
%token END_kw
%token EXIT_kw
%token EXPORTS_kw
%token EXTENDS_kw
%token FOR_kw
%token FORWARD_kw
%token FUNCTION_kw
%token GLOBAL_kw
%token IF_kw
%token IMPLEMENTS_kw
%token IMPORT_kw
%token IN_kw
%token INTERFACE_kw
%token IS_kw
%token LAMBDA_kw
%token LOCKED_kw
%token LOOP_kw
%token MOD_kw
%token MUTABLE_kw
%token NEW_kw
%token NOT_kw
%token NULL_kw
%token OF_kw
%token OPERATOR_kw
%token OPTIONAL_kw
%token OR_kw
%token PRIVATE_kw
%token PROCEDURE_kw
%token QUEUED_kw
%token REF_kw
%token REM_kw
%token RETURN_kw
%token REVERSE_kw
%token SELECT_kw
%token SOME_kw
%token THEN_kw
%token TYPE_kw
%token UNTIL_kw
%token VAR_kw
%token WHILE_kw
%token WITH_kw
%token XOR_kw

%start module_list


module_list : 
  | module_list module

module : 
    import_clauses interface_declaration ';' 
  | import_clauses class_definition ';' 
  | import_clauses standalone_operation_definition ';'
  | import_clauses error ';'

import_clauses : 
  | import_clauses IMPORT_kw qualified_name_list ';' 

qualified_name_list : 
  | qualified_name_list ',' qualified_name 

interface_declaration : 
   opt_interface_qualifier INTERFACE_kw module_defining_name 
   END_kw opt_INTERFACE_kw module_defining_name 

opt_interface_qualifier : 

interface_qualifier : 
  | ABSTRACT_kw opt_class_qualifier 
  | PRIVATE_kw opt_class_qualifier 

opt_class_qualifier : 

class_qualifier : CONCURRENT_kw ;

standalone_operation_definition : 
  | procedure_definition 
  | operator_definition 
  | operation_import 

formals : '<' opt_module_formal_list '>' ;

formals_and_implemented_interfaces :
    opt_formals opt_implements_list 
  | opt_formals EXTENDS_kw interface_name opt_implements_list 

opt_formals : 

opt_implements_list : 

implements_list : IMPLEMENTS_kw interface_name_list  ;

interface_name_list :
  | interface_name_list ',' interface_name 

interface_name : 
  | module_instantiation 
module_name : qualified_name ;

module_defining_name : 
  | qualified_name add_on_label 

add_on_label : 
    '[' operation_actual_list ']' ;

opt_module_formal_list : 
  | ;

module_formal_list : 
  | module_formal_list ';' annotated_module_formal 

annotated_module_formal : 
    opt_annotation type_formal opt_annotation 
  | opt_annotation operation_formal 
  | opt_annotation value_formal opt_annotation 

opt_annotation : 

type_formal : 
    id IS_kw module_instantiation 
  | module_instantiation 

operation_formal : 
    operation_declaration opt_operation_default  

opt_operation_default : 
    IS_kw simple_expression 

value_formal : 
    id_list ':' opt_output_modifier operand_type_specifier 
  | id_list ':' opt_output_modifier operand_type_specifier 
      ASSIGN_or_equal simple_expression  
  | ref_or_global_modifier operand_type_specifier 

id : Identifier 

id_list : 
  | id_list ',' id 

type_name : 
  | polymorphic_type_name 

polymorphic_type_name : qualified_name '+' ;

qualified_name : 
  | qualified_name DOUBLE_COLON id_or_string_literal ;

id_or_string_literal :
  | String_Literal 
module_instantiation : 
    module_name '<' opt_module_actual_list '>' 
  | name '[' opt_operation_actual_list ']' '<' opt_module_actual_list '>' 

opt_add_on_label :

opt_module_actual_list : 

module_actual_list :
  | module_actual_list ',' module_actual 

module_actual : 
  | id REFERS_TO simple_type_specifier_or_expression 

-- simple_expression subsumes simple type_name in this rule
simple_type_specifier_or_expression : 
    qualified_name annotation 
  | qualified_type_specifier opt_annotation 
  | simple_expression              
    -- simple_expr to avoid problems with '>'
  | lambda_expression 
  | module_instantiation 
annotated_type_specifier : 
  | type_specifier annotation 

type_specifier :
  | qualified_type_specifier 

basic_type_specifier : 
  | module_instantiation 
  | module_instantiation EXTENDS_kw type_specifier 

qualified_type_specifier : 
    type_qualifier type_name 
  | type_qualifier module_instantiation 
  | type_qualifier module_instantiation 
      EXTENDS_kw type_specifier 

type_qualifier :

opt_CONCURRENT_kw : 

interface_element_list : 
  | interface_element_list interface_element ';' 
  | interface_element_list operation_import ';' 
  | interface_element_list error ';' 

interface_element : 
  | object_declaration 
  | interface_declaration 
  | type_declaration 

operation_import :
    function_declaration IS_kw import_operation 
  | procedure_declaration IS_kw import_operation 
  | operator_declaration IS_kw import_operation 

class_definition :
   opt_class_qualifier CLASS_kw module_defining_name 
   END_kw opt_CLASS_kw module_defining_name ; 

opt_CLASS_kw : CLASS_kw
class_formals_and_implemented_interfaces :
  | opt_formals EXTENDS_kw id ':' interface_name opt_implements_list 

class_element_list : 
  | local_class_element_list
  | local_class_element_list 

local_class_element_list : 
  | local_class_element_list local_class_element ';' 

local_class_element : 
  | operation_import 
  | annotated_exported_class_element 
exported_class_element_list : 
  | exported_class_element_list annotated_exported_class_element ';' 
  | exported_class_element_list operation_import ';' 
  | exported_class_element_list interface_element ';' 
  | exported_class_element_list error ';' 

annotated_exported_class_element : 
  | exported_class_element 
  | annotation 
  | annotation exported_class_element 

exported_class_element : 
  | object_definition  
  | class_definition  
annotation : '' 
  | annotation '' 

annotation_element_list : 
  | annotation_element_list ';' annotation_element 
  | annotation_element_list ';' error 

annotation_element : 
  | operation_import 
  | condition 
  | quantified_expression 
  | annotation 

condition : expression  ;

operation_declaration : 
  | procedure_declaration 
  | operator_declaration 

function_declaration :
  opt_ABSTRACT_or_OPTIONAL_kw FUNCTION_kw id_or_string_literal
    operation_inputs opt_annotation 
      GIVES_or_RETURN_kw operation_outputs opt_annotation ;

  | RETURN_kw 

procedure_declaration :
    operation_inputs opt_annotation ;

operator_declaration :
    opt_ABSTRACT_or_OPTIONAL_kw OPERATOR_kw operator_designator 
      operation_inputs opt_annotation 
  | opt_ABSTRACT_or_OPTIONAL_kw OPERATOR_kw operator_designator 
    operation_inputs opt_annotation 
      GIVES_or_RETURN_kw operation_outputs opt_annotation 

  | OPTIONAL_kw 

operator_designator : String_Literal ;
operation_inputs :
  | '(' opt_annotated_operation_input_list ')' 
  | '(' id_list ',' id ')' 

simple_operation_input :   -- avoids trailing use of "IS"
    id ':' opt_input_modifier simple_operand_type_specifier 
  | input_modifier simple_operand_type_specifier 
  | simple_operand_type_specifier 

opt_annotated_operation_input_list : 

annotated_operation_input_list : 
  | annotated_operation_input_list ';' annotated_operation_input 

annotated_operation_input : 
    operation_input opt_annotation 
  | annotation operation_input opt_annotation 
  | function_declaration opt_operation_default 
  | annotation function_declaration opt_operation_default 
  | procedure_declaration opt_operation_default 
  | annotation procedure_declaration opt_operation_default 

operation_input : 
    id_list ':' opt_input_modifier operand_type_specifier opt_ASSIGN_expression
  | input_modifier operand_type_specifier opt_ASSIGN_expression 
  | operand_type_specifier opt_ASSIGN_expression 

opt_input_modifier : 
simple_operand_type_specifier :
  | module_instantiation 

operand_type_specifier : 
  | id IS_kw module_instantiation 

input_modifier : 
  | QUEUED_kw mutable_or_var_or_const 
  | LOCKED_kw mutable_or_var_or_const 

mutable_or_var_or_const :
    MUTABLE_kw opt_VAR_kw 
  | VAR_kw 
  | CONST_kw 

opt_VAR_kw : 

operation_outputs : 
  | annotation simple_operation_output 
  | '(' annotated_operation_output_list ')' 
  | '(' id_list ',' id ')' 

simple_operation_output :   -- avoids trailing use of "IS"
    id ':' opt_output_modifier simple_operand_type_specifier 
  | output_modifier simple_operand_type_specifier 
  | simple_operand_type_specifier 

annotated_operation_output_list :
  | annotated_operation_output_list ';' annotated_operation_output 

annotated_operation_output : 
    operation_output opt_annotation 
  | annotation operation_output opt_annotation  

operation_output : 
  id_list ':' opt_output_modifier operand_type_specifier 
  | output_modifier operand_type_specifier  
  | operand_type_specifier  

opt_output_modifier :  

output_modifier :  
  | ref_or_global_modifier 

ref_or_global_modifier :
  | REF_or_GLOBAL_opt_optional_mutable VAR_kw 
  | REF_or_GLOBAL_opt_optional_mutable CONST_kw 

REF_or_GLOBAL_opt_optional_mutable :
  | REF_or_GLOBAL_kw MUTABLE_kw 

REF_or_GLOBAL_kw : 
  | GLOBAL_kw 

object_declaration : 
    VAR_kw id ':' 
  | CONST_kw id ':' annotated_type_specifier 
  | id ':' annotated_type_specifier 

opt_ASSIGN_expression : 
    ASSIGN_or_equal expression 
object_definition :
    CONST_kw id ASSIGN_or_equal expression 
  | VAR_kw id ASSIGN_or_equal expression 
  | CONST_kw id REFERS_TO name 
  | VAR_kw id REFERS_TO name 

opt_OPTIONAL_kw : 
opt_MUTABLE_kw : 

type_declaration : 
    TYPE_kw id IS_kw opt_NEW_kw annotated_type_specifier ;

opt_NEW_kw : 

operation_definition : 
  | procedure_definition 
  | operator_definition 

function_definition : 
  function_declaration IS_kw opt_queued_clause 
  END_kw opt_FUNCTION_kw id 


procedure_definition : 
  procedure_declaration IS_kw opt_queued_clause 
  END_kw opt_PROCEDURE_kw id 


operator_definition : 
  operator_declaration IS_kw 
  END_kw opt_OPERATOR_kw operator_designator  


opt_queued_clause : 

queued_clause :
    QUEUED_kw WHILE_or_UNTIL_kw condition THEN_kw ;

import_operation :
    IMPORT_kw '(' opt_operation_actual_list ')' ;

statement_list_with_semi : 
  | statement_list_no_semi THEN_kw parallel_sequence_with_semi 
  | statement_list_with_semi THEN_kw parallel_sequence_with_semi 
  | statement_list_with_semi use_BEGIN_kw parallel_sequence_with_semi 
  | use_BEGIN_kw parallel_sequence_with_semi 

use_BEGIN_kw : BEGIN_kw ;

statement_list_no_semi : 
  | statement_list_no_semi THEN_kw parallel_sequence_no_semi 
  | statement_list_with_semi THEN_kw parallel_sequence_no_semi 

parallel_sequence_with_semi : 
  | parallel_sequence_no_semi PARALLEL statement_sequence_with_semi 
  | parallel_sequence_with_semi PARALLEL statement_sequence_with_semi 

parallel_sequence_no_semi :
  | parallel_sequence_no_semi PARALLEL statement_sequence 
  | parallel_sequence_with_semi PARALLEL statement_sequence 

statement_sequence_opt_semi :
  | statement_sequence 

statement_sequence_with_semi : statement_sequence ';' ;

statement_sequence :
  | statement_sequence SEQUENCE annotated_statement 
  | statement_sequence ';' SEQUENCE annotated_statement 
  | statement_sequence ';' annotated_statement 
annotated_statement : 
    opt_annotation local_declaration 
  | opt_annotation statement opt_annotation 
  | annotation 

statement : 
  | simple_statement 
  | label compound_statement 
  | compound_statement 

simple_statement :
  | name equal_as_assign expression 
  | NULL_kw 
  | name '(' opt_operation_actual_list ')' 
  | RETURN_kw expression 
  | RETURN_kw opt_WITH_values  
  | CONTINUE_kw LOOP_kw opt_id opt_WITH_values  
  | EXIT_kw compound_statement_kind opt_id opt_WITH_values 

primitive_statement :
    name assign_operator_not_divide expression 
  | name DIVIDE_ASSIGN expression 
  | name SWAP name 
  | '(' opt_operation_actual_list ')' ASSIGN expression 

opt_operation_actual_list : 

opt_WITH_values : 

WITH_values : WITH_kw operation_actual ;

opt_id : 

compound_statement_kind : 
  | IF_kw 
  | CASE_kw 
  | SELECT_kw 
  | BLOCK_kw 

local_declaration : 
  | type_declaration 
  | object_declaration

local_definition :
  | operation_definition 

label : '*' id '*' ;

compound_statement :
  | case_statement 
  | indefinite_loop_statement 
  | while_until_loop_statement 
  | for_loop_statement 
  | block_statement  
  | select_statement 
  | error ';' 

if_statement : 
  IF_kw condition THEN_kw 
  END_kw IF_kw opt_id opt_WITH_values ;

opt_else_part : 
    ELSIF_kw condition THEN_kw
  | ELSE_kw statement_list_with_semi 

case_statement : 
  CASE_kw expression OF_kw
  END_kw CASE_kw opt_id opt_WITH_values ;

case_alt_list : 
  | case_alt_list case_alt 

case_alt :
    '[' simple_expression_opt_named ']' REFERS_TO statement_list_with_semi 

simple_expression_opt_named :
  | id ':' simple_expression 
opt_default_alt : 
    '[' dot_dot_opt_named ']' REFERS_TO statement_list_with_semi 

dot_dot_opt_named :
  | id ':' dot_dot_as_interval 
dot_dot_as_interval : DOT_DOT ;

indefinite_loop_statement :
  END_kw LOOP_kw opt_id opt_WITH_values ;

while_until_loop_statement :
  WHILE_or_UNTIL_kw condition LOOP_kw
  END_kw LOOP_kw opt_id opt_WITH_values ;

  | UNTIL_kw 

for_loop_statement :
  FOR_kw iterator_spec opt_direction LOOP_kw
  END_kw LOOP_kw opt_id opt_WITH_values ;

iterator_spec : 
  | '(' iterator_list ')' 

iterator_list :
  | iterator_list ';' iterator 

iterator :
  | EACH_kw element_iterator 
  | initial_next_while_iterator 
  | initial_value_iterator 

index_set_iterator :
    id opt_COLON_type_specifier IN_kw opt_REVERSE_kw expression ;

opt_REVERSE_kw : 
  | REVERSE_kw ;

element_iterator :
    id opt_COLON_type_specifier OF_kw expression 
  | '[' id REFERS_TO id ']' OF_kw expression 

initial_next_while_iterator :
    id opt_COLON_type_specifier ASSIGN_or_equal expression 
      WHILE_or_UNTIL_kw condition 
  | id opt_COLON_type_specifier REFERS_TO name 
      WHILE_or_UNTIL_kw condition 

opt_THEN_next_value_list :
    THEN_kw next_value_list 

opt_THEN_next_name_list :
    THEN_kw next_name_list 

initial_value_iterator :
    id opt_COLON_type_specifier ASSIGN_or_equal expression 
  | id opt_COLON_type_specifier REFERS_TO name 

opt_COLON_type_specifier : 
    ':' type_specifier 

next_value_list : 
  | next_value_list PARALLEL expression 

next_name_list : 
  | next_name_list PARALLEL name 

opt_direction : direction  

direction : 
  | FORWARD_kw 
  | REVERSE_kw 

select_statement :
  END_kw SELECT_kw opt_id opt_WITH_values ;

select_alt_list : 
  | select_alt_list PARALLEL select_alt

select_alt : 
  '[' statement_sequence_opt_semi ']' REFERS_TO statement_sequence_with_semi ;

block_statement :
    END_kw opt_BLOCK_kw opt_id opt_WITH_values 

opt_BLOCK_kw : BLOCK_kw
expression :
  | expression_no_err divide_assign_as_not_equal expression_no_err 

divide_assign_as_not_equal :

expression_no_err :
  | logical_expression '?' expression ':' expression_no_err 
  | lambda_expression 

lambda_expression :
    LAMBDA_kw operation_inputs opt_annotation IS_kw 
  | LAMBDA_kw operation_inputs opt_annotation
      GIVES operation_outputs opt_annotation IS_kw 

simple_expression_or_expr_stmt_seq :
  | '(' expr_statement_seq ')' 

expr_statement_seq : expr_statement ';' expr_statement 
  | expr_statement_seq ';' expr_statement 

expr_statement : 
  | expression_no_err 

logical_expression :  
  | logical_expression logical_operator comparison_expression 

comparison_expression :  -- comparisons are non associative
  | simple_expression comparison_operator simple_expression 
  | adding_expression IN_kw simple_expression 
  | adding_expression NOT_kw IN_kw simple_expression 
  | adding_expression IS_kw NULL_kw 
  | adding_expression NOT_kw NULL_kw 

simple_expression : -- used to avoid use of '>' in module instantiation
  | simple_expression '|' simple_expression_component 

simple_expression_component :
  | adding_expression interval_operator adding_expression 
  | adding_expression interval_operator 
  | interval_operator adding_expression 
  | adding_expression '+' 

adding_expression :
  | adding_expression adding_operator term 

term : 
  | term multiplying_operator factor 

factor : 
  | primary power_operator factor 
  | unary_operator factor  

primary :
  | literal 
  | '(' conditional_expression ')' 
  | '(' quantified_expression ')' 
  | aggregate 
literal:  -- NOTE: See "name" for String_Literal
  | Real_Literal 
  | Char_Literal 
  | Enum_Literal 
  | NULL_kw 

name :
    qualified_name_and_property opt_PRIME 
  | qualified_name DOUBLE_COLON literal 
  | name '(' opt_operation_actual_list ')' 
  | name '[' opt_operation_actual_list ']' 
  | name '.' selector 

qualified_name_and_property :
  | qualified_name_and_property Enum_Literal 

opt_PRIME : 
  | PRIME Identifier 

operation_actual_list : 
  | operation_actual_list ',' operation_actual 

operation_actual : 
  | id REFERS_TO expression 

selector : id ;

unary_operator : 
  | '-' 
  | ABS_kw 
  | NOT_kw 

adding_operator : 
  | '-' 

multiplying_operator : 
  | '/' 
  | MOD_kw 
  | REM_kw 

power_operator : POWER ;

assign_operator : assign_operator_not_divide 

assign_operator_not_divide :

ASSIGN_or_equal : ASSIGN 
  | equal_as_assign 

equal_as_assign : '=' 

comparison_operator : 
  | EQ 
  | NEQ 
  | '<' 
  | LEQ 
  | '>' 
  | GEQ 
  | '<' '<' 
  | '>' '>' 
  | '=' 

logical_operator :
  | OR_kw 
  | XOR_kw  
  | AND_kw THEN_kw 
  | OR_kw ELSE_kw 

interval_operator :

aggregate : 
  | container_aggregate  

class_aggregate : 
    '(' opt_operation_actual_list ')' 
  | '(' name DIVIDE_ASSIGN expression ')' 
  | qualified_name DOUBLE_COLON '(' opt_operation_actual_list ')' 

container_aggregate : 
    '[' opt_container_element_list ']' 
  | qualified_name DOUBLE_COLON '[' opt_container_element_list ']' 
opt_container_element_list : 
  | DOT_DOT 

container_element_list : 
  | container_element_list ',' container_element 

container_element : 
  | simple_expression REFERS_TO filtered_expression_stream 
  | DOT_DOT REFERS_TO filtered_expression_stream 
  | FOR_kw iterator REFERS_TO filtered_expression_stream 

filtered_expression_stream : 
  | expression ':' condition 

conditional_expression :
  | case_expression 

if_expression : 
  IF_kw condition THEN_kw 
  opt_else_expr ;

opt_else_expr : 
    ELSIF_kw condition THEN_kw 
  | ELSE_kw expression 

case_expression : 
  CASE_kw expression OF_kw
    case_expr_alt_list ;

case_expr_alt_list : 
  | case_expr_alt_list ';' case_expr_alt 

case_expr_alt : 
    '[' simple_expression_opt_named ']' REFERS_TO expression 
  | '[' dot_dot_opt_named ']' REFERS_TO expression 

quantified_expression :
    FOR_kw ALL_or_SOME_kw quantified_iterator REFERS_TO
      condition_or_quantified_expression ;

condition_or_quantified_expression :
  | if_expression 
  | quantified_expression 

ALL_or_SOME_kw : 
  | SOME_kw 

quantified_iterator :
  | element_iterator 
  | initial_next_while_iterator