This blog will follow the trials and tribulations of designing a new programming language designed to allow productive development of parallel, high-integrity (safety-critical, high-security) software systems. The language is tentatively named "ParaSail" for Parallel, Specification and Implementation Language.
We have just made a release of the ParaSail interpreter, VM, and compiler. This is version 6.5, and is mostly a bug-fix release relative to 6.3. We are working on a static analyzer and optimizer for ParaSail, and this release contains prototypes for both of those (ParaScope, and a combination of ParaScope and the compiler). The static analyzer can be invoked using "bin/scope.csh file1.psl file2.psl ...". The optimizer is not quite ready for prime time at this point, but feel free to investigate lib/vn_il.ps? to see how the compiler and static analyzer are being integrated to provide LLVM optimization. As before, the source release is available at:
We now have an LLVM-based compiler for ParaSail, thanks to great work this past summer by Justin Hendrick, a summer intern from Cornell. To download the latest source release for both the ParaSail interpreter and the LLVM-based compiler, visit http://parasail-lang.org
There are a number of interesting design issues associated with creating a compiler for a pointer-free, pervasively parallel language, and it seemed worth writing about some of them here. So here is the first in a series of such blog entries.
Clearly pervasive fine-grained parallelism is one of the things that makes ParaSail interesting and a bit different from typical languages. So let's start with that -- how are picothreads, or parallel work items (as we have taken to describing them in some contexts), represented in the generated LLVM? The ParaSail front end already does the work to decide where it is worth creating a separate thread of control as part of generating instructions for the ParaSail Virtual Machine (PSVM instructions). In the PSVM, these are represented as nested blocks within a single PSVM routine. That is, a single ParaSail operation (func or op) produces a single PSVM routine, but that routine may have zero or more nested blocks to represent code suitable for execution by a separate picothread. A nested block is invoked by the Start_Parallel_Op or Add_Parallel_Op PSVM instructions, awaited by the Wait_For_Parallel_Op, and terminated by an Exit_Op instruction. On the other hand, a whole routine is invoked by a Call_Op, Start_Parallel_Call_Op, or Add_Parallel_Call_Op instruction, and terminated by the Return_Op instruction -- Wait_For_Parallel_Op is used for parallel invocations of both nested blocks and whole routines.
At the LLVM level, we made the decision to make the calling sequence essentially the same whether it was an invocation of a nested block or a routine. Every such call has three arguments. These are the Context, the Param_List, and the Static_Link. The Param_List points to a stack-based parameter list, where the first parameter is the result, if any, and the other parameters are the input parameters. The Context points to a data structure that is created when a new picothread is created, and is updated when a new storage region is created (more about that in a later blog entry). The Context is effectively the per-picothread information. The Static_Link either points at a type descriptor, for a routine that corresponds to an operation of a module, or to the enclosing stack frame, for a nested block or a routine that corresponds to a nested operation. The first word of a stack frame holds a copy of the passed-in static link, so this supports up-level references across multiple levels, as well as access to the type descriptor passed into an enclosing module operation.
Type descriptors are fundamental to the ParaSail run-time model. Remember that at the source level, all ParaSail modules are considered parameterized, and a ParaSail type is produced by instantiating a module. Operations are generally associated with modules, and unlike in C++ or Ada, instantiating a module does not produce a new set of code for these operations. Instead, the code is generated once for a given module, and then used for all instantiations. But that means that the code needs to be passed some information that identifies the particular instantiation for which it is being executed. This is what a type descriptor provides -- all of the information that is dependent on the particular instantiation being used.
For example, a Set module might have various operations like Union and Intersection and Insert and Count, but the type of the elements being manipulated is determined by the particular instantiation, be it Set<Integer>, Set<String>, or Set<Map<String, Tree<Float>>>. Presuming it is a hashed Set, the only requirements on the element type is that it have the operations of the abstract interface Hashable, which generally means Hash and "=?" (aka compare). So when we call the Insert operation of Set, we pass it the type descriptor (as the Static_Link argument) for the particular instance of Set we are using. Since Set only has one type parameter, the type descriptor of Set consists primarily of a reference to a type descriptor for this one type parameter. In addition to having references to the type descriptors for the type parameters, a type descriptor also includes the equivalent of a C++ virtual function table. That is, for each of the operations of Set, we have a reference to the (compiled or interpreted) routine for that operation. This is not generally needed for the code within Set itself, since that code generally knows at compile time what routines are used for all of the other Set operations. However, since we also use a type descriptor for the type parameter of Set, we will need to use the routine table within that type descriptor to gain access to the Hash and "=?" operation for the particular element type being used. So in the type descriptor for Set<Integer>, there will be a reference to the type descriptor for Integer, and from there you can gain access to the Integer Hash and Integer "=?" routines, which will certainly be needed at least for the Insert routine.
One last wrinkle on type descriptors -- because ParaSail uses a variant of the class-and-interface model of inheritance, it supports multiple inheritance, so different types that implement the Hashable interface might have different sets of routines in their routine table. So how does the code for the Insert routine know where it can find the Hash and "=?" routines for Integer or String, given that they might also have many other routines? The solution here is an extra level of indirection. We actually have two types of type descriptors, one is the full type descriptor, and has all of the information so far described (and more, such as nested constants). The second kind of type descriptor is called an operation map (or op map for short). This consists of a reference to the full type descriptor for the type, plus a simple mapping from an interface's operation index to the underlying type's operation index. If we sequentially number the operations of any given module's interface, then that gives us an operation index which we can use at run-time for selecting from the routine table in a type descriptor for an instance of that module. The op map provides the necessary conversion when the operations defined in the abstract interface (specified for the element's type when declaring a module like Set) are numbered differently than the actual element type's operations. An op-map for a type that implements Hashable might be defined by a simple mapping such as (1 => 5, 2 => 3), meaning that the first operation of Hashable is in fact the fifth operation of the actual type, and the second operation of Hashable is the third operation of the actual type. An op-map provides for constant-time execution of calls on operations, even in the presence of multiple inheritance.
Note that this op-map approach does not work for languages where all objects carry around a reference to their type descriptor at run-time, since a single type descriptor must work for all uses of the object. One of the features of ParaSail is that typical objects have no type descriptor overhead. The compiler generally knows where to find a type descriptor for any object, without the object having to carry it around. The one exception to this are explicitly polymorphic objects. In ParaSail these are declared with a syntax of a type name followed by a "+". For example, Set<Imageable+> would be a set of objects that implement the Imageable interface, where each object might be of a different type. This means that each Imageable+ object consists of a reference to the underlying object, plus a reference to a type descriptor identifying the actual type of the object. But even these sorts of objects can preserve the constant-time execution of operation calls, because an object is polymorphic for a particular interface (Imageable in this case), and so the type descriptor that such a polymorphic object carries around will likely be an op-map tailored to the particular interface being implemented. The ParaSail Imageable interface actually has four operations (To_String, From_String, Hash, and "=?"), so such an op-map might look like (1 => 13, 2 => 5, 3 =>9, 4 => 11), which provides constant-time access to any of the operations of Imageable.
One final point worth noting -- type descriptors are used in various contexts, as suggested above (as a static link, as a type parameter, and for run-time-type identification). In most of these contexts op-maps can be used instead of a full type descriptor. An important exception to this is a type descriptor used as a static link. In that case, it is always a full type descriptor, and the compiled code can rely on that fact.
ParaSail is a language specifically designed to simplify the
construction of programs that make full, safe use of parallel
hardware. ParaSail achieves this largely through simplification of the language, rather than by adding numerous rules.
In particular, ParaSail eliminates global variables, parameter aliasing, and most significantly, re-assignable pointers.
ParaSail has adopted a pointer-free approach to defining
data structures. Rather than using pointers, ParaSail supports flexible data structuring using expandable (and
shrinkable) objects, along with generalized indexing. By
eliminating global variables, parameter aliasing, and pointers, ParaSail reduces the complexity for the programmer,
while also allowing ParaSail to provide pervasive, safe,
object-oriented parallel programming.
The compiler is now able to compile many ParaSail programs and most of the ParaSail Standard Library. It's probably easier to just list the things we know it can't do yet:
functions as parameters
functions with locked or queued parameters
Pretty small list, right! Well, to be honest, it's the list of known bugs. There are probably bugs we don't know about.
The most exciting thing about this is that the compiler itself uses neither of these features, so it's able to compile itself! The process is called bootstrapping. The executable it produces is able to compile other ParaSail programs.
Over the past few weeks, we've spent a lot of time debugging compiled ParaSail programs. We're tired of stepping through assembly, and so, if given a "-g", the compiler will produce some debugging information usable by gdb. Right now it's only ParaSail source file line numbers and function names, but it's a start.
Syntax Highlighting on the Web with Pygments
Pygments is a generic syntax highlighter written in python. We've submitted a pull request to add a ParaSail highlighter and are awaiting a response from the maintainers.
Next, we're going to spend more time on static analysis, especially checking for nullness of objects and recognizing unused variables.
We've been evaluating different alternatives for synchronization primitives in the ParaSail runtime and we've found that OpenMP performs the best when compared against Ada protected objects and our own library. Thus, we are moving our runtime system to OpenMP for the performance benefits and the fact that it's supported in both gcc and llvm.
Hello, It's Justin again. See the previous blog post for a bit of context. (Hint: we're building the compiler)
Linking to the Built-ins
The interpreter has a library of functions it uses to evaluate ParaSail code. We don't want to and can't write every ParaSail operation directly in llvm. So, it was necessary to link the generated llvm code with the interpreter's built-in functions. At first we thought the built-ins needed to be translated to llvm code to successfully link with our generated llvm. To accomplish this, we used a tool called AdaMagic to convert the Ada source code (in which the built-ins are currently written) and Ada's run time system (RTS) to C source code then used the llvm C front-end "clang" to compile the rest of the way. Clang complained with hundreds of warnings, but, it worked. We were able to print integers, floats, and characters! We couldn't do much more with the built-ins at the time because we didn't yet have type descriptors working (see below).
After all the effort and dealing with the messy generated C code, we found out that the system linker could link object files compiled with the llvm backend called "llc" together with object files produced by the GNAT Ada compiler with no problem. That was a relief, as we really didn't want to go mucking around in the generated C code more than we had to.
ParaSail types are represented in the interpreter with Type_Descriptors. Basically,a type descriptor is a large record with everything you need to know about a type. Most importantly, it holds a list of operations, a "null" value to be used for the type, and descriptors for any other type it depends on (such as the component type for an array type). When we want to execute compiled ParaSail code that has types in it, we need much of this information at run time, particularly when executing code that is "generic" in some way (such as a Set where we need to get the Hash operation for Some_Hashable_Type, and perhaps its representation for "null").
Here's an example:
func Count_Nulls(Numbers : Basic_Array<optional Univ_Integer>) -> Univ_Integer is var Count := 0; var I := 1; while I <= Length(Numbers) loop if Numbers[I] is null then
Count += 1; end if;
I += 1; end loop; return Count; end func Count_Nulls;
func main(Args : Basic_Array<Univ_String>) is var A : Basic_Array<optional Univ_Integer> := Create(10, null);
A := 42;
A := 0;
Print("There are ");
Println(" nulls"); end func main;
There are quite a few places that need type information, but the easiest to show is "Numbers[I] is null". There is a specific 64 bit value that represents null for the Univ_Integer type that needs to be checked against Numbers[I].
To accomplish this, we encode the type descriptors as "linkonce" global byte arrays in llvm. Before the ParaSail main routine is invoked, these byte streams are reconstructed into Type_Descriptors for use at run time. We reconstruct these by appending our own parameterless function to the @llvm.global_ctors global variable. But, we need to call into the Ada RTS while reconstructing type descriptors, and, much to our dismay, the functions in @llvm.global_ctors are called before the Ada RTS has a chance to initialize. To solve this problem, the parameterless function in global_ctors adds a node to a todo (linked) list. Then, after the Ada RTS has been initialized, we walk the "todo" list and reconstruct the type descriptors from the streams.
A very similar method is used to reconstruct the appropriate run-time representations for Univ_Strings and Univ_Enumerations from their stream representations.
Back to the example
First of all: It compiles and runs! Here's what it prints out:
There are 8 nulls
(that part was me)
You might wonder why we used a 'while' loop instead of a 'for each' loop. Well, that's because for loops use parallel stuff we haven't implemented yet. Even a forward/reverse for loop uses parallel stuff because it allows you to do things like this
for I := 1 while I < N forward loop block continue loop with I => I * 2; || continue loop with I => I + 1; end block; end loop;
While loops can be implemented with simple llvm 'br' instructions.
We can't compile aaa.psi (the ParaSail standard library) yet, so we don't have access to all the modules defined there, but Basic_Array::Create, Basic_Array::"var_indexing", and Basic_Array::"indexing" are all built-ins, so we're able to use that container.
If a ParaSail function has the name "main," with one argument of type Basic_Array<Univ_String>, and no return value, then that is treated as a special case by the llvm code generator, and it's name will be changed to "_parasail_main_routine". A real main function "int main(int argc, char** argv)" function exists in ParaSail's RTS that builds up the Args array (well actually not yet, but it will!) and calls this _parasail_main_routine. Why the preceding underscore you ask? Well, it's not legal to start an identifier with an underscore in ParaSail, so, we're insuring no name collisions this way. However, one downside of this is that it is currently not possible to call main from elsewhere in your program. However, that's not unprecedented, C++ disallows it as well. This isn't set in stone, though.
"Reflection" is a ParaSail module that allows ParaSail code to inspect itself and retrieve the ParaSail Virtual Machine (PSVM) instructions for any routine that is in the Interpreter's memory at the same time. This is how we compile: the user loads compiler.psl (the llvm code generator written in ParaSail itself), its dependent module(s), and the ParaSail source file to be compiled. Then, the main function in compiler.psl, called "Compile," searches through all the routines in the interpreter's memory (using the reflection module) until it finds those that come from the file whose name matches the file name given as an argument to Compile. It then proceeds to translate each of those routines from PSVM instructions into LLVM instructions, as well as build up the various tables need for reconstructing type descriptors, strings, etc.
The Static Link passed implicitly in each ParaSail function call is used by the called function to retrieve data from outside the function. If the function is nested inside another function, then the static link points to the local data area of that enclosing function. If the function is a top-level operation of some module, then the static link points to a type descriptor for some instance of that module. In a call on a stand-alone function, the static link is null.
We're making tremendous headway on this compiler and I'm very excited about where we could reach by the end of this summer.
My name is Justin Hendrick and I'm an intern working on ParaSail for the summer. My first task is code generation.
Up until now, ParaSail has been interpreted. We’re proud to announce that we’ve begun building the code generation phase, written in ParaSail, that generates LLVM Intermediate Representation code. For information about LLVM see llvm.org and the reference manual.
So far, we can successfully compile simple functions that branch and do arithmetic on Univ_Integers and Univ_Reals.
For example, this ParaSail max function:
func Max(A : Univ_Integer; B : Univ_Integer) -> Univ_Integer is if A > B then return A; else return B; end if; end func Max;
Is converted to ParaSail Virtual Machine Intermediate Representation. See this post for more details on the PSVM and the calling convention in use.
ParaSail has three basic iterator formats, with some sub-formats (unbolded "[ ... ]" indicate optional parts, unbolded "|" indicate alternatives, bold indicates reserved words or symbols that are part of the syntax itself): 1. Set iterator: for I in Set [forward | reverse | concurrent] loop ... 2. Element iterator: foreach E of Container [forward | reverse | concurrent] loop ... or foreach[K => V]of Container [forward | reverse | concurrent] loop ... 3. Value iterator: for V := Initial [then Next_Value(V)] [while Predicate(V)] loop ... or for T => Root [then T.Left | T.Right] [while T not null] loop ...
These iterators can be combined into a single loop by parenthesizing them; the loop quits as soon as any of the iterators completes:
for (each E of Container; I in 1..100) forwardloop ... // Display up to 100 elements of Container
As we have written more ParaSail, one pattern that has come up multiple times (particularly when doing output) is the case where you have a special value to be used for the first iteration, and then the same value thereafter. For example, presume we want to display each of the values of a Vector, separated by commas, enclosed in brackets. A common way of doing this is to have an "Is_First" boolean value which is tested, and then set to #false, to decide whether to display the opening "[" or the separating ", ". By using a combination of two iterators, this becomes simpler, with no extra conditionals:
for (each V of Vec; Sep := "[" then ", ") forwardloop Print(Sep | V); end loop Print("]")
Note that the value iterator has no "while" part, so it will continue forever to have the loop variable "Sep" bound to the value ", "; when combined with another iterator as it is in this case, the loop will end once the container iterator ends.
Nothing too magical here, but it is sometimes interesting to see a pattern like this that keeps cropping up. The ParaSail reference manual has more details on these iterators. The most recent manual may be found at http://parasail-lang.org .