Designing ParaSail, a new programming language

Full Object-Oriented Programming support in rev 2.0 alpha 0.5

2012-02-05T15:26:00.000-05:00

We have just made available a new alpha release of the prototype ParaSail compiler and virtual machine, rev 2.0, alpha 0.5:

http://bit.ly/zuSIz1

This new release has full support for inheritance and polymorphism. In ParaSail terms, this means that you can now use polymorphic types, using the T+ syntax, and you can define one module as an extension of another, using the extends keyword. (The implements keyword was already supported in earlier releases.) This release includes a new example, "expr_tree.psl", which illustrates a hierarchy of types defined using module extension and polymorphic components. As usual, we include executables for Mac, Linux, and Windows.

The prior blog entry discussed the implementation of polymorphic objects. An upcoming blog entry will discuss the implementation of the inheritance of operations and components. As in Java, C#, and Ada, ParaSail supports single inheritance of implementation, and multiple inheritance of interfaces. The multiple inheritance of interfaces was implemented from the very first ParaSail release, but this is the first ParaSail release that supports inheritance of the implementation of operations, and of components. This involved some additions to the virtual machine instruction set, and significant work in the compiler.

Both polymorphism and inheritance (of implementation) are handled by ParaSail in a somewhat non-traditional way, in part because there are no pointers in ParaSail, and in part because objects are expandable "in place" without the use of pointers. Polymorphic objects in ParaSail can be assigned new values which are of different types in the hierarchy. In most object-oriented languages, only pointers or references can be truly polymorphic; the type of a particular object is set when the object is created and cannot change during its lifetime. See the prior and upcoming blog entries for more details, as well as the reference manual included with the above release in the "doc" subdirectory and the "expr_tree.psl" example in the "examples" subdirectory.

Implementing Polymorphic Objects

2012-01-24T18:57:00.001-05:00

ParaSail has a somewhat different approach to (run-time) polymorphism than is typical. There is a separate notation for indicating an object is polymorphic. If you declare "var X : T" then X is of type T. If you declare "var X : T+" then X is a polymorphic object, meaning it can hold an object of type T or any type that extends or implements T. Adding a "+" sign to the end of a type name is used to indicate a polymorphic type rooted at the given type. For a longer discussion of ParaSail's object-oriented model, see:

http://parasail-programming-language.blogspot.com/2009/09/parasail-extension-inheritance-and.html

We have just completed the initial implementation of polymorphic objects, and there were some interesting trade-offs involved. First we should recap the implementation of "regular" objects in ParaSail. Some of this is covered in:

http://parasail-programming-language.blogspot.com/2011/05/when-null-isnt-just-null-value.html

Regular objects come in two basic varieties, small and large. A small object is represented by a single 64-bit word. It has no type information at run-time. The compiler "knows" from context the type of the object. One bit pattern is reserved to represent null for a given small type. As mentioned in the above blog entry, we use NaN for a floating point null, and -2**63 for a 64-bit integer null. Other values can be used for types with fewer values, of course, and one less than the smallest normal value or one greater than the largest normal value would work.

A large object is represented by a 64-bit address, pointing to a sequence of 64-bit words, the first of which is a header, followed by the components. The header identifies the object's size (in 64-bit words), its structural type-id (primarily an indication of which components are small and which are large), its storage region-id, and a lock-id if the object is a concurrent object.

If a composite type has exactly one component, then rather than creating another level of indirection, we simply adopt the representation for the component as the representation for the composite type. This means that a composite type whose only component is of a small type is itself represented as a small object. Hence, there is no extra storage overhead in wrapping an object in another type, just to give it a new interface. So a user-defined numeric type, for instance, need be no bigger than the underlying component used to represent its value. We call these wrapper types. Objects of a wrapper type are indistinguishable at run-time from objects of their component type, and if their component is large, then the type-id in the header of an object of the wrapper type will be the same as the type-id in the header of an object of the component type. This is one reason we call the type-id in the header of a large object its structural type-id.

A null for a large type was originally represented by the 64-bit address of an object consisting only of a header, with a structural type-id indicating it was a null object, and the storage region-id indicating where to allocate storage for it when it is assigned a non-null value. We have since switched over to a representation where the 64-bit address itself is recognizable as representing a large null value, with the storage region-id encoded in 16 bits of the 64-bit address representation, avoiding the extra level of indirection, and the need to create null objects when first creating a new region.

So where does that leave us for polymorphic objects? Polymorphic objects need to carry around an indication of their true run-time type-id, not just structural information. For example, a polymorphic object that started out as an object of a wrapper type, needs to be distinguishable at run-time from a polymorphic object that started out as an object of the wrapper's component type. So we choose to make polymorphic objects always use the large representation, meaning they always have a header. Furthermore, the type-id in this header explicitly identifies this object as being a polymorphic object, with a single "component." The true (run-time) type-id of this single "component" is also identified by the polymorphic type-id. Furthermore, if this true type implements (rather than extends) the root type of the polymorphic type, an operation map is provided to map the true type's operations to those of the root type. For a discussion of these operation maps (called slot-number mappings in the blog entry), see:

http://parasail-programming-language.blogspot.com/2010/08/initial-implementation-model-for.html

So the representation of a polymorphic object is essentially a "real" wrapper object, to allow us to specify the true type of the wrapped underlying object. To some degree this is the price we pay for having small objects that don't carry around any type information, and for allowing wrapper types to be represented identically to their component types. When we really need a polymorphic object, we need to add an extra level of header, so we can record the true type information.

What can you do with polymorphic objects? They can be assigned a value of any type that extends or implements the root type of the polymorphic type. Furthermore, when passed as a parameter to an operation of the root type, the true type-id of the wrapped object is consulted, and that type-id is used to find the actual body to execute for this given operation.

For example, if T has a visible "Print(X : T)" operation, then any type NT that extends or implements T must also have a corresponding Print operation, but taking NT rather than T (i.e. "Print(X : NT)"). If we pass a polymorphic object of type T+ to the Print operation of T, it will dispatch to the appropriate body for Print. So if the true type-id for the polymorphic object passed identifies NT, then we will execute the "Print(X : NT)" operation.

As part of passing the polymorphic object, the polymorphic "wrapper" is stripped off, so by the time we get to the appropriate operation's body, the representation for the parameter is back to the "normal" representation expected by that operation. For example, this means that operations designed to take "small" representations for values, will work fine in this context, because the large-object, polymorphic header will have been stripped off, and just the small value will be passed to the operation's body, as expected.

Rev 1.8 of alpha 0.3 release of ParaSail compiler and virtual machine

2012-01-06T18:23:00.000-05:00

Rev 1.8 of the 0.3 Alpha release of ParaSail is now available at:

http://bit.ly/AAWk7Y

This release has initial support for generic operations, where the type of one of the operands is not specified exactly, but merely as being any type that implements a given interface. For example, to declare a concatenation operator between Univ_String and any type that implements the Imageable interface, you can write:

op "|"(Left : Univ_String; Right : Right_Type is Imageable<>) -> Univ_String;

This operator can be implemented using operations on Right that are defined in the Imageable interface, such as To_String.

Rev 1.6 of alpha 0.2 release of ParaSail compiler and VM

2011-11-07T06:03:00.000-05:00

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

http://bit.ly/tJyc5E

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.

Alpha release 0.2 of ParaSail Compiler and Virtual Machine

2011-10-24T19:33:00.000-04:00

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

http://bit.ly/rsxQDX

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.
-Tuck

Upcoming panels, tutorials, and workshops on ParaSail

2011-10-14T16:35:00.000-04:00

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:

A panel that is part of the Transitioning to Multicore (TMC) workshop, on Sunday Oct. 23rd, at 2:00PM -- see http://tmc.supertriceratops.com/
A panel on Multicore, Manycore, and Cloud computing -- Is a new programming language paradigm required?, on Wednesday Oct. 26th, at 4:00PM -- see http://splashcon.org/2011/program/229

The events at the upcoming SIGAda conference in Denver are:

A tutorial on Experimenting with ParaSail, which will be held Monday November 7th, from 9:00AM to 12:30PM -- see http://www.sigada.org/conf/sigada2011/tutorials-descriptions.html#MA1
A workshop/birds-of-a-feather session on ParaSail, which will be on Tuesday, November 8th, from 4:30PM to 5:30PM -- see http://www.sigada.org/conf/sigada2011/workshops.html

I believe all of these event are still open for additional attendees.

Deadlocking the Virtual Machine

2011-10-13T16:56:00.000-04:00

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 http://parasail-programming-language.blogspot.com/2010/11/virtual-machine-for-parasail-with.html). 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 http://parasail-programming-language.blogspot.com/2011/09/n-queens-join-party.html) 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
http://supertech.csail.mit.edu/papers/steal.pdf). 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...

Alpha release of ParaSail Compiler and Virtual Machine

2011-10-03T11:46:00.000-04:00

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:

http://groups.google.com/group/parasail-programming-language

N Queens Join the Party

2011-09-14T12:44:00.001-04:00

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.

Enjoy!

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
      exports
        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;

  exports
    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.
    is
      var Solutions : concurrent Vector<Solution> := [];
      
     *Outer_Loop*
      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);
                  else
                      // 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;
        Print('\n');
    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

Another ParaSail example that compiles and runs

2011-09-08T15:04:00.000-04:00

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
  exports
    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;
            else
               // 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;
                 block
                   // 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))}
               
             then
               // 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
            Print(",");
        end if;
    end loop;
    Print("\n");

    My_Sorter::Quicksort(Vec);

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

    My_Sorter::Quicksort(Vec2);

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

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

ParaSail compiler reaches a milestone

2011-09-07T15:34:00.000-04:00

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: 
    //       http://en.wikipedia.org/wiki/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;
            else
                // 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;
        else
            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;
            else
                // 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;
        else
            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
            return;
        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;

  exports

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

        Skew(T);
        Split(T);
    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?
            return;
        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;
            else
                // 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?
            return;  
        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
            return;
        end if;

        Decrease_Level(T);
        Skew(T);
        Skew(T.Right);
        if T.Right not null then
            Skew(T.Right.Right);
        end if;
        Split(T);
        Split(T.Right);
    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;
        else 
            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;
        else
            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;
        else
            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;
        else
            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;

    Println(Result);
end func Htmlize_Line;

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

ParaSail on Intel Parallel Programming Talk video

2011-09-02T09:36:00.000-04:00

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:

http://software.intel.com/en-us/blogs/2011/08/26/parasail-a-new-programming-language-parallel-programming-talk-120/

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

A load-and-null-out operation

2011-07-30T17:50:00.000-04:00

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.

Adapting one interface to implement another

2011-07-25T15:46:00.001-04:00

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

Another slight shift in syntax

2011-07-23T16:43:00.000-04:00

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; 
      exports
        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;
             else
                 // Recurse down the left side
                 return
                   (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));
            else
                // 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:
http://groups.google.com/group/parasail-programming-language

Everything in a func?

2011-07-13T18:17:00.000-04:00

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

Implementing concurrent loops in ParaSail

2011-07-07T14:48:00.000-04:00

The implementation of the ParaSail compiler and virtual machine (see http://parasail-programming-language.blogspot.com/2010/11/virtual-machine-for-parasail-with.html) 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] =>
          Process(X.Data);
        ||
          continue loop with X => X.Operand;
      [#binary] =>
          Process(X.Data);
        ||
          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 http://parasail-programming-language.blogspot.com/2010/06/generalized-for-loops-in-parasail.html and http://parasail-programming-language.blogspot.com/2010/06/intentional-race-condition-in-parasail.html 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.

Upcoming presentations on ParaSail -- Edinburgh and Portland

2011-06-03T08:52:00.001-04:00

This summer we will be presenting on ParaSail at:

AdaEurope 2011 in Edinburgh, Scotland, Tutorial/Workshop on Experimenting with ParaSail (Monday 20-June-2011, 9:00am - 1:00pm GMT) http://conferences.ncl.ac.uk/adaconnection2011/tutorials/T1.html
OSCON 2011 in Portland, Introduction to ParaSail (Weds. 27-July-2011 10:40am - 11:20am PDT Room: E144 --NOTE the time change) http://www.oscon.com/oscon2011/public/schedule/detail/18557

You can still register for both of these conferences. For OSCON, there is a 20% registration discount if you use the code "os11fos".

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

2011-05-25T14:06:00.000-04:00

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

Updated YACC grammar for ParaSail

2011-05-09T10:53:00.000-04:00

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
  | 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 
  | qualified_name_list ',' qualified_name 
  ;

interface_declaration : 
   opt_interface_qualifier INTERFACE_kw module_defining_name 
     formals_and_implemented_interfaces
     IS_kw
      interface_element_list
   END_kw opt_INTERFACE_kw module_defining_name 
   ; 

opt_INTERFACE_kw : INTERFACE_kw
  | 
  ;
   
opt_interface_qualifier : 
    interface_qualifier 
  | 
  ;

interface_qualifier : 
    class_qualifier 
  | ABSTRACT_kw opt_class_qualifier 
  | PRIVATE_kw opt_class_qualifier 
  ;

opt_class_qualifier : 
    class_qualifier 
  | 
  ;

class_qualifier : CONCURRENT_kw ;

standalone_operation_definition : 
    function_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 : 
    formals  
  | 
  ;

opt_implements_list : 
    implements_list 
  | 
  ;

implements_list : IMPLEMENTS_kw interface_name_list  ;

interface_name_list :
    interface_name 
  | interface_name_list ',' interface_name 
  ;

interface_name : 
    module_name 
  | module_instantiation 
  ;
   
module_name : qualified_name ;

module_defining_name : 
    qualified_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 
  | 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 : 
    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 
  | id_list ',' id 
  ;

type_name : 
    qualified_name 
  | polymorphic_type_name 
  ;

polymorphic_type_name : qualified_name '+' ;

qualified_name : 
    id_or_string_literal 
  | qualified_name DOUBLE_COLON id_or_string_literal ;

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

opt_add_on_label :
    add_on_label 
  | 
  ;

opt_module_actual_list : 
    module_actual_list 
    | 
    ;

module_actual_list :
    module_actual 
  | module_actual_list ',' module_actual 
  ;

module_actual : 
    simple_type_specifier_or_expression 
  | 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 
  | type_specifier annotation 
  ;

type_specifier :
    basic_type_specifier 
  | qualified_type_specifier 
  ;

basic_type_specifier : 
    type_name 
  | 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 :
    OPTIONAL_kw opt_MUTABLE_kw opt_CONCURRENT_kw 
  | MUTABLE_kw opt_CONCURRENT_kw 
  | CONCURRENT_kw 
  ;

opt_CONCURRENT_kw : 
    CONCURRENT_kw 
  | 
  ;

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

interface_element : 
    operation_declaration 
  | 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 
      class_formals_and_implemented_interfaces
   IS_kw
      class_element_list
   END_kw opt_CLASS_kw module_defining_name ; 

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


class_element_list : 
    local_class_element_list
  EXPORTS_kw 
    exported_class_element_list 
  | local_class_element_list
    annotation
  EXPORTS_kw 
    exported_class_element_list 
  | local_class_element_list 
  ;

local_class_element_list : 
  | local_class_element_list local_class_element ';' 
  ;

local_class_element : 
    interface_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 : 
    operation_definition  
  | object_definition  
  | class_definition  
  ;
  
   
annotation : '' 
  | annotation '' 
  ;

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

annotation_element : 
    interface_element 
  | operation_import 
  | condition 
  | quantified_expression 
  | annotation 
  ;

condition : expression  ;


operation_declaration : 
    function_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 ;

GIVES_or_RETURN_kw : GIVES
  | RETURN_kw 
  ;

procedure_declaration :
  opt_ABSTRACT_or_OPTIONAL_kw PROCEDURE_kw id 
    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 
  ;

opt_ABSTRACT_or_OPTIONAL_kw :
    ABSTRACT_kw 
  | OPTIONAL_kw 
  | 
  ;

operator_designator : String_Literal ;
  
operation_inputs :
    simple_operation_input 
  | '(' 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_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 : 
    input_modifier 
  | 
  ;
  
simple_operand_type_specifier :
    type_name 
  | module_instantiation 
  ;

operand_type_specifier : 
    simple_operand_type_specifier 
  | id IS_kw module_instantiation 
  ;

input_modifier : 
    output_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 : 
    VAR_kw 
  | 
  ;

operation_outputs : 
    simple_operation_output 
  | 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 
  | 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 
  | 
  ;

output_modifier :  
    OPTIONAL_kw 
  | ref_or_global_modifier 
  ;

ref_or_global_modifier :
    REF_or_GLOBAL_opt_optional_mutable 
  | 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 
  | REF_or_GLOBAL_kw OPTIONAL_kw 
  | REF_or_GLOBAL_kw MUTABLE_kw 
  | REF_or_GLOBAL_kw OPTIONAL_kw MUTABLE_kw 
  ;

REF_or_GLOBAL_kw : 
    REF_kw 
  | GLOBAL_kw 
  ;

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

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 : 
    OPTIONAL_kw 
  | 
  ;
opt_MUTABLE_kw : 
    MUTABLE_kw 
  | 
  ;

type_declaration : 
    TYPE_kw id IS_kw opt_NEW_kw annotated_type_specifier ;

opt_NEW_kw : 
    NEW_kw 
  | 
  ;

operation_definition : 
    function_definition 
  | procedure_definition 
  | operator_definition 
  ;

function_definition : 
  function_declaration IS_kw opt_queued_clause 
     statement_list_with_semi 
  END_kw opt_FUNCTION_kw id 
  ;

opt_FUNCTION_kw : FUNCTION_kw
  | 
  ;

procedure_definition : 
  procedure_declaration IS_kw opt_queued_clause 
     statement_list_with_semi 
  END_kw opt_PROCEDURE_kw id 
  ;

opt_PROCEDURE_kw : PROCEDURE_kw
  | 
  ;

operator_definition : 
  operator_declaration IS_kw 
     statement_list_with_semi 
  END_kw opt_OPERATOR_kw operator_designator  
  ;

opt_OPERATOR_kw : OPERATOR_kw
  | 
  ;

opt_queued_clause : 
    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 : 
    parallel_sequence_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 : 
    parallel_sequence_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 : 
    statement_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 :
    statement_sequence 
  | parallel_sequence_no_semi PARALLEL statement_sequence 
  | parallel_sequence_with_semi PARALLEL statement_sequence 
  ;

statement_sequence_opt_semi :
    statement_sequence_with_semi 
  | statement_sequence 
  ;

statement_sequence_with_semi : statement_sequence ';' ;

statement_sequence :
    annotated_statement 
  | 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 : 
    local_definition 
  | simple_statement 
  | label compound_statement 
  | compound_statement 
  ;

simple_statement :
    primitive_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 : 
    operation_actual_list 
  | 
  ;

opt_WITH_values : 
    WITH_values 
  | 
  ;

WITH_values : WITH_kw operation_actual ;

opt_id : 
    id 
  | 
  ;

compound_statement_kind : 
    LOOP_kw 
  | IF_kw 
  | CASE_kw 
  | SELECT_kw 
  | BLOCK_kw 
  ;

local_declaration : 
    operation_declaration 
  | type_declaration 
  | object_declaration
  ;

local_definition :
    object_definition 
  | operation_definition 
  ;

label : '*' id '*' ;

compound_statement :
    if_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 
     statement_list_with_semi
  opt_else_part
  END_kw IF_kw opt_id opt_WITH_values ;

opt_else_part : 
    ELSIF_kw condition THEN_kw
      statement_list_with_semi 
    opt_else_part 
  | ELSE_kw statement_list_with_semi 
  | 
  ;


case_statement : 
  CASE_kw expression OF_kw
    case_alt_list
    opt_default_alt
  END_kw CASE_kw opt_id opt_WITH_values ;

case_alt_list : 
    case_alt 
  | case_alt_list case_alt 
  ;

case_alt :
    '[' simple_expression_opt_named ']' REFERS_TO statement_list_with_semi 
  ;

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

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


indefinite_loop_statement :
  LOOP_kw 
    statement_list_with_semi
  END_kw LOOP_kw opt_id opt_WITH_values ;

while_until_loop_statement :
  WHILE_or_UNTIL_kw condition LOOP_kw
    statement_list_with_semi
  END_kw LOOP_kw opt_id opt_WITH_values ;

WHILE_or_UNTIL_kw :
    WHILE_kw 
  | UNTIL_kw 
  ;

for_loop_statement :
  FOR_kw iterator_spec opt_direction LOOP_kw
    statement_list_with_semi
  END_kw LOOP_kw opt_id opt_WITH_values ;

iterator_spec : 
    iterator 
  | '(' iterator_list ')' 
  ;

iterator_list :
    iterator 
  | iterator_list ';' iterator 
  ;

iterator :
    index_set_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 
      opt_THEN_next_value_list 
      WHILE_or_UNTIL_kw condition 
  | id opt_COLON_type_specifier REFERS_TO name 
      opt_THEN_next_name_list
      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 : 
    expression  
  | next_value_list PARALLEL expression 
  ;

next_name_list : 
    name  
  | next_name_list PARALLEL name 
  ;

opt_direction : direction  
  | 
  ;

direction : 
    CONCURRENT_kw 
  | FORWARD_kw 
  | REVERSE_kw 
  ;

select_statement :
  SELECT_kw 
     select_alt_list
  END_kw SELECT_kw opt_id opt_WITH_values ;

select_alt_list : 
    select_alt
  | select_alt_list PARALLEL select_alt
  ;

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

block_statement :
    BLOCK_kw
      statement_list_with_semi
    END_kw opt_BLOCK_kw opt_id opt_WITH_values 
  ;

opt_BLOCK_kw : BLOCK_kw
  | 
  ;
   
expression :
    expression_no_err 
  | expression_no_err divide_assign_as_not_equal expression_no_err 
  ;

divide_assign_as_not_equal :
    DIVIDE_ASSIGN 
  ;

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

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

simple_expression_or_expr_stmt_seq :
    simple_expression 
  | '(' expr_statement_seq ')' 
  ;

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

expr_statement : 
    primitive_statement 
  | expression_no_err 
  ;

logical_expression :  
    comparison_expression 
  | logical_expression logical_operator comparison_expression 
  ;

comparison_expression :  -- comparisons are non associative
    simple_expression 
  | 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_component 
  | simple_expression '|' simple_expression_component 
  ;

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

adding_expression :
    term 
  | adding_expression adding_operator term 
  ;

term : 
    factor 
  | term multiplying_operator factor 
  ;

factor : 
    primary 
  | primary power_operator factor 
  | unary_operator factor  
  ;

primary :
    name 
  | literal 
  | '(' conditional_expression ')' 
  | '(' quantified_expression ')' 
  | aggregate 
  ;
  
literal:  -- NOTE: See "name" for String_Literal
    Integer_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 
  | qualified_name_and_property Enum_Literal 
  ;

opt_PRIME : 
    PRIME 
  | PRIME Identifier 
  | 
  ;

operation_actual_list : 
    operation_actual 
  | operation_actual_list ',' operation_actual 
  ;

operation_actual : 
    expression_no_err 
  | 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 
  | DIVIDE_ASSIGN 
  ;

assign_operator_not_divide :
    ASSIGN 
  | PLUS_ASSIGN 
  | MINUS_ASSIGN 
  | TIMES_ASSIGN 
  | CONCAT_ASSIGN 
  | AND_ASSIGN 
  | OR_ASSIGN 
  | XOR_ASSIGN 
  ;

ASSIGN_or_equal : ASSIGN 
  | equal_as_assign 
  ;

equal_as_assign : '=' 
  ;

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

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

interval_operator :
    DOT_DOT 
  | OPEN_INTERVAL 
  | CLOSED_OPEN_INTERVAL 
  | OPEN_CLOSED_INTERVAL 
  ;

aggregate : 
    class_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 : 
    container_element_list 
  | DOT_DOT 
  | 
  ;

container_element_list : 
    container_element 
  | container_element_list ',' container_element 
  ;

container_element : 
    expression 
  | 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 
  | expression ':' condition 
  ;

conditional_expression :
    if_expression 
  | case_expression 
  ;

if_expression : 
  IF_kw condition THEN_kw 
     expression
  opt_else_expr ;

opt_else_expr : 
    ELSIF_kw condition THEN_kw 
      expression 
    opt_else_expr 
  | ELSE_kw expression 
  | 
  ;

case_expression : 
  CASE_kw expression OF_kw
    case_expr_alt_list ;

case_expr_alt_list : 
    case_expr_alt 
  | 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 :
    condition 
  | if_expression 
  | quantified_expression 
  ;

ALL_or_SOME_kw : 
    ALL_kw 
  | SOME_kw 
  ;

quantified_iterator :
    index_set_iterator 
  | element_iterator 
  | initial_next_while_iterator 
  ;

%%

ParaSail Reference Manual -- first complete draft posted

2011-05-08T23:46:00.000-04:00

We have posted the first complete draft of the reference manual for the ParaSail programming language to the ParaSail google group:

http://groups.google.com/group/parasail-programming-language

Comments welcomed!

Writing preconditions and postconditions incrementally

2011-04-10T16:48:00.000-04:00

Once you start enforcing pre- and postconditions at compile time, as in ParaSail, some interesting things start to happen. Unless programmers are very familiar with writing pre- and postconditions as a matter of course, chances are that the code will be written initially with few if any pre/postconditions. However, presuming that the language-provided abstractions, such as Arrays, already have some preconditions (such as you cannot index into an array with an index that is out of the array bounds), the compiler pretty quickly identifies places where the programmer will have to write some of their own preconditions, constraints, invariants, etc. For example, consider the classic Stack abstraction. This might be written in ParaSail as follows, initially without any pre/postconditions:

interface Stack
  <Component is Assignable<>; 
   Size_Type is Integer<>> is
    function Create(Max : Size_Type) -> Stack;
    function Top(S : ref Stack) -> ref Component;
    procedure Pop(S : ref var Stack);
    procedure Push
      (S : ref var Stack; 
       X : Component);     
end interface Stack;

class Stack is
    const Max_Len : Size_Type;
    var Cur_Len : Size_Type;
    type Index_Type is Size_Type {Index_Type in 1..Max_Len};
    var Data : Array<optional Component, Indexed_By => Index_Type>;    
  exports
    function Create(Max : Size_Type) -> Stack is
      return (Max_Len => Max, Cur_Len => 0, Data => [.. => null]);
    end function Create;

    procedure Push(S : ref var Stack; X : Component) is
      S.Cur_Len += 1;
      S.Data[S.Cur_Len] := X;
    end procedure Push;
      
    function Top(S : ref Stack) -> ref Component is
      return S.Data[S.Cur_Len];
    end function Top;                

    procedure Pop(S : ref var Stack) is
      S.Cur_Len -= 1;
    end procedure Pop;     
end class Stack;

This all looks pretty straightforward until we try to compile it, and the compiler begins to complain at various places. For example, we blithely add one to S.Cur_Len in Push without any apparent concern about overflow. Then we blithely use the incremented S.Cur_Len as an index into S.Data, again with no apparent concern for the index being out of bounds.

The ParaSail compiler is never blithe, and will complain because the Array abstraction imposes a precondition on the indexing into S.Data, requiring that the index be in the range of Index_Type (1..Max_Len). It will also complain because the increment of S.Cur_Len might cause it to exceed the maximum Size_Type value (this precondition is from the "+=" operation of the Integer abstraction).

We could resolve these problems by adding a meaningful constraint on the range of values of Cur_Len (namely {Cur_Len in 0 .. Max_Len}) and adding a precondition on the Push operation ensuring that Cur_Len < Max_Len before any call on Push. However, Cur_Len and Max_Len are not exported in the Stack interface, so we need to provide functions that reveal their value, say "Count" and "Max_Stack_Size." So our new Stack abstraction would look like this:

interface Stack
  <Component is Assignable<>; 
   Size_Type is Integer<>> is
    function Max_Stack_Size(S : Stack) -> Size_Type;
    function Count(S : Stack) -> Size_Type;
    function Create(Max : Size_Type) -> Stack;
    function Top(S : ref Stack) -> ref Component;
    procedure Pop(S : ref var Stack);
    procedure Push
      (S : ref var Stack {Count(S) < Max_Stack_Size(S)}; 
       X : Component);
end interface Stack;

class Stack is
    const Max_Len : Size_Type;
    var Cur_Len : Size_Type {Cur_Len in 0..Max_Len};
    type Index_Type is Size_Type {Index_Type in 1..Max_Len};
    var Data : Array<optional Component, Indexed_By => Index_Type>;    
  exports
    function Max_Stack_Size(S : Stack) -> Size_Type is
      return S.Max_Len;
    end function Max_Stack_Size;
    
    function Count(S : Stack) -> Size_Type is
      return S.Cur_Len;
    end function Count; 

    function Create(Max : Size_Type {Max > 0}) -> Stack is
      return (Max_Len => Max, Cur_Len => 0, Data => [.. => null]);
    end function Create;

    procedure Push
      (S : ref var Stack {Count(S) < Max_Stack_Size(S)}; 
       X : Component) is
      S.Cur_Len += 1;
      S.Data[S.Cur_Len] := X;
    end procedure Push;
      
    function Top(S : ref Stack) -> ref Component is
      return S.Data[S.Cur_Len];
    end function Top;                

    procedure Pop(S : ref var Stack) is
      S.Cur_Len -= 1;
    end procedure Pop;
end class Stack;

So with these changes, Push should now compile. However, we are going to run into similar problems in Top and Pop, and we will need a precondition on both of those of {Count(S) > 0}. Top also presents a more subtle problem. The Data array is defined as being an array of optional Element_Type, but we are returning S.Data[S.Cur_Len] with a return type of simply Element_Type, implying that we somehow know that S.Data[S.Cur_Len] is not null. So how do we know that? Well, we know that Push only pushes non-null elements onto the stack (because the parameter type for X is a non-optional Element_Type. But Data starts out all null, and when looking only at Top we have no way of knowing that S.Data[S.Cur_Len] is not null.

What we need is some kind of class invariant which ensures that when we get into Top, S.Data[S.Cur_Len] is not null. What might that invariant look like? What we know about a stack is that all of the elements that have been pushed onto the stack are non-null, but the slots in the stack past Cur_Len might be null if they have never been used. So our invariant would seem to be:

   {for all I in 1..Cur_Len => Data[I] not null}

The basic requirement for a class invariant is that, presuming it is true on entering any externally visible operation, it is true again on exiting that operation. It might be false in the middle of some operation, but it is preserved overall by all visible operations. Furthermore, for any operation that creates an object of type Stack, the returned object must satisfy the invariant.

So let us check whether the above proposed invariant is true upon creation of a Stack object, and is preserved by operations that modify a Stack. Create produces a new value with Cur_Len == 0, so the invariant is trivially true, since there are no values in the interval 1..Cur_Len. Push and Pop modify a Stack object. Pop is trivial since it is decrementing Cur_Len, so the interval 1..Cur_Len is shrinking. Push is not trivial, because it is adding one to Cur_Len. But if we presume the invariant holds on entry to Push, then the only new value to worry about is S'.Data[S'.Cur_Len], where S' represents the value of S after the Push operation is complete. Since S'.Data[S'.Cur_Len] is set to X, and X is not null, our invariant is preserved.

Note that we might have tried an invariant of simply {Data[Cur_Len] not null}, which would have satisfied Top, and would be preserved by Push, but it would not be preserved by Pop, since without the more sophisticated invariant, Pop would know nothing about S'.Data[S'.Cur_Len]. It might be null if the invariant only claims that the very top element is non-null.

So after adding the class invariant, and the various preconditions, we can now get the Stack abstraction to compile. However, it now becomes time to write some code that tests the Stack abstraction. What we quickly discover is that the compiler rejects any call on any Stack operation with a precondition, since there are no postconditions that would allow it to know whether Count(S) > 0 or Count(S) < Max_Stack_Size(S). At the call site there is no peeking into the class that defines the interface. The compiler must prove the preconditions of the call looking only at information in the interface. And without any postconditions, the compiler is stuck.

So now we have to start adding postconditions to the operations. If we do a Create and then immediately try to do a Push onto the created stack object, our first job is to prove that Count(S) < Max_Stack_Size(S). This implies we need a postcondition on Create that indicates the values of Count() and Max_Stack_Size() for the result of Create. We could write this as follows:

   {Max_Stack_Size(Create) == Max; Count(Create) == 0}

What this says is that the result of Create (within a postcondition, we can use the name of the creating function to represent the result) has a Max_Stack_Size that corresponds to the passed in parameter Max, and starts out with a Count of zero. No big surprise here, but without such a postcondition the compiler would be pretty much at a loss. We also might want to impose a precondition on Max of {Max > 0} just so the stack is at least of some use.

Next question we might have is what happens to Count as a result of Push. This brings up an interesting question that is sometimes called the frame problem. How do we know what might be written by an operation -- what is the write frame? (We might also be interested in exactly what might be read by an operation -- what is the read frame -- but that is less relevant as far as checking preconditions.) Since the Push operation has S as a ref var parameter, we could assume the worst and assume any function of S' (the value of S after Push) might return a different value, so after Push we know pretty much nothing about Count(S') and Max_Stack_Size(S'). Alternatively, we could take the view that if there is no postcondition, then nothing is changed.

For ParaSail we are (tentatively) adopting a model that for any function of S mentioned in any precondition of an operation on a Stack object S, if such a function is not mentioned in a postcondition then it is presumed unchanged. Now that we have mentioned Count() and Max_Stack_Size() in the preconditions of Push, we are duty bound to write postconditions any time the value of Count() or Max_Stack_Size() is changed. This obligation will be checked when we compile the Stack class, so having written some preconditions, the compiler is going to start complaining because Count(S') is clearly going to be different from Count(S) after the call on Push. Similar obligations will apply to Pop. So now we will need to add a postcondition to Push of {Count(S') == Count(S) + 1} and a postcondition to Pop of {Count(S') == Count(S) - 1}. We don't need to say that {Max_Stack_Size(S') == Max_Stack_Size(S)} because as indicated, our default assumption is that anything used in any precondition, but not mentioned in a postcondition, is presumed to be unchanged by the operation. Again, the compiler will check that when it compiles the code for the operation. If we don't want to say anything about the new value other than it is not the same as the old value, we could say {Some_Property(S') != Some_Property(S)}. That won't help the compiler with proving later preconditions, but it will at least satisfy the obligation to mention the changed property in a postcondition.

So if we continue this process until we make the compiler happy, both with the Stack module itself, and with our various test programs, we will probably end up with a relatively fully annotated Stack like the following:

interface Stack
  <Component is Assignable<>; 
   Size_Type is Integer<>> is
    function Max_Stack_Size(S : Stack) -> Size_Type;
    function Count(S : Stack) -> Size_Type;

    function Create(Max : Size_Type {Max > 0}) -> Stack 
      {Max_Stack_Size(Create) == Max; Count(Create) == 0};
    
    procedure Push
      (S : ref var Stack {Count(S) < Max_Stack_Size(S)}; 
       X : Component) {Count(S') == Count(S) + 1};

    function Top(S : ref Stack {Count(S) > 0}) -> ref Component;
    
    procedure Pop(S : ref var Stack {Count(S) > 0}) 
      {Count(S') == Count(S) - 1};
end interface Stack;

class Stack is
    const Max_Len : Size_Type;
    var Cur_Len : Size_Type {Cur_Len in 0..Max_Len};
    type Index_Type is Size_Type {Index_Type in 1..Max_Len};
    var Data : Array<optional Component, Indexed_By => Index_Type>;    
  exports
    {for all I in 1..Cur_Len => Data[I] not null}   // invariant for Top()

    function Max_Stack_Size(S : Stack) -> Size_Type is
        return S.Max_Len;
    end function Max_Stack_Size;
    
    function Count(S : Stack) -> Size_Type is
      return S.Cur_Len;
    end function Count; 

    function Create(Max : Size_Type {Max > 0}) -> Stack
      {Max_Stack_Size(Create) == Max; Count(Create) == 0} is
      return (Max_Len => Max, Cur_Len => 0, Data => [.. => null]);
    end function Create;

    procedure Push
      (S : ref var Stack {Count(S) < Max_Stack_Size(S)}; 
       X : Component) {Count(S') == Count(S) + 1} is
      S.Cur_Len += 1;
      S.Data[S.Cur_Len] := X;
    end procedure Push;
      
    function Top(S : ref Stack {Count(S) > 0}) -> ref Component is
      return S.Data[S.Cur_Len];
    end function Top;                

    procedure Pop(S : ref var Stack {Count(S) > 0}) 
      {Count(S') == Count(S) - 1} is
        S.Cur_Len -= 1;
    end procedure Pop;
end class Stack;

One thing to note is that the compiler has not forced us to create postconditions that ensure all the nice properties of Stacks, such as after Push(S,X), then Top(S') == X, or if Top(S) == A, then after Push(S, X) and Pop(S'), Top(S'') == A. These might be called correctness preconditions as opposed to merely safety preconditions, and they are up to the programmer to add if they see fit. We have considered having a second class annotation in ParaSail which is not required to be provable at compile-time, but is designed to aid in correctness proofs, and provide additional debugging support. We have set aside a syntax of doubly nested {{...}} for such correctness preconditions, but we aren't worrying about them more than that at this point.

WoDet 2011, ParaSail, and back to the future with Value Semantics

2011-03-09T00:14:00.000-05:00

This past Sunday WoDet 2011, the 2nd Workshop on Determinism and Correctness in Parallel Programming was held in Newport Beach, CA. It was a very interesting event, with a number of excellent talks and a lively debate at the end on the topic of whether current programming models are sufficient given the right tools, etc., or whether we need fundamentally new models to support programming going forward in a multi-core world.

After listening to the various talks at the workshop, and while thinking about the debate topic, it seemed that ParaSail aligned nicely with an underlying thread in the research community moving toward, or perhaps returning to, what might best be called value semantics. A number of the talks described one variant or another of multi-version concurrency control, which at its heart involves giving different threads their own private copy/version/snapshot of an object, and then dealing with merging any updates at specific later points, possibly rolling back one of the threads if no meaningful merge is possible. This is in contrast to an approach where multiple threads share access to a single object, and use some kind of locking or "careful" lock-free operations to make direct updates to the shared object. The multi-version approach results in fewer interactions between the threads, fewer synchronization points, and hence generally higher throughput in a highly parallel world.

Looked at another way, the multi-version approach means that objects are being passed around by value rather than by reference, and updating the original object is done after all the new "values" have been generated independently and then appropriately merged (perhaps using some kind of parallel merging process). This isn't going all the way to pure functional programming, because updates can eventually happen, but the bulk of the processing is performed on object values, with no underlying sharing.

If we go all the way back to the original versions of BASIC, a la Kemeny and Kurtz or Microsoft CP/M BASIC, pointers didn't exist, but there were strings, and you could create them and concatenate them and assign them, and you never by mistake overwrote memory because you concatenated into a too-short buffer, nor did you ever have two variables unintentionally referring to the "same" string in memory, such that changing one would unintentionally alter what you had in the other (even though the implementation might choose to share the space until one of them was altered).

These kinds of value-semantics strings still exist in many scripting languages, but they have essentially disappeared from compiled languages in the years since BASIC was widely used (and compiled, in some cases). In almost all modern compiled languages, strings are manipulated by reference, though in some languages they are immutable which to some extent skirts the issue of by-value vs. by-reference semantics. And certainly when you get to larger, more abstract objects, by-reference semantics rules, with only the simplest of "struct" objects being manipulated by value. And even when declared objects have value semantics, parameters generally revert to by-reference semantics, again introducing the possibility of unintended aliasing between two distinctly named objects. (Or if by-value semantics are available for parameter passing (as in C++), it can result in "slicing" of the object, so that it is truncated from its original run-time type to the compile-time type of the formal parameter.)

Unintended aliasing due to by-reference semantics can cause nasty (but still reproducible) bugs in any sequential language that uses by-reference semantics, but in a parallel language, such bugs can become race conditions, which can result in hard-to-reproduce, timing-dependent bugs.

In any case, the net effect of the various ParaSail rules that restrict aliasing, eliminate reassignable pointers, disallow global variables, etc. is that ParaSail provides value semantics for all non-concurrent objects, of arbitrarily complex types. Note that this does not imply that objects need to be copied when passed as a parameter. Rather the ParaSail rules allow non-concurrent objects to be passed by reference or by copy, with the same results. This allows efficient by-reference parameter passing when the call stays within the same address space, but allows transferring the object between address spaces, such as might be needed by a call between a CPU and a GPU. This essentially value semantics eliminates a large class of common bugs, and makes it straightforward for the compiler to detect and disallow at compile-time any possible race conditions.

As implied by the growing interest in multi-version concurrency control in the research community, a return to the world of value semantics might be a good answer for the multi-core challenges.

Streaming in Parasail -- A Unix-like pipeline

2011-03-01T10:38:00.000-05:00

We have been considering how streaming can best be supported in ParaSail. By streaming we mean having a series of components each of which reads inputs from a stream and writes outputs to a stream, with each component running in parallel with the others. The most natural seems to be to define an abstract Stream_Component interface which takes an Input_Stream and Output_Stream type and declares an operation Transform which reads one or more input elements from the Input_Stream, transforms the input(s) in some way, and then writes one or more output elements to the Output_Stream. An actual component would be defined by some concrete module that implements this abstract interface, with an appropriate constructor function that provides whatever arguments are needed to specify or control the transformation.

This might be the abstract Stream_Component interface:

abstract interface Stream_Component
  <Input_Stream<>; Output_Stream<>> is
    procedure Transform
      (Args : Stream_Component;
       Inp : ref var Input_Stream; 
       Outp : ref var Output_Stream);
end interface Stream_Component;

The Input_Stream and Output_Stream interfaces might look like this:

abstract concurrent interface Input_Stream
  <Element_Type is Assignable<>> is
    function Get(Stream : queued var Input_Stream) -> optional Element_Type;
end interface Input_Stream;

abstract concurrent interface Output_Stream
  <Element_Type is Assignable<>> is
    procedure Put
      (Stream : queued var Output_Stream; Element : Element_Type);
    procedure Close(Stream : queued var Output_Stream);
end interface Output_Stream;

We now want to put together two or more stream components into a pipeline. Let us presume we define a Pipeline interface:

interface Pipeline
  <Pipe_Input is Input_Stream<>;
   Pipe_Output is Output_Stream<>> 
  implements Stream_Component<Pipe_Input, Pipe_Output> is
    operator "|"
     (Left is Stream_Component
        <Pipe_Input,
         Output_Stream<Internal_Type is Assignable<>>;
      Right is Stream_Component
        <Input_Stream<Internal_Type>,
         Pipe_Output>)
     -> Pipeline;
    procedure Transform
      (Args : Pipeline;
       Inp : ref var Pipe_Input; 
       Outp : ref var Pipe_Output);
end interface Pipeline;

The pipeline "|" operator takes two stream components and produces a Pipeline stream component, feeding the output of the first stream component into the input for the second stream component, by using an IO_Queue:

concurrent interface IO_Queue<Element_Type is Assignable<>> 
  implements Input_Stream<Element_Type>, Output_Stream<Element_Type> is
    function Create(Buffer_Size : Univ_Integer := 100) -> IO_Queue;
    function Get(Queue : queued var IO_Queue) -> optional Element_Type;
    procedure Put
      (Queue : queued var IO_Queue; Element : Element_Type);
    procedure Close(Queue : queued var IO_Queue);
end interface IO_Queue;

When constructing a pipeline from two stream components, the output stream of the first must have the same Element_Type as the input stream for the second, so that they can be opposite ends of the IO_Queue. The result pipeline has the same input stream as the first, and the same output stream as the second. The implementation of the pipeline Transform procedure would construct an IO_Queue object and then pass it to parallel invocations of the Transform procedures of the two stream components:

class Pipeline is
    const Left : Stream_Component+;
    const Right : Stream_Component+;
  exports
    operator "|"
     (Left is Stream_Component
        <Pipe_Input,
         Output_Stream<Internal_Type is Assignable<>>;
      Right is Stream_Component
        <Input_Stream<Internal_Type>,
         Pipe_Output>)
     -> Pipeline is
      return (Left => Left; Right => Right);
    end operator "|"; 
    procedure Transform
      (Args : Pipeline;
       Inp : ref var Pipe_Input; 
       Outp : ref var Pipe_Output) is
        var Queue : IO_Queue := Create();
      then
        Transform(Left, Inp, Queue);
      || 
        Transform(Right, Queue, Outp);
    end procedure Transform;
end class Pipeline;

If we have a set of components with both input and output streams being streams of characters, then the "|" operator is essentially equivalent to the Unix shell's "|" pipe command. To write a "program" that is compatible with such a pipeline, we define a module that implements Stream_Component, with Input_Stream and Output_Stream both having Element_Type of Character<>. Any constructor function within such a module may be used to provide the parameters to the program. The Transform procedure of the module is the one that actually performs the action of the program. Alternatively, we can be somewhat more flexible, and allow the streams to have higher level element types, such as words or lines.

For example, here is a trivial "element count" program, which allows the input element type to be any sort of thing. The output element type is presumed to be some Character type:

interface Elem_Count
  <Input_Stream<>, Output_Stream<Character<>>>
  implements Stream_Component
    <Input_Stream, Output_Stream> is
    function Args()->Elem_Count;  // takes no parameters
    procedure Transform
      (Args : Elem_Count;
       Inp : ref var Input_Stream; Outp : ref var Output_Stream);
       // Prints a count of the elements in Inp on the Outp stream
end interface Elem_Count;

class Elem_Count is
  exports
    function Args() -> Result : Elem_Count is
      return;
    end function Args;
    procedure Transform
      (Args : Character_Count;
       Inp : ref var Input_Stream; Outp : ref var Output_Stream) is
       // Prints a count of the elements in Inp on the Outp stream
       var Count : Univ_Integer := 0;
       while Get(Inp) not null loop
         Count += 1;
       end loop;
       const Answer : String<Output_Stream::Element_Type> := To_String(Count);
       // Copy the answer to the output stream one character at a time
       // (in all probability, we would actually use an output stream
       //  with an operation that takes a string of characters directly).
       for each C of Answer forward loop
          Put(Outp, C);
       end loop;
       Close(Outp);
    end procedure Transform;
end class Elem_Count;

In a more realistic example, the Args constructor function would take one or more arguments, which it would store as fields of the stream component object. The Transform procedure would refer to the arguments using the Args parameter, which is an instance of the stream component object.

Presuming we create a number of stream components like Elem_Count, we could construct a pipeline like the following:

Read::Args("my_file.txt") | Break_Into_Words::Args() | Elem_Count::Args()

This would presumably read my_file.txt producing a stream of characters, break it into a stream of words, and then count the words and produce the count as a string on the output stream of characters. With a little syntactic sugar by some kind of ParaSail "shell" this could become:

Read my_file.txt | Break_Into_Words | Elem_Count

This is a little bit of a "cheat" as we would have to pass in the "Context" or equivalent to "Read" to provide it access to the underlying file system. The Context argument could presumably be supplied automatically as part of the syntactic sugar provided by the "shell" if desired.

Map/Reduce in ParaSail; Parameterized operations

2011-02-08T17:29:00.000-05:00

The Map/Reduce paradigm popularized by Google has a long history. In APL, there is a reduction operator "/", which can be combined with an operator like "+" to reduce a vector to a scalar, by summing its individual members. That is "+/ V" adds up the elements of V producing a scalar sum. To include a map operation, you could simply insert the name of the scalar->scalar function of interest in the middle, and you get the map-reduce functionality. For example, "+/ V*2" would produce the sum of squares of the vector V ("*" is exponentiation in APL, "x" is used for multiplication).

In Google's variant of Map/Reduce, the input is a vector of key/value pairs, and the map operation takes one key/value pair and produces as output a list of key/value pairs. The reduce operation takes all values produced by any map invocation with the same key and combines them to produce a single value, or optionally a list of values, to be associated with this (output) key.

A simple, parallel version of Map/Reduce can be implemented relatively straightforwardly in ParaSail, as a single function, parameterized by the input and output types of the "Map" function:

// ParaSail Function to perform Map-Reduce operation.

function Map_Reduce
  (function Map(Input is Any<>) -> (Output is Any<>);
   function Reduce(Left, Right : Output) -> Output;
   Inputs : Vector<Input>)  {Length(Inputs) > 0} -> Output is
       // Handle singleton directly, recurse for longer inputs
       if Length(Inputs) == 1 then
         return Map(Inputs[1]);
       else
         // Split and recurse
         const Half_Length := Length(Inputs)/2;
         return Reduce
           (Map_Reduce(Map, Reduce, Inputs[1..Half_Length]),
             Map_Reduce(Map, Reduce, 
        Inputs[Half_Length <.. Length(Inputs)]));
       end if;
end function Map_Reduce;

procedure Test() is  // Test Map_Reduce function -- compute sum of squares
    Print_Int(Map_Reduce
      (Map => lambda(X : Integer) -> Integer is (X**2),
       Reduce => "+",
       Inputs => [1, 2, 3, 4, 5, 6]));
end procedure Test;

In ParaSail, the parameters in any call can be evaluated concurrently, so the two operands in the call on Reduce, which are recursive calls on Map_Reduce, will become separate pico-threads, allowing the Map_Reduce to be executed using a binary tree of pico-threads, providing significant potential for parallelism.

A couple of things to notice about the ParaSail implementation. One key feature is that one parameter of an operation may provide type parameters for a later parameter. In this case, the Map parameter has two type parameters, indicated by the use of the "type_name is interface_name<>" notation. This says that the type (which must be an instance of module that implements interface_name) of the corresponding parameter of the actual Map function is henceforth available as type_name for use in later parameters and within the body of the operation. It would be possible to make these instead be type parameters of an enclosing module, but it is more natural (and in some cases more powerful) to have the type parameters determined by the actual operation provided. C++ provides a similar capability with template functions, where there is no need to explicitly specify the function template arguments, since the compiler can generally deduce the types from the call on the function, but the type parameters are not generally available outside the template function itself. In ParaSail, the actual operation passed in for a parameter like Map can determine types that are to be used for later parameters (such as Reduce and Inputs) to the module or operation of which they are a parameter.

A second feature to notice is the use of an anonymous lambda construct in the call on Map_Reduce within the Test procedure, which allows a relatively simple operation (such as squaring) to be created at the point of call. It would also be possible to declare a function named, for example, Square, immediately before the call and pass that. Note also that we can pass an operator such as "+" as the actual operation for the formal Reduce parameter.

Thinking/Drinking in Parallel in ParaSail

2011-02-01T17:28:00.000-05:00

As mentioned in an earlier post, we have put up a "Drinking Philosopher's" example in the google group for ParaSail:

http://groups.google.com/group/parasail-programming-language

When writing this example, there was only one loop which ended up sequential which seems like it could have been concurrent -- the one in the Eliminate_Duplicates function:

    function Eliminate_Duplicates(Bottle_Map : Phil_To_Bottle_Map) 
      -> Result : Phil_To_Bottle_Map 
          {(for all P1 in Philosopher_Index =>
             for all P2 in Philosopher_Index => 
                if P1 != P2 then Result[P1] * Result[P2] == [])}
        // Ensure that there are no duplicates in resulting mapping
          {(for all B in Bottle_Index => for some P in Philosopher_Index =>
              B in Result[P])}
        // Ensure that every bottle is somewhere
    is
        var Earlier_Bottles : Bottle_Set := [];

        for Phil in Philosopher_Index loop
            // Remove bottles assigned to earlier philosophers
            // NOTE: We don't actually need a "forward loop" here
            //       so long as the loop runs sequentially.
            //       "Earlier" bottles merely means earlier iterations,
            //       independent of the order in which they are performed.
            Result[Phil] := Bottle_Map[Phil] - Earlier_Bottles;
            Earlier_Bottles += Result[Phil];
        end loop;

        if Count(Earlier_Bottles) != Num_Bottles then
            // Some bottles not assigned to anyone
            // Give them to Philosopher 1
            Result[1] += [1..Num_Bottles] - Earlier_Bottles;
        end if;

    end function Eliminate_Duplicates;

When first written, it was written as a forward loop, but after looking at the logic, it became clear that there was no particular dependence on order, so making it the default unordered loop seemed preferable. But upon further thought, it seems that there is a straightforward concurrent solution to removing duplicates from a mapping like this.

The input mapping (Bottle_Map) is a map from philosophers to bottles, where to make it interesting, multiple philosophers are interested in the same bottle. However, to start the simulation going, we want to know where the bottles should start out, so we want a mapping from philosophers to bottles that has no duplicates; that is, a bottle is associated with only one philosopher. As you can see above, we eliminated duplicates by accumulating a set of bottles already assigned (Earlier_Bottles) as we went through the sequence of philosophers, and subtracted this set from each set of bottles in the Bottle_Map as we processed the next philosopher. This is inherently a sequential algorithm (even if the actual sequential order doesn't matter).

If we want to think in parallel, we might think about a more free for all approach. Namely, each philosopher tries to grab each of the bottles of interest, and first come, first serve! It turns out with this approach there is one danger: if we end up with a perfectly symmetrical initial state, such that each philosopher ends up with one of the two bottles they want, then the simulation could enter an immediate deadlock.

In Chandy and Misra's paper, they show that so long as the initial graph of preferences is not cyclic, then the individual steps will preserve the acyclic nature. We accomplished this originally with the sequential loop, where the first philosopher gets all of the bottles they want, the next gets all but those already assigned, and so on. This avoids starting out with a symmetric, deadlock-prone, cyclic preference graph.

We can accomplish the same thing in a series of concurrent loops using a different approach: we initialize the bottles and bar stools to a default state, and then complete the initialization incrementally, rather than trying to precompute the initial mapping of philosophers to bottles:

    var Bottles : Array<Bottle, Indexed_By=> Bottle_Index> :=
      [Bottle_Index => Create(1)];

    var Bar_Stools : Array<Bar_Stool, Indexed_By=> Philosopher_Index> :=
      [Philosopher_Index => Create([])];
    
    for Phil in Philosopher_Index concurrent loop
        for B in Who_Drinks_What[Phil] concurrent loop
            Set_Initial_Owner(Bottles[B], Phil);
        end loop;
    end loop;

    for B in Bottle_Index concurrent loop
        Add_Initial_Bottle(Bar_Stools[Initial_Owner(Bottles[B])], B);
    end loop;

The new operations, Set_Initial_Owner/Initial_Owner, and Add_Initial_Bottle, would have to be added to the Bottle and Bar_Stool interfaces, respectively. Set_Initial_Owner would update the bottle's Who_Gets_It field only if the new owner had a higher Philosopher_Index, thereby ensuring the acyclic preference graph. Originally initializing the Who_Gets_It to a default value of 1 ensures that Philosopher 1 ends up with any bottles of no interest to anyone. The Initial_Owner function would simply return the value of Who_Gets_It for the given Bottle, which, at the point of call, is the Philosopher with the highest index with an interest in the bottle. The Add_Initial_Bottle operation would then add the given bottle to the Used_Bottles set of the Bar_Stool associated with that highest-numbered Philosopher.

Clearly a programmer's goal with a language like ParaSail is to minimize the amount of sequential code, so that as the number of available processors goes up, the program will have the parallelism to take advantage of them. Having primitives which make it easy and safe to do things concurrently helps, but the programmer will still have to shift their thinking a bit to achieve the full potential benefit.

Philosopher examples

2011-01-27T10:55:00.000-05:00

We have just posted two new examples to the ParaSail Google group -- a very simple dining philosophers example, and a more interesting drinking philosophers example, based on Chandy and Misra's 1984 ACM TOPLAS paper. The drinking philosophers example was more challenging as it required orchestrating the use of two different concurrent data structures, one representing a philosopher's bar stool, and one representing the bottles being shared between the philosophers.

To see these examples, visit ParaSail Google Group.

CUDA, OpenCL, Cilk, and ParaSail

2011-01-04T09:26:00.000-05:00

NVIDIA, AMD, and Intel have all gotten interested in parallel programming languages over the past few years, and for good reason. It is clear that all programmers will have to start learning how to take advantage of parallelism if they expect their programs to continue to benefit from Moore's law, with its wonderful doubling of computing power every two years. And chips that make it easier to take advantage of parallelism will be the more successful chips.

NVIDIA has been championing CUDA as the way to use their GPUs for general purpose parallel processing (GPGPU), though they have also been part of the group designing OpenCL, which is the more hardware-independent approach first developed by Apple and now being standardized by the Khronos group. AMD (after swallowing ATI) started with CTM (Close to Metal) and some other approaches, but now seem to be putting most of their energy behind OpenCL for GPGPU programming. Intel has been encouraging a number of different approaches, including Cilk, Threading Building Blocks (TBB), Concurrent Collections (CnC), etc., and they are part of the OpenCL effort as well.

Cilk and OpenCL seem to be emerging as two important, rather distinct approaches to parallel programming. Cilk makes it easy to spawn threads off to compute an arbitrary expression, and then uses a set of worker processes to service the threads, using the approach we discussed in an earlier post, where threads spawned by a given worker are serviced LIFO, but when a worker runs out of threads, it steals from other workers using a FIFO strategy. OpenCL, on the other hand, is focused on data parallelism, where many data items are all being manipulated in nearly the same way. It is roughly a SIMD (Single Instruction Multiple Data) approach, though some variation in control flow is permitted, meaning that it is somewhat closer to the SPMD (Single Program, Multiple Data) approach fostered by the Connection Machine folks. In OpenCL (and CUDA), the per-data-item code is bundled into a kernel, which is essentially a function that operates on a single data item in a large array or stream of such items.

So how does this relate to ParaSail? In some ways, Cilk and OpenCL can be seen as lower-level languages, where the programmer has to worry about identifying particularly places where threads should be spawned (in Cilk), or worry about extracting kernels from code that operates on an array or stream (in OpenCL). ParaSail on the other hand is focused on expressing the algorithm at a relatively high level with pervasive opportunities for parallelism, presuming the compiler or run-time support routines can identify how best to map all of the opportunities for parallelism on to the underlying parallel hardware.

One of the key advantages that ParaSail provides is that there is no hidden aliasing, unlike in C, C++, Java, etc., where aliasing is everywhere. (Cilk and OpenCL are both piggy-backed on C/C++; various threading APIs are available to Java, C#, Python, etc.) This makes it dramatically easier for a compiler or run-time to automatically partition computations into pieces to be executed in parallel. Furthermore, the ParaSail compiler detects all race conditions (and various other problems) at compile time, has no exceptions, allows memory to be partitioned into non-overlapping regions, etc., which simplify both the programmer's model and the process of automatic parallelization.

Parallel Quicksort in ParaSail and "slicing"

2010-12-17T12:17:00.005-05:00

Quicksort is a classic "divide-and-conquer" algorithm, and lends itself naturally to parallelization. However, unlike some of the other algorithms we have discussed in past postings, it is updating rather than merely walking a data structure. This means that we need a way to safely partition the array to be sorted so that the ParaSail compiler knows that the threads are manipulating non-overlapping parts of the array, so it can be certain there are no race conditions possible.

In several languages there is the notion of an array slice. In particular, in Fortran and Ada there is built-in syntax for selecting a contiguous part of an array. In newer versions of Fortran this can be done on multi-dimensional arrays. In Ada slicing is limited to single-dimensional arrays. In both Fortran and Ada, array slices are updatable, that is they effectively represent a view of the underlying array. APL (not surprisingly!) has all of these capabilities and more. In many other languages there are operations for selecting a slice of a string (and in some cases arrays), but these are generally not updatable views, and hence cannot be used on the left-hand side of an assignment nor be passed as an in out parameter. In some cases there are explicit "replace-slice" operations which do allow for updating a slice of an array.

In any case, in ParaSail, because we expect the compiler to catch race-conditions at compile-time, operations that return a view of a part of an object need to have well-defined properties so the compiler can correctly determine whether two different views have any overlap (i.e. are potentially aliased). The simplest solution seems to be to recognize a "slicing" operator, similar to the "indexing" operator. A "slicing" operator would take an indexable container, and then one or more operands at least one of which is an interval or a set, and return a view of the container that represents the subset of components identified by the operand(s). For example, this might be an interface for a One_Dim_Array with both "indexing" and "slicing" operators:

interface One_Dim_Array
  <Element_Type is Assignable<>;
   Index_Type is Discrete<>> is

    function Bounds(A : One_Dim_Array) -> Interval<Index_Type>; 

    function Create(Bounds : Interval<Index_type>)
      -> One_Dim_Array {Bounds(Create) == Bounds};

    operator "indexing"(
       A : ref One_Dim_Array;
       Index : Index_Type {Index in Bounds(A)})
     -> ref Element_Type;

    operator "slicing"(
       A : ref One_Dim_Array;
       Slice : Interval<Index_Type> {Is_Subset(Slice, Bounds(A))})
     -> ref Result: One_Dim_Array {Bounds(Result) == Slice};
    ... 
end interface One_Dim_Array;

As with the "indexing" operator, the "slicing" operator would be invoked by using A[...] notation, but where one or more of the operands inside the [] would be intervals or sets. The ParaSail compiler would impose requirements on implementations of "indexing" and "slicing" operators. For a given "indexing" operator, if the operands are different in two different calls, then the resulting elements must be distinct. For a given "slicing" operator, if the operands are non-overlapping sets or intervals, then the resulting slices must be non-overlapping. Note that the implementor of the "slicing" operator can decide whether the bounds of the result correspond to those of the selecting interval, or slide back to always starting at zero or one. In the above example, the bounds correspond to the original indices of the selected elements, as indicated by the postcondition on the "slicing" operator. In an interface designed for string manipulation, it might be more convenient for the slice to have bounds starting at zero or one.

Note that if there are multiple "indexing" operators, or multiple "slicing" operators for the same type, then they are presumed to be creating potentially overlapping elements or views, as they presumably represent different indexing schemes into the same data structure. For example, a hash-table might be indexable both by the key and by some unique internal index. That is, there is no guarantee that A["key"] and A[35] are unaliased just because "key" and 35 are distinct values, presuming these represent invocations of different "indexing" operators defined for the same indexable container.

Note that in all languages, you can achieve the equivalent of slicing by passing in the entire array and the bounds for the sub-array of interest. This would however not allow the compiler to determine as easily whether two different calls are manipulating non-overlapping slices by looking only at the call sites. A goal with ParaSail is that the compiler can identify any possible race-conditions by looking only at call sites and associated pre- and postconditions. This argues for having explicit ways of indicating in a precondition or postcondition what parts of an object are read, what parts are updated, and what parts are not referenced at all. Bu this probably comes back to being able to specify slices of a container, if only in annotations.

In any case, given the above notion of "slicing" operators, we are now in a position to write our parallel Quicksort:

interface Sorting<One_Dim_Array<>> is
    procedure Quicksort(Arr : ref var One_Dim_Array;
       function Before(Left, Right : One_Dim_Array::Element_Type) 
         -> Boolean is "<");
          // Sort Arr according to the sorting function "Before" 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
  exports
    procedure Quicksort(Arr : ref var One_Dim_Array;
       function Before(Left, Right : One_Dim_Array::Element_Type) 
         -> Boolean is "<")
    is
        // Handle short arrays directly.  Partition longer arrays.
        case Length(Arr) of
          [0..1] => return;
          
          [2] => 
               if Before(Arr[Arr.Last], Arr[Arr.First]) then
                   // Swap elements
                   Arr[Arr.First] :=: Arr[Arr.Last];
               end if;
               return;
               
          [..] =>
               // Partition array
               const Mid := Arr[Arr.First + Length(Arr)/2];
               var Left : Index_Type := Arr.First;
               var Right : Index_Type := Arr.Last;
               until Left > Right loop
                 var New_Left : Index_Type := Right+1;
                 var New_Right : Index_Type := Left-1;
                 block
                   // Find item in left half to swap
                   for I in Left .. Right forward loop
                       if not Before(Arr[I], Mid) then
                           // Found an item that can go into right partitition
                           New_Left := I;
                           if Before(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 Before(Mid, Arr[J]) then
                           // Found an item that can go into left partitition
                           New_Right := J;
                           if Before(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 Before(Mid, Arr[I]));
                (for all J in Left .. Arr.Last : not Before(Arr[J], Mid));
                (for all K in Right+1 .. Left-1 : 
                  not Before(Mid, Arr[K]) and not Before(Arr[K], Mid))}
               
               // Recurse on two halves
               block
                   Quicksort(Arr[Arr.First .. Right], Before);
                 ||
                   Quicksort(Arr[Left .. Arr.Last], Before);
               end block;
        end case;        
   end procedure Quicksort;
end class Sorting;

We have used slicing as part of the recursion. Because the compiler can prove Left > Right, there is no overlap between the two slices, and hence no race condition. It turns out that in ParaSail we could have written this without explicit recursion by using the continue loop with ... construct. We will save that for a later posting.

Deterministic parallelism and aliasing in ParaSail

2010-12-03T13:47:00.000-05:00

There is growing interest in parallelization approaches that provide deterministic results. See for example Deterministic Parallel Java. In ParaSail, we have a somewhat different model. Determinism should be provided for computations when it makes sense, but when the program is interactive or part of a real-time system, then clearly the environment is dynamic and time-dependent, and the notion of determinism becomes less relevant, and arguably not even desirable.

It turns out that it is easy to know when non-determinism might be entering the execution of a ParaSail program. It occurs only as a result of operations on concurrent objects. Because ParaSail eliminates all race-conditions associated with non-concurrent objects at compile time, the results of a ParaSail program that manipulates only non-concurrent objects are inherently deterministic. However, should the programmer decide to use a concurrent object, then the order in which operations on the concurrent object are performed by concurrent threads is unspecified, though the programmer can control it to some extent by specifying dequeue conditions when the operand is marked as queued. (See blog posting parasail-concurrent-interfaces.html for more information on queued operands.)

Minimizing use of concurrent objects is generally a good idea anyway for performance reasons, as there is inevitably more overhead involved in coordinating access to a shared object, even when using lock-free approaches. But how can a group of threads work in parallel to build up a large data structure, without the data structure itself being a concurrent object? The normal answer to such a question is divide and conquer.

What does divide and conquer really mean in ParaSail terms? That means that a data structure needs to be conceptually divided up into non-overlapping parts and passed out to multiple threads for manipulation. In ParaSail, a function can return a reference to a part of an object passed by reference as an input to the function. However, the compiler needs to understand the aliasing implications of that, since in ParaSail, the compiler disallows race-conditions, which implies it must understand all aliasing related to non-concurrent objects at compile-time. If two potentially concurrent computations are both updating parts of the same non-concurrent object, then the compiler must be able to convince itself that the two parts are non-overlapping (i.e. not aliased with one another).

Because there are no (re)assignable pointers in ParaSail, there are no cycles in data structures, so it is clear that Obj.Left and Obj.Right do not overlap. On the other hand, when dealing with generalized containers, it is more difficult to know whether Container[X] and Container[Y] overlap, and even more complex when we are calling arbitrary functions that happen to return a reference to part of their input parameter, such as Lower_Left(Matrix) and Upper_Right(Matrix). Clearly the programmer needs some way in a postcondition of such a function to convey the aliasing properties of the result.

ParaSail has a built-in, primitive, Basic_Array interface. The compiler has built-in knowledge that, given an object BA based on the Basic_Array interface, BA[X] does not alias with BA[Y] if X != Y. So one way to describe the "part" of a container that is included within the result of calling a function like "Lower_Left" is to describe the set of underlying array indices associated with the elements of the container that can be referenced from the result of Lower_Left. More generally we can see that there is a set of primitive subcomponents accessible via any reference to a part of a container, and the aliasing problem comes down to proving that the subcomponent set from one reference does not overlap with the subcomponent set from some other reference. This all implies that ParaSail needs a notation for identifying the set of accessible subcomponents of a reference, and a built-in Subcomponent_Set interface for specifying the values and the relationships between these subcomponent sets.

Type conversion in ParaSail

2010-11-01T16:43:00.001-04:00

Allowing for user-defined type conversion is complex, as it is an NxN problem, where you want to allow conversion of N different types to each other, and each pair might involve a different set of operations. ParaSail addresses this problem in the following ways:

Allows use of the [[ ... ]] operation, which converts the operand to a universal type.

The user defines which universal type(s) a given type converts to by defining the "to_univ" operator(s). Once the value has been converted to a universal type, it will be implicitly converted to any other type which defines a "from_univ" operator from that same universal type.

Using a prefix can disambiguate if necessary: T2::[[T1_Obj]] will convert T1_Obj first to a universal type using T1's "from_univ" operator, and then to T2 using T2's "to_univ" operator.

Allows use of the target type's name as a function name.

This will convert between two types that are structurally equivalent (that is, the same module parameters were used in their defining instantiation), but which were distinguished by one or both being defined as new. For example:

type T1 is new Vector<Integer<>> and type T2 is new Vector<Integer<>> define two distinct types because of the use of new, but T2(T1_Obj) and T1(T2_Obj) will convert T1_Obj to type T2, and T2_Obj to type T1, respectively.

The target type's name can also convert an object from some source type if the user defines a "convert" operator for either of the two types, and this operator's input and output parameter types match the source and target of the conversion. Note that this matching might be thanks to the input or output formal being itself parameterized. For example, the interface Int_Vector below provides a "convert" operator that converts to any other instance of Int_Vector:

            interface Int_Vector<Element is Integer<>> is
               ...
               operator "convert"(X : Int_Vector) 
                 -> Result_Type is
                      Int_Vector<Target_Element is Integer<>>;
            end interface Int_Vector;

These capabilities seem to provide enough flexibility for the user to define the desired explicit conversion functions. Note that the only implicit conversion in ParaSail is from a universal type to a type with an appropriate "from_univ" operator.

A virtual machine for ParaSail with picothread scheduling

2010-11-01T11:01:00.000-04:00

As we have worked toward having an initial compiler/interpreter for ParaSail, we have decided to define a ParaSail Virtual Machine (PSVM) which will support the kind of very-light-weight threading structure (picothreading) needed to be able to evaluate small constructs, like parameters in parallel. We have decided to turn each ParaSail operation into a single PSVM Routine, even if its execution will involve multiple threads executing bits and pieces of the code for the operation. Each PSVM routine is identified by a unique index, the routine index, and is represented by a routine header and a sequence of PSVM instructions.

The ParaSail Virtual Machine instructions use relatively conventional addressing modes to refer to operands in memory. Memory is presumed to be organized into areas, each area being a contiguous sequence of 64-bit words. While executing, a PSVM routine has access to the following areas:

Parameter_Area: An area for input and output parameters. Output parameters, if any, come first, followed by input parameters. Parameters may be a single 64-bit value, or may be a 64-bit pointer to a larger object.
Local_Area: An area for storing local variables, and parameter lists being built up to pass as a Parameter_Area to a called routine. The first word of a local area is a link to the local area of the enclosing block or operation, in the presence of nesting. This sort of link is generally called a static link. The second word of a local area is a link to the associated parameter area.
Type_Area: Each type, which is an instance of a module, is represented by an area containing the actual module parameters, and a table of operations. Each operation in the operation table is represented by a pair: routine index and type area. In many cases the type area for an operation is the same as the enclosing Type_Area, but for inherited operations, the type area for the operation would refer to the type area for the super-class from which the operation was inherited. The actual module parameters are most frequently other types (represented by a pointer to their type area), but can be values, object references, or operations.

Instructions identify a memory location of interest by a pair: memory area and offset. This pair is called an object locator. In addition to the Parameter_Area, Local_Area, and Type_Area, an object locator can specify a memory area pointed-to by a local variable, and the locator offset is the offset within the pointed-to area. The local pointers are called local base registers, and may reside in any of the first 64 words of the local area. Finally, in the presence of nesting, the chain of static links may be followed to find an enclosing local area or enclosing parameter area.

Here is a sampling of ParaSail Virtual Machine instructions:

Move_Word, Store_Int_Literal, Store_String_Literal, Store_Real_Literal, Jump, Conditional_Jump, Call, Return, Parallel_Call, Parallel_Block, Parallel_Wait. 

Operands are generally identified with object locators, except for literal operands which are identified either by their actual value, or by an index into a table of literals.

Note that there are no instructions for doing normal arithmetic or logical operations. These are all implemented by calling routines. There are a set of built-in routines for doing the typical set of arithmetic and logical operations, on operands of various sizes.

The more interesting instructions are the Parallel_Call, Parallel_Block, and Parallel_Wait. Parallel_Call is essentially equivalent to Call, where the calling routine computes the input parameters and places them in a parameter area, and then calls the routine. The difference with a Parallel_Call is that the caller also identifies a picothread master and allocates a small area for a picothread control block (pTCB), and the instruction completes without waiting for the call to complete. Instead, the Parallel_Call instruction adds the pTCB to a queue waiting to be serviced by one of the virtual processors (vCPUs) executing the ParaSail program. When the caller thread has finished its own work and wants to wait for the Parallel_Call to complete, it uses the Parallel_Wait instruction, identifying the same picothread master as was specified in the Parallel_Call instruction. This suspends the calling thread until all of the parallel picothreads associated with the picothread master complete.

The Parallel_Block instruction is very similar to the Parallel_Call instruction, except that it identifies instructions that are part of the current routine, rather than calling a separate routine. The execution of these instructions is performed by a separate picothread, which has its own pTCB, and local area. The static link of the local area for the Parallel_Block picothread refers to the local area of the thread invoking the Parallel_Block instruction, allowing the nested picothread to use up-level references to reach the local variables of the enclosing picothread.

The Return instruction is used to complete processing of both a Parallel_Call and a Parallel_Block, and the Parallel_Wait is used to wait for either kind of parallel activity.

We recently completed a prototype implementation of the ParaSail Virtual Machine, including the picothread scheduling. We learned some interesting lessons along the way. Initially, a vCPU that was executing a picothread that performed a Parallel_Wait was itself suspended. That quickly exhausted the number of vCPUs, and led us to start dynamically creating new vCPUs. That caused the overall stack space to grow dramatically, since each vCPU needed its own heavy-weight threading context in the underlying operating system, along with a stack.

At this point, we concluded that a vCPU that executed a Parallel_Wait instruction should service the queue of waiting pTCBs if the picothread master it was waiting for was not yet complete. That significantly reduced the number of vCPUs needed. However, it still didn't seem to be as efficient as it could be. As originally implemented, the queue of waiting pTCBs was first-in, first-out (FIFO). However, after looking at various traces of execution, we realized that it was the last pTCB that was created which was always the first pTCB to be awaited. Hence, we concluded that the pTCB queue should be last-in, first-out (LIFO). That is, a vCPU should preferentially service the most recently queued pTCB when it had cycles to spare, since that would more likely be associated with a picothread master that is being awaited, and by servicing that pTCB first, it will reduce the number of pTCBs that were suspended in a Parallel_Wait instruction. After making this final change, even a heavily recursive algorithm throwing off lots of parallel picothreads was handled efficiently.

Notation for "intervals" in ParaSail

2010-09-14T09:25:00.000-04:00

It is quite common in a precondition or postcondition to want to indicate that the value of a variable must be within some interval of values (aka "range" of values), such as 1..10, or 0..+inf. When dealing with real values (e.g. floating point values) as opposed to integer values, it is often desirable to represent an open or half-open interval, where the boundary value is not included in the specified interval. For example, to specify that X must be in the interval 0.0 .. 10.0, but not including zero itself, the notation "(0.0 .. 10.0]" is sometimes used, where where "(" and ")" represent an open (exclusive) boundary, while "[" and "]" represent a closed (inclusive) boundary.

For ParaSail, because "()" and "[]" are already used in the syntax, we have adopted a different notation for open and half-open intervals:

0.0 .. 10.0       closed interval
0.0 <.. 10.0     half-open on left
0.0 ..< 10.0     half-open on right
0.0 <..< 10.0   open on both sides

Hence, one can write in an annotation:

{ X in A <.. B }

as a short-hand for

{ A < X and then X <= B }

with the additional difference that X is only evaluated once (though that will rarely matter in an annotation).

Like the other relational operators, these interval operators are defined automatically once the "=?" operator has been appropriately defined.

Finalization (destructors) and multi-thread exits in ParaSail

2010-09-01T07:42:00.000-04:00

Languages such as C++ and Ada that support both finalization (destructors) and exceptions generally face some degree of distributed overhead due to the complex interactions between these two features. Since exceptions can arise virtually anywhere, if there is finalization to be performed (e.g. destructors to be called) on the way "out" of a scope, there is generally a need for some kind of per-thread cleanup list to be walked as part of propagating exceptions, or the need for numerous implicit exception handlers and a precise indication of exactly how much initialization has been performed (e.g. constructors that have been completed) at any given moment.

As indicated in an earlier post, we have tentatively decided to do without exceptions in ParaSail, but the exit ... with feature can result in potentially numerous scopes being exited in the various other threads which are all being terminated as a result of some thread initiating an exit from a compound statement such as a block or loop. We have also suggested that ParaSail will support some notion of finalization, if an "end" operator is associated with the type of an object, such that on exiting the scope of the object, the "end" operator will be invoked automatically. So the question is: must these "end" operator calls be performed on all of the local objects of the threads being terminated as a side effect of an exit by some parallel thread? Our tentative answer is "no."

To avoid race conditions between a thread being terminated and the code executing after an exit, we believe that we need to restrict a thread that might be prematurely terminated, so that it can update only objects local to the exitable construct. The only code of an exitable construct that would be permitted to update objects declared outside the construct would be the code following an "exit ... with" or the code following "end ... with".

For example, here is the exitable construct we used in an earlier post:

const Result : optional Tree_Id;
for T => Root then T.Left || T.Right
while T not null concurrent loop
    if T.Value == Desired_Value then
// Found desired node, exit with its identifier
        exit loop with (Result => T.Id);
    end if;
end loop with (Result => null);

In this example, we might have many threads all executing inside the loop concurrently. To avoid race conditions, we would not allow any of these threads to update objects declared outside the loop, because they might be terminated at any moment, and the update might be disrupted in the middle. However, we would allow the code following the "exit loop with" to update Result, as well as the code following "end loop with." This is safe because only one of these is ever executed for a given execution of the loop, and once we begin executing such code it won't be disrupted by some other thread of the same loop initiating an exit.

Note that the code following an exit ... with or end ... with might be disrupted by a thread exiting some enclosing construct, but this code would not be allowed to update objects outside that enclosing construct, thereby avoiding the race condition.

Given this rule that code in a compound statement with multiple threads may not update objects declared outside the compound statement, if there is a chance that at least one of those threads might perform an exit ... with, we can simplify the finalization problem. There is no need to invoke the "end" operator on an object if that operator cannot possibly affect objects that will survive the exit statement.

Thinking more specifically about the "end" operator, and the general lack of access to global variables within an operation, what exactly can an "end" operator do? The answer is that an "end" operator cannot really do anything unless the object being finalized includes a reference of some sort to an object that will outlive the finalization. We will talk more in a future posting about what if any restrictions exist on incorporating a reference to one object as part of another object, but for now let us presume that such objects can exist, but they cannot be overwritten by a whole-object assignment statement (i.e. they are not "assignable").

What would be the purpose of such an object with an embedded reference? One use would be to perform a kind of "mark/release" style of resource allocation. On entry to a scope, a "mark" object could be created with a reference to an enclosing resource manager of some sort. Inside the scope, allocations of the resource would be mediated by the "mark" object, such that when exiting the scope, the "end" operator applied to the "mark" object could automatically release all of the resources allocated on behalf of objects local to the scope.

Now returning to our original question about whether finalization needs to be performed on all objects local to a thread that is being prematurely terminated -- if we presume that the "end" operators are performing something analogous to a "release" operation, then we can see how we could safely skip all intermediary release operations so long as we perform the ones associated with the actual compound statement being exited. This also presumes that the only references permitted from an object local to a multi-threaded compound statement with an exit, to an object declared outside the compound statement, are references to concurrent objects that are themselves local to the innermost enclosing multi-threaded-with-exit compound statement. For example:

var Enclosing_Obj1 : concurrent T := ...
    ...
*Block1*
block
    var Mark1 := Create_Mark(Enclosing_Obj1, ...);
// Mark1 contains a reference to Enclosing_Obj1
        // and has an "end" operator which performs a release operation.
    for I in 1..10 concurrent loop
var Mark2 := Create_Mark(Mark1, ...);
              // Here we have an inner mark
          Allocate_Resource(Mark2, ...);
   // Here we allocate some resource using Mark2 to mediate the
             // allocation from Mark1 which in turn is mediating allocation
             // from Enclosing_Obj1. The marks allow the resources to be
             // automatically released on block exit as a side effect of
   // finalization via the "end" operator.
if This_Looks_Good(I, ...) then
               exit block Block1 with (Result => I);
                 // This terminates any other threads inside Block1.
          end if;
    end loop;
end block Block1 with (Result => 0);

Now if some thread is deep within a call on "This_Looks_Good" when some other thread initiates the block exit, the only object that gets explicitly finalized will be Mark1. The multiple Mark2 objects (one for each thread of the concurrent loop) will not be finalized, as presumably performing an "end" on Mark1 will also release any allocations that were mediated by one of the Mark2 objects.

The bottom line is that when a tree of threads is terminated by an exit from a multi-threaded compound statement, the only finalization that needs to be performed is for the objects immediately local to the compound statement being exited. Objects local to the various threads being terminated need not be separately finalized. This avoids the kind of complex interaction that exists between finalization and exception propagation, including avoiding the overhead of maintaining precise initialization information, and avoiding performing a lot of potentially wasteful finalization.

No exceptions in ParaSail, but exitable multi-thread constructs

2010-08-24T13:41:00.000-04:00

We have been mulling over the idea of exceptions in ParaSail, and have pretty firmly concluded that they aren't worth the trouble. In a highly parallel language, with lots of threads, exception propagation across threads becomes a significant issue, and that is a nasty area in general. Also, exceptions can introduce many additional paths into a program, making thorough testing that much harder. And the whole business of declaring what exceptions might be propagated, and then deciding what to do if some other exception is propagated can create numerous maintenance headaches.

There is a feature in ParaSail as currently designed which provides some of the same capabilities of exceptions, but is particularly suited to parallel programming. This is the "exit with" statement, which allows a construct to be exited with one or more values specified as results, and at the same time terminating any other threads currently executing within the construct. For example, here is a loop implementing a parallel search of a tree with the first thread finding the desired node exiting and killing off all of the other threads as part of the "exit ... with" statement:

const Result : optional Tree_Id;
for T => Root then T.Left || T.Right
while T not null concurrent loop
    if T.Value == Desired_Value then
// Found desired node, exit with its identifier
        exit loop with (Result => T.Id);
    end if;
end loop with (Result => null);

This declares a Result object of type Tree_Id. It then walks the tree in parallel, starting at Root and continuing with T.Left and T.Right concurrently. It continues until it reaches "null" on each branch, or some node is found with its Value component matching the Desired_Value. The value of Identifier at the end indicates the identifier of the node having the desired Value, or null to indicate that no node was found. The presence of optional in the declaration for Result indicates that its value might be null.

Supporting this kind of intentional "race" seems important in parallel programming, as many problems are amenable to a divide and conquer approach, but it is important that as soon as a solution is found, no further time is wasted searching other parts of the solution space. The "end ... with" phrase allows the specification of one or more results if the construct ends normally, as opposed to via an "exit ... with" (in this case, ending normally means all threads reach a null branch in the walk of the tree without finding the desired node). Effectively the "exit ... with" skips over the "end ... with" phrase.

So how does this all relate to exceptions? Well given the "exit ... with" capability, one can establish two or more threads, one which monitors for a failure condition, and the others which do the needed computation. The thread monitoring for a failure condition performs an "exit ... with" if it detects a failure, with the result indicating the nature of the failure, and as a side-effect killing off any remaining computation threads. If the normal computation succeeds, then an "exit ... with" giving the final result will kill off the monitoring thread. Note that the "exit ... with" statements must occur textually within the construct being exited, so it is visible whether such a premature exit can occur, unlike an exception which can arise deep within a call tree and be propagated out many levels.

As an example of the kind of failure condition which might be amenable to this kind of monitoring, imagine a resource manager object, which provides up to some fixed maximum of some kind of resource (e.g. storage) to code within a block. This resource manager (which is presumably of a concurrent type) could be passed down to operations called within the block for their use. Meanwhile, a separate monitoring thread would be created immediately within the block which would call an operation on the resource manager which would suspend the thread until the resource runs out, at which point it would be awakened with an appropriate indication of the resource exhaustion, and any other information that might be helpful in later diagnosis. On return from this Wait_For_Exhaustion operation, the monitoring thread would do an "exit block with (Result => Failure, ...)" or equivalent, to indicate that the computation required more resources than were provided. The code following the block would then be able to take appropriate action.

Initial implementation model for ParaSail types

2010-08-23T18:16:00.000-04:00

ParaSail supports object-oriented programming, and as such there needs to be some kind of run-time representation for types to support dispatching calls (aka virtual function calls, method calls, etc.). Most "normal" objects need no run-time type information associated with them, but an object or parameter of a polymorphic type (such as "Int_Expr+") needs some run-time type information to support dispatching calls on its operations. In addition, each operation of an interface generally needs an implicit parameter identifying its "enclosing" type, to gain access to the module parameters, given that every module is effectively a "generic" module.

Because ParaSail supports multiple inheritance of interfaces (including ad hoc interface matching -- see blog entry on that topic), a simple table of operations for each type with a compile-time-known slot-number in the table doesn't work as it would if ParaSail only supported single inheritance. Instead we adopt the notion of a "type view" which consists of a pointer to the overall table of operations of the type, as well as an "slot-number mapping" to provide the particular "view" of the type. The slot-number mapping is a simple vector of operation slot numbers for the operation table, indexed by the interface slot number of the particular interface through which the type is being "viewed." For example, presume we have an interface "Assignable" with only two operations, say, Assign and Copy, with interface slot numbers one and two. Given some type with many operations, where the operation slot numbers of 21 and 33 are for Assign and Copy respectively, then the Assignable "view" of the type would have a slot-number mapping of:

      [1 => 21, 2 => 33]

The actual operation table would be a vector of pairs, each pair being a reference to the type from which the code for the operation was inherited, and the reference to the actual code for the operation. Hence, the operation table for Type_C could be imagined as something like:

     [1 => (Type_A, Op1_Code),
      2 => (Type_B, Op2_Code),
      ...,
     21 => (Type_A, Assign_Code),
     ...,
     33 => (Type_C, Copy_Code),
     ...]

Here we assume that the code for Op1 and Assign originated with Type_A, the code for Op2 originated with Type_B, and the code for Copy originated with Type_C.

In addition to an operation table, a type would have a table of module actuals, one for each module formal parameter. Module actuals could be themselves "type views," operations, or (constant) objects.

If an interface declared externally-visible components (const or var), these would be represented for uniformity by operations that take a reference to an object of the interface's type and return a reference to the component. This allows multiple inheritance of such (at least conceptual) components from one or more implemented interfaces, though the actual offset of the components within the object (or whether they are true components in the case of consts) might very well differ from the corresponding components of the interface.

When an operation is called, in addition to its explicit parameters, it would be passed a reference to the type from which it originated. This would allow it to gain access to the other operations of its module, as well as to the module actuals. Because ParaSail allows the type from which a type is extended to be overridden (see blog entry on ParaSail extension, inheritance, and polymorphism), the operation table may vary depending on which type is the base for extension (since the type from which a given operation originates could vary). Hence an operation doesn't necessarily "know" where one of the other operations of its module originates (presuming the operation is inherited rather than redefined within the module's class directly).

Because each type has its own operation table with pointers to the code for each operation, it is possible for some of the operations to be specially compiled for that type, rather than simply reusing the "generic" code generated when the module was first compiled. This allows the code to incorporate information about the module actuals (as an optimization), rather than having to use the information only at run-time which is what the "generic" code would do. Hence, in the example above, the Copy_Code for Type_C might incorporate directly information about the module actuals or the operation table for Type_C, rather than having to index into the table of module actuals or into the operation table at run-time.

Other implementation models are of course possible, but this one seems to have the advantage of uniformity and flexibility, with constant-time run-time performance for making a dispatching call.

Ad hoc interface matching in ParaSail

2010-08-23T15:25:00.000-04:00

When a module is instantiated in ParaSail to form a type, actual parameters must be specified for each module formal parameter. When the module formal is itself a type, the module actual must be a type that matches the formal appropriately.   For example, given:

interface Set<Element_Type is Assignable<>> is
    function Union(Left, Right : Set) -> Set;
    function Unit_Set(Elem : Element_Type) -> Set;
   ...
end interface Set;

we will want to be able to write:

    type My_Int_Set is Set<My_Integer_Type>;

Now the question is whether My_Integer_Type must be based on an interface that is explicitly indicated as extending or implementing Assignable, or should we simply require that My_Integer_Type has all of the operations expected of a type based on Assignable. In other words, does an actual type match a formal type only if it extends or implements the specified interface, or is ad hoc matching permitted, where at the point of instantiation a check is made that all of the required operations are present? A similar question would come up when converting an object of a particular type to a polymorphic type (such as Assignable+).

Our initial instincts were to require that the actual type (or the type being converted) explicitly extend or implement the formal type (or the target type). However, this will tend to cause a proliferation of interfaces being added to the list of implements for any given module, such as Assignable or Comparable or Numeric or ..., and still the actual subset of operations of interest might not be mentioned explicitly.

Given the above concern, we now favor allowing ad hoc matching requirements for matching of module actuals to module formals, and when converting from a normal type to a polymorphic type. There are some potential problems during maintenance if the operations of an interface change, but those problems exist anyway, since any code that makes calls on individual operations defined in an interface may suffer maintenance issues when operations change. Note, however, that adding operations to the actual type, or removing them from the formal type, don't create maintenance issues.

In general, there are many fewer places where modules are instantiated, or conversions to polymorphic types occur, than there are normal calls on operations, and defining and using (presumably abstract) interfaces such as Assignable or Comparable as module formals, if they capture exactly what operations of interest are needed by the module, could reduce rather than increase maintenance problems when trying to decide whether to change an existing operation of some interface.

So the answer to the above question about instantiating Set with My_Integer_Type is now answered as follows: My_Integer_Type must provide the operations defined in the interface Assignable, but it need not directly or indirectly extend or implement Assignable. This generally means that the list of interfaces specified in the implements list is there primarily for documentation, and for imposing a linkage such that if additional operations are added to the implemented interface, the need to define the operations is known at the point of module definition, rather than being deferred until some point of use. This also implies that when ad hoc matching is used, there is a presumption that the module formal (or target type) is very stable and new operations are not expected to be added to it. A type like Assignable<> certainly qualifies.

Eliminating the need for the Visitor Pattern in ParaSail

2010-08-23T14:33:00.002-04:00

The "Visitor" pattern is one of the more widely recognized patterns identified by the "Gang of Four" in Design Patterns: Elements of Reusable Object-Oriented Software. Object-oriented programming makes it relatively painless to add more types into a type hierarchy, but it makes it relatively painful to add more operations to an existing type hierarchy. The Visitor pattern is intended to allow adding more operations without doing major surgery on the original type hierarchy, but it requires the use of a visitor object, plus an additional operation, often called accept, on each type, which turns around and calls a visit operation on the visitor object that is unique to that particular type in the hierarchy.

Object-oriented frameworks like that of Common Lisp Object System effectively eliminate the need for the visitor pattern by allowing the addition of dispatching operations (aka virtual functions, methods, etc.) after the type hierarchy has been established, with CLOS in particular allowing additional methods to be added to preexisting generic functions.

In ParaSail, we propose to support the definition of additional dispatching operations to be used with polymorphic types in a somewhat more modular way. The basic idea is that an interface hierarchy can be extended horizontally in addition to vertically. By this we mean that an additional named bundle of operations may be specified for the root interface of an interface hierarchy, and then this same named bundle may be defined for each descendant of this root interface, such that operations from this new bundle may be "dispatched" to when operating on polymorphic objects, just as can be the operations of the original root interface.

Here is an example based on a simple interface hierarchy used to represent numeric expressions:

interface Expr <Value_Type is Integer<>> is
    function Evaluate(E : Expr) -> Value_Type;
end interface Expr;

interface Binary extends Expr is
type Binary_Op_Enum is Enum<[#add, #sub, #mul, #div, ...]>;
function Create(Op : Binary_Op_Enum; Left, Right : Expr+) -> Binary;
    function Evaluate(B : Binary) -> Value_Type;
end interface Binary;

interface Unary extends Expr is
type Unary_Op_Enum is Enum <[#plus, #minus, #not, #abs, ...]>;
function Create(Op : Unary_Op_Enum; Operand : Expr+) -> Unary;
    function Evaluate(U : Unary) -> Value_Type;
end interface Unary;

interface Leaf extends Expr is
    function Create(Value : Value_Type) -> Leaf;
function Evaluate(L : Leaf) -> Value_Type;
end interface Leaf;

    ...

interface Calculator<Int_Expr is Expr<>> is
    ...
    procedure Print_Value(Str : Output_Stream; E : Int_Expr+) is
// E is of the polymorphic type Int_Expr+
    // so calls on its operations will dispatch.
        const Result := Evaluate(E);   // dispatching call
        Print(Str, Result);
    end procedure Print_Value;
end interface Calculator;

Now if we decide we want to add some more "dispatching" operations, we could either disrupt the existing hierarchy of interfaces by adding the operation to each interface, or we could add an operation to each interface to support the visitor pattern, and use that for defining additional operations. For ParaSail, we are proposing a third approach:

interface Expr[#output] is
    function Text_Image(E : Expr) -> Univ_String;
function XML_Image(E : Expr) -> Univ_String;
    ...
end interface Expr[#output];

interface Binary[#output] is
    function Text_Image(B : Binary) -> Univ_String;
    function XML_Image(B : Binary) -> Univ_String;
    ...
end interface Binary[#output];
...

Here we have defined an interface extension labeled "#output". We could define additional interfae extensions with other labels. Now we have effectively added Text_Image and XML_Image as dispatching operations of Expr without a need for a visitor pattern and without disrupting the original Expr interface hierarchy. These operations are available when we refer to "Expr[#output]" rather than simply "Expr". If we had another extension labeled "#input," we could gain access to both by referring to "Expr[#input | #output]".

Then we could write:

interface Calculator<Int_Expr is Expr[#input | #output]<>> is
   // Now we can use operations from the #input and #output extensions
       // of Expr when manipulating polymorphic objects of type Int_Expr+
    ...
    procedure Print_Expr_And_Value(Str : Output_Stream; E : Int_Expr+) is
// E is of the polymorphic type Int_Expr+
    // so calls on its operations (including those from the
        // interface extensions #input and #output) will dispatch.

        const Result := Evaluate(E);   // dispatching call.
Print(Str, Text_Image(E));      // Now display the expression
        Print(Str, " = ");
        Print(Str, Result);                    // and then display its value.
    end procedure Print_Expr_And_Value;
end interface Calculator;

This approach allows the definition of additional dispatching operations in a modular fashion to an existing type hierarchy, while not disrupting existing users. It seems to provide some advantages over the Visitor pattern approach as well, as the new operations are not second class citizens requiring the construction of a visitor object, etc.

Pointer-free primitives for ParaSail

2010-07-19T10:35:00.000-04:00

Having pretty much settled on eliminating explicit pointers from ParaSail (largely to simplify compile-time alias analysis and race-condition elimination), the question is: what sorts of primitive data structures are needed in ParaSail to allow the user to construct essentially arbitrary abstractions on top of the primitives without using explicit pointers? The ParaSail interface/class module already provides a basic kind of basic record or struct capability. As mentioned in an earlier posting, we have also suggested the use of the keyword optional to signify that an object might or might not have a value of its specified type, with its default being a null value. Internally this could be implemented either with an extra bit to signify null-ness, or with an implicit level of indirection with a null pointer used to indicate null-ness (some indirection is clearly necessary for a recursive data structure).

By using the optional keyword and the basic record capability provided by a class, the user can quite easily construct structures such as linked lists and binary trees. However, more complex structures will have to end up falling back on a generalized notion of container with pointers replaced by the use of generalized indexing. For example, a directed graph structure can be represented by a vector of nodes with the edges between the nodes being represented by indices into the vector. To some extent this is going back to a Fortran array-oriented view of the world. However, with the arrays being extensible, and the elements of the arrays being arbitrarily complex objects, which themselves are potentially optional and extensible, there is significantly more flexibility available to the programmer than what the original Fortran arrays provided.

As a first stab at what primitive container types are needed, it would seem that a basic array type, indexed by integers, and extensible only by whole-array assignment with a longer or shorter array, might be adequate. The elements of the array would be of an arbitrary type, including user-defined types. The whole-array assignment would deal with whatever storage management is necessary to reuse or reclaim the prior value of the object being assigned. The compiler would attempt to arrange to have the new value be created in the storage region associated with the object to which it will be assigned, so as to avoid having to physically move the new value into that storage region as part of the assignment (see earlier post on region-based storage management). For example, given:

    var X : Basic_Array<...> := Build_Array(Length => 10);
    ...
    X := Extend_Array(X, New_Length => 20);

the compiler would arrange for the calls on Build_Array and Extend_Array to create their resulting array in a storage region appropriate for X, so that the assignment need not move the created array into that region. Essentially, as part of being called, a function would receive information about the region in which its result(s) should be allocated. This information would be propagated as necessary to try to minimize the unnecessary movement of data between storage regions as part of an assignment operation.

It would seem that with this combination of the record-like capability provided by classes, the notion of optional, and something like this Basic_Array type extensible only by whole-array assignment, we have all of the building blocks needed to create arbitrary data structures in ParaSail without the use of pointers.

Updated (A)Yacc grammar for ParaSail

2010-07-18T14:56:00.000-04:00

Here is an update to the ParaSail (A)Yacc grammar posted a few weeks ago. This one has no shift/reduce or reduce/reduce conflicts. The "N Queens" example is accepted by this grammar. Below the grammar is the slightly updated (A)Flex lexer:

--------------------------------------
-- Tentative YACC Grammar for ParaSail
--------------------------------------

-- Single-character delimiters --
%token ',' ';' ':' '.'
%token '+' '-' '*' '/' 
%token '?'
%token '(' ')' '[' ']' '<' '>' '{' '}'
%token '|' 
%token PRIME -- '''

-- Compound delimiters --
%token COMPARE -- "=?"
%token EQ   -- "=="
%token NEQ  -- "!="
%token GEQ  -- ">="
%token LEQ  -- "<="
%token POWER  -- "**"
%token ASSIGN -- ":="
%token SWAP   -- ":=:"
%token DOT_DOT -- ".."
%token DOUBLE_COLON  -- "::"
%token DOUBLE_LEFT_BRACKET  -- "[["
%token DOUBLE_RIGHT_BRACKET -- "]]"
%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 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 IF_kw
%token IMPLEMENTS_kw
%token IMPORT_kw
%token IN_kw
%token INTERFACE_kw
%token IS_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 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 VAR_kw
%token WHILE_kw
%token WITH_kw
%token XOR_kw

%start module_list

{ 
   subtype yystype is integer;
}


%%

module_list : 
    module
  | module_list module
  ;

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

import_clauses : 
  | import_clauses IMPORT_kw qualified_name_list ';'
  ;

qualified_name_list : 
    qualified_name
  | qualified_name_list ',' qualified_name
  ;

interface_declaration : 
   opt_interface_qualifier INTERFACE_kw module_defining_name 
     formals_and_implemented_interfaces
     IS_kw
      interface_element_list
   END_kw INTERFACE_kw module_defining_name ;
   
opt_interface_qualifier : interface_qualifier | ;

interface_qualifier : 
    class_qualifier
  | ABSTRACT_kw opt_class_qualifier
  ;

opt_class_qualifier : class_qualifier | ;

class_qualifier : CONCURRENT_kw ;

standalone_operation_definition : 
    function_definition
  | procedure_definition
  ;

formals : '<' opt_module_formal_list '>' ;

formals_and_implemented_interfaces :
    formals
  | formals implements_list
  | opt_formals EXTENDS_kw interface_name opt_implements_list
  ; 

opt_formals : formals | ;

opt_implements_list : implements_list | ;

implements_list : IMPLEMENTS_kw interface_name_list ;

interface_name_list :
    interface_name
  | interface_name_list ',' interface_name
  ;

interface_name : module_name | module_instantiation ;
   
module_name : qualified_name ;

module_defining_name : qualified_name ;

opt_module_formal_list : module_formal_list | ;

module_formal_list : 
    annotated_module_formal 
  | 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 : annotation | ;

type_formal : 
    Identifier IS_kw module_instantiation 
  | module_instantiation 
  ;

operation_formal : operation_declaration ;

value_formal : 
    id_list ':' type_specifier 
  | id_list ':' type_specifier ASSIGN simple_expression  -- to avoid use of '>'
  ;

id_list : 
    Identifier
  | id_list ',' Identifier
  ;

type_name : 
    qualified_name 
  | polymorphic_type_name
  ;

polymorphic_type_name : qualified_name '+' ;

qualified_name : 
    Identifier 
  | qualified_name DOUBLE_COLON Identifier ;


module_instantiation : 
  module_name '<' opt_module_actual_list '>' ;

opt_module_actual_list : module_actual_list | ;

module_actual_list :
    module_actual 
  | module_actual_list ',' module_actual 
  ;

module_actual : 
    simple_type_specifier_or_expression
  | Identifier REFERS_TO simple_type_specifier_or_expression
  ;

-- simple_expression subsumes simple type_name in this rule
simple_type_specifier_or_expression : 
    qualified_name annotation      -- polymorphic type name not allowed here
  | simple_expression              -- simple_expr to avoid problems with '>'
  | module_instantiation
  ;
  
annotated_type_specifier : 
    type_specifier
  | type_specifier annotation
  ;

type_specifier : 
    opt_CONCURRENT_kw type_name 
  | opt_CONCURRENT_kw module_instantiation 
  ;

opt_CONCURRENT_kw : CONCURRENT_kw | ;

interface_element_list : 
  | interface_element_list interface_element ';'
  ;

interface_element : 
    operation_declaration 
  | object_declaration 
  | interface_declaration 
  | type_declaration 
  ;


class_definition :
   opt_class_qualifier CLASS_kw module_defining_name 
      class_formals_and_implemented_interfaces
   IS_kw
      class_element_list
   END_kw CLASS_kw module_defining_name ;

class_formals_and_implemented_interfaces :
    formals_and_implemented_interfaces
  | opt_formals EXTENDS_kw Identifier ':' interface_name opt_implements_list
  ; 


class_element_list : 
    local_class_element_list
  EXPORTS_kw 
    exported_class_element_list ;

local_class_element_list :
  | local_class_element_list local_class_element ';'
  ;

local_class_element : interface_element | exported_class_element ;
  
exported_class_element_list :
  | exported_class_element_list exported_class_element ';'
  ;

exported_class_element : 
    operation_definition 
  | object_definition 
  | class_definition 
  ;
  
   
annotation : '{' annotation_element_list '}' ;

annotation_element_list : 
    annotation_element
  | annotation_element_list ';' annotation_element
  ;

annotation_element : interface_element | condition | quantified_expression ;

condition : expression ;


operation_declaration : 
    function_declaration 
  | procedure_declaration 
  | operator_declaration 
  ;

function_declaration :
  FUNCTION_kw Identifier operation_inputs GIVES operation_outputs ;

procedure_declaration :
  PROCEDURE_kw Identifier operation_inputs ;
  
operator_declaration :
  OPERATOR_kw operator_designator operation_inputs opt_gives_operation_outputs ;

opt_gives_operation_outputs : GIVES operation_outputs | ;
  
operator_designator : String_Literal ;
  
operation_inputs :
    simple_operation_input opt_annotation
  | annotation simple_operation_input opt_annotation
  | '(' opt_annotated_operation_input_list ')' opt_annotation
  ;

simple_operation_input :   -- avoids trailing use of "IS"
    id_list ':' 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_list ';' annotated_operation_input
  ;

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

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 : input_modifier | ;
  
simple_operand_type_specifier :
    type_name
  | module_instantiation
  ;

operand_type_specifier : 
    simple_operand_type_specifier
  | Identifier IS_kw module_instantiation 
         -- NOTE: Operation can have "type" parameters 
         -- such as "Left_Type is Integer<>"
  ;

input_modifier : 
    output_modifier 
  | QUEUED_kw opt_output_modifier
  | LOCKED_kw opt_output_modifier
  ;


operation_outputs : 
    simple_operation_output opt_annotation
  | annotation simple_operation_output opt_annotation
  | '(' annotated_operation_output_list ')' opt_annotation
  ;

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

annotated_operation_output_list :
    annotated_operation_output
  | 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 | ;

output_modifier :  
    OPTIONAL_kw
  | REF_opt_optional_mutable 
  | REF_opt_optional_mutable VAR_kw 
  | REF_opt_optional_mutable CONST_kw 
  ;

REF_opt_optional_mutable :
    REF_kw
  | REF_kw OPTIONAL_kw
  | REF_kw MUTABLE_kw
  | REF_kw OPTIONAL_kw MUTABLE_kw
  ;

object_declaration : 
    VAR_kw Identifier ':' 
      opt_OPTIONAL_kw opt_MUTABLE_kw annotated_type_specifier 
      opt_ASSIGN_expression
  | CONST_kw Identifier ':' opt_OPTIONAL_kw annotated_type_specifier 
      opt_ASSIGN_expression
  ;

opt_ASSIGN_expression : ASSIGN expression | ;
   
object_definition :
    CONST_kw Identifier ASSIGN expression
  | VAR_kw Identifier ASSIGN expression
  | CONST_kw Identifier REFERS_TO name
  | VAR_kw Identifier REFERS_TO name
  ;

opt_OPTIONAL_kw : OPTIONAL_kw | ;
opt_MUTABLE_kw : MUTABLE_kw | ;

type_declaration : 
    TYPE_kw Identifier IS_kw opt_NEW_kw annotated_type_specifier ;

opt_NEW_kw : NEW_kw | ;

operation_definition : 
    function_definition 
  | procedure_definition 
  | operator_definition 
  ;

function_definition : 
  function_declaration IS_kw 
     statement_list_with_semi 
  END_kw FUNCTION_kw Identifier ;

procedure_definition : 
  procedure_declaration IS_kw 
     statement_list_with_semi 
  END_kw PROCEDURE_kw Identifier ;

operator_definition : 
  operator_declaration IS_kw 
     statement_list_with_semi 
  END_kw OPERATOR_kw Identifier  ;

statement_list_opt_semi :
    statement_sequence
  | statement_list_with_semi
  ;

statement_list_with_semi : 
    statement_sequence_with_semi
  | statement_list_opt_semi PARALLEL statement_sequence_with_semi
  ;

statement_list :                -- "||" is lower precedence than ";" and ";;"
    statement_sequence
  | statement_list_opt_semi PARALLEL statement_sequence
  ;

statement_sequence_with_semi : statement_sequence ';' ;

statement_sequence :
    annotated_statement
  | statement_sequence SEQUENCE annotated_statement
  | statement_sequence_with_semi SEQUENCE annotated_statement
  | statement_sequence_with_semi annotated_statement
  ;
  
annotated_statement : 
    opt_annotation local_declaration  
            -- NOTE: these already allow trailing annotations
  | opt_annotation statement opt_annotation
  ;

statement : 
    local_definition 
  | simple_statement 
  | label compound_statement
  | compound_statement
  -- NOTE: now will use BLOCK instead of: '(' statement_list_opt_semi ')' 
  ;

opt_label : label | ;

simple_statement :
    name assign_operator expression
  | name SWAP name
  | name '(' opt_operation_actual_list ')'
  | '(' operation_actual_list ')' ASSIGN expression  -- multiple assignment
  | 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
  ;

opt_operation_actual_list : operation_actual_list | ;

opt_WITH_values : WITH_values | ;

WITH_values : WITH_kw '(' operation_actual_list ')' ;

opt_id : Identifier | ;

compound_statement_kind : LOOP_kw | IF_kw | CASE_kw | SELECT_kw | BLOCK_kw ;

local_declaration : 
    operation_declaration 
  | type_declaration 
  | object_declaration
  ;

local_definition :
    object_definition 
  | operation_definition 
  ;

label : '*' Identifier '*' ;

compound_statement :
    if_statement
  | case_statement
  | while_loop_statement
  | for_loop_statement
  | block_statement 
  | select_statement
  ;

if_statement : 
  IF_kw condition THEN_kw 
     statement_list_with_semi
  elsif_list
  opt_else
  END_kw IF_kw opt_id opt_WITH_values ;

elsif_list : 
  | elsif_list elsif_clause
  ;

elsif_clause :
  ELSIF_kw condition THEN_kw
     statement_list_with_semi ;

opt_else : ELSE_kw statement_list_with_semi | ;

case_statement : 
  CASE_kw expression OF_kw
    case_alt_list
    opt_default_alt
  END_kw CASE_kw opt_id opt_WITH_values ;

case_alt_list : 
    case_alt
  | case_alt_list case_alt
  ;

case_alt :
    '[' choice_list ']' REFERS_TO statement_list_with_semi ;

choice_list : 
    choice  
  | choice_list '|' choice 
  ;

choice : term_or_range ;

opt_default_alt : '[' DOT_DOT ']' REFERS_TO statement_list_with_semi | ;

while_loop_statement :
  WHILE_kw condition LOOP_kw
    statement_list_with_semi
  END_kw LOOP_kw opt_id opt_WITH_values ;

for_loop_statement :
  FOR_kw iterator_spec opt_direction LOOP_kw
    statement_list_with_semi
  END_kw LOOP_kw opt_id opt_WITH_values ;

iterator_spec : 
    iterator 
  | '(' iterator_list ')'
  ;

iterator_list :
    iterator
  | iterator_list ';' iterator
  ;

iterator :
    Identifier IN_kw choice_list
  | EACH_kw Identifier OF_kw expression
  | Identifier ASSIGN expression THEN_kw next_value_list WHILE_kw condition
  | Identifier REFERS_TO name THEN_kw next_name_list WHILE_kw condition
  | Identifier ':' type_specifier ASSIGN expression 
  ;

next_value_list : 
    expression 
  | next_value_list PARALLEL expression 
  ;

next_name_list : 
    name 
  | next_name_list PARALLEL name 
  ;

opt_direction : direction | ;

direction : CONCURRENT_kw | FORWARD_kw | REVERSE_kw ;

select_statement :
  SELECT_kw 
     select_alt_list
  END_kw SELECT_kw opt_id opt_WITH_values ;

select_alt_list : 
    select_alt
  | select_alt_list PARALLEL select_alt
  ;

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

block_statement :
  BLOCK_kw
    statement_list_with_semi
  END_kw BLOCK_kw opt_id opt_WITH_values ;
 
expression :  
    expression_component
  | expression '|' expression_component
  ;

expression_component : -- logical operators are non-associative
    comparison_expression
  | comparison_expression logical_operator comparison_expression
  | comparison_expression '?' expression_component ':' expression_component
  ;

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

simple_expression : -- used to avoid use of '>' in module instantiation
    term
  | simple_expression adding_operator term
  ;

type_or_term_or_range :
    polymorphic_type_name
  | term_or_range       -- includes simple type name
  ;

term_or_range : 
    term
  | term DOT_DOT term  -- avoid ambiguity on use of '+'
  ;
  
term : 
    factor
  | term multiplying_operator factor
  ;

factor : 
    primary
  | primary power_operator factor  -- right associative
  | unary_operator factor  -- makes unary ops higher precedence 
  ;

primary :
    name
  | Integer_Literal
  | Real_Literal
  | Char_Literal
  | String_Literal
  | Enum_Literal
  | NULL_kw
  | '(' conditional_expression ')'
  | '(' quantified_expression ')'
  | aggregate
  | DOUBLE_LEFT_BRACKET expression DOUBLE_RIGHT_BRACKET 
  ;
  
name :
    qualified_name attribute_list opt_PRIME
  | qualified_name PRIME
  | qualified_name 
  | name '(' opt_operation_actual_list ')'
  | name '[' opt_operation_actual_list ']'
  | name '.' selector
  ;

attribute_list :
    Enum_Literal
  | attribute_list Enum_Literal 
  ;

opt_PRIME : PRIME | ;

operation_actual_list : 
    operation_actual 
  | operation_actual_list ',' operation_actual 
  ;

operation_actual : 
    expression
  | Identifier REFERS_TO expression 
  ;

selector : Identifier ;

unary_operator : '+' | '-' | ABS_kw | NOT_kw ;

adding_operator : '+' | '-' ;

multiplying_operator : '*' | '/' ;

power_operator : POWER ;

assign_operator : 
    ASSIGN | PLUS_ASSIGN | MINUS_ASSIGN | TIMES_ASSIGN | DIVIDE_ASSIGN 
  | CONCAT_ASSIGN | AND_ASSIGN | OR_ASSIGN | XOR_ASSIGN
  ;

comparison_operator : COMPARE | EQ | NEQ | '<' | LEQ | '>' | GEQ ;

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


aggregate : class_aggregate | container_aggregate ;

class_aggregate : '(' opt_operation_actual_list ')' ;

container_aggregate : '[' opt_container_element_list ']' ;
  
opt_container_element_list : container_element_list | ;

container_element_list : 
    container_element 
  | container_element_list ',' container_element 
  ;

container_element : 
    expression_component
  | choice_list REFERS_TO filtered_expression_stream 
  | DOT_DOT REFERS_TO filtered_expression_stream 
  ;

container_key : expression ;

filtered_expression_stream : 
    expression
  | expression ':' condition
  ;

conditional_expression :
    if_expression
  | case_expression
  ;

if_expression : 
  IF_kw condition THEN_kw 
     expression
  elsif_expr_list
  opt_else_expr ;

elsif_expr_list : 
    elsif_expr_clause
  | elsif_expr_list elsif_expr_clause
  ;

elsif_expr_clause :
  ELSIF_kw condition THEN_kw expression ;

opt_else_expr : ELSE_kw expression | ;

case_expression : 
  CASE_kw expression OF_kw
    case_expr_alt_list ;

case_expr_alt_list : 
    case_expr_alt
  | case_expr_alt_list ';' case_expr_alt
  ;

case_expr_alt : 
    '[' choice_list ']' REFERS_TO expression 
  | '[' DOT_DOT ']' REFERS_TO expression   -- NOTE: must come last
  ;

quantified_expression :
    FOR_kw ALL_or_SOME_kw iterator ':' condition ;

ALL_or_SOME_kw : ALL_kw | SOME_kw ;

%%


package parasail_parser is

    procedure yyparse;

    echo : boolean := false;
    number_of_errors : natural := 0;


end parasail_parser;

with parasail_tokens, parasail_lex_io, parasail_goto, parasail_shift_reduce;
with parasail_lex, text_io;

use  parasail_tokens, parasail_lex_io, parasail_goto, parasail_shift_reduce;
use  parasail_lex, text_io;
package body parasail_parser is

    procedure yyerror(s: in string := "syntax error") is
    begin
 number_of_errors := number_of_errors + 1;
 put("<<< *** ");
 put_line(s);
    end yyerror;


##%procedure_parse

end parasail_parser;

---------------------------------------------------
And here is the (A)Flex lexer:
---------------------------------------------------

%START IDENT Z


GRAPHIC_CHAR  [ !"#$%&'()*+,-./0-9:;<=>?@A-Z\[\\\]^_`a-z{|}~]

STRING_LITERAL  (\"([^\"]|[\\][.])*\")

CHAR_LITERAL    (\'([^\']|[\\][.])\')

IDENTIFIER        [a-zA-Z]([_]?[a-zA-Z0-9])*

  -- The following are used to match all numeric literals.
  -- Note that double underscores are rejected.
DIGIT_SEQUENCE    [0-9]([_]?[0-9])*
HEX_SEQUENCE      [0-9a-fA-F]([_]?[0-9a-fA-F])*
EXPONENT          [Ee][-+]?{DIGIT_SEQUENCE}

%%

  -- ParaSail reserved words
"abs"     {ECHO_L; ENTER(Z); return (ABS_kw);}
"abstract" {ECHO_L; ENTER(Z); return (ABSTRACT_kw);}
"all"  {ECHO_L; ENTER(Z); return (ALL_kw);}
"and"  {ECHO_L; ENTER(Z); return (AND_kw);}
"block"  {ECHO_L; ENTER(Z); return (BLOCK_kw);}
"case"  {ECHO_L; ENTER(Z); return (CASE_kw);}
"class"  {ECHO_L; ENTER(Z); return (CLASS_kw);}
"concurrent" {ECHO_L; ENTER(Z); return (CONCURRENT_kw);}
"const"  {ECHO_L; ENTER(Z); return (CONST_kw);}
"continue" {ECHO_L; ENTER(Z); return (CONTINUE_kw);}
"each"  {ECHO_L; ENTER(Z); return (EACH_kw);}
"else"  {ECHO_L; ENTER(Z); return (ELSE_kw);}
"elsif"  {ECHO_L; ENTER(Z); return (ELSIF_kw);}
"end"  {ECHO_L; ENTER(Z); return (END_kw);}
"exit"  {ECHO_L; ENTER(Z); return (EXIT_kw);}
"exports" {ECHO_L; ENTER(Z); return (EXPORTS_kw);}
"extends" {ECHO_L; ENTER(Z); return (EXTENDS_kw);}
"for"  {ECHO_L; ENTER(Z); return (FOR_kw);}
"forward" {ECHO_L; ENTER(Z); return (FORWARD_kw);}
"function" {ECHO_L; ENTER(Z); return (FUNCTION_kw);}
"if"  {ECHO_L; ENTER(Z); return (IF_kw);}
"implements" {ECHO_L; ENTER(Z); return (IMPLEMENTS_kw);}
"import" {ECHO_L; ENTER(Z); return (IMPORT_kw);}
"in"  {ECHO_L; ENTER(Z); return (IN_kw);}
"interface" {ECHO_L; ENTER(Z); return (INTERFACE_kw);}
"is"  {ECHO_L; ENTER(Z); return (IS_kw);}
"locked" {ECHO_L; ENTER(Z); return (LOCKED_kw);}
"loop"  {ECHO_L; ENTER(Z); return (LOOP_kw);}
"mod"  {ECHO_L; ENTER(Z); return (MOD_kw);}
"mutable" {ECHO_L; ENTER(Z); return (MUTABLE_kw);}
"new"  {ECHO_L; ENTER(Z); return (NEW_kw);}
"not"  {ECHO_L; ENTER(Z); return (NOT_kw);}
"null"  {ECHO_L; ENTER(Z); return (NULL_kw);}
"of"  {ECHO_L; ENTER(Z); return (OF_kw);}
"operator" {ECHO_L; ENTER(Z); return (OPERATOR_kw);}
"optional" {ECHO_L; ENTER(Z); return (OPTIONAL_kw);}
"or"  {ECHO_L; ENTER(Z); return (OR_kw);}
"procedure" {ECHO_L; ENTER(Z); return (PROCEDURE_kw);}
"queued" {ECHO_L; ENTER(Z); return (QUEUED_kw);}
"ref"  {ECHO_L; ENTER(Z); return (REF_kw);}
"rem"  {ECHO_L; ENTER(Z); return (REM_kw);}
"return" {ECHO_L; ENTER(Z); return (RETURN_kw);}
"reverse" {ECHO_L; ENTER(Z); return (REVERSE_kw);}
"select" {ECHO_L; ENTER(Z); return (SELECT_kw);}
"some"  {ECHO_L; ENTER(Z); return (SOME_kw);}
"then"  {ECHO_L; ENTER(Z); return (THEN_kw);}
"type"  {ECHO_L; ENTER(Z); return (TYPE_kw);}
"var"  {ECHO_L; ENTER(Z); return (VAR_kw);}
"while"  {ECHO_L; ENTER(Z); return (WHILE_kw);}
"with"  {ECHO_L; ENTER(Z); return (WITH_kw);}
"xor"  {ECHO_L; ENTER(Z); return (XOR_kw);}

  -- Match all the compound ParaSail delimiters. 
"=?"  {ECHO_L; ENTER(Z); return(COMPARE);}
"=="  {ECHO_L; ENTER(Z); return(EQ);}
"!="  {ECHO_L; ENTER(Z); return(NEQ);}
">="  {ECHO_L; ENTER(Z); return(GEQ);}
"<="  {ECHO_L; ENTER(Z); return(LEQ);}
"**"  {ECHO_L; ENTER(Z); return(POWER);}
":="  {ECHO_L; ENTER(Z); return(ASSIGN);}
":=:"  {ECHO_L; ENTER(Z); return(SWAP);}
".."  {ECHO_L; ENTER(Z); return(DOT_DOT);}
"::"  {ECHO_L; ENTER(Z); return(DOUBLE_COLON);}
"[["  {ECHO_L; ENTER(Z); return(DOUBLE_LEFT_BRACKET);}
"]]"  {ECHO_L; ENTER(Z); return(DOUBLE_RIGHT_BRACKET);}
"=>"  {ECHO_L; ENTER(Z); return(REFERS_TO);}
"->"  {ECHO_L; ENTER(Z); return(GIVES);}
"==>"  {ECHO_L; ENTER(Z); return(IMPLIES);}
";;"  {ECHO_L; ENTER(Z); return(SEQUENCE);}
"||"  {ECHO_L; ENTER(Z); return(PARALLEL);}
"+="  {ECHO_L; ENTER(Z); return(PLUS_ASSIGN);}
"-="  {ECHO_L; ENTER(Z); return(MINUS_ASSIGN);}
"*="  {ECHO_L; ENTER(Z); return(TIMES_ASSIGN);}
"/="  {ECHO_L; ENTER(Z); return(DIVIDE_ASSIGN);}
"**="  {ECHO_L; ENTER(Z); return(POWER_ASSIGN);}
"|="  {ECHO_L; ENTER(Z); return(CONCAT_ASSIGN);}
"and="  {ECHO_L; ENTER(Z); return(AND_ASSIGN);}
"or="  {ECHO_L; ENTER(Z); return(OR_ASSIGN);}
"xor="  {ECHO_L; ENTER(Z); return(XOR_ASSIGN);}

  -- Match all the ParaSail single-character delimiters.
<IDENT>\'  {ECHO_L; ENTER(Z);     return(PRIME);}
"("        {ECHO_L; ENTER(Z);     return('(');}
")"        {ECHO_L; ENTER(IDENT); return(')');}
"["        {ECHO_L; ENTER(Z);     return('[');}
"]"        {ECHO_L; ENTER(IDENT); return(']');}
"<"        {ECHO_L; ENTER(Z);     return('<');}
">"        {ECHO_L; ENTER(Z);     return('>');}
"{"    {ECHO_L; ENTER(Z);   return('{');}
"}"    {ECHO_L; ENTER(Z);   return('}');}
"*"        {ECHO_L; ENTER(Z);     return('*');}
"+"        {ECHO_L; ENTER(Z);     return('+');}
","        {ECHO_L; ENTER(Z);     return(',');}
"-"        {ECHO_L; ENTER(Z);     return('-');}
"."        {ECHO_L; ENTER(Z);     return('.');}
"/"        {ECHO_L; ENTER(Z);     return('/');}
":"        {ECHO_L; ENTER(Z);     return(':');}
";"        {ECHO_L; ENTER(Z);     return(';');}
"|"        {ECHO_L; ENTER(Z);     return('|');}
"?"        {ECHO_L; ENTER(Z);     return('?');}

  -- The following is used to match all valid ParaSail identifiers
  -- except reserved words. Note that leading digits and underscores
  -- are not allowed and that double underscores are not allowed.

{IDENTIFIER}       {ECHO_L; ENTER(IDENT);return(Identifier);}

  -- Enumeration literals
[#]{IDENTIFIER}    {ECHO_L; ENTER(IDENT);return(Enum_Literal);}

  -- Decimal numeric literals
{DIGIT_SEQUENCE}{EXPONENT}?  {
         ECHO_L; ENTER(Z);
         return(Integer_Literal);}

{DIGIT_SEQUENCE}[.]{DIGIT_SEQUENCE}{EXPONENT}?  {
         ECHO_L; ENTER(Z);
         return(Real_Literal);}

  -- Based numeric literals.

{DIGIT_SEQUENCE}[#]{HEX_SEQUENCE}[#]{EXPONENT}? {
         ECHO_L; ENTER(Z);
         return(Integer_Literal);}

{DIGIT_SEQUENCE}[#]{HEX_SEQUENCE}[.]{HEX_SEQUENCE}[#]{EXPONENT}? {
         ECHO_L; ENTER(Z);
         return(Real_Literal);}

"0"[xX]{HEX_SEQUENCE}  {ECHO_L; ENTER(Z); return(Integer_Literal);}
"0"[bB]{DIGIT_SEQUENCE}  {ECHO_L; ENTER(Z); return(Integer_Literal);}

  -- Match all valid character literals.  See Ada LRM 2.6.

<Z>{CHAR_LITERAL}      {ECHO_L; ENTER(Z); return(Char_Literal);}

  -- Match all valid string literals.  See Ada LRM 2.6.

{STRING_LITERAL}                {ECHO_L; ENTER(Z); return(String_Literal);}

"//".*    {ECHO_L;}           -- ignore comments to end-of-line

"--".*    {ECHO_L;}           -- ignore comments to end-of-line

  -- The following matches all whitespace.  Except for vertical tabs.  AFLEX,
  -- ALEX and LEX does not support vertical tabs.  This causes use to fail
  -- when parsing some of the ACVC Btests.

[ \r\t\f]+ {ECHO_L;}        -- ignore spaces,Carriage returns,tabs,form feeds

  -- The following matches all new lines.

[\n]       {ECHO_L; linenum;}

  -- The following matches everything else and prints an error message
  -- indicating that something unexpected was found.

.          {ECHO_L; 
            text_io.put_line("?? lexical error '" & 
       parasail_lex_dfa.yytext & "' ??");
     num_errors := num_errors + 1;}

%%

with parasail_tokens; 
use  parasail_tokens;
use text_io;

package parasail_lex is
  
  lines      : positive := 1;
  num_errors     : natural := 0;
  Trace          : Boolean := False;

  procedure ECHO_L; --local version_of define_string.
  procedure linenum; 

  function yylex return token;

end parasail_lex;

package body parasail_lex is

  procedure ECHO_L is
  --
  -- Local version of the  define string.
  -- 
  begin
-----    if Trace then
-----      TEXT_IO.PUT_Line("Token :" & YYTEXT & ":");
-----    end if;
 text_io.put(yytext);
  end ECHO_L;


  procedure linenum is
    line_number_string : constant string :=
          integer'image ( lines );
  begin
    lines := lines + 1;
    put(line_number_string);
    for i in 1 .. 5 - integer ( line_number_string'length ) loop
      text_io.put(" ");
    end loop;

  end linenum;

##

end parasail_lex;

N Queens Problem in ParaSail

2010-07-17T23:33:00.003-04:00

Here is a (parallel) solution to the "N Queens" problem in ParaSail, where we try to place N queens on an NxN chess board such that none of them can take each other. This takes the idea of using the "continue" statement as a kind of implicit recursion to its natural conclusion. This presumes you can turn a "normal" data structure like Vector<> into a concurrent data structure by using the keyword "concurrent," which presumably means that locking is used on all operations to support concurrency. It is debatable whether this use of a "continue" statement to effectively start the next iteration of a loop almost like a recursive call is easier or harder to understand than true recursion.

interface N_Queens <N : Univ_Integer := 8> is
    // Place N queens on a checkerboard so that none of them can
    // "take" each other.
    type Row is new Integer<1, N>;
     
    function Place_Queens() -> Vector<Vector<Row>> 
      {for all I in Place_Queens#range : Length(Place_Queens[I]) == N};
end interface N_Queens;

class N_Queens <N : Univ_Integer := 8> is
    type Column is new Integer<1, N>;
    type Sum is Vector<Boolean, Index => Integer<2, 2*N>>;
    type Diff is Vector<Boolean, Index => Integer<1-N, N-1>>;
    
exports
    
    function Place_Queens() -> Vector<Vector<Row>> 
      {for all I in Place_Queens#range : Length(Place_Queens[I]) == N} is
      // Place N queens on checkerboard so that none of them can "take" each other
      var Solutions : concurrent Vector<Vector<Row>> := [];
      
      *Outer_Loop*
      for (C : Column := 1; Trial : Vector<Row> := [];
        Diag1 : SSum := [.. => #false]; Diag2 : Diff := [.. => #false]) loop
          // Iterate over the columns
        
          for R in Row concurrent loop
              // Iterate over the rows
              if not Diag1[R + C] and then not Diag2[R - C] then
                  // Found a Row/Column combination that is not on any diagonal
                  // already occupied.
                  if C < N then
                      // Keep going since haven't reached Nth column.
                      continue loop Outer_Loop with (C => C+1, Trial => Trial | R,
                        Diag1 => Diag1 | [(R+C) => #true],
                        Diag2 => Diag2 | [(R-C) => #true]);
                  else
                      // All done, remember trial result.
                      Solutions |= Trial;
                  end if;
              end if;
          end loop;
          
          
      end loop Outer_Loop;
      return Solutions;
      
    end function Place_Queens;
end class N_Queens;

Some additional examples of ParaSail

2010-06-24T00:20:00.001-04:00

Here is a grab-bag of ParaSail examples, with interspersed musings embedded in the comments. These are acceptable to the ayacc/aflex-based parser posted earlier.

import XXYZ;  // TBD: Does this precede the interface?
              //      Any notion of "use" or "using"
interface Hello_World <Standard_IO<>> is
    procedure Main(IO : ref Standard_IO);
end interface Hello_World;

// TBD: What do enumeration type declarations look like?
//      The first parameter is an id-list type.  The other
//      parameters might be something relating to first/last,
//      'image, etc.

// TBD: What is the comment syntax?  "//" or "--"?  
//      Modula and ML use "(* *)" but ML folks are suggesting
//      the use of "# " as the start of a comment that goes to the EOL.
//      For some reason I find "#" pretty ugly, especially in the
//      middle of a line.
//      C#, C++, and Java all support "//", as well as the
//      partial line '/* ... */'.  That seems error-prone,
//      so sticking with "//" by itself seems simplest.
//      Also "--" means decrement to half the world.

// Syntax:  module::module, type::operation, type::nested_entity,
//          object.component, object.operation [equiv to type::operation(object, ...)]

// TBD: When a non-abstract interface has no module parameters, does that mean
//      the module name can be used directly as a type name?  Or are the "<>"
//      mandatory?  Can we say "interface Univ_Enumeration<> is ..."

// TBD: Should we make aggregates usable when outside the associated class?
//      What about "extension" aggregates?  Operator "aggregate"?

// TBD: Get rid of "subtype" and just use "type Blah is ..." or "type Blah is new ..."
//      "subtype" is a relationship, not a kind of entity.

interface Std <> is

    abstract interface Any<> is
        operator "end" (Obj : ref var Any);
    end interface Any;
    
    abstract interface Assignable<> extends Any is
        operator "copy" Assignable -> Assignable;
    end interface Assignable;

    -- type Univ_Enumeration is ...; // type with all enumerals
    
    type Boolean is Enum <[#false, #true]>; // True or False
    type Ordering is Enum <[#less, #equal, #greater, #unordered]>;

    -- type Univ_Integer is ...; // infinite precision integers with +/- inf
    -- type Univ_Real is ...;    // infinite precision rational numbers 
         // with +/- zero and inf
    -- type Univ_Character is ...;  // ISO 10646, 31-bit character
    -- type Univ_String is ...;  // UTF-32
    
    
end interface Std;

interface Std::Integer<First, Last : Univ_Integer> is
    operator "from_univ"(Univ : Univ_Integer {Univ in First .. Last}) 
      -> Integer;
    operator "to_univ"(Int : Integer) 
      -> Result: Univ_Integer {Result in First .. Last};

    operator "+"(Left, Right : Integer {[[Left]] + [[Right]] in First .. Last}) 
      -> Result : Integer {[[Result]] == [[Left]] + [[Right]]};
end interface Std::Integer;

// [[x]] means "to_univ"(X), as a nod to the double bracket notation used in
// denotational semantics to define the meaning of an expression in a program.


abstract interface Std::Ref<Target_Type is Any<>> 
is
   function Is_Writable(R : Ref) -> Boolean;
   function Exists(R : Ref) -> Boolean;
   function Fetch(R : Ref {Exists(R)}) -> Target_Type;
   procedure Store(R : Ref {Is_Writable(R)}; 
     New_Contents : Target_Type) {Exists(R)};
   procedure Delete(R : Ref {Is_Writable(R)}) {not Exists(R)};
end interface Std::Ref;

class Hello_World <Context<>; Standard_IO<>> is
  exports
    procedure Main(IO : ref Standard_IO) is
       Put_Line(IO.Output, "Hello World");
    end procedure Main;
end class Hello_World;

interface String<Character<>; Index is Integer<>> is
    operator "in"(Lit : Univ_String) -> Boolean;
    operator "from_univ"(Lit : Univ_String {Lit in String}) 
      -> String;
    operator "to_univ"(Str : String) -> Result : Univ_String
      {Result in String};
    operator "~"(Left, Right : String) -> Result : String
      {Length(Result) == Length(Left) + Length(Right)};
end interface String;
      
interface Standard_IO<Context<>; Input_Stream<>; Output_Stream<>> is
    function Output(Context) -> Output_Stream;
    function Input(Context) -> Input_Stream;
end interface Standard_IO;

interface Output_Stream<String<>> is
    procedure Put(Output : ref Output_Stream; Char : String::Character);
    procedure Put(Output : ref Output_Stream; Message : String);
    procedure Put_Line(Output : ref Output_Stream; Message : String);
end interface Output_Stream;

interface Input_Stream<String<>> is
    function Get(Input : ref Input_Stream) -> String::Character;
    function Get_Line(Output : ref Input_Stream) -> String;
end interface Input_Stream;

interface Integer<First, Last : Univ_Integer> is
    operator "in"(Lit : Univ_Integer) -> Result : Boolean 
      {Result == Lit in First .. Last};
    operator "from_univ"(Univ_Integer {Univ_Integer in First .. Last}) 
      -> Integer;
    operator "to_univ"(Integer) -> Result : Univ_Integer 
      {Result in First .. Last};
    operator "+"(Left, Right : Integer 
      {[[Left]] + [[Right]] in First .. Last}) 
      -> Result : Integer
        {[[Result]] == [[Left]] + [[Right]]};
    operator "-"(Left, Right : Integer
      {[[Left]] - [[Right]] in First .. Last}) 
        -> Integer;
    operator "*"(Left, Right : Integer
      {[[Left]] * [[Right]] in First .. Last}) 
        -> Integer;
    operator "/"(Left, Right : Integer
      {[[Left]] / [[Right]] in First .. Last}) 
        -> Integer;
    operator "=?"(Left, Right : Integer) -> Ordering;
end interface Integer;

interface Character<> is
    operator "in"(Lit : Univ_Character) -> Boolean;
    operator "from_univ"(Lit : Univ_Character {Lit in Character}) 
      -> Character;
    operator "to_univ"(Char : Character) 
      -> Result : Univ_Character 
      {Result in Character};
end interface Character;

interface Vector<Component is Assignable<>; 
   First : Univ_Integer := 1;
   Max_Length : Univ_Integer := +inf> is
    function Length(Vec : ref const Vector) -> Univ_Integer 
      {Length in 0..Max_Length};
    function Last(Vec : ref const Vector) -> Univ_Integer 
      {Last == Length(Vec) + First - 1};
    operator "[]"(Vec : ref Vector; Index : Univ_Integer 
      {Index in First..Last(Vec)}) 
      -> ref Component_Type;
    operator "~"(Left, Right : Vector) -> Result : Vector 
      {Length(Left) + Length(Right) == Length(Result)}; 
        // "~" is pronounced "concatenate"
        // or "connect" or "tied to"
        // or "chained to" or "linked to" or ...?
    operator "~"(Left : Vector; Right : Component) -> Result : Vector
      {Length(Left) + 1 == Length(Result)};
    operator "~"(Left : Component; Right : Vector) -> Result : Vector
      {Length(Right) + 1 == Length(Result)};
    operator "~"(Left, Right : Component) -> Result : Vector
      {Length(Result) == 2}; // Do we really need this one?  
                             // Is equivalent to "[Left, Right]"
    operator "null"() -> Result : Vector {Length(Result) == 0};
    procedure Append(Vec : ref mutable Vector; Value : Component)
      {Length(Vec') == Length(Vec) + 1};
    procedure Append(Vec : ref mutable Vector; Other_Vec : Vector)
      {Length(Vec') == Length(Vec) + Length(Other_Vec)}; 
                                        // Vec' means new value
                                        // do we prefer "old(...)"?
                                        // How about post(...) and pre(...)?
                                        // or "new(...)" and "old(...)"?
                                        // Since these are appearing in
                                        // a postcondition, it seems
                                        // redundant to say "post" or "new".
                                        // In any case "new" reads better than post.

    operator ":="(Left : ref var Vector; Right : Vector)
      {Length(Left) == Length(Right)};
      
    operator ":=:"(Left, Right : ref var Vector)
      {Length(Left') == Length(Right) and 
       Length(Right') == Length(Left)};
    operator "+"(Left, Right : Vector {Length(Left) == Length(Right)}) 
      -> Result : Vector
      {Length(Result) == Length(Left)};  // component-wise addition
    
end interface Vector;

interface Stack<Component is Assignable<>; 
  Size_Type is Integer<>> is
    
    function Max_Stack_Size(S : Stack) -> Size_Type 
      {Max_Stack_Size > 0};
    
    function Count(S : Stack) -> Size_Type 
      {Count <= Max_Stack_Size(S)};
    
    function Init(Max : Size_Type {Max > 0}) -> Stack 
      {Max_Stack_Size(Init) == Max and Count(Init) == 0};
    
    function Is_Empty(S : Stack) -> Boolean
      {Is_Empty == (Count(S) == 0)};
    
    function Is_Full(S : Stack) -> Boolean
      {Is_Full == (Count(S) == Mas_Stack_Size(S))};
      
    function Top(S : Stack {not Is_Empty(S)}) -> Component;
    
    procedure Pop(S : ref var Stack {not Is_Empty(S)}) 
      {Count(S') == Count(S) - 1};
      
    procedure Push(S : ref var Stack {not Is_Full(S)}; 
      X : Component) {Count(S') == Count(S) + 1};
      
end interface Stack;

Flex-based lexical scanner for ParaSail

2010-06-23T17:05:00.004-04:00

In this entry and the next are Flex and Yacc grammars for the current definition for ParaSail. They are actually grammars designed for aflex and ayacc, Ada equivalents of flex and yacc produced many years ago by the Arcadia project, so the commenting conventions and the code are for Ada rather than some other language. But hopefully you can make the transformation fairly easily to your language of choice.

This entry contains the "aflex"-compatible grammar; the next will contain the "ayacc"-compatible grammar.

-- Flex-compatible grammar for ParaSail
%START IDENT Z

STRING_LITERAL  (\"([^\"]|[\\][.])*\")

CHAR_LITERAL    (\'([^\']|[\\][.])\')

IDENTIFIER        [a-zA-Z]([_]?[a-zA-Z0-9])*

  -- The following are used to match all numeric literals.
  -- Note that double underscores are rejected.
DIGIT_SEQUENCE    [0-9]([_]?[0-9])*
HEX_SEQUENCE      [0-9a-fA-F]([_]?[0-9a-fA-F])*
EXPONENT          [Ee][-+]?{DIGIT_SEQUENCE}

%%

  -- ParaSail reserved words
"abs"        {ECHO_L; ENTER(Z); return (ABS_kw);}
"abstract"    {ECHO_L; ENTER(Z); return (ABSTRACT_kw);}
"all"        {ECHO_L; ENTER(Z); return (ALL_kw);}
"and"        {ECHO_L; ENTER(Z); return (AND_kw);}
"block"        {ECHO_L; ENTER(Z); return (BLOCK_kw);}
"case"        {ECHO_L; ENTER(Z); return (CASE_kw);}
"class"        {ECHO_L; ENTER(Z); return (CLASS_kw);}
"concurrent"    {ECHO_L; ENTER(Z); return (CONCURRENT_kw);}
"const"        {ECHO_L; ENTER(Z); return (CONST_kw);}
"continue"    {ECHO_L; ENTER(Z); return (CONTINUE_kw);}
"each"        {ECHO_L; ENTER(Z); return (EACH_kw);}
"else"        {ECHO_L; ENTER(Z); return (ELSE_kw);}
"elsif"        {ECHO_L; ENTER(Z); return (ELSIF_kw);}
"end"        {ECHO_L; ENTER(Z); return (END_kw);}
"exit"        {ECHO_L; ENTER(Z); return (EXIT_kw);}
"exports"    {ECHO_L; ENTER(Z); return (EXPORTS_kw);}
"extends"    {ECHO_L; ENTER(Z); return (EXTENDS_kw);}
"for"        {ECHO_L; ENTER(Z); return (FOR_kw);}
"forward"    {ECHO_L; ENTER(Z); return (FORWARD_kw);}
"function"    {ECHO_L; ENTER(Z); return (FUNCTION_kw);}
"if"        {ECHO_L; ENTER(Z); return (IF_kw);}
"import"    {ECHO_L; ENTER(Z); return (IMPORT_kw);}
"in"        {ECHO_L; ENTER(Z); return (IN_kw);}
"interface"    {ECHO_L; ENTER(Z); return (INTERFACE_kw);}
"is"        {ECHO_L; ENTER(Z); return (IS_kw);}
"locked"    {ECHO_L; ENTER(Z); return (LOCKED_kw);}
"loop"        {ECHO_L; ENTER(Z); return (LOOP_kw);}
"mod"        {ECHO_L; ENTER(Z); return (MOD_kw);}
"mutable"    {ECHO_L; ENTER(Z); return (MUTABLE_kw);}
"new"        {ECHO_L; ENTER(Z); return (NEW_kw);}
"not"        {ECHO_L; ENTER(Z); return (NOT_kw);}
"null"        {ECHO_L; ENTER(Z); return (NULL_kw);}
"of"        {ECHO_L; ENTER(Z); return (OF_kw);}
"operator"    {ECHO_L; ENTER(Z); return (OPERATOR_kw);}
"optional"    {ECHO_L; ENTER(Z); return (OPTIONAL_kw);}
"or"        {ECHO_L; ENTER(Z); return (OR_kw);}
"procedure"    {ECHO_L; ENTER(Z); return (PROCEDURE_kw);}
"queued"    {ECHO_L; ENTER(Z); return (QUEUED_kw);}
"ref"        {ECHO_L; ENTER(Z); return (REF_kw);}
"rem"        {ECHO_L; ENTER(Z); return (REM_kw);}
"return"    {ECHO_L; ENTER(Z); return (RETURN_kw);}
"reverse"    {ECHO_L; ENTER(Z); return (REVERSE_kw);}
"select"    {ECHO_L; ENTER(Z); return (SELECT_kw);}
"some"        {ECHO_L; ENTER(Z); return (SOME_kw);}
"then"        {ECHO_L; ENTER(Z); return (THEN_kw);}
"type"        {ECHO_L; ENTER(Z); return (TYPE_kw);}
"var"        {ECHO_L; ENTER(Z); return (VAR_kw);}
"while"        {ECHO_L; ENTER(Z); return (WHILE_kw);}
"with"        {ECHO_L; ENTER(Z); return (WITH_kw);}
"xor"        {ECHO_L; ENTER(Z); return (XOR_kw);}

  -- Match all the compound ParaSail delimiters. 
"=?"        {ECHO_L; ENTER(Z); return(COMPARE);}
"=="        {ECHO_L; ENTER(Z); return(EQ);}
"!="        {ECHO_L; ENTER(Z); return(NEQ);}
">="        {ECHO_L; ENTER(Z); return(GEQ);}
"<="        {ECHO_L; ENTER(Z); return(LEQ);}
"**"        {ECHO_L; ENTER(Z); return(POWER);}
":="        {ECHO_L; ENTER(Z); return(ASSIGN);}
":=:"        {ECHO_L; ENTER(Z); return(SWAP);}
".."        {ECHO_L; ENTER(Z); return(DOT_DOT);}
"::"        {ECHO_L; ENTER(Z); return(DOUBLE_COLON);}
"[["        {ECHO_L; ENTER(Z); return(DOUBLE_LEFT_BRACKET);}
"]]"        {ECHO_L; ENTER(Z); return(DOUBLE_RIGHT_BRACKET);}
"=>"        {ECHO_L; ENTER(Z); return(REFERS_TO);}
"->"        {ECHO_L; ENTER(Z); return(GIVES);}
"==>"        {ECHO_L; ENTER(Z); return(IMPLIES);}
";;"        {ECHO_L; ENTER(Z); return(SEQUENCE);}
"||"        {ECHO_L; ENTER(Z); return(PARALLEL);}

  -- Match all the ParaSail single-character delimiters.
<IDENT>\'  {ECHO_L; ENTER(Z);     return(PRIME);}
"("        {ECHO_L; ENTER(Z);     return('(');}
")"        {ECHO_L; ENTER(IDENT); return(')');}
"["        {ECHO_L; ENTER(Z);     return('[');}
"]"        {ECHO_L; ENTER(IDENT); return(']');}
"<"        {ECHO_L; ENTER(Z);     return('<');}
">"        {ECHO_L; ENTER(Z);     return('>');}
"{"       {ECHO_L; ENTER(Z);      return('{');}
"}"       {ECHO_L; ENTER(Z);      return('}');}
"*"        {ECHO_L; ENTER(Z);     return('*');}
"+"        {ECHO_L; ENTER(Z);     return('+');}
","        {ECHO_L; ENTER(Z);     return(',');}
"-"        {ECHO_L; ENTER(Z);     return('-');}
"."        {ECHO_L; ENTER(Z);     return('.');}
"/"        {ECHO_L; ENTER(Z);     return('/');}
":"        {ECHO_L; ENTER(Z);     return(':');}
";"        {ECHO_L; ENTER(Z);     return(';');}
"|"        {ECHO_L; ENTER(Z);     return('|');}
"?"        {ECHO_L; ENTER(Z);     return('?');}
"~"        {ECHO_L; ENTER(Z);     return('~');}

  -- The following is used to match all valid ParaSail identifiers
  -- except reserved words. Note that leading digits and underscores
  -- are not allowed and that double underscores are not allowed.

{IDENTIFIER}       {ECHO_L; ENTER(IDENT);return(Identifier);}

  -- Enumeration literals
[#]{IDENTIFIER}    {ECHO_L; ENTER(IDENT);return(Enum_Literal);}

  -- Decimal numeric literals
{DIGIT_SEQUENCE}{EXPONENT}?  {
                  ECHO_L; ENTER(Z);
                  return(Integer_Literal);}

{DIGIT_SEQUENCE}[.]{DIGIT_SEQUENCE}{EXPONENT}?  {
                  ECHO_L; ENTER(Z);
                  return(Real_Literal);}

  -- Based numeric literals.

{DIGIT_SEQUENCE}[#]{HEX_SEQUENCE}[#]{EXPONENT}? {
                  ECHO_L; ENTER(Z);
                  return(Integer_Literal);}

{DIGIT_SEQUENCE}[#]{HEX_SEQUENCE}[.]{HEX_SEQUENCE}[#]{EXPONENT}? {
                  ECHO_L; ENTER(Z);
                  return(Real_Literal);}

"0"[xX]{HEX_SEQUENCE}        {ECHO_L; ENTER(Z); return(Integer_Literal);}
"0"[bB]{DIGIT_SEQUENCE}        {ECHO_L; ENTER(Z); return(Integer_Literal);}

  -- Match all valid character literals.
<Z>{CHAR_LITERAL}            {ECHO_L; ENTER(Z); return(Char_Literal);}

  -- Match all valid string literals.
{STRING_LITERAL}                {ECHO_L; ENTER(Z); return(String_Literal);}

"//".*    {ECHO_L;}           -- ignore comments to end-of-line

"--".*    {ECHO_L;}           -- ignore comments to end-of-line

  -- The following matches all whitespace.  Except for vertical tabs.  AFLEX,
  -- ALEX and LEX do not support vertical tabs.
[ \r\t\f]+ {ECHO_L;}        -- ignore spaces,Carriage returns,tabs,form feeds

  -- The following matches all new lines.

[\n]       {ECHO_L; linenum;}

  -- The following matches everything else and prints an error message
  -- indicating that something unexpected was found.

.          {ECHO_L; 
            text_io.put_line("?? lexical error '" & 
          parasail_lex_dfa.yytext & "' ??");
        num_errors := num_errors + 1;}

%%
with parasail_tokens; 
use  parasail_tokens;
use text_io;

package parasail_lex is
  
  lines      : positive := 1;
  num_errors     : natural := 0;
  Trace          : Boolean := False;

  procedure ECHO_L; --local version_of define_string.
  procedure linenum; 

  function yylex return token;

end parasail_lex;

package body parasail_lex is

  procedure ECHO_L is
  --
  -- Local version of the  define string.
  -- 
  begin
     text_io.put(yytext);
  end ECHO_L;


  procedure linenum is
    line_number_string : constant string :=
          integer'image ( lines );
  begin
    lines := lines + 1;
    put(line_number_string);
    for i in 1 .. 5 - integer ( line_number_string'length ) loop
      text_io.put(" ");
    end loop;

  end linenum;

##

end parasail_lex;

(A)Yacc-based parser for ParaSail

2010-06-23T17:05:00.001-04:00

Here is the ayacc-compatible grammar for ParaSail and a simple driver program adapted from an old Ada parser. Again the commenting conventions and the code are in Ada, but it should be straightforward to transform it into some other language.

--------------------------------------
-- Tentative YACC Grammar for ParaSail
--------------------------------------

-- Single-character delimiters --
%token ',' ';' ':' '.'
%token '+' '-' '*' '/' 
%token '~' '?'
%token '(' ')' '[' ']' '<' '>' '{' '}'
%token '|' 
%token PRIME -- '''

-- Compound delimiters --
%token COMPARE -- "=?"
%token EQ   -- "=="
%token NEQ  -- "!="
%token GEQ  -- ">="
%token LEQ  -- "<="
%token POWER  -- "**"
%token ASSIGN -- ":="
%token SWAP   -- ":=:"
%token DOT_DOT -- ".."
%token DOUBLE_COLON  -- "::"
%token DOUBLE_LEFT_BRACKET  -- "[["
%token DOUBLE_RIGHT_BRACKET -- "]]"
%token REFERS_TO  -- "=>"
%token GIVES    -- "->"
%token IMPLIES    -- "==>"
%token SEQUENCE   -- ";;"
%token PARALLEL   -- "||"

-- 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 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 IF_kw
%token IMPORT_kw
%token IN_kw
%token INTERFACE_kw
%token IS_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 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 VAR_kw
%token WHILE_kw
%token WITH_kw
%token XOR_kw

%start module_list

{ 
   subtype yystype is integer;
}


%%

module_list : 
    module
  | module_list module
  ;

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

import_clauses : 
  | import_clauses IMPORT_kw qualified_name_list ';'
  ;

qualified_name_list : 
    qualified_name
  | qualified_name_list ',' qualified_name
  ;

interface_declaration : 
   opt_ABSTRACT_kw opt_CONCURRENT_kw INTERFACE_kw module_defining_name 
     formals_and_implemented_interfaces
     IS_kw
      interface_element_list
   END_kw INTERFACE_kw module_defining_name ;
   
opt_ABSTRACT_kw :  ABSTRACT_kw | ;

opt_CONCURRENT_kw : CONCURRENT_kw | ;

formals : '<' opt_module_formal_list '>' ;

formals_and_implemented_interfaces :
    formals
  | opt_formals EXTENDS_kw interface_name_list
  ; 

opt_formals : formals | ;

interface_name_list :
    interface_name
  | interface_name_list ',' interface_name
  ;

interface_name : module_name | module_instantiation ;
   
module_defining_name : qualified_name ;

opt_module_formal_list : module_formal_list | ;

module_formal_list : 
    annotated_module_formal 
  | module_formal_list ';' annotated_module_formal 
  ;

annotated_module_formal : opt_annotation module_formal opt_annotation ;

opt_annotation : annotation | ;

module_formal : type_formal | value_formal ;

type_formal : 
    Identifier IS_kw module_instantiation 
  | module_instantiation 
  ;

value_formal : 
    id_list ':' type_name 
  | id_list ':' type_name ASSIGN simple_expression  -- to avoid use of '>'
  ;

id_list : 
    Identifier
  | id_list ',' Identifier
  ;

type_name : qualified_name ;

qualified_name : 
    Identifier 
  | qualified_name DOUBLE_COLON Identifier ;


module_instantiation : 
  module_name '<' opt_module_actual_list '>' ;


module_name : qualified_name ;

opt_module_actual_list : module_actual_list | ;

module_actual_list :
    module_actual 
  | module_actual_list ',' module_actual 
  ;

module_actual : 
    type_specifier_or_expression
  | Identifier REFERS_TO type_specifier_or_expression
  ;

-- simple_expression subsumes type_name in this rule
type_specifier_or_expression : 
    type_name annotation
  | simple_expression              -- to avoid problems with '>'
  | module_instantiation
  ;
  
type_specifier : 
    type_name annotation 
  | type_name 
  | module_instantiation 
  ;

interface_element_list : 
  | interface_element_list interface_element ';'
  ;

interface_element : 
    operation_declaration 
  | object_declaration 
  | interface_declaration 
  | type_declaration 
  ;


class_definition :
   opt_CONCURRENT_kw CLASS_kw module_defining_name 
      formals_and_extended_interface 
   IS_kw
      class_element_list
   END_kw CLASS_kw module_defining_name ;

formals_and_extended_interface :
    formals
  | opt_formals EXTENDS_kw interface_name
  | opt_formals EXTENDS_kw Identifier ':' interface_name
  ; 


class_element_list : 
    local_class_element_list
  EXPORTS_kw 
    exported_class_element_list ;

local_class_element_list :
  | local_class_element_list local_class_element ';'
  ;

local_class_element : interface_element | exported_class_element ;
  
exported_class_element_list :
  | exported_class_element_list exported_class_element ';'
  ;

exported_class_element : 
    operation_definition 
  | object_definition 
  | class_definition 
  ;
  
   
annotation : '{' annotation_element_list '}' ;

annotation_element_list : 
    annotation_element
  | annotation_element_list ';' annotation_element
  ;

annotation_element : interface_element | condition ;

condition : expression ;


operation_declaration : 
    function_declaration 
  | procedure_declaration 
  | operator_declaration 
  ;

function_declaration :
  FUNCTION_kw Identifier operation_inputs GIVES operation_outputs ;

procedure_declaration :
  PROCEDURE_kw Identifier operation_inputs ;
  
operator_declaration :
  OPERATOR_kw operator_designator operation_inputs opt_gives_operation_outputs ;

opt_gives_operation_outputs : GIVES operation_outputs | ;
  
operator_designator : String_Literal ;
  
operation_inputs :
    annotated_operation_input
  | '(' opt_annotated_operation_input_list ')' opt_annotation 
  ;

opt_annotated_operation_input_list : annotated_operation_input_list | ;

annotated_operation_input_list : 
    annotated_operation_input
  | annotated_operation_input_list ';' annotated_operation_input
  ;

annotated_operation_input : opt_annotation operation_input opt_annotation ;

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

opt_input_modifier : input_modifier | ;
  
operand_type_specifier : type_name | type_formal ;

input_modifier : 
    output_modifier 
  | QUEUED_kw opt_output_modifier
  | LOCKED_kw opt_output_modifier
  ;


operation_outputs : 
    annotated_operation_output
  | '(' annotated_operation_output_list ')' opt_annotation 
  ;

annotated_operation_output_list :
    annotated_operation_output
  | annotated_operation_output_list ';' annotated_operation_output
  ;

annotated_operation_output : opt_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 | ;

output_modifier :  
    REF_opt_optional_mutable 
  | REF_opt_optional_mutable VAR_kw 
  | REF_opt_optional_mutable CONST_kw 
  ;

REF_opt_optional_mutable :
    REF_kw
  | REF_kw OPTIONAL_kw
  | REF_kw MUTABLE_kw
  | REF_kw OPTIONAL_kw MUTABLE_kw
  ;

object_declaration : 
   var_or_const Identifier ':' type_specifier opt_ASSIGN_expression ;

opt_ASSIGN_expression : ASSIGN expression | ;
   
var_or_const : VAR_kw | CONST_kw ;

object_definition :
    CONST_kw Identifier opt_colon_type_specifier ASSIGN expression
  | VAR_kw Identifier ':' opt_OPTIONAL_kw opt_MUTABLE_kw type_specifier 
      opt_ASSIGN_expression
  | VAR_kw Identifier ASSIGN expression 
  ;

opt_colon_type_specifier : ':' type_specifier | ;

opt_OPTIONAL_kw : OPTIONAL_kw | ;
opt_MUTABLE_kw : MUTABLE_kw | ;

type_declaration : TYPE_kw Identifier IS_kw opt_NEW_kw type_specifier ;

opt_NEW_kw : NEW_kw | ;

operation_definition : 
    function_definition 
  | procedure_definition 
  | operator_definition 
  ;

function_definition : 
  function_declaration IS_kw statement_list ';' END_kw FUNCTION_kw Identifier ;

procedure_definition : 
  procedure_declaration IS_kw statement_list ';' END_kw PROCEDURE_kw Identifier ;

operator_definition : 
  operator_declaration IS_kw statement_list ';' END_kw OPERATOR_kw Identifier  ;


statement_list : 
    annotated_statement
  | statement_list SEQUENCE statement_list
  | statement_list ';' statement_list
  | statement_list PARALLEL statement_list
  | statement_list ';' PARALLEL statement_list
  ;
  
opt_semi : ';' | ;

annotated_statement : opt_annotation statement opt_annotation ;

statement : 
    local_declaration 
  | local_definition 
  | simple_statement 
  | label compound_statement
  | compound_statement
  | '(' statement_list opt_semi ')' 
  ;

opt_label : label | ;

simple_statement :
    name ASSIGN expression
  | name SWAP name
  | name '(' opt_operation_actual_list ')'
  | RETURN_kw opt_WITH_values 
  | CONTINUE_kw LOOP_kw opt_id opt_WITH_values 
  | EXIT_kw compound_statement_kind opt_id opt_WITH_values
  ;

opt_operation_actual_list : operation_actual_list | ;

opt_WITH_values : WITH_values | ;

WITH_values : WITH_kw '(' operation_actual_list ')' ;

opt_id : Identifier | ;

compound_statement_kind : LOOP_kw | IF_kw | CASE_kw | SELECT_kw | BLOCK_kw ;

local_declaration : operation_declaration | type_declaration ;

local_definition :
    object_definition 
  | operation_definition 
  ;

label : '*' Identifier '*' ;

compound_statement :
    if_statement
  | case_statement
  | while_loop_statement
  | for_loop_statement
  | block_statement 
  | select_statement
  ;

if_statement : 
  IF_kw condition THEN_kw 
     statement_list ';'
  elsif_list
  opt_else
  END_kw IF_kw opt_id opt_WITH_values ;

elsif_list : 
    elsif_clause
  | elsif_list elsif_clause
  ;

elsif_clause :
  ELSIF_kw condition THEN_kw
     statement_list ';' ;

opt_else : ELSE_kw statement_list ';' | ;

case_statement : 
  CASE_kw expression OF_kw
    case_alt_list
    opt_default_alt
  END_kw CASE_kw opt_id opt_WITH_values ;

case_alt_list : 
    case_alt
  | case_alt_list case_alt
  ;

case_alt :
    '[' choice_list ']' REFERS_TO statement_list ';' ;

choice_list : 
    choice  
  | choice_list '|' choice 
  ;

choice : expression_or_range ;

opt_default_alt : '[' DOT_DOT ']' REFERS_TO statement_list ';' | ;

while_loop_statement :
  WHILE_kw condition LOOP_kw
    statement_list ';'
  END_kw LOOP_kw opt_id opt_WITH_values ;

for_loop_statement :
  FOR_kw iterator_list opt_direction LOOP_kw
    statement_list ';'
  END_kw LOOP_kw opt_id opt_WITH_values ;

iterator_list : 
    iterator 
  | iterator_list ',' iterator
  ;

iterator :
    Identifier IN_kw choice_list
  | EACH_kw Identifier OF_kw expression
  | Identifier ASSIGN expression THEN_kw next_value_list WHILE_kw condition
  | Identifier REFERS_TO name THEN_kw next_name_list WHILE_kw condition
  ;

next_value_list : 
    expression 
  | next_value_list PARALLEL expression 
  ;

next_name_list : 
    name 
  | next_name_list PARALLEL name 
  ;

opt_direction : direction | ;

direction : CONCURRENT_kw | FORWARD_kw | REVERSE_kw ;

select_statement :
  SELECT_kw 
     select_alt_list
  END_kw SELECT_kw opt_id opt_WITH_values ;

select_alt_list : 
    select_alt
  | select_alt_list PARALLEL select_alt
  ;

select_alt : '[' statement_list opt_semi ']' REFERS_TO statement_list opt_semi ;

block_statement :
  BLOCK_kw
    statement_list ';'
  END_kw BLOCK_kw opt_id opt_WITH_values ;
 
expression : 
    simple_expression
  | expression binary_operator expression
  | expression IN_kw expression_or_range
  | expression NOT_kw IN_kw expression_or_range
  | expression '?' expression ':' expression 
  ;

simple_expression :  -- used to avoid use of '>' in module instantiation
    primary
  | unary_operator simple_expression  -- makes unary ops higher precedence
  ;

expression_or_range : 
    expression
  | expression DOT_DOT expression ;
  
primary :
    name
  | Integer_Literal
  | Real_Literal
  | Char_Literal
  | String_Literal
  | Enum_Literal
  | NULL_kw
  | '(' expression ')'
  | '(' conditional_expression ')'
  | '(' quantified_expression ')'
  | aggregate
  | DOUBLE_LEFT_BRACKET expression DOUBLE_RIGHT_BRACKET 
  ;
  
name :
    qualified_name attribute_list opt_PRIME
  | qualified_name PRIME
  | qualified_name 
  | name '(' opt_operation_actual_list ')'
  | name '[' opt_operation_actual_list ']'
  | name '.' selector
  ;

attribute_list :
    Enum_Literal
  | attribute_list Enum_Literal 
  ;

opt_PRIME : PRIME | ;

operation_actual_list : 
    operation_actual 
  | operation_actual_list ',' operation_actual 
  ;

operation_actual : 
    expression
  | Identifier REFERS_TO expression 
  ;

selector : Identifier ;

unary_operator : '+' | '-' | ABS_kw | NOT_kw ;

binary_operator :
    '+'  | '-' | '*'  | '/' | POWER | '~' 
  | COMPARE | EQ | NEQ | '<' | LEQ | '>' | GEQ
  | AND_kw | OR_kw | XOR_kw  
  | AND_kw THEN_kw | OR_kw ELSE_kw | IMPLIES
  ;


aggregate : class_aggregate | container_aggregate ;

class_aggregate : '(' opt_operation_actual_list ')' ;

container_aggregate : '[' container_element_list ']' ;
  
container_element_list : 
    container_element 
  | container_element_list ',' container_element 
  ;

container_element : 
    expression
  | choice_list REFERS_TO filtered_expression_stream ;

container_key : expression ;

filtered_expression_stream : 
    expression_stream
  | expression_stream ':' condition
  ;

expression_stream : 
    expression 
  | expression_stream '~' expression
  ;

conditional_expression :
    if_expression
  | case_expression
  ;

if_expression : 
  IF_kw condition THEN_kw 
     expression
  elsif_expr_list
  opt_else_expr ;

elsif_expr_list : 
    elsif_expr_clause
  | elsif_expr_list elsif_expr_clause
  ;

elsif_expr_clause :
  ELSIF_kw condition THEN_kw expression ;

opt_else_expr : ELSE_kw expression | ;

case_expression : 
  CASE_kw expression OF_kw
    case_expr_alt_list
    opt_default_expr_alt ;

case_expr_alt_list : 
    case_expr_alt
  | case_expr_alt_list case_expr_alt
  ;

case_expr_alt : '[' choice_list ']' REFERS_TO expression ;

opt_default_expr_alt : '[' DOT_DOT ']' REFERS_TO expression | ;

quantified_expression :
    FOR_kw ALL_or_SOME_kw iterator ':' condition ;

ALL_or_SOME_kw : ALL_kw | SOME_kw ;

%%


package parasail_parser is

    procedure yyparse;

    echo : boolean := false;
    number_of_errors : natural := 0;


end parasail_parser;

with parasail_tokens, parasail_lex_io, parasail_goto, parasail_shift_reduce;
with parasail_lex, text_io;

use  parasail_tokens, parasail_lex_io, parasail_goto, parasail_shift_reduce;
use  parasail_lex, text_io;
package body parasail_parser is

    procedure yyerror(s: in string := "syntax error") is
    begin
       number_of_errors := number_of_errors + 1;
       put("<<< *** ");
       put_line(s);
    end yyerror;


##%procedure_parse

end parasail_parser;

------------------

And here is the driver program, also written in Ada:

with parasail_parser, parasail_lex_io, parasail_lex, text_io;
use  parasail_parser, text_io;

with parasail_lex_dfa;
procedure parasail_main is
  in_file_name: string(1..80);
  last        : natural;
begin
    text_io.put("Enter input file: ");
    text_io.get_line(in_file_name, last);
    parasail_lex_io.open_input(in_file_name(1..last));
    parasail_lex_io.create_output;

    put_line("---- Starting parse ----");

    -- parasail_lex_dfa.aflex_debug := True;

    parasail_lex.linenum;
    yyparse;


    parasail_lex_io.close_input;
    parasail_lex_io.close_output;

    put_line("---- Finished parse ----");
    new_line;
    put(integer'image(number_of_errors));
    put_line(" errors found");


end parasail_main;

An intentional race condition in a ParaSail concurrent loop

2010-06-09T00:02:00.001-04:00

An intriguing question, given the presence of the concurrent loop construct in ParaSail, is what would happen if there were a loop exit or a return statement in the body of a concurrent loop. Earlier we have said that only forward and reverse loops would allow an exit statement. But perhaps we should allow an exit or a return from within a concurrent loop as a way of terminating a concurrent computation, aborting all threads besides the one exiting or returning. This would essentially be an intentional race condition, where the first thread to exit or return wins the race. This would seem to be a relatively common paradigm when doing a parallel search, where you want to stop as soon as the item of interest is found in the data structure being walked, for example, and there is no need for the other threads to continue working.

In some sense, a return statement in a concurrent loop is easier to understand, if we presume we are in a function searching (in parallel) for some item in a data structure, and we want to return the item as soon as any thread finds it. An exit statement in a concurrent loop is a bit harder to understand, since we would need a way to record the result of the winning thread somehow. Perhaps we would want to allow some code associated with the exit statement that occurs after all of the other threads have been aborted. Perhaps "exit loop then record winner;" might be a syntax indicating that the record winner code is to be executed after the loop has effectively been stopped, but still in the context of the winning thread, with visibility on the local variables of the loop body containing the exit loop then ... construct.

For example, using the generalized for loop from the previous posting:

    var Winner : Node := null;
    for T := Root then T.Left || T.Right 
      while T != null concurrent loop
        if T.Key == Desired_Key then
            exit loop then Winner := T;
        end if;
    end loop;

At this point Winner is either still null if no node in the tree has the Desired_Key, or is equal to some node whose Key equals the Desired_Key. If there is more than one such node, it would be non-deterministic which such node Winner designates.

Clearly this kind of brute force search of the tree would not be needed if the tree were organized based on Key values. This example presumes the Key is not controlling the structure of the tree. Also note that if this were a function whose whole purpose was to find the node of interest, the exit loop then ... statement could presumably be replaced by simply return T and we wouldn't need the local variable Winner at all.