ParaSailing without a (garbage) chute

Here is a video of a presentation on ParaSail given at Mozilla Research in Mountain View, CA a couple of weeks ago, to the folks who are developing the Rust language:

https://air.mozilla.org/region-based-storage-management-parasailing-without-a-garbage-chute/

A particular area of interest was the use of pointer-free region-based storage management which eliminates the need for a garbage collector.  Rust has per-task heaps which are garbage collected, but in a single-threaded environment, plus a global heap which is managed more like one of ParaSail's regions, where all pointers into the global heap are unique/owned pointers.  Setting such a pointer to null allows immediate reclamation of the associated storage, preventing accumulation of any garbage.

Slides are on the ParaSail google group:
  https://groups.google.com/forum/#!topic/parasail-programming-language/hMiRrQijNPg

The ParaSail "import" clause -- library level visibility

We have postponed implementing the "import" clause for ParaSail until just recently.  That may seem somewhat surprising.  Up until now, any ParaSail module could refer to any other ParaSail module, provided it used its full expanded name (e.g. a name of the form Acme::Killer_App::Driver).  This works fine for small programs, but as programs grow larger, there is often a desire to be more restrictive (on the one hand) as far as interdependencies, and provide a shorthand (on the other hand) for long module names.

So now in ParaSail, you can both restrict visibility, and create shorthands, using a (Java-like) import clause:

   import Acme::Killer_App::Driver

will both give visibility on this Driver module, and provide a shorthand of simply "Driver" to refer to it.  Alternatively, you can gain visibility on all of the modules in a hierarchy, along with shorthands for the top-level items in the hierarchy:

   import Acme::Killer_App::*

gives visibility on Acme::Killer_App::Driver, Acme_Killer_App::Utilities, etc. as well as allowing the use of the shorthand names "Driver" and "Utilities" directly in the source code that follows the import clause.

In the absence of any applicable import clauses, a default is provided based on the name of the module being compiled.  If the module being compiled has the name "A::B::C" then the default import clause, when none is supplied, is "import A::B::*".  That is, the module has visibility on the entire hierarchy of modules rooted at its parent module A::B, and can use the names of its sibling modules directly as a shorthand (e.g. can refer to A::B::D as simply "D").

Whether or not explicit import clauses apply to a piece of ParaSail source code, the following two implicit import clauses always apply:

    import PSL::Core::*
    import PSL::Containers::*

This ensures visibility on, and shorthands for, the standard ParaSail types such as Boolean and Univ_Integer, and the standard ParaSail containers such as Vector and Map.

Within a single source file containing multiple modules, a given set of import clauses apply to the modules following the import clause(s) up until the end of the source file, or to the next set of import clauses.  Whenever a new set of import clauses is given, the new set completely replace any earlier imports.   So there is no inheritance or accumulation of import clauses.  Only one set applies at a time (after always adding in the implicit ones for PSL::Core::* and PSL::Containers::*).

So why did we choose this particular approach for the import clause, and how does it compare to that of other languages?

Programming languages take many different approaches to controlling visibility between standalone program units defined at the top level of some source file.  C and C++ use a strictly textual #include approach, where what is defined by some included declaration is visible, and what is not declared in any included text file is invisible.  There are many well known troublesome issues with such an approach, but it has the advantage of simplicity.  However, some of the nice simplicity is lost when you add in the notion of "extern" declarations and single-definition rules and such.  Much of the nastiness comes from nested includes, and multiple includes with redefinitions of macros which allow the various includes of the same file to have different effects.

Languages like Modula, Ada, Java, etc., adopted a module-based approach to standalone unit visibility, where an import clause or a with clause or something similar is used to indicate what other modules are available for use within a given module.  The import clause specifies the name of the module or modules to be imported, using their programming language name rather than their file name.  Some implementations of such languages require that modules be stored in files whose filenames are derivable from the module name, but that is not always required, and in Java is only required for a public class or interface, but not for package-visible classes or interfaces that come along for the ride in the same file.  In module-based approaches, there is typically no transitive importing, in that each module must specify the modules on which it wants visibility -- it doesn't get visibility on a module B just because it imports a module A that imports B.  It must import B directly.

Note that Ada does allow the body of a library unit to inherit the with clauses from its spec, as well as from its parent units in the library unit hierarchy.  Hence a with clause on the spec for a package Acme would be inherited by the Acme package body, as well as the Acme.Killer_App spec and body, and so on.  For most other languages, there is no inheriting of import clauses between source files, even when one is defining the implementation for a module and the other is defining the interface for the module.

The new language Go has an interesting approach, where filenames are used in the import clauses, but they are treated more like modules, in that there is no automatic transitivity, and the imported files never need be read more than once, even if they are indirectly imported several times.  Go was designed in part in response to the unpleasant effects of the C++ #include rules, which in large systems can dramatically slow down compilation.

Other solutions to the C/C++ #include unpleasantries exist, some based on a "#pragma Once" approach which says that a given include file should only be read once, and others based on an idiomatic use of #ifndef/#endif's bracketing the text of each include file.

Another dimension over which importing differs is the provision of shorthands for imported declarations.  In Java, for example, no import clause is required if the programmer is willing to refer to an externally-defined class by using its full name (such as java.io.InputStream).  A Java import clause is primarily designed to provide a shorthand for a class/interface name (by writing "import java.io.InputStream"), or for all of the classes/interfaces in a given package (by writing "import java.io.*").  Java also provides an implicit import of java.lang.*, providing shorthands for all of the most basic Java classes and interfaces without need for an explicit import clause.  Modula (and Python) provides a shorthand when using an import clause of the form "from M import A, B" which makes the names A and B directly visible.

Ada has a different approach to shorthands.  The contents of any package may be made directly nameable using a "use" clause (e.g. "use Pkg;" makes Pkg.A nameable as simply "A").

So now back to the approach adopted for ParaSail.  ParaSail follows the Java model as far as shorthands, in that an "import Acme::Killer_App::Driver" has the effect of making "Driver" usable directly within the code that follows.  But unlike in Java, if the programmer gives explicit import clauses, then they restrict what modules the source code may use.  If the name of a module is not covered by one of the explicit import clauses, and is not within PSL::Core::* or PSL::Containers::*, then no reference may be made to it, even with its full name.  What this means is that if an import clause is present, it ensures that no unexpected dependencies on outside modules can occur due to some buried full-name reference.

ParaSail also eschews any inheritance of import clauses from other modules, such as the parent module or the interface of the module.  Import clauses apply to a piece of source code, namely the source code that follows the import clauses, up until the next set of import clauses, or the end of the file.  This means that identifying what other modules are relevant to understanding a given piece of source code is fully circumscribed by the applicable import clauses.

Rev 3.8 release brings initial I/O library, import clauses

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

http://bit.ly/Mx9DRb

This release includes a number of new features, including support for the import clause, and a standard library now defining modules with names like PSL::Core::Boolean and PSL::Containers::Set (rather than simply Boolean or Set). There are some new I/O modules, including PSL::Core::IO, PSL::Core::File_Input_Stream, and PSL::Core::File_Output_Stream. These last two support simple textual file I/O. We will be providing additional libraries oriented toward a graphical user interface in an upcoming release. The reference manual has also been updated to cover some of the newer features. As usual, consult the release notes for more details on the 3.8 revision.

We will write a separate blog entry about the design of the import clause -- it brought out some interesting issues. Every ParaSail module has an implicit import of PSL::Core::* and PSL::Containers::* so the introduction of the import clause shouldn't cause any compatibility issues with existing code.

Rev 3.7 release with map/reduce; Python-like syntax

Revision 3.7 of the alpha release 0.5 of the ParaSail compiler and virtual machine is now available at the same URL we have been using recently:
 
    http://bit.ly/Mx9DRb

This release has a number of new features, including a special syntax for map/reduce style computations, filters added to iterators, and support for an optional Python-like syntax.  For a description and some examples of the new map/reduce syntax, see:

  http://parasail-programming-language.blogspot.com/2012/11/special-syntax-for-mapreduce-in-parasail.html

Here is a simple example using the map/reduce syntax (and a filter) to compute the square of N by summing the first N odd integers:

    func Square(N : Univ_Integer {N >= 0}) -> Univ_Integer is
        return (for I in 1 ..< 2*N {I mod 2 == 1} => <0> + I);
    end func Square;

Filters are mentioned in the above blog entry, and illustrated in the above example. Here is another example where a "functional" version of QSort uses filters with a triplet of container comprehensions.  The filters are immediately before the "=>", enclosed in {...}:

    
    func QSort(Vec : Vector<Element>) -> Vector<Element> is
        if |Vec| <= 1 then
            return Vec;  // The easy case
        else
            const Mid := Vec[ |Vec|/2 ];  // Pick a pivot value
            return 
                QSort( [for each E of Vec {E < Mid} => E] )  // Recurse
              | [for each E of Vec {E == Mid} => E]
              | QSort( [for each E of Vec {E > Mid} => E] ); // Recurse
        end if;
    end func QSort; 

Note that we have added a "magnitude" operator "|...|" which can be defined as appropriate for a given interface; for vectors |V| is equivalent to Length(V).

The ParaSail compiler now recognizes a Python-like variant, in addition to the "normal" ParaSail syntax. In the Python-like syntax variant, "is", "then", "of", and "loop" are replaced by ":"; semicolons are optional; "end if", "end case", etc. are not used. "end class", "end interface, "end func" are optional. Indenting is significant. There are also some Python-inspired synonyms: "def" may be used instead of "func"; "elif" may be used instead of "elsif"; "# " may be used instead of "//" to introduce a comment (notice the required space).

The Python-like syntax is best illustrated by example. Here is the same QSort function given above using the Python-like syntax:

    
    def QSort(Vec : Vector<Element>) -> Vector<Element>:
        if |Vec| <= 1:
            return Vec  # The easy case
        else:
            const Mid := Vec[ |Vec|/2 ]  # Pick a pivot value
            return 
                QSort( [for each E of Vec {E < Mid} => E] )  # Recurse
              | [for each E of Vec {E == Mid} => E]
              | QSort( [for each E of Vec {E > Mid} => E] )  # Recurse

Note that the above is strongly typed (unlike Python), but because of type inference on declarations, types only show up in the parameter and result types.

Currently the two syntax variants can be mixed and matched. At some point we may have some restrictions on mixing and matching. In any case semicolons will remain optional in both variants, and probably will start disappearing from examples given in future blog entries.

Both syntax variants are being supported at the moment as we are still ambivalent about whether the Python-like syntax is preferable. We have tentatively named this ParaSail-with-Python-like-syntax variant "PARython" or perhaps "Parython." We may be adding more scripting-oriented libraries so PARython might be usable in more contexts where Python is chosen today.

Special syntax for Map/Reduce in ParaSail?

The Map/Reduce operation has become widely known recently.  A traditional way of implementing a Map/Reduce operation is to pass to the map_reduce operation, a container such as a set, vector, or list, a mapping function which is applied to each element, and a reducing function which is used to combine two mapped elements into one result.  The mapping step is relatively straightforward, but the reducing step can come in various forms, as it depends on whether the reducing function is associative, commutative, symmetric, etc.  Most functional languages have at least two standard reducing mechanisms, often called foldl and foldr.  These differ in the way the elements of the sequence are combined, either starting at the left or starting at the right.  Typically there is also an initial value which most often corresponds to the identity element for the reducing function, and this becomes the result if the sequence is empty.  If there is no convenient identity element (such as for maximum), versions of foldl and foldr are provided that use the use the first or last element as the initial value (called foldl1 and foldr1 in Haskell), but then only work on non-empty sequences.  Here is the wikipedia entry on the various forms of fold/reduce:

    http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

Because ParaSail supports passing functions as parameters to other functions, Map/Reduce in all its forms can be supported in the "traditional" way.  The question is whether some alternative syntax might be useful as well, analogous to the special syntax provided for quantified expressions (which essentially use and or or as the reducing function over a set of boolean values), and for container comprehensions (which essentially use "|" as a reducing operation to combine values into a new container).  As examples, here is a ParaSail quantified expression that asserts an array is sorted:

  (for all I in 1 ..< Length(Vec) => Vec[I] <= Vec[I+1])

and here is a container comprehension that creates a vector of squares:

   const Squares : Vector<Integer> := [for I in 1..10 => I**2]

Quantified expressions and container comprehensions could also be implemented by passing functions as parameters, but clearly the special syntax makes it somewhat more convenient, and arguably easier to understand.  So the question is: is there an analogous situation for the general map/reduce operation?  Would a special syntax make it more convenient and/or easier to understand?

Here is an example using possible syntax for a general map/reduce:

   (for I in 1 .. Length(Vec) => <0> + Vec[I]**2)

This is to be interpreted as a map/reduce operation which produces the sum of the squares of the values of the Vec.  The initial result (in the case of an empty vector) is given inside the <...>, and then after each element is combined with the ongoing result, the new result replaces the <...> for the next element.  Here would be a dot product of two vectors (first we assert they are of the same length):

  {Length(Vec1) == Length(Vec2)}
 (for I in 1 .. Length(Vec1) => <0> + (Vec1[I] * Vec2[I]))

Here is a computation of factorial(N):

   (for I in 1 .. N => <1> * I)

If we wanted to compute the maximum of the elements of some function evaluated over a range of inputs, and we wanted to use the first value as the initial result (analogous to foldl1 in Haskell) we could write (after first asserting we have a non-empty set of inputs):

    {N > 0}
   (for I in 1 <.. N => Max(<F(1)>, F(I)))

This general syntax could be used with any ParaSail iterator, so if we wanted to count the number of symbols in a symbol table whose names are shorter than 3 letters, we could write:

   (for each S of Sym_Table => <0> + (Length(S.Name) < 3? 1: 0))

Here we might better use a filter annotation on the iterator (unfortunately, iterator filters are not yet implemented in the ParaSail compiler):

   (for each S of Sym_Table {Length(S.Name) < 3} => <0> + 1)
   
An explicit reverse or forward could be used with the iterator if we want to distinguish between foldr and foldl for reducing ordered sequences of values.  Otherwise, the default is an unordered parallel reduction.

Note that a quantified expression can be re-expressed in this more general map/reduce syntax.  For example, the above assertion of Vec being sorted could be re-expressed as:

   (for I in 1 ..< Length(Vec) => <#true> and then Vec[I] <= Vec[I+1])

Similarly, a container comprehension could be re-expressed using this general syntax.  For example, the table of squares could be re-expressed as:

   (for I in 1 .. 10 forward => <[]> | [I**2])

Overall this special syntax seems to provide a nice alternative for map/reduce.  In the traditional approach, we would have to "bundle" up the mapping and reducing operations into functions, whereas with this special syntax, we can write the operations directly in a relatively "normal" looking expression syntax.

We would appreciate comments on this proposed special map/reduce syntax.

Work Stealing Statistics; Qsort vs. N-queens

We recently added more statistics to the ParaSail interpreter that relate to work stealing (see recent blog entry about rev 3.5 release).  ParaSail uses work stealing to map the very light weight picothreads generated by the compiler, to the heavier-weight server threads which are provided by the underlying operating system, typically about one per physical core.  For more general information on work stealing, see:

   http://supertech.csail.mit.edu/papers/steal.pdf

Work stealing is a scheduling approach where each server thread has its own (double-ended) queue of picothreads.  When a server executing code spawns off another picothread, it is added to the end of that server's queue.  When a server finishes its current picothread and needs another one to execute, it removes the most-recently added picothread from its queue.  In other words, it uses a last-in, first-out (LIFO) discipline with its own picothread queue.  If at some point, the server finds its own queue to be empty, it looks around at other servers' queues, and if it finds one with some picothreads, it will steal a picothread from that queue.  However, in this case it will choose the oldest picothread, that is, it uses a first-in, first-out (FIFO) discipline when stealing from another server's queue.

So an interesting question is: When a server goes about picking a new picothread to execute, what proportion of the time does the server have to steal a picothread rather than simply pick one off its own queue?  We have added statistics to the ParaSail interpreter to determine this.  So the next interesting question is: Do all algorithms produce the same proportion of stealing, or does the stealing proportion vary significantly from one algorithm to another?

So here are some answers, based on having four server threads:

Qsort : Sort array of 500 randomly selected values between 0 and 99, twice:

  43139 thread steals out of 67096 total thread initiations;
 64.3% stealing proportion
 
N-queens: Generate all solutions to the N queens problem for 8x8 chess board, 6x6, and 4x4:

  1690 thread steals out of 25015 total thread initiations;
 6.8% stealing proportion

Quite a dramatic difference.

The classic (inefficient) recursive fibonacci produces an even smaller proportion of steals, for Fib(15):

  17 thread steals out of 986 total thread initiations;
 1.7% stealing proportion

We also collect statistics on how many of the servers are doing useful work on average, and how many picothreads are waiting on any server's queue, on average.  For these three cases, the averages are:
 Qsort:   3.45 servers active,  0.92 threads waiting for service
 N-Queens:3.89 servers active, 13.94 threads waiting for service
 Fib(15): 3.99 servers active, 17.99 threads waiting for service

We have also started collecting statistics about the proportion of allocations from regions that are performed by the server that created the region initially, versus by some other server (which presumably stole some work from the "owning" server).  This clearly reflects something about the work stealing, but also provides some additional information about what proportion of typical work is manipulating objects coming from an enclosing picothread, and how much is manipulating objects local to the scope of the picothread doing the work.   Here are the results for the above three test cases:
 Qsort:   64,578 non-owner allocs out of 445,479 = 14.5%
 N-Queens:29,489 non-owner allocs out of 115,586 = 25.5%
 Fib(15): [no allocations -- all objects were small]

So what about the algorithm determines the thread stealing proportion and/or the owner vs. non-owner allocations from a region?  Sounds like an interesting research project...

Rev 3.5 alpha 0.5 release of ParaSail

We just released a new version (3.5 alpha 0.5) of the ParaSail compiler and virtual machine, available at the same URL as before:

    http://bit.ly/Mx9DRb

We have added some improved statistics to the virtual machine interpreter related to work stealing and region usage, and a command "stats" to view the statistics without exiting the interpreter, and "stats clear" to view and zero-out the statistics.  We will shortly be posting another blog entry about some of the more interesting results of these new statistics.

Additional updates in this release:

• The conditional expression "(if X then Y)" is now equivalent to "(if X then Y else null)"
• We now use the "<|=" operator, if available, when building up an aggregate with an iterator inside, such as "[for I in 1..10 => I*5]".  Before we used the "var_indexing" operator instead if both "<|=" and "var_indexing" were available, using the value of "I" as the index.  This didn't make much difference when building up a vector, but was somewhat limiting in other cases.
• We now allow "reverse" when defining an aggregate with an iterator, such as "[for I in 1..10 reverse => I * 5]," allowing the creation of a reverse-order vector, for example.
• We have fixed a bug which meant that certain annotations were ignored if they immediately preceded or followed a call on an operation.